比赛链接:https://codeforces.ml/contest/1748

A题:水题,大意是给出n,存在n个方块,边长为n/i ,向下上取整。

根据样例直接找规律。

B题:给出0-9的字符串,找出有多少组l - r中,每个数字出现的次数不超过l - r中所有不同类别数字的组数。
数据量比较大1e5 ,显然暴力不可取

思路:我们很容易发现,如果存在一个数组在段中出现的次数超过了10,那么之后的字符串便无需遍历。这样每个子串最多枚举100个元素
直接暴力 1e7的复杂度解决。

code:

void solve()
{
	mem(sign);
	mem(cnt);
	ll ans = 0;
	int n;
	cin>>n;
	string s;
	cin>>s;
	for(int i=0;i<n;i++){
		mem(sign); mem(cnt);
		int ts = 0;
		int maxt = 0;
		for(int j=i;j<n;j++){
			int num = s[j]-'0';
			if(!sign[num]) ts++,sign[num]=true;
			cnt[num]++;
			maxt = max(maxt,cnt[num]);
			if(maxt<=ts) ans++;
			if(maxt>10) break;
		}
	}
	cout<<ans<<endl;
}

C题:大意是给出一堆数,有部分数字为0,0可以修改为任意数字。求通过修改后,最多存在多少个前缀和为0

这个题读懂了,但是没有写明白,可能还是有一些细节处理的不是很到位,尤其是边界问题还是有些许模糊。

思路:前面的s0直接加一块,之后我们选择性的影响每个独立的段,map记录每个前缀,存在多次相同情况可以置为0。最后边界可以置为一个0用于处理前面。和我的处理很像,但是我没写出来ε=(´ο`*)))

code:

void solve()
{
	mem(a); mp.clear();	
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	a[n+1] = 0;
	ll ans = 0; bool have =  false;
	ll maxzero = 0; ll s = 0;
	for(int i=1;i<=n+1;i++){
		if(a[i]==0){
			if(!have) ans+=mp[0],have=true; //第一次遇到0直接加之前和0的个数 
			else ans+=maxzero;//之后我们把这个0影响后面 
			maxzero = 0;
			mp.clear();
		}
		s+=a[i];
		maxzero = max(maxzero,++mp[s]);
	}
	cout<<ans<<endl;
}