A：即求長度為偶數的異或和為0的區間個數，對前綴異或和用桶記錄即可。

#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 300010 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; } int n,a[N],cnt[1<<20][2]; ll ans; signed main() { #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);const char LL[]="%I64d\n"; #endifn=read();for (int i=1;i<=n;i++) a[i]=a[i-1]^read();cnt[0][0]=1;for (int i=1;i<=n;i++){ans=ans+cnt[a[i]][i&1];cnt[a[i]][i&1]++;}cout<<ans;return 0;//NOTICE LONG LONG!!!!! }

　　B：顯然如果有解，答案一定不大于2，因為原串是回文串，找到第一個不是回文串的前綴和對其對應后綴切掉并交換即可。無解直接判斷是否字母都相同或只有最中間字母不同。然后只需要check是否為1，暴力枚舉切割點暴力判斷即可。

#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 5010 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; } int n; char s[N],a[N]; signed main() { #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);const char LL[]="%I64d\n"; #endifscanf("%s",s+1);n=strlen(s+1);if (n==1) {cout<<"Impossible";return 0;}bool flag=1;for (int i=2;i<=n;i++) if (s[i]!=s[1]) {flag=0;break;}if (flag) {cout<<"Impossible";return 0;}if (n&1){bool flag=1;for (int i=2;i<=n;i++) if (s[i]!=s[1]&&i!=(n+1)/2) {flag=0;break;}if (flag) {cout<<"Impossible";return 0;}}for (int i=1;i<n;i++){for (int j=1;j<=n-i;j++) a[j]=s[j+i];for (int j=n-i+1;j<=n;j++) a[j]=s[j-(n-i)];bool flag=1;for (int j=1;j<=n;j++) if (a[j]!=a[n-j+1]) {flag=0;break;}if (!flag) continue;for (int j=1;j<=n;j++) if (a[j]!=s[j]) {cout<<1;return 0;}}cout<<2;return 0;//NOTICE LONG LONG!!!!! }

　　D：顯然枚舉兩點路徑上有多少個點，選出這些點并排列，給路徑上每條邊插板分配權值，剩余邊權值任意取。只剩下一個問題，就是如何計算固定這條路徑后，樹的形態個數。考慮將這條邊縮點，一條邊連接某兩個點的方案數是1，而連接某個點和這條鏈的方案數則是其鏈長。將鏈長作為這個點的權值，其余點權值為1，于是我們要統計的東西相當于縮點后每棵樹的所有點權值^度數之積的和。注意到出現了度數，考慮prufer序列。序列中每個點出現次數=其度數-1，并且由于要統計所有樹，每種對應的prufer序列都存在。這樣由分配律可得方案數即為(i+1)*n^n-2-i，其中i為路徑上點的個數。

#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 1000010 #define P 1000000007 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; } int n,m,a,b,fac[N],inv[N],ans; int ksm(int a,int k) {int s=1;for (;k;k>>=1,a=1ll*a*a%P) if (k&1) s=1ll*s*a%P;return s; } int C(int n,int m){if (m>n) return 0;return 1ll*fac[n]*inv[m]%P*inv[n-m]%P;} signed main() { #ifndef ONLINE_JUDGEfreopen("d.in","r",stdin);freopen("d.out","w",stdout);const char LL[]="%I64d\n"; #endifn=read(),m=read();read(),read();fac[0]=1;for (int i=1;i<=N-10;i++) fac[i]=1ll*fac[i-1]*i%P;inv[0]=inv[1]=1;for (int i=2;i<=N-10;i++) inv[i]=P-1ll*(P/i)*inv[P%i]%P;for (int i=1;i<=N-10;i++) inv[i]=1ll*inv[i-1]*inv[i]%P;for (int i=1;i<n;i++){int x;if (i==n-1) x=1;else x=1ll*(i+1)*ksm(n,n-2-i)%P;x=1ll*x*C(m-1,i-1)%P*C(n-2,i-1)%P*ksm(m,n-i-1)%P*fac[i-1]%P;ans=(ans+x)%P;}cout<<ans;return 0;//NOTICE LONG LONG!!!!! }

