NOIP模拟赛 · ooliver

DAY1 A. 剪切字符串可以想到一个简单的贪心，就是在最坏情况下，我两个字串长度都取 1，此时 \text{LCP} 最大为 3，即每个 \text{LCP} 最大为 1。所以我们贪心地认为 i=1，此时可以对字符串 c 中的每一个字母个数进行前缀和，然后枚举 j，判断 c 的字串中能否找到一个字母异于 a_i 和 b_j。代码如下： #include using namespace std; const int N=1e5+5; int T,n; string a,b,c; int sum[N][30]; int main(){ freopen("lcp.in","r",stdin); freopen("lcp.out","w",stdout); cin>>T; while(T--){ memset(sum,0,sizeof sum); int ans=3; cin>>n>>a>>b>>c; a=" "+a,b=" "+b,c=" "+c; for(int i=1;i `#include using namespace std; const int N=1e5+5; int T,n; string a,b,c; int sum[N][30]; int main(){ freopen("lcp.in","r",stdin); freopen("lcp.out","w",stdout); cin>>T; while(T--){ memset(sum,0,sizeof sum); int ans=3; cin>>n>>a>>b>>c; a=" "+a,b=" "+b,c=" "+c; for(int i=1;i for(int j=0;j30;j++) sum[i][j]+=sum[i-1][j]; sum[i][c[i]-'a']++; } for(int i=2;i if(a[1]==b[i]){ int cnt=sum[n][a[1]-'a']-sum[i][a[1]-'a']; if(cntmin(ans,1); else ans=min(ans,3); } else{ int cnt=(sum[n][a[1]-'a']-sum[i][a[1]-'a'])+(sum[n][b[i]-'a']-sum[i][b[i]-'a']); if(cntmin(ans,0); else ans=min(ans,1); } } cout } return 0; }` DAY2 A. gcd&xor 一看到是数学题，直接枚举了一下 100 以内的符合题意的数对，发现数对的一个充分不必要条件，即 |a-b|= \gcd(a,b)。发现可以枚举 \gcd，对于每一个 i=\gcd，循环判断每一个 j \oplus (j+i) 是否与 i 相等，需要 O(\sum^{n}_{i=1} \frac{n}{i}) 的复杂度。注意到： \sum^{n}_{i=1} \frac{n}{i} = n\sum^{n}_{i=1} \frac{1}{i} 其中调和级数 \sum^{n}_{i=1} \frac{1}{i} 满足： $$ \sum^{n}_{i=1} \frac{1}{i} = \ln(n+1)+γ #include using namespace std; int n,ans; int main(){ freopen("gcdxor.in","r",stdin); freopen("gcdxor.out","w",stdout); cin>>n; for(int i=1;i>1;i++) for(int j=i;j+i `#include using namespace std; int n,ans; int main(){ freopen("gcdxor.in","r",stdin); freopen("gcdxor.out","w",stdout); cin>>n; for(int i=1;i>1;i++) for(int j=i;j+iif((j^(j+i))==i) ans++; cout return 0; }` B. 异或树先讨论操作一：对于每个点权为 w 的叶子节点，会新增两个点权分别为 w 和 w \oplus x 的子节点，对于子树异或和的贡献为两个值为 w \oplus x 的子树，而对于叶子节点的贡献是新增一个点权为 w \oplus x 的点。所以很容易想到去枚举每一次操作后的叶子节点。但是操作次数 q≤8000，又发现 k_0, x \in [0,2^{13})，想到可以用两个桶数组分别存储答案和每个值对应叶子节点数量，并再用一个桶数组表示每个值新增叶子节点的数量，最后转移到总叶子节点桶数组即可，可以避免在同层加叶子节点时重复计算。代码： #include using namespace std; #define int long long int read(){ int k=0,f=1; char c=getchar(); while(c'9'){ if(c=='-')f=-1; c=getchar(); } while(c>='0'&&c `#include using namespace std; #define int long long int read(){ int k=0,f=1; char c=getchar(); while(c'0'||c>'9'){ if(c=='-')f=-1; c=getchar(); } while(c>='0'&&c'9')k=k*10+c-'0',c=getchar(); return k*f; } const int N=8200,mod=998244353; int k,q; int t[N],tag[N],ntag[N]; signed main(){ freopen("xortree.in","r",stdin); freopen("xortree.out","w",stdout); k=read(),q=read(); t[k]=tag[k]=1; while(q--){ int op,x; op=read(),x=read(); if(op==1){ for(int i=0;iif(tag[i]){ (ntag[(i^x)]+=tag[i])%=mod; (t[(i^x)]+=2*tag[i])%=mod; } for(int i=0;itag[i]+=ntag[i])%=mod,ntag[i]=0; } else if(op==2) printf("%lld\n",t[x]%mod); } return 0; }` DAY3 只写了第一题，结果还挂了50分，现在玄关了……