当前鸽掉没补完的题解，为了能复制还是先发出来吧哈哈
Problem C
解题思路：
按照题意暴力的做，记得对于操作2，找到终点时压缩一下路径。
代码：
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> #define ll long long using namespace std; const int N = 1e5+5; int n,m,t,x,y; int lzq[N]; int cao[N],pos[N]; int main() { int t; scanf("%d",&t); while (t--){ int n,m; scanf("%d %d",&n,&m); memset(lzq,0,sizeof lzq); for (int i=1;i<=m;i++){ scanf("%d %d",cao+i,pos+i); if (cao[i]==1){ lzq[pos[i]]++; } else { int p = pos[i]; while (cao[p]!=1) p = pos[p]; pos[i] = p; lzq[pos[p]]++; } } for (int i=1;i<=n;i++) if (i==1) printf("%d",lzq[i]); else printf(" %d",lzq[i]); printf("\n"); } return 0; }
Problem E
解题思路：
注意是环
当个数为1，2的时候，A胜利；
否则，A将串断开后，B可以一次取走所有，或者根据情况取一个或者两个，使得剩下的两堆相同，然后只要模仿A的行动就可以了，最后B一定胜利。
代码：
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> #define ll long long using namespace std; const int N = 1e5+5; int n,m,t,x,y; int main() { ll n; while (~scanf("%lld",&n)){ if (n==1||n==2) printf("A\n"); else printf("B\n"); } return 0; }Problem H
解题思路：
个数等于a/gcd(a,b)*b/gcd(a,b)
代码：
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> #define ll long long using namespace std; const int N = 1e5+5; int n,m,t,x,y; ll gcd(ll a,ll b){ return (a-a/b*b)==0? b:gcd(b,a-a/b*b); } int main() { ll a,b; while (~scanf("%lld %lld",&a,&b)){ if (a==b) { printf("1\n"); continue; } ll sb = gcd(a,b); a = a/sb; b = b/sb; printf("%lld\n",a*b); } return 0; }Problem H
解题思路：
后缀数组模板题。
后缀数组构造的时候需要s[n] = 0,然后构造n+1，不然越界。
#include<cstdio>8 #include<cstring> #include<algorithm> #define lson rt<<1,l,m #define rson rt<<1|1,m+1,r #define mid int m=l+r>>1 #define tl tree[rt<<1] #define tr tree[rt<<1|1] #define debug(x) printf("----Line %s----\n",#x) #define inf 0x3f3f3f3f using namespace std; const int N = 2e5+5; int wa[N],wb[N],cnt[N<<1],sa[N],rnk[N],height[N]; int tree[N<<2],ans; char s[N]; void push_up(int rt) { tree[rt] = min(tl,tr); } void build(int rt,int l,int r)///线段树维护height[1]~height[n-1] (不会RMQ) { if (l==r){ tree[rt] = height[l]; return ; } mid; build(lson); build(rson); push_up(rt); } void query(int L,int R,int rt,int l,int r)///查找L~R的最小值 { if (L<=l && r<=R){ ans = min(ans,tree[rt]); return ; } mid; if (L<=m) query(L,R,lson); if (R>m) query(L,R,rson); } void sufbuild(int n,int m)///构造后缀数组 { int p,i,j,*x=wa,*y=wb; for (i=0;i<m;i++) cnt[i] = 0; for (i=0;i<n;i++) cnt[x[i]=s[i]]++; for (i=1;i<m;i++) cnt[i] += cnt[i-1]; for (i=n-1;i>=0;i--) sa[--cnt[x[i]]] = i; for (j=1,p=1;p<n;j<<=1,m=p){//debug("喵喵喵"); for (p=0,i=n-j;i<n;i++) y[p++] = i/*,printf("y[%d]=%d\n",p-1,y[p-1])*/; for (i=0;i<n;i++) if (sa[i]>=j) y[p++] = sa[i]-j; //debug("汪汪汪"); for (i=0;i<m;i++) cnt[i] = 0;//debug("汪"); for (i=0;i<n;i++) /*printf("y[%d]=%d,x[y[%d]]=%d\n",i,y[i],i,x[y[i]]),*/cnt[x[y[i]]]++;//debug("吐"); for (i=1;i<m;i++) cnt[i] += cnt[i-1];//debug("碎"); for (i=n-1;i>=0;i--) sa[--cnt[x[y[i]]]] = y[i];//debug("佛"); //debug("fuckfuckfuck"); swap(x,y); x[sa[0]] = 0; p = 1; for (i=1;i<n;i++) x[sa[i]] = ( y[sa[i]]==y[sa[i-1]] && y[sa[i]+j]==y[sa[i-1]+j] )? p-1:p++; } } void getheight(int n) { int k=0; for (int i=0;i<n;i++) rnk[sa[i]] = i; for (int i=0;i<n;i++){ if (rnk[i]==0){ height[rnk[i]] = k = 0; continue; } if (k) k--; int j = sa[rnk[i]-1]; while (i+k<n && j+k<n && s[i+k]==s[j+k]) k++; height[rnk[i]] = k; } } int main() { int n; scanf("%d",&n); scanf("%s",s);//debug(0); s[n]=0; sufbuild(n+1,256);//debug(1); getheight(n+1);//debug(2); build(1,1,n);///维护height[1]~height[n] /* printf("\n"); for (int i=0;i<n;i++) printf("%s\n",s+sa[i]); for (int i=0;i<n;i++) printf("rank[%d]=%d\n",i,rnk[i]); for (int i=0;i<n;i++) printf("height[%d]=%d\n",i,height[i]); */ int q; scanf("%d",&q); while (q--){ int l,r,ll,rr; scanf("%d %d %d %d",&l,&r,&ll,&rr); int L=rnk[l],R=rnk[ll]; if (L==R){///两者起点相同，特殊处理 printf("%d\n",min(r-l+1,rr-ll+1)); continue; } if (L>R) swap(L,R); L++; ans = inf; query(L,R,1,1,n); printf("%d\n",min(ans,min(r-l+1,rr-ll+1))); } return 0; }