　　E：傻逼題，要是先開E而不是C說不定就碼完了。對模數的質因子分別記錄次數即可，線段樹瞎維護。質因子的次冪可以預處理一下，略卡常。

#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 100010 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; } int n,P,a[N],q,L[N<<2],R[N<<2],ans[N<<2],p[12],u[12][2][1000010],cnt; ll lazy[N<<2][12]; int ksm(int a,ll k) {return 1ll*u[a][0][k%1000000]*u[a][1][k/1000000]%P; } void exgcd(int &x,int &y,int a,int b) {if (b==0){x=1,y=0;return;}exgcd(x,y,b,a%b);int t=x;x=y;y=t-a/b*x; } int inv(int a) {int x,y;exgcd(x,y,a,P);return (x%P+P)%P; } void up(int k){ans[k]=(ans[k<<1]+ans[k<<1|1])%P;} void update(int k) {ans[k]=lazy[k][0];for (int i=1;i<=cnt;i++) ans[k]=1ll*ans[k]*ksm(i,lazy[k][i])%P; } void down(int k,int i) {lazy[k<<1][i]+=lazy[k][i],lazy[k<<1|1][i]+=lazy[k][i];ans[k<<1]=1ll*ans[k<<1]*ksm(i,lazy[k][i])%P,ans[k<<1|1]=1ll*ans[k<<1|1]*ksm(i,lazy[k][i])%P;lazy[k][i]=0; } void down(int k) {lazy[k<<1][0]=1ll*lazy[k<<1][0]*lazy[k][0]%P;lazy[k<<1|1][0]=1ll*lazy[k<<1|1][0]*lazy[k][0]%P;ans[k<<1]=1ll*ans[k<<1]*lazy[k][0]%P;ans[k<<1|1]=1ll*ans[k<<1|1]*lazy[k][0]%P;lazy[k][0]=1;for (int i=1;i<=cnt;i++)down(k,i); } void build(int k,int l,int r) {L[k]=l,R[k]=r;lazy[k][0]=1;if (l==r){ans[k]=lazy[k][0]=a[l];ans[k]%=P;for (int i=1;i<=cnt;i++)while (lazy[k][0]%p[i]==0)lazy[k][0]/=p[i],lazy[k][i]++;return;}int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);up(k); } void add(int k,int l,int r,int i,int x,int u) {if (L[k]==l&&R[k]==r) {ans[k]=1ll*ans[k]*u%P;lazy[k][i]+=x;return;}down(k,i);int mid=L[k]+R[k]>>1;if (r<=mid) add(k<<1,l,r,i,x,u);else if (l>mid) add(k<<1|1,l,r,i,x,u);else add(k<<1,l,mid,i,x,u),add(k<<1|1,mid+1,r,i,x,u);up(k); } void mul(int k,int l,int r,int x) {if (L[k]==l&&R[k]==r) {ans[k]=1ll*ans[k]*x%P;lazy[k][0]=1ll*lazy[k][0]*x%P;return;}down(k);int mid=L[k]+R[k]>>1;if (r<=mid) mul(k<<1,l,r,x);else if (l>mid) mul(k<<1|1,l,r,x);else mul(k<<1,l,mid,x),mul(k<<1|1,mid+1,r,x);up(k); } void add(int k,int p,int i,int x) {if (L[k]==R[k]) {lazy[k][i]+=x;update(k);return;}down(k,i);int mid=L[k]+R[k]>>1;if (p<=mid) add(k<<1,p,i,x);else add(k<<1|1,p,i,x);up(k); } void mul(int k,int p,int x) {if (L[k]==R[k]) {lazy[k][0]=1ll*lazy[k][0]*x%P;update(k);return;}down(k);int mid=L[k]+R[k]>>1;if (p<=mid) mul(k<<1,p,x);else mul(k<<1|1,p,x);up(k); } int query(int k,int l,int r) {if (L[k]==l&&R[k]==r) return ans[k];down(k);int mid=L[k]+R[k]>>1;if (r<=mid) return query(k<<1,l,r);else if (l>mid) return query(k<<1|1,l,r);else return (query(k<<1,l,mid)+query(k<<1|1,mid+1,r))%P; } signed main() { #ifndef ONLINE_JUDGEfreopen("e.in","r",stdin);freopen("e.out","w",stdout);const char LL[]="%I64d\n"; #endifn=read(),P=read();int v=P;for (int i=2;i*i<=v;i++)if (v%i==0){p[++cnt]=i;while (v%i==0) v/=i;}if (v>1) p[++cnt]=v;for (int i=1;i<=cnt;i++){u[i][0][0]=1;for (int j=1;j<=1000000;j++) u[i][0][j]=1ll*u[i][0][j-1]*p[i]%P;u[i][1][0]=1;for (int j=1;j<=1000000;j++) u[i][1][j]=1ll*u[i][1][j-1]*u[i][0][1000000]%P;}for (int i=1;i<=n;i++) a[i]=read();build(1,1,n);q=read();while (q--){int op=read();if (op==1){int l=read(),r=read(),x=read();for (int i=1;i<=cnt;i++){int t=0;while (x%p[i]==0) t++,x/=p[i];if (t) add(1,l,r,i,t,ksm(i,t));}mul(1,l,r,x);}if (op==2){int u=read(),x=read();for (int i=1;i<=cnt;i++){int t=0;while (x%p[i]==0) t++,x/=p[i];if (t) add(1,u,i,-t);}mul(1,u,inv(x));}if (op==3){int l=read(),r=read();printf("%d\n",query(1,l,r));}}return 0;//NOTICE LONG LONG!!!!! }

