2018中国大学生程序设计竞赛 - 网络选拔赛1001 贪心 1003数学 1004费马大定理+奇偶数列法则 1007 循环节+线段树优化 1009 排列组合 1010树状数组维护dp

1001
题意：给一些城市的买卖价格，要求选择买或者卖一个或者不买不卖，问最后获得的最大利润。
思路：贪心。set维护最小堆，最小的价格小于当前的就可以卖了获得利润，不过这题可以反悔，就是说如果已经卖了这件物品，后面碰到获得更大利润的城市，需要反悔再卖，所以加上标记，如果是直接买的就次数加一并且利润加，如果是交换过了就不加次数，保证次数最小，要确定好优先级保证同等加个交换过的大于买的。
Code:

#include <bits/stdc++.h>
#define LL long long 
#define mp make_pair
using namespace std;
typedef pair<LL,int> P;
int main(){
    int T; 
    int n ; 
    int num ; 
    multiset<P>s;
    scanf("%d",&T);
    while( T-- ){
        LL x ; 
        s.clear();
        LL res = 0LL;
        num = 0 ;
        scanf("%d",&n);
        multiset<P>::iterator it ;
        for( int i = 0 ; i < n ; i++ ){
            scanf("%lld",&x);
            if( s.size() ){
                it = s.begin();
                if( (*it).first < x ){
                    res += ( x - (*it).first );
                    if( (*it).second ){
                        num ++;
                    }
                    s.erase(it);
                    s.insert(mp(x,0));
                    s.insert(mp(x,1));
                }else{
                    s.insert(mp(x,1));
                }
            }else{
                s.insert(mp(x,1));
            }
        }
        printf("%lld %d\n",res,num<<1);
    }
    return 0 ; 
}

1003
题意：要求定义+和*运算，使得(m+n)^p = m ^ p + n ^ p，p为素数。
还要满足题中给定的集合相等的约束。
思路：取模运算。

Code：

#include <bits/stdc++.h>
using namespace std;

#define LL long long 
const int AX = 1e5+666;
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T ;
    int n ;
    cin >> T;
    while( T-- ){
        cin >> n ; 
        for( int i = 0 ; i < n ; i ++ ){
            cout << i ; 
            for( int j = 1 ; j < n ; j ++ )
                cout << ' ' << ( i + j ) % n ; 
            cout << endl;
        }
        for( int i = 0 ; i < n ; i++ ){
            cout << 0 ;
            for( int j = 1 ; j < n ; j ++ )
                cout << ' ' << ( i * j ) % n ; 
            cout << endl;
        }
    }
    return 0;
}

1004
题意：
思路：费马大定理:n > 2 时，等式无解。
奇偶数列法则
如a^2+b^2=c^2是直角三角形的三个整数边长，则必有如下a值的奇数列、偶数列关系成立；
（一） 直角三角形a^2+b^2=c^2奇数列a法则：
若a表为2n+1型奇数（n=1、2、3 …）， 则a为奇数列平方整数解的关系是：
a=2n+1
b= n^2+（n+1）^2-1
c= n^2+（n+1）^2
（二） 直角三角形a^2+b^2=c^2的偶数列a法则：
若a表为2n型偶数（n=2、3、4…）， 则a为偶数列平方整数解的关系是：
a= 2n
b= n^2 -1
c= n^2+1
Code：

#include <bits/stdc++.h>
using namespace std;
#define LL long long 
const int AX = 1e5 + 66 ;
int main(){
    int T;
    LL n , a  ;
    scanf("%d",&T);
    while( T -- ){
        scanf("%lld%lld",&n,&a);
        if( !n || n > 2 ) {
            printf("-1 -1\n");
        }else{
            if( n == 1 ){
                printf("1 %lld\n",a+1);
            }
            else if( n == 2 ) {
                if( a & 1 ){
                    LL tmp = a / 2 ;
                    LL b = 2 * tmp * tmp + 2 * tmp;
                    LL c = 2 * tmp * tmp + 2 * tmp + 1 ; 
                    printf("%lld %lld\n",b,c);
                }
                else{
                    LL tmp = a / 2 ;
                    LL b = tmp * tmp - 1;
                    LL c = tmp * tmp + 1;
                    printf("%lld %lld\n",b,c);
                }
            }
        }
    }
    return 0;
}

