比赛链接: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; }