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