1007
题意：n个数，m步，每步走k个数，到每个数会获得一个值（可正可负），求能获得的最大值，如果大于s，输出0，否则输出差值。
思路：对于固定的步距k，会有固定的循环节，并且可得，循环节个数为gcd（n，k），每个长度为len = n/gcd（n，k）。
求出循环节后，对于每个循环节求出长度<=m%len的最大子段和（走完m/len个循环节后余下的步数），再加上
( m / len ) * sum.（走完m/len个循环节）
如果m>=len,还要求长度<=len的最大子段和.少走一个循环节，选择性的提前停止以获得更大的值。再加上( ( m - len ) / len ) * sum (走完m/len-1个循环节)
Code：

#include <bits/stdc++.h>
#define LL long long 
#define INF 1e18
using namespace std;
const int AX = 1e4+666;
LL a[AX];
bool vis[AX];
std::vector<LL> v;
LL sum[AX*4];
LL s[AX*20];

int gcd( int a , int b ){
    return b == 0 ? a : gcd( b , a % b );
}

void pushUp( int rt ){
    s[rt] = min( s[rt<<1] , s[rt<<1|1] ) ;
}

void build( int l , int r , int rt ){
    if( l == r ){
        s[rt] = sum[l];
        return ;
    }
    int mid = ( l + r ) >> 1;  
    build( l , mid , rt << 1 ) ;
    build( mid + 1 , r , rt << 1 | 1 ) ;
    pushUp( rt ) ;
}

LL query( int L , int R ,  int l , int r , int rt ){
    if( l >= L && r <= R ){
        return s[rt] ; 
    }
    int mid = ( l + r ) >> 1; 
    LL ans = INF ;
    if( L <= mid ) ans = min( ans , query( L , R , l , mid , rt<<1 ) );
    if( R > mid ) ans = min( ans , query( L , R , mid + 1 , r , rt << 1 | 1 ) ) ;
    return ans ;  
}

int main(){
    int T;
    scanf("%d",&T);
    int Case = 0 ;
    int n , m , k  ;
    LL ss ;   
    while( T-- ){
        scanf("%d%lld%d%d",&n,&ss,&m,&k);

        for( int i = 0 ; i < n ; i++ ){
            scanf("%lld",&a[i]);
        }
        LL res = 0LL ; 
        int cnt = gcd(n,k); 
        int len = n / cnt ; 
        for( int i = 1 ; i <= cnt ; i++ ){
            v.clear();
            int cur = i - 1 ; 
            for( int j = 1 ; j <= len ; j ++ ){ 
                v.push_back(a[cur]);
                cur += k ;
                if( cur >= n ) cur %= n ;
            }
            for( int j = 0 ; j < len ; j++ ){
                v.push_back(v[j]);
            }
            sum[0] = 0 ; 
            for( int j = 1 ; j <= len * 2 ; j++ ){
                sum[j] = sum[j-1] + v[j-1];
            }
            build( 1 , len * 2 , 1 ) ;
            LL tmp = 0 ; 
            LL M = 0LL ;
            if( sum[len] > 0 ) M = sum[len] * ( m / len ) ;
            int kk = m % len ;
            for( int j = len + 1 ; j <= 2 * len  ; j++ ){
                tmp = max( tmp , sum[j] - query( j - kk , j , 1 , 2 * len , 1 ) );
            }
            res = max( res , tmp + M ) ; 
            if( m >= len ){
                M = 0 ;
                if( sum[len] > 0 ) M = sum[len] * ( ( m - len ) / len );
                for( int j = len + 1 ;j <= len * 2 ; j++ ){
                    tmp = max(tmp, sum[j] - query( j - len , j , 1 , len*2 , 1 ) );
                }
                res = max( res, M + tmp );
            }
        }
        printf("Case #%d: ",++Case);
        printf("%lld\n",max( ss - res , 0LL ) ) ;
    }
    return 0 ;
}