　　C實在不想補。

　　result：rank 37 rating +142

　　F：先考慮一維情況怎么做。一些點在序列上連續相當于點數-邊數（即相鄰兩點同時被選）=1，考慮在值域上不斷移動右端點，用線段樹維護每個后綴區間的點數-邊數的值。由于每次只是對每個區間都增加該右端點，考慮該點對每個區間的影響，顯然根據其相鄰兩數將值域分成幾段，分別用線段樹區間加即可。因為點數-邊數>=1，維護區間最小值及個數即可統計答案。

　　拓展到二維，考慮使用同樣的做法，但需要保證選出的點構成樹。一個自然的想法是由于已經要求點數-邊數=1，只要讓選出的點構成連通塊即可，但這個東西沒有任何單調性。事實上注意到只要不形成環，加上點數-邊數=1，也可以保證這是一棵樹，而這個東西則是單調的。使用雙指針，枚舉右端點，找到最靠前的滿足不構成環的左端點即可，可以LCT實現帶刪邊并查集。

#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 200010 #define lson tree[k].ch[0] #define rson tree[k].ch[1] #define lself tree[tree[k].fa].ch[0] #define rself tree[tree[k].fa].ch[1] char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; } int n,m,a[1010][1010],near[N][4]; ll ans; struct data{int ch[2],fa,rev; }tree[N]; void rev(int k){if (k) swap(lson,rson),tree[k].rev^=1;} void down(int k){if (tree[k].rev) rev(lson),rev(rson),tree[k].rev=0;} int whichson(int k){return rself==k;} bool isroot(int k){return lself!=k&&rself!=k;} void push(int k){if (!isroot(k)) push(tree[k].fa);down(k);} void move(int k) {int fa=tree[k].fa,gf=tree[fa].fa,p=whichson(k);if (!isroot(fa)) tree[gf].ch[whichson(fa)]=k;tree[k].fa=gf;tree[fa].ch[p]=tree[k].ch[!p],tree[tree[k].ch[!p]].fa=fa;tree[k].ch[!p]=fa,tree[fa].fa=k; } void splay(int k) {push(k);while (!isroot(k)){int fa=tree[k].fa;if (!isroot(fa))if (whichson(fa)^whichson(k)) move(k);else move(fa);move(k);} } void access(int k){for (int t=0;k;t=k,k=tree[k].fa) splay(k),tree[k].ch[1]=t;} int findroot(int k){if (!k) return 0;access(k);splay(k);for (;lson;k=lson) down(k);splay(k);return k;} void makeroot(int k){access(k),splay(k),rev(k);} void link(int x,int y){makeroot(x);tree[x].fa=y;} void cut(int x,int y){makeroot(x),access(y),splay(y);tree[y].ch[0]=tree[x].fa=0;} int L[N<<2],R[N<<2],sum[N<<2],top[N<<2],lazy[N<<2]; void up(int k) {if (top[k<<1]==top[k<<1|1]){top[k]=top[k<<1];sum[k]=sum[k<<1]+sum[k<<1|1];}else if (top[k<<1]<top[k<<1|1]) top[k]=top[k<<1],sum[k]=sum[k<<1];else top[k]=top[k<<1|1],sum[k]=sum[k<<1|1]; } void build(int k,int l,int r) {L[k]=l,R[k]=r;if (l==r) {sum[k]=1;return;}int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);up(k); } void Down(int k) {top[k<<1]+=lazy[k],top[k<<1|1]+=lazy[k];lazy[k<<1]+=lazy[k],lazy[k<<1|1]+=lazy[k];lazy[k]=0; } void add(int k,int l,int r,int op) {if (L[k]==l&&R[k]==r) {lazy[k]+=op;top[k]+=op;return;}if (lazy[k]) Down(k);int mid=L[k]+R[k]>>1;if (r<=mid) add(k<<1,l,r,op);else if (l>mid) add(k<<1|1,l,r,op);else add(k<<1,l,mid,op),add(k<<1|1,mid+1,r,op);up(k); } int query(int k,int l,int r) {if (L[k]==l&&R[k]==r) return (top[k]==1)*sum[k];if (lazy[k]) Down(k);int mid=L[k]+R[k]>>1;if (r<=mid) return query(k<<1,l,r);else if (l>mid) return query(k<<1|1,l,r);else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r); } void print(int k,int l,int r) {if (L[k]==R[k]) {cout<<top[k]<<' ';return;}if (lazy[k]) Down(k);int mid=L[k]+R[k]>>1;if (r<=mid) print(k<<1,l,r);else if (l>mid) print(k<<1|1,l,r);else print(k<<1,l,mid),print(k<<1|1,mid+1,r); } signed main() { #ifndef ONLINE_JUDGEfreopen("f.in","r",stdin);freopen("f.out","w",stdout); #endifn=read(),m=read();for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)a[i][j]=read();for (int i=1;i<=n;i++)for (int j=1;j<=m;j++){near[a[i][j]][0]=a[i-1][j];near[a[i][j]][1]=a[i+1][j];near[a[i][j]][2]=a[i][j-1];near[a[i][j]][3]=a[i][j+1];}build(1,1,n*m);int l=1;for (int i=1;i<=n*m;i++){bool flag;do{flag=0;int u[5],t=0;u[t++]=findroot(i);for (int j=0;j<4;j++) if (near[i][j]) u[t++]=findroot(near[i][j]);for (int x=0;x<t;x++)for (int y=x+1;y<t;y++)if (u[x]==u[y]) {flag=1;break;}if (!flag) break;for (int j=0;j<4;j++) if (near[l][j]>=l&&near[l][j]<i) cut(l,near[l][j]);l++;}while (1);add(1,l,i,1);for (int j=0;j<4;j++)if (near[i][j]>=l&&near[i][j]<=i)link(i,near[i][j]),add(1,l,near[i][j],-1);ans+=query(1,l,i);//print(1,l,i);cout<<endl;//cout<<l<<' '<<i<<' '<<ans<<endl;}cout<<ans;return 0;//NOTICE LONG LONG!!!!! }

?

　　

?

轉載于:https://www.cnblogs.com/Gloid/p/10392343.html

總結

以上是生活随笔為你收集整理的Codeforces Round #539 Div. 1的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。