不小心在上午十一点多点开了比赛界面。
结果最后少打了两个小时。
100+100+0+0 遗憾离场
T1 春
题意
给定一个字符串 \(s\)，至多进行一次操作：反转 \(s\) 的任意一个子串。
求最后能得到多少种不同的字符串。
赛时
观察半天。
以为是回文串，还想着我不会马拉车。结果仔细想了想发现其实是个糖糖题。
题解
以 abca 为例。不难发现，反转 abca 和反转 bc 得到的结果是一样的。
所以我们可以发现，对于一对相同的字符，我们反转这两个相同字符中间的子串，和带上这两个字符，会导致一个重复的答案。
所以就变成了糖糖题。
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
using namespace std;string s;
long long n;long long mp[26];int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>s;n=s.length(),s=' '+s;for(int i=1;i<=n;i++) mp[s[i]-'a']++;long long ans=n*(n-1)/2+1;for(int i=0;i<26;i++){long long nw=mp[i];ans-=(nw*(nw-1)/2);}cout<<ans;return 0;
}
T2 夏
题意
定义奶糖序列为满足 \(\forall 1\le x,y,xy\le n,a_x+a_y=a_{xy}\) 的序列。
现在你有一个奶糖序列。\(q\) 次询问，每次修改一个位置，问最坏情况下，把序列重新变回奶糖序列的最小操作次数。
赛时
这题是下午抓住仅剩的不到一个小时搓的。
结果算糖了。
\(O(q\sqrt n \log n)\) 居然能过？？
题解
补题的时候发现洛谷上还能写题解，所以这里直接复制我的题解了。
我们首先考虑最特殊的 \(a_1\)。不难注意到，对于任意的 \(x\)，\(a_x=a_1+a_x\)。也就是 \(a_1\) 只能为 \(0\)。
我们尝试构造一个对数序列：
我们发现，对于序列的第合数项，值只由其分解质因数后对应的值得到。
如 \(a_{12}=a_{2}+a_{6}=2a_{2}+a_{3}\)。
而对于质数，其值不受限制。
也就是说，我们修改一个位置 \(x\)，将会影响到 \(x\) 的质因数的值。而且不难注意到，我们只需要修改其中一个质因数对应的取值就足够了。
那么很显然，根据贪心策略，我们应该修改 \(x\) 的最大质因数，和 \(x\) 的最大质因数的所有倍数。
所以答案就是 \(x\) 的最大质因数在 \([1,n]\) 中的倍数数量减 \(1\)。因为我们不需要额外修改 \(x\)。
时间复杂度 \(O(q\sqrt n)\)。
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
using namespace std;long long n,q;
long long calc(long long x){long long lst=1;for(long long i=2;i*i<=x;i++) while(x%i==0) x/=i,lst=i;if(x!=1) lst=max(lst,x);return lst;
}int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>q;while(q--){long long x;cin>>x;if(x==1) cout<<"-1\n";else{long long p=calc(x);cout<<n/p-1<<"\n";}}return 0;
}
总结
没打满。挂完了。
至少切了两道题。不算太炸。