Codeforces Round 784 (Div. 4)

感觉是所有cf里简单的一场了

D:题意：给一排白砖染色，每次可以选择两个相邻的数染成红蓝或蓝红，可以覆盖。多次询问，每次给出一个终态（红蓝白），问这个状态有没有可能作为终态？

Solution：快速猜猜题.首先发现white直接将状态分割成若干段，也就是染色操作显然不能跨过W，所以考虑单独考察某一段，发现无论怎么操作只要出现两种颜色怎么样都能成功，所以对每个段维护颜色种类数，每段的种类数都为2才合法。

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
void solve(){
	cin>>n;
	string str;cin>>str;str=" "+str;
	bool flag=true;
	set<char>s;
	bool end=0;
	bool st=0;
	for(int i=1;i<=n;i++){
		if(str[i]=='W'){
			if(i==n)end=true;
			if(s.size()<=1&&st)flag=false;
		    s.clear();
		}
		else {
			//len++;
			st=true;
			s.insert(str[i]);
		}
	}
	if(end==0&&s.size()<=1)flag=false;
		    
	
	if(flag)cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	
}

E:题意：给出n个二元组，查询有多少对二元组恰好有一维相同。

Solution：考虑到偏序关系，对于当前二元组，我们只考虑在我们前面的元素。考虑维护第一维，第二维，二元组的三个哈希表记录出现次数，简单的容斥考虑我们需要发现重复出现的二元组会多加2，故mp[x]+mp[y]-2*mp[str]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve(){
	map<char,int>mp1,mp2;
	map<string,int>mp;
	cin>>n;int ans=0;
	for(int i=1;i<=n;i++){
		string s;cin>>s;
		//对于完全相同子串会计算两次
		ans+=mp1[s[0]]+mp2[s[1]]-mp[s]*2;
		//cerr<<ans<<endl;
		mp[s]++;mp1[s[0]]++;mp2[s[1]]++;
		
	}
	cout<<ans<<endl;
}

找到不相交前缀和后缀，满足前缀和=后缀和，求两段长度和最大值

Solution：考虑维护后缀和的哈希表，后缀和映射到后缀左端点，每次查询前缀和是不是在哈希表中并且查询端点有没有相交，判断合法性，维护长度之和最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve(){
	int ans=0;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	vector<int>pre(n+1,0),suf(n+2,0);
	for(int i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];
	for(int i=n;i>=1;i--)suf[i]=suf[i+1]+a[i];
	map<int,int>pr,su;
	for(int i=1;i<=n;i++){
		pr[pre[i]]=i;
		su[suf[i]]=i;
	}
	
	for(int i=1;i<=n;i++){
		if(su.count(pre[i])==0)continue;
		int pos=su[pre[i]];
		if(pos>i){
			if(ans<i+n-pos+1){
				ans=i+n-pos+1;
			}
		}
	}
   cout<<ans<<endl;
}

G:题意：给定一个网格图，有物体，障碍，空白。要求给出物体自由落体的结果图。

Solution：考虑最下面的物体落到障碍物或者最后一行（地上），我们应该从行的逆序考虑，因为只有下面的物体确定，上面的物体才能确定。对于每个物体我们直接进行暴力下行试探，看什么时候出边界或者遇到障碍物或者遇到已经确定位置的球。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve(){
	cin>>n>>m;
	vector<string>v(n+1);
	for(int i=1;i<=n;i++){
		string s;cin>>s;
		v[i]=" "+s;
	}
	for(int i=n;i>=1;i--){
		for(int j=1;j<=m;j++){
			if(v[i][j]=='*'){
				int x=i;
				while(x+1<=n&&v[x+1][j]=='.')x+=1;
				swap(v[i][j],v[x][j]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cout<<v[i][j];
		}
		cout<<endl;
	}
	//cout<<endl;
}

H:题意：给定n个数，有k次操作的机会，每次可以给一个数int范围内的某个二进制位变为1，要求k次操作结束后，最大化数组的与和值（n个数与起来）

Solution:首先统计每一位是0的数的个数。考虑按高位贪心，如果剩余次数足以完成本次贪心，那么维护次数，更新答案。否则，就考虑下一位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve(){
	//cerr<<(1<<31)-1<<endl;
	cin>>n;int k;cin>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	vector<int>v(40,0);
	for(int i=1;i<=n;i++){
		for(int j=30;j>=0;j--){
			int u=(a[i]>>j)&1;
			if(u==0)v[j]++;
		}
	}
	int ans=0;
	for(int i=30;i>=0;i--){
		if(k>=v[i]){
			ans|=(1<<i);
			k-=v[i];
		}
	}
	cout<<ans<<endl;
}