Codeforces Round #446 (Div. 2) 题解

题目链接：http://codeforces.com/contest/892

A. Greed

解法：就是所有饮料能不能倒入两个瓶子内，找到两个最大的，判断一下。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100010;
int n;
struct node{
    int a, b;
}a[maxn];
bool cmp(node a,node b){
    return a.b<b.b;
}
int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i].a);
    for(int i=1; i<=n; i++) scanf("%d", &a[i].b);
    sort(a+1,a+n+1,cmp);
    LL sum = 0;
    for(int i=1; i<=n; i++) sum += a[i].a;
    if(sum<=(1LL)*(a[n].b+a[n-1].b)) puts("YES");
    else puts("NO");
    return 0;
}

B. Wrath

题意：有n个人，每个人可以杀死刚好在他前面的Li个人，问最后有多少人活下来？

解法：从后往前做，前缀和打个标记，O(n)。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1000010;
int n, a[maxn];
LL sum[maxn];
int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=n; i>=1; i--){
        sum[i-1]++;
        int pre=i-a[i];
        if(pre<=0) continue;
        sum[pre-1]--;
    }
    int ans = 0;
    for(int i=n; i>=1; i--){
        sum[i]+=sum[i+1];
        if(sum[i]==0) ans++;
    }
    return 0*printf("%d\n", ans);
}

C. Pride
题意：有一个序列，每次可以将一对相邻的数x,y的其中一个变成gcd(x,y)，求使序列全部变成1的最少操作次数，若不能，输出−1。

解法：若原序列中有1，则不断向旁边扩展即可。若没有1，则O(n2)找到一个最短的、gcd为1的区间，再向两边扩展。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2010;
int n, a[maxn];
int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    if(n==1&&a[1]==1) return 0*puts("0");
    int ans = 1e9;
    for(int i=1; i<=n; i++){
        int tt = a[i], pos = 0;
        for(int j=i; j<=n; j++){
            tt = __gcd(tt, a[j]);
            if(tt==1){
                pos = j;
                break;
            }
        }
        if(pos){
            int t1=0,t2=0;
            for(int j=i-1; j>=1; j--) if(a[j]!=1) t1++;
            for(int j=pos+1;j<=n; j++) if(a[j]!=1) t2++;
            ans = min(ans, pos-i+pos-i+t1+t2);
        }
    }
    if(ans==1e9) return 0*puts("-1");
    return 0*printf("%d\n", ans);
}

D. Gluttony

来自：http://blog.csdn.net/weixin_37517391/article/details/78569584

我们可以这样构造，始终让a序列对应位置的数小于b序列对应位置的数，这样的话，不管怎么取，b子序列的和总是大于a子序列的和。

我们可以把a序列做一个排序，设为c序列，然后我们开始构造b序列
b[i]=c[(j+1)%n]，满足c[j]=a[i]
例如：
a=[0,3,1,2]
那么
c=[0,1,2,3]
那么
b=[1,0,2,3]
b 就是我们要构造的序列。

#include <bits/stdc++.h>
using namespace std;
int n, a[30], b[30];
map <int,int> mp;
int main(){
    scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d", &a[i]), b[i]=a[i];
    sort(b,b+n);
    for(int i=0; i<n; i++) mp[b[i]] = b[(i+1)%n];
    for(int i=0; i<n; i++) printf("%d ", mp[a[i]]);
    printf("\n");
}

E. Envy

题意：给了一个图，n个点m条边，然后q个查询，每次查询给了一个集合，问集合中的边是否全部可能是一个最小生成树的边

解法：考虑离线处理所有询问，按边的长度从小到大的顺序处理，若已经处理了所有比该边短的边，现在要加入这条新边，则考虑如果它连接的两端不在同一个并查集中，那么这条边可以存在于MST中，否则不可以。为了保存上一次的状态，并查集编号利用权值编码的原理。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1000010;
struct edge{
    int u,v,w,id;
}c[maxn];
unordered_map <LL, int> mp;
int n, m, q, fa[maxn];
LL L[maxn],R[maxn];
int find_set(int x){
	return fa[x]?fa[x]=find_set(fa[x]):x;
}
bool cmp(edge a, edge b){
    return a.w<b.w;
}
int main(){
    scanf("%d %d", &n,&m);
    for(int i=1; i<=m; i++){
        scanf("%d %d %d", &c[i].u,&c[i].v,&c[i].w);
        c[i].id=i;
    }
    sort(c+1, c+m+1, cmp);
    int i, j, k;
    for(i=1; i<=m; i=j+1){
        for(j=i; j<m&&c[j+1].w==c[i].w; j++);
        for(k=i; k<=j; k++) L[c[k].id] = 1LL*c[k].w*m + find_set(c[k].u), R[c[k].id] = 1LL*c[k].w*m + find_set(c[k].v);
        for(k=i; k<=j; k++) if(find_set(c[k].u)!=find_set(c[k].v)) fa[find_set(c[k].u)] = find_set(c[k].v);
    }
    memset(fa, 0, sizeof(fa));
    scanf("%d", &q);
    for(i=1; i<=q; i++){
        int s;
        scanf("%d", &s);
        mp.clear();
        bool flag = 1;
        int x, clk = 0;
        for(j=1; j<=s; j++){
            scanf("%d", &x);
            if(!mp[L[x]]) fa[mp[L[x]]=++clk]=0;
            if(!mp[R[x]]) fa[mp[R[x]]=++clk]=0;
            if(find_set(mp[L[x]])==find_set(mp[R[x]])) flag = 0;
            else fa[find_set(mp[L[x]])] = find_set(mp[R[x]]);
        }
        if(flag) puts("YES");
        else puts("NO");
    }
}