江西理工大学摸底测试1

题目
A题意：n个瓶子排成一排，给出瓶子容量a[i]，初始瓶子为空。m次操作：每次向x瓶中加入y容量的水，如果瓶子水有多则将多的水倒入下一个瓶子。
问：最终每一个瓶子里的水量。
解法：以前做这题的思路是模拟每一次加水并将多的水倒入下一水瓶。代码写的很烂。
现在重新回顾这题思路就是，先不管瓶子容量直接加水，最后统一将多的水倒入下一瓶子。

const int maxn = 1e5+9;
int a[maxn] , b[maxn];
void solve(){
    int n , m ;
    scanf("%lld%lld" , &n , &m);
    rep(i , 1 , n){
        b[i] = 0;
    }
    rep(i , 1 , n){
        scanf("%lld" , &a[i]);
    }
    rep(i , 1 , m){
        int x , y ;
        scanf("%lld%lld" , &x , &y);
        b[x] += y ;
    }
    rep(i , 1 , n){
        if(b[i] > a[i]){
            b[i+1] += b[i] - a[i];
            b[i] = a[i] ;
        }
    }
    rep(i , 1 , n-1){
        printf("%lld " , b[i]);
    }
    printf("%lld\n" , b[n]);
}

signed main()
{
    int t ; scanf("%lld" , &t);while(t--)
    //int _ ;cin>>_;while(_--)
        solve();
}

B题意：给定一个整数n（4e4），能不能将其分解为三个素数之和,有多少种分法。（2，2，3）与（2，3，2）属于同一种。
解法：打比赛的时候不敢想直接枚举，第一感觉就是必超时。回过头来分析一波，时间复杂度还是可行的。
根据素数定理：1-4e4有大概有5e3个素数，暴力枚举两个素数，判断所剩的第三个数是否素数且递增。时间复杂度（\(n^2\)）1e7数量级可接受。

const int maxn = 4e4+9;
int prime[maxn] , len ;
bool is_prime[maxn];
void init(){
    ME(is_prime , true);
    is_prime[1] = false;
    rep(i , 2 , maxn){
        if(is_prime[i]){
            prime[++len] = i ;

            for(int j = i*i ; j <= maxn ; j += i){
                is_prime[j] = false;
            }
        }
    }
}

void solve(){
    int n , cnt = 0;
    scanf("%lld" , &n);
    for(int i = 1 ; i <= len && prime[i] < n; i++){
        for(int j = i ; j <= len && prime[i] + prime[j] < n && n-prime[i]-prime[j] >= prime[j] ; j++){
            int k = n - prime[i] - prime[j] ;
            if(is_prime[k] && k >= prime[j]){
                cnt++;
            }
        }
    }
    cout << cnt << endl;
}

C题意：n(2e5)个坐标点(x,y,z)，连接两个点的花费为\(MIN(|X_u?X_v|,|Y_u?Y_v|,|Z_u?Z_v|),将n个点连起来最小花费为多少\)
解法：稍一分析可以知道是最小生成树问题，难在如何建图，分别以x，y，z排序并以其建图，可得3*（n-1）条边，直接上Kruskal。

const int maxn = 2e5+9;
int fa[maxn];
int len ;
struct node{
    int x , y , z , id;
}p[maxn];

struct edge{
    int u , v , val;
}e[maxn*3];

void AddEdge(int u , int v , int w){
    e[++len].u = u ;
    e[len].v = v ;
    e[len].val = w ;
}

int cal(int x , int y){return abs(x - y);}
bool cmp(edge a , edge b){return a.val < b.val;}
bool cmp1(node a , node b){return a.x < b.x;}
bool cmp2(node a , node b){return a.y < b.y;}
bool cmp3(node a , node b){return a.z < b.z;}
int find(int x){
    if(x != fa[x]){
        return fa[x] = find(fa[x]);
    }
    return fa[x];
}
void unite(int x , int y){
    x = find(x) , y = find(y);
    fa[x] = y ;
}
void solve(){
    int n ;
    scanf("%d" , &n);
    rep(i , 1 , n) fa[i] = i ;
    rep(i , 1 , n){
        scanf("%d%d%d" , &p[i].x , &p[i].y , &p[i].z);
        p[i].id = i ;
    }
    sort(p+1 , p+1+n , cmp1);
    rep(i , 2 , n){
        AddEdge(p[i].id , p[i-1].id , cal(p[i].x , p[i-1].x));
    }
    sort(p+1 , p+1+n , cmp2);
    rep(i , 2 , n){
        AddEdge(p[i].id , p[i-1].id , cal(p[i].y , p[i-1].y));
    }
    sort(p+1 , p+1+n , cmp3);
    rep(i , 2 , n){
        AddEdge(p[i].id , p[i-1].id , cal(p[i].z , p[i-1].z));
    }
    ll ans = 0 ;int cnt = 0 ;
    sort(e+1 , e+1+len , cmp);
    rep(i , 1 , len){
        int u , v , w ;
        u = e[i].u , v = e[i].v , w = e[i].val;
        if(find(fa[u]) != find(fa[v])){
            unite(u , v);
            ans += w ;
            cnt++;
        }
        if(cnt == n-1) break;
    }
    printf("%lld\n" , ans);
}

D题意：数位dp，以后再补。

原文：https://www.cnblogs.com/nonames/p/13111347.html