Codeforces Round #833 (Div. 2)

 比赛链接：Dashboard - Codeforces Round #833 (Div. 2) - Codeforces

A: 签到题

题意：给定整数 n ，表示存在长度为 ⌊i⌋(i∈[1,n]) 宽度为 1 的木板，求这些木板能够拼接成的变长最大的正方形。

思路：通过样例发现：ans=⌈n⌉

代码：

#include
#define int long long
using namespace std;
const int N=2e5+10;
int a[N];
 
inline void solve(){
	int n;cin>>n;
	cout<<(n+1)/2<<"\n";//对奇数进行向上取整
}
 
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--) solve();
}

B:思维

题意：定义了一个特殊的数字串，当且仅当该串中出现的数字种类是大于相同子串出现次数最多的的数。给定一个初始的数字串，问存在多少子串是特殊的。

思路：我们发现，出现数字的种类只有10种（0~9）。那么，当一个串的长度超过了100，那么肯定有个数字是出现了11次，10<11的，就不满足定义。因此只需要从每个位置出发，暴力枚举长度100以内的数即可。

代码：

#include
#define int long long
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=110;
int cnt[N];//记录数字出现的次数
int n;
 
inline void solve(){
	int n;cin>>n;
	string s;cin>>s;s="*"+s;
	for(int i=1;i<10;i++) cnt[i]=0;
	int mx=0,cc=0,ans=0;
	for(int i=1;i<=n;i++){
		//for(int j=0;j<10;j++) cnt[j]=0;
		mx=0,cc=0;memset(cnt,0,sizeof cnt);//mx：记录出现次数最多的数  //cc：记录数字种类
		for(int j=i;j<=min(i+99,n);j++){//保证合法，如果长度大于100，就枚举100，否则就枚举n
			cnt[s[j]-'0']++;
			if(cnt[s[j]-'0']==1) cc++;
			mx=max(mx,cnt[s[j]-'0']);
			if(cc>=mx) ans++;//如果满足定义
		}
	}
	cout<"\n";
}
 
signed main(){
	fast;
	int T;cin>>T;
	while(T--) solve();
}

C:思维+构造

题意：给定一个长度为 n 的数组，对于某一位置 i 满足 ai=0 ，可以将 ai 修改为任意整数。求最终前缀和数组中 0 出现的最多次数。

思路:

考虑从后往前构造。如果一个 0 出现，最优操作一定是让这个 0 后面出现次数最多的某一个值变成 0。虽然在这个 0 前面可能仍然存在 0，但是我们一定可以让这个位置的 0 自适应成某一个值使得出现次数最多的值的前缀和变为 0 。

通解： 考虑两个 0 之间出现次数最多的数，也就是对答案真正的贡献。最少的贡献是 1 。

坑点： 第一个 0 出现前的位置如果前缀和为 0 记得要加到答案上。

ps：此题的题解是典儿的，有兴趣可以看他的blog哦 

链接：Codeforces Round #833 (Div. 2) A - D - 知乎

简要说明一下思路：因为要使前缀和为0的个数最多，那么从后往前进行构造，我们发现，只要统计前缀和出现最多的数字，那么当遇到数字0的时候，一定是可以将整个前缀和变为0的，那么就尽最大可能使多个前缀和变为0（因为改变的是前缀和出现最多的数）但是这种方法还有个bug，那就是，如果原始的前缀和就为0，那么就没有统计进去，所以，答案最终还要去统计从前往后，前缀和为0的个数，直到出现第一数为0的位置结束

代码：

#include
#define int long long
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e5+10;
int a[N],s[N];
int n,mx;
map<int,int>mp;
bool p[N];//标记数组 表示从这个位置开始 后面已经清过了
 
inline void add(int x){
	mp[x]++;
	mx=max(mx,mp[x]);
}
 
inline void clear(int x){//清空之前记录的
	mx=0;
	for(int i=x;i<=n;i++){
		if(p[i]) return;
		else mp[s[i]]--,p[i]=true;
	}
}
 
inline void solve(){
	cin>>n;mp.clear();mx=0;
	memset(p,false,sizeof p);
	for(int i=1;i<=n;i++){
		cin>>a[i];s[i]=s[i-1]+a[i];
	}
	int ans=0;
	for(int i=n;i>=1;i--){
		add(s[i]);
		if(a[i]==0){
			ans+=max(1LL,mx);clear(i);
		}
	}
	for(int i=1;i<=n;i++){//特判
		if(a[i]==0) break;
		else if(s[i]==0) ans++;
	}
	cout<"\n";
}
 
signed main(){
	fast;
	int T;cin>>T;
	while(T--) solve();
}