1009
题意：1-n的排列有n！种，给出n-1条边为两点的权值。求所有排列构成所有图的和。
思路：对于每一条边，要经过该边，x，y一定在该边的左右两侧，设左边为m个点，右边为n-m个。
所有排列的情况则为：2* 左边点个数右边点个数权值除了这条边外点的排列边数
2*m*(n-m)w(n-2)!*(n-1)
Code：

#include <bits/stdc++.h>
#define pb push_back
#define LL long long
using namespace std;
const int AX = 1e5+66;
const int MOD = 1e9+7;
struct Node{
    int  v , w ; 
};
LL fac[AX];
LL res ;
LL num[AX];
int n ;
std::vector<Node> G[AX];
void dfs( int x , int pre ){
    num[x] = 1 ;
    for( int i = 0 ; i < G[x].size() ; i++ ){
        int v = G[x][i].v ;
        int w = G[x][i].w ;
        if( v == pre ) continue;
        dfs( v , x ) ;
        num[x] += num[v];
        res += ( 1LL * num[v] * ( n - num[v] ) % MOD * w % MOD );
    }
}

void init(){
    fac[0] = 1 ; 
    for( int i = 1 ; i < AX ; i++ ){
        fac[i] = 1LL * i * fac[i-1] % MOD;
    }
}

int main(){
    init();
    while( ~scanf("%d",&n) ){
        res = 0LL;
        for( int i = 0 ; i <= n ; i++ ){
            G[i].clear();
            num[i] = 0 ; 
        }
        int x , y , v ; 
        for( int i = 1 ; i < n ; i ++ ){
            scanf("%d%d%d",&x,&y,&v);
            G[x].pb((Node){y,v});
            G[y].pb((Node){x,v});
        }
        dfs( 1 , 0 ) ;
        printf("%lld\n",2LL*res%MOD*fac[n-1]%MOD);
    }
    return 0 ; 
}

1010
题意：给n个村庄，只能向上向右向右下走，只能右下方向进入村庄，进入村庄会给一定价值，问从0，0到1e9，1e9，能够获得的最大价值。
思路：可以得到dp转移方程：
dp[i][j] = max( dp[i-1][j-1] , dp[i-1][j] , dp[i][j-1] ) + v[i][j]
可以用树状数组维护前缀的最大值优化dp
注意的是1e9过大，需要将纵坐标离散化。
Code:

#include <bits/stdc++.h>
#pragma comment(linker, “/STACK:1024000000,1024000000”)
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int AX = 1e5+66; 
int a[AX]; 
std::vector<int> v;
struct Node{
    int x , y , v ; 
    bool operator < (const Node &z) const{
        return ( ( x < z.x ) || ( x == z.x && y > z.y ) );
    }
}G[AX];
int n ;
int getid( int x ){
    return lower_bound( v.begin() , v.end() , x ) - v.begin() + 1 ; 
}
int lowbit( int x ){
    return ( x & (-x) );
}
int getsum( int x ){
    int res = 0 ; 
    while( x ){
        res = max( res , a[x] );
        x -= lowbit(x);
    }
    return res ; 
}
void update( int site , int v ){
    while( site < AX ){
        a[site] = max( a[site] , v );
        site += lowbit(site);
    }
}
int main(){ 
    int T ;
    scanf("%d",&T);
    while( T-- ){
        scanf("%d",&n);
        memset( a, 0 , sizeof(a) ); 
        for( int i = 0 ; i < n ; i ++ ){
            scanf("%d%d%d",&G[i].x,&G[i].y,&G[i].v); 
            v.push_back(G[i].y);
        }
        sort( G , G + n );
        sort( v.begin() , v.end() );
        v.erase( unique( v.begin() , v.end() ) , v.end() ) ;
        int res = 0 ;
        for( int i = 0 ; i < n ; i++ ){
            if( !G[i].x || !G[i].y ) continue;
            int idx = getid( G[i].y );  
            int ans = getsum( idx - 1 );
            res = max( res , G[i].v + ans );
            update( idx , G[i].v + ans );
        }
        printf("%d\n",res);
    }
    return 0 ;
}