来自FallDream的博客，未经允许，请勿转载，谢谢。
ditoly几分钟就AK了 跪下来了
-----------------------------
A.有1到5 5个点，每个点到它的编号+1和+2都有单向边。给出边的长度，你要从1号点出发走恰好距离恰好为N的路，并求出经过的点最少的情况下字典序最小的方案。n<=500000
题解：倒过来DP一下，然后直接走呗。
#include<iostream> #include<cstdio> #include<cstring> #define INF 200000000 using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } int b[7][500005]; int n,to[5][2]={{3,4},{4,0},{0,1},{1,2},{2,3}},d[5][2],ans=INF,from=-1; void dfs(int x,int dd) { printf("%d ",x+1); if(dd==n) return; for(int i=0;i<5;i++) for(int k=0;k<2;k++) if(to[i][k]==x&&dd+d[i][k]<=n&&b[i][dd+d[i][k]]==b[x][dd]-1) { dfs(i,dd+d[i][k]); return; } } int main() { n=read(); d[1][1]=read();d[2][0]=read(); d[2][1]=read();d[3][0]=read(); d[3][1]=read();d[4][0]=read(); d[4][1]=read();d[0][0]=read(); d[0][1]=read();d[1][0]=read(); memset(b,64,sizeof(b)); for(int i=0;i<5;i++) b[i][n]=0; for(int i=n;i;i--) for(int j=0;j<5;j++) for(int k=0;k<2;k++) if(i-d[j][k]>=0) b[to[j][k]][i-d[j][k]]=min(b[to[j][k]][i-d[j][k]],b[j][i]+1); if(b[0][0]>=INF) return 0*puts("-1"); else dfs(0,0); return 0; }
B.给定n个数ai，求满足积是完全平方数的子串的个数。n<=500000 ai<=1000000
题解：先分解质因数，然后求出每个的前缀异或和，发现前缀异或和都相同的才会计入答案，所以可以哈希一下，给每个质数对应一个哈希值，每次异或上质数的哈希值就行了。
#include<iostream> #include<cstdio> #define ll long long #define MX 1000000 #define orz 2333333 using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } int n,s[MX+5],a[MX],num=0,nn[MX+5];ll p[MX+5],p2[MX+5],X=1e10,Y=1e11,ans=0; bool b[MX+5]; int head[orz],cnt=0; struct my_map{int ans,next;ll x,y;}e[MX+5]; void ins(ll x,ll y) { int j=x%orz; for(int i=head[j];i;i=e[i].next) if(e[i].x==x&&e[i].y==y) { ans+=e[i].ans;++e[i].ans; return; } e[++cnt]=(my_map){1,head[j],x,y};head[j]=cnt; } int Ran() { static unsigned int x=88956; x^=(x<<13);x^=(x>>17);x^=(x<<5); return x; } int main() { n=read();for(int i=1;i<=n;i++) a[i]=read(); for(int i=2;i<=MX;i++) { if(!b[i]) s[++num]=i,p[i]=Ran()*Ran()%ditoly,p2[i]=Ran()*Ran()%ditoly; for(int j=1;s[j]*i<=MX&&j<=num;j++) b[s[j]*i]=1; } ins(X,Y); for(int i=1;i<=n;i++) { int j=a[i]; for(int k=1;j>1&&s[k]<=1000;k++) while(j%s[k]==0) j/=s[k],X^=p[s[k]],Y^=p2[s[k]]; if(j>1) X^=p[j],Y^=p2[j]; ins(X,Y); } cout<<ans<<endl; return 0; }
C.给定一个n*m的棋盘，你在(x,y)，要走到棋盘的任意一个角。每次移动，你只能让横坐标变化a，纵坐标变化b，且不能到棋盘外，求最小的变化次数。
题解：大判断。
#include<iostream> #include<cstdio> #define INF 2000000000 using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } int ans=INF,n,m,x,y,a,b; int calc(int xx,int yy) { if((xx&1)!=(yy&1)) return INF; if(xx>yy&&y+b>m&&y-b<=0) return INF; if(yy>xx&&x+a>n&&x-a<=0) return INF; return max(xx,yy); } int main() { n=read();m=read();x=read();y=read();a=read();b=read(); if((x-1)%a==0&&(y-1)%b==0) ans=min(ans,calc((x-1)/a,(y-1)/b)); if((x-1)%a==0&&(m-y)%b==0) ans=min(ans,calc((x-1)/a,(m-y)/b)); if((n-x)%a==0&&(y-1)%b==0) ans=min(ans,calc((n-x)/a,(y-1)/b)); if((n-x)%a==0&&(m-y)%b==0) ans=min(ans,calc((n-x)/a,(m-y)/b)); if(ans<INF) printf("%d ",ans); else puts("Poor Inna and pony!"); return 0; }
D.给定一个由小写字母(长度<=100000)组成的字符串，支持两个操作 1）让一段字符后移t位 后移一位是指 a->b b->c z->a
2) 求一段字符有多少个子集可以组成完全平方数。
题解：考虑线段树维护字符串每种字符的出现次数，然后每次询问找出次数之后排列组合算答案。复杂度$O(26nlogn)$
#include<iostream> #include<cstdio> #include<cstring> #define MN 100000 #define ll long long #define mod 1000000007 using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } int n,q,qu[50],p[MN+5]; char st[MN+5]; struct data { int c[26]; data(){} data(int x){memset(c,0,sizeof(c));c[x]=1;} data operator+(const data&b) { data x; for(register int i=0;i<26;i++) x.c[i]=c[i]+b.c[i]; return x; } void change(int x) { for(register int i=0;i<26;i++) qu[(i+x)%26]=c[i]; for(register int i=0;i<26;i++) c[i]=qu[i]; } }; struct Tree{int l,r,val;data x;}T[MN*4+5]; void pushdown(int x) { int l=x<<1,r=x<<1|1; T[l].x.change(T[x].val); T[r].x.change(T[x].val); T[l].val=(T[l].val+T[x].val)%26;; T[r].val=(T[r].val+T[x].val)%26; T[x].val=0; } void build(int x,int l,int r) { if((T[x].l=l)==(T[x].r=r)) {T[x].x=data(st[l]-'a');return;} int mid=l+r>>1; build(x<<1,l,mid);build(x<<1|1,mid+1,r); T[x].x=T[x<<1].x+T[x<<1|1].x; } void renew(int x,int l,int r,int t) { if(T[x].l==l&&T[x].r==r){T[x].x.change(t);T[x].val=(T[x].val+t)%26;return;} if(T[x].val) pushdown(x); int mid=T[x].l+T[x].r>>1; if(r<=mid) renew(x<<1,l,r,t); else if(l>mid) renew(x<<1|1,l,r,t); else renew(x<<1,l,mid,t),renew(x<<1|1,mid+1,r,t); T[x].x=T[x<<1].x+T[x<<1|1].x; } data query(int x,int l,int r) { if(T[x].l==l&&T[x].r==r) return T[x].x; if(T[x].val) pushdown(x); int mid=T[x].l+T[x].r>>1; if(r<=mid)return query(x<<1,l,r); else if(l>mid)return query(x<<1|1,l,r); else return query(x<<1,l,mid)+query(x<<1|1,mid+1,r); } int pow(int x,int k) { int sum=1; for(int i=x;k;k>>=1,i=1LL*i*i%mod) if(k&1) sum=1LL*sum*i%mod; return sum; } int main() { n=read();q=read(); for(int i=1;i<=n;i++) p[i]=pow(2,i-1); scanf("%s",st+1);build(1,1,n); for(int i=1;i<=q;i++) { int op=read(),l=read()+1,r=read()+1; if(op==1) {int x=read()%26;if(x) renew(1,l,r,x);} else { data ans=query(1,l,r);int pa=1,sum=0; for(int i=0;i<26;i++)if(ans.c[i]) pa=1LL*pa*p[ans.c[i]]%mod; for(int i=0;i<26;i++) if(ans.c[i]) sum=(sum+1LL*pow(2,ans.c[i]-1)*pa%mod*pow(p[ans.c[i]],mod-2)%mod)%mod; sum=(sum+pa)%mod; printf("%d ",sum-1); } } return 0; }
E....... 求[a,b]里面有多少个数能被k整除。 a,b,k<=10^18
题解：.......瞎搞
#include<iostream> #include<cstdio> #include<cstring> #define ll long long #define LL (ll)5e18 using namespace std; inline ll read() { ll x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } ll k,a,b; int main() { k=read();a=read();b=read();a+=LL/k*k;b+=LL/k*k; ll bg=(a+k-1)/k,ed=b/k; printf("%lld ",ed-bg+1); return 0; }
F.一棵树，要求支持两种操作。 n<=100000 m<=100000 1)让一棵子树的所有点加上v+kd vk给定，d表示那个点和子树的根的深度差。
2)询问一条链上的权值和
有链操作和子树操作，考虑树剖。第一个操作我们可以通过线段树上打标记实现，所以这道题就做完啦。复杂度$O(nlog^{2}n)$
#include<iostream> #include<cstdio> #define mod 1000000007 #define Mod 10000000070000000LL #define INF 2000000000 #define MN 100000 #define ll long long using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } int n,m,rt,mx[MN+5],size[MN+5],head[MN+5],cnt=0,nl[MN+5],nr[MN+5],top[MN+5],fa[MN+5],dep[MN+5],dn=0,p[MN+5]; struct edge{int to,next;}e[MN*2+5]; struct TREE{int l,r;ll val,tag,x,d;}T[MN*4+5]; inline void ins(int f,int t) { e[++cnt]=(edge){t,head[f]};head[f]=cnt; e[++cnt]=(edge){f,head[t]};head[t]=cnt; } void dfs1(int x,int f) { fa[x]=f;size[x]=1;mx[x]=0; for(int i=head[x];i;i=e[i].next) if(e[i].to!=f) { dep[e[i].to]=dep[x]+1; dfs1(e[i].to,x); size[x]+=size[e[i].to]; if(size[e[i].to]>size[mx[x]]) mx[x]=e[i].to; } } void dfs2(int x,int tp) { top[x]=tp;nl[x]=++dn;p[dn]=x; if(mx[x]) dfs2(mx[x],tp); for(int i=head[x];i;i=e[i].next) if(e[i].to!=fa[x]&&e[i].to!=mx[x]) dfs2(e[i].to,e[i].to); nr[x]=dn; } void pushdown(int x) { int l=x<<1,r=x<<1|1; if(T[x].tag) { T[l].tag=(T[l].tag+T[x].tag)%mod; T[r].tag=(T[r].tag+T[x].tag)%mod; T[l].x=(T[l].x+1LL*(T[l].r-T[l].l+1)*T[x].tag)%mod; T[r].x=(T[r].x+1LL*(T[r].r-T[r].l+1)*T[x].tag)%mod; T[x].tag=0; } if(T[x].val) { T[l].val=(T[l].val+T[x].val)%mod; T[r].val=(T[r].val+T[x].val)%mod; T[l].x=(T[l].x+1LL*T[l].d*T[x].val+Mod)%mod; T[r].x=(T[r].x+1LL*T[r].d*T[x].val+Mod)%mod; T[x].val=0; } } void build(int x,int l,int r) { if((T[x].l=l)==(T[x].r=r)){T[x].d=dep[p[l]];return;} int mid=l+r>>1; build(x<<1,l,mid);build(x<<1|1,mid+1,r); T[x].d=(T[x<<1].d+T[x<<1|1].d)%mod; } void Renew(int x,int l,int r,int ad) { if(T[x].l==l&&T[x].r==r) { T[x].tag=(T[x].tag+ad)%mod; T[x].x=(T[x].x+1LL*(r-l+1)*ad)%mod; return; } if(T[x].val||T[x].tag) pushdown(x); int mid=T[x].l+T[x].r>>1; if(r<=mid) Renew(x<<1,l,r,ad); else if(l>mid) Renew(x<<1|1,l,r,ad); else Renew(x<<1,l,mid,ad),Renew(x<<1|1,mid+1,r,ad); T[x].x=(T[x<<1].x+T[x<<1|1].x)%mod; } void renew(int x,int l,int r,int ad) { if(T[x].l==l&&T[x].r==r) { T[x].val=(T[x].val+ad+Mod)%mod; T[x].x=(T[x].x+1LL*T[x].d*ad+Mod)%mod; return; } if(T[x].val||T[x].tag) pushdown(x); int mid=T[x].l+T[x].r>>1; if(r<=mid) renew(x<<1,l,r,ad); else if(l>mid) renew(x<<1|1,l,r,ad); else renew(x<<1,l,mid,ad),renew(x<<1|1,mid+1,r,ad); T[x].x=(T[x<<1].x+T[x<<1|1].x)%mod; } ll query(int x,int l,int r) { if(T[x].l==l&&T[x].r==r) return T[x].x; if(T[x].val||T[x].tag) pushdown(x); int mid=T[x].l+T[x].r>>1; if(r<=mid) return query(x<<1,l,r); else if(l>mid) return query(x<<1|1,l,r); else return (query(x<<1,l,mid)+query(x<<1|1,mid+1,r))%mod; } int Solve(int x,int y) { ll sum=0; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); sum=(sum+query(1,nl[top[x]],nl[x]))%mod; x=fa[top[x]]; } if(nl[x]>nl[y]) swap(x,y); sum=(sum+query(1,nl[x],nl[y]))%mod; return sum; } char op[5]; int main() { n=read();m=read();rt=read(); for(int i=1;i<n;i++) ins(read(),read()); dep[rt]=1;dfs1(rt,0);dfs2(rt,rt); build(1,1,n); for(int i=1;i<=m;i++) { scanf("%s",op+1); if(op[1]=='U') { int t=read(),v=read(),k=read(); Renew(1,nl[t],nr[t],(v-1LL*k*dep[t]+Mod)%mod); renew(1,nl[t],nr[t],k); } else { int x=read(),y=read(); printf("%d ",Solve(x,y)); } } return 0; }