Codeforces 每日一练 1278C+228E

1278C Berry Jam

题目链接
一开始想的是双指针去贪心，然后wa2wa了三发QAQ
然后换了思路，草莓果酱还用1，蓝莓果酱用-1表示，那么最终的结果就是现存果酱的总和为0。
并且考虑到左右剩余的果酱一定是连续的，欸嘿嘿嘿，连续+和，然后就想到可以前缀和的思路搞一搞。
左边就是从1到n求出前缀和，右边n+1~2n求一个后缀和，显然就是对左边任意一个点的前缀和去后缀和里找与其和为0的点，但是暴力匹配O(n^2)，考虑用map存下右边的后缀和以及对应的剩余果酱数。然后遍历左边前缀和即可。（记得考虑任一侧果酱数为0的情况）
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);
#define maxn 200005
int a[maxn],s[maxn],b[maxn];
map<int,int> mp;
int main(){
    // IOS
    int t;
    cin>>t;
    while (t--){
        memset(s,0, sizeof(s));
        memset(b,0, sizeof(b));
        mp.clear();
        memset(a,0, sizeof(a));
        int n;
        cin>>n;
        int sum=0;
        for(int i=1;i<=2*n;i++){
            cin>>a[i];
            if(a[i]==2)a[i]=-1;
            sum+=a[i];
            if(i<=n)s[i]=s[i-1]+a[i];
        }

        mp[0]=0;
        for (int j = 2*n; j >=n+1 ; --j) {
            b[j]=a[j]+b[j+1];
            mp[b[j]]=2*n-j+1;
        }
        if(sum==0)cout<<0<<endl;
        else{
            int ans=0;
            for (int i = 0; i <=n ; ++i) {
                if(mp.count(0-s[i])){
                    ans=max(ans,i+mp[0-s[i]]);
                }
            }
            cout<<2*n-ans<<endl;
        }
    }
    return 0;
}

228E The Road to Berland is Paved With Good Intentions

题目链接
很明显对于任意点，只有取和不取两种情况（取偶数次周围情况不变，取n次与取n%2次效果一样）.
考虑每一条边，如果是1，那么两端要么取，要么不取，如果是0，则只能取一端。想到这，就联想到了关押罪犯的思路，一个传统并查集＋一个enemy数组存敌人。边权为0时，两个端点互相存一个enemy。
那么就是随便取一个点，然后取所有和它父亲一样或敌人一样的。
然后就~

猛男落泪.jpg
然后想到图可能不是联通的，需要把每个连通块里都任意取一个点出来，然后神速写了个dfs染色，结果还是wa43，然后今天早上被大佬指点，发现处理并查集的时候，任意两个点如果父亲相同（取的状态相同），那么也应该合并他们敌人的家族。
然后就ac了~
代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);
#define maxn 105
#define for_(i,n) for(ll (i)=1;(i)<=(n);i++)
struct edge{
    int u,v,w;
};
vector<edge> e;
set<int> ans;
int f[maxn],enemy[maxn];
int findfa(int x){
    if(x==f[x])return x;
    else {
        f[x]=findfa(f[x]);
        return f[x];
    }
}
void mergefa(int a,int b){
    int fa=findfa(a),fb=findfa(b);
    if(fa==fb)return ;
    else{
        f[fa]=fb;
        return ;
    }
}
vector<int> g[maxn];
int col[maxn];
void dfs(int x,int fa,int co){
    col[x]=co;
    for(auto i:g[x]){
        if(i!=fa&&col[i]==0)dfs(i,x,co);
    }
}
int main(){
    IOS
    int n,m;
    cin>>n>>m;
    while(m--){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back(v);
        g[v].push_back(u);
        e.push_back({u,v,w});
    }
    for_(i,n){
        f[i]=i;
        if(!col[i]){dfs(i,0,i);}
    }
    for(auto i:e){
        int u=i.u,v=i.v;
        if(i.w==1){
            mergefa(i.u,i.v);
        }else{
            if(findfa(u)==findfa(v)){
                cout<<"Impossible";
                return 0;
            }
            if(!enemy[u])enemy[u]=findfa(v);
            else mergefa(enemy[u],v);
            if(!enemy[v])enemy[v]=findfa(u);
            else mergefa(enemy[v],u);
        }
    }
    for_(i,n){
        for_(j,n){
            if(findfa(i)==findfa(j)&&enemy[i]!=0&&enemy[j]!=0){
                mergefa(enemy[i],enemy[j]);
            }
        }
    }
    for_(i,n)ans.insert(col[i]);
    set<int> sum;
    for(auto i:ans){
        int fa=findfa(i);
        for_(j,n){
            if(col[j]!=i)continue;
            if(findfa(j)==fa){sum.insert(j);}
        }
    }
    cout<<sum.size()<<endl;
    for(auto i:sum)cout<<i<<" ";
    return 0;
}

相比位运算的并查集的确多了不少码~（原谅蒟蒻没看懂取异或的并查集做法QAQ）