woc day2T1太难辣。。
弃坑了。。。想看D2T1的去吉利blog
兔子与樱花：
贪心，肯定从深度大的先合并，这样影响少，然后每个点选最小的儿子。。（口胡不会证）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | #include<algorithm>#include <iostream>#include <string.h>#include <stdlib.h>#include <stdio.h>#include <math.h>#include <time.h>#include <vector>#include <queue>#include <map>#include <set>using namespace std;const int N=2000005;vector<int> Son[N];int n,m,d[N],Ans,val[N];void dfs(int u){ for(int i=0;i<Son[u].size();i++) dfs(Son[u][i]), Son[u][i]=val[Son[u][i]]; sort(Son[u].begin(),Son[u].end()); for(int i=0;i<Son[u].size();i++) if(val[u]+Son[u][i]-1<=m) val[u]+=Son[u][i]-1, Ans++; else return;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&val[i]); for(int u,i=1,k;i<=n;i++) { scanf("%d",&k); val[i]+=k; while(k--) scanf("%d",&u), Son[i].push_back(++u), d[u]=1; } for(int i=1;i<=n;i++) if(!d[i]) dfs(i); cout<<Ans<<endl; return 0;} |
公约数数列：
我会分块我自豪！每块建个hash表，查询如果这段gcd都相同就在hash表里找，否则就暴力，显然gcd只会有log种，最多log次，时间复杂度q∗n0.5log2n跑的还很快shenmegui啊。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 | #include<algorithm>#include <iostream>#include <string.h>#include <stdlib.h>#include <stdio.h>#include <math.h>#include <time.h>#include <vector>#include <queue>#include <map>#include <set>using namespace std;typedef long long LL;const int N=100005,Mod=357;int gcd(int a,int b){ return b?gcd(b,a%b):a;}struct H_SH{ int tot,num[Mod],G[Mod],next[Mod]; void clear() { tot=0; memset(G,0,sizeof(G)); } bool operator[](int x) { int k=x%Mod; for(int i=G[k];i;i=next[i]) if(num[i]==x) return 1; return 0; } void insert(int x) { if((*this)[x]) return; int k=x%Mod; num[++tot]=x;next[tot]=G[k];G[k]=tot; }}H[Mod];int Lzz[N],_xor[N],_gcd[N],Ed[Mod],n,q,flag,Ans,sz,K;LL x;void build(int t){ int l=Ed[t-1]+1,r=Ed[t]; H[t].clear(); H[t].insert(_xor[l]=_gcd[l]=Lzz[l]); for(int i=l+1;i<=r;i++) _gcd[i]=gcd(_gcd[i-1],Lzz[i]), H[t].insert(_xor[i]=_xor[i-1]^Lzz[i]);}void find(int t,int Lxor,int Lg){ int l=Ed[t-1]+1,r=Ed[t]; for(int i=l;i<=r;i++) if((_xor[i]^Lxor)*(LL)gcd(Lg,_gcd[i])==x) { flag=1; Ans=i; return; }}void solve(){ flag=0; int Lxor=0,Lg=0; for(int i=1;i<=K;i++) { int g=gcd(Lg,_gcd[Ed[i]]); if(g!=Lg) { find(i,Lxor,Lg); if(flag) break; } else if(x%g==0&&((x/g)^Lxor)<=2000000000&&H[i][(x/g)^Lxor]) { find(i,Lxor,Lg); break; } Lxor^=_xor[Ed[i]]; Lg=g; } if(flag) printf("%d\n",Ans-1); else puts("no");}int main(){ scanf("%d",&n); sz=sqrt(n)+1; K=(n-1)/sz+1; for(int i=1;i<=n;i++) scanf("%d",Lzz+i); for(int i=1;i<=K;i++) Ed[i]=min(Ed[i-1]+sz,n), build(i); scanf("%d",&q); while(q--) { char s[10]; scanf("%s",s); if(s[0]=='M') { int x,y; scanf("%d%d",&x,&y); Lzz[++x]=y; build((x-1)/sz+1); } else scanf("%lld",&x), solve(); } return 0;} |
定价：
枚举末尾0个数，算下就好
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | #include<algorithm>#include <iostream>#include <string.h>#include <stdlib.h>#include <stdio.h>#include <math.h>#include <time.h>#include <vector>#include <queue>#include <map>#include <set>using namespace std; typedef long long LL; LL Ans,Num; LL work(LL k){ while(k%10==0) k/=10; LL w=-(k%10==5); while(k) k/=10,w+=2; return w;} void Update(LL k){ LL w=work(k); if(w<Num||(w==Num&&k<Ans)) Ans=k,Num=w;} int main(){ LL t,l,r; scanf("%lld",&t); while(t--) { scanf("%lld%lld",&l,&r); Ans=l;Num=work(l); for(LL w=1;w<=r;w*=10) { LL k=l/(w*10)*(w*10); while(k<l) k+=w*10; if(k<=r) Update(k); k=l/(w*10)*(w*10)+w*5; while(k<l) k+=w*10; if(k<=r) Update(k); } cout<<Ans<<endl; } return 0;} |
小Z的房间：
Matrix−tree定理裸上
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | #include<algorithm>#include <iostream>#include <string.h>#include <stdlib.h>#include <stdio.h>#include <math.h>#include <time.h>#include <vector>#include <queue>#include <map>#include <set>using namespace std; typedef long long LL; const int N=15,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1},Mod=1000000000; int d[N*N][N*N],id[20][20],n,m,k; #define Pr pair<int,int>#define x first#define y second Pr operator-(const Pr& A,const Pr& B){ return Pr((A.x-B.x+Mod)%Mod,(A.y-B.y+Mod)%Mod);} Pr operator*(const Pr& A,const int& B){ return Pr(A.x*(LL)B%Mod,A.y*(LL)B%Mod);} int Gauss(int n){ int flag=1; for(int i=1;i<=n;i++) { int p; for(p=i;p<=n;p++) if(d[p][i]) break; if(p!=i) { flag=-flag; for(int j=i;j<=n;j++) swap(d[i][j],d[p][j]); } for(int j=i+1;j<=n;j++) { int Lzz=d[i][i],ZZl=d[j][i]; Pr A=Pr(1,0),B=Pr(0,1); while(ZZl) swap(A,B), B=B-A*(Lzz/ZZl), swap(Lzz,ZZl), ZZl%=Lzz, flag=-flag; for (int k=i;k<=n;k++) { int Yjc=d[i][k],Cjy=d[j][k]; d[i][k]=((LL)A.x*Yjc+(LL)A.y*Cjy)%Mod; d[j][k]=((LL)B.x*Yjc+(LL)B.y*Cjy)%Mod; } } } int S=flag; for(int i=1;i<=n;i++) S=S*(LL)d[i][i]%Mod; return (S+Mod)%Mod;} int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { char s[15]; scanf("%s",s+1); for(int j=1;j<=m;j++) if(s[j]=='.') id[i][j]=++k; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(id[i][j]) for(int k=0;k<4;k++) { int x=i+dx[k],y=j+dy[k]; if(id[x][y]) d[id[i][j]][id[i][j]]++, d[id[i][j]][id[x][y]]--; } cout<<Gauss(k-1)<<endl; return 0;} |
最短不公共子串：
出题人和yjc一样啊。。。。bfs4合1！如果要求B是子串就用后缀自动机，要求B是子序列就是一个记录suc[a][b]表示a后第一个字符b的位置的东西
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 | #include<algorithm>#include <iostream>#include <string.h>#include <stdlib.h>#include <stdio.h>#include <math.h>#include <time.h>#include <vector>#include <queue>#include <map>#include <set>using namespace std; const int N=2005; namespace SAM{ int Son[N*2][26],pre[N*2],len[N*2],last=1,now=1; void Extend(int x) { int p=last,np=last=++now; len[np]=len[p]+1; for(;p&&!Son[p][x];p=pre[p]) Son[p][x]=np; if(!p) pre[np]=1; else { int q=Son[p][x]; if(len[q]==len[p]+1) pre[np]=q; else { int nq=++now; memcpy(Son[nq],Son[q],sizeof Son[nq]); len[nq]=len[p]+1; pre[nq]=pre[q]; pre[q]=pre[np]=nq; for(;p&&Son[p][x]==q;p=pre[p]) Son[p][x]=nq; } } }} int sucA[N][26],sucB[N][26],n,m,vis[N][N*2]; char A[N],B[N]; struct Lzz{ int x,y,l; Lzz(int a=0,int b=0,int l=0):x(a),y(b),l(l){}}; int OrzLzz1(){ queue<Lzz> Orz; for(int i=0;i<n;i++) Orz.push(Lzz(i,1,0)); while(!Orz.empty()) { Lzz w=Orz.front(); Orz.pop(); if(w.x==n) continue; int next=SAM::Son[w.y][A[w.x+1]-'a']; if(!next) return w.l+1; if(vis[w.x+1][next]!=1) vis[w.x+1][next]=1, Orz.push(Lzz(w.x+1,next,w.l+1)); } return -1;} int OrzLzz2(){ queue<Lzz> Orz; for(int i=0;i<n;i++) Orz.push(Lzz(i,0,0)); while(!Orz.empty()) { Lzz w=Orz.front(); Orz.pop(); if(w.x==n) continue; int next=sucB[w.y][A[w.x+1]-'a']; if(!next) return w.l+1; if(vis[w.x+1][next]!=2) vis[w.x+1][next]=2, Orz.push(Lzz(w.x+1,next,w.l+1)); } return -1;} int OrzLzz3(){ queue<Lzz> Orz; Orz.push(Lzz(0,1,0)); while(!Orz.empty()) { Lzz w=Orz.front(); Orz.pop(); for(int i=0;i<26;i++) { int nextx=sucA[w.x][i],nexty=SAM::Son[w.y][i]; if(!nextx) continue; if(!nexty) return w.l+1; if(vis[nextx][nexty]!=3) vis[nextx][nexty]=3, Orz.push(Lzz(nextx,nexty,w.l+1)); } } return -1;} int OrzLzz4(){ queue<Lzz> Orz; Orz.push(Lzz(0,0,0)); while(!Orz.empty()) { Lzz w=Orz.front(); Orz.pop(); for(int i=0;i<26;i++) { int nextx=sucA[w.x][i],nexty=sucB[w.y][i]; if(!nextx) continue; if(!nexty) return w.l+1; if(vis[nextx][nexty]!=4) vis[nextx][nexty]=4, Orz.push(Lzz(nextx,nexty,w.l+1)); } } return -1;} int main(){ gets(A+1); n=strlen(A+1); gets(B+1); m=strlen(B+1); for(int i=1;i<=m;i++) SAM::Extend(B[i]-'a'); for(int i=n-1;~i;i--) memcpy(sucA[i],sucA[i+1],sizeof sucA[i]), sucA[i][A[i+1]-'a']=i+1; for(int i=m-1;~i;i--) memcpy(sucB[i],sucB[i+1],sizeof sucB[i]), sucB[i][B[i+1]-'a']=i+1; printf("%d\n%d\n%d\n%d\n",OrzLzz1(),OrzLzz2(),OrzLzz3(),OrzLzz4()); return 0;} |
评论 (0)
