好了做了SDOI day1的3道题，来讲下做法及感想吧
T1：排序（暴力，搜索）
题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3990
我们可以很轻易的发现，对于一个操作方案，交换两个操作顺序不会影响答案，因此我们可以从小到大枚举答案，可以发现，对于第i种操作过后，每个2^i的块必须是连续的
那么在第i种操作之前，最多只能有2个块不连续，那么如果没有块不连续，不用执行该种操作；只有一个块不连续，交换这个块的两小块；两个块分4种情况讨论，用dfs暴力搜索即可
时间复杂度看上去是O(4^N)，但好像可以证出复杂度其实是O(2^NlogN)N=20都能跑过
CODE：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 #define maxn 5000 7 int a[maxn],n,f[15]; 8 long long ans=0; 9 inline void _swap(int *a,int *b,int step) { 10 for (int i=1;i<=step;i++) swap(a[i],b[i]); 11 } 12 inline bool check(int x,int y) {return a[x+y]+1==a[x+y+1];} 13 int dfs(int x,int y) { 14 if (x==n+1) return ans+=f[y]; 15 int w[5],cnt=0; 16 int step=1<<(x-1); 17 for (int i=0;i<1<<n;i+=1<<x) { 18 if (!check(i,step)) w[++cnt]=i; 19 if (cnt>2) return 0; 20 } 21 if (cnt==0) dfs(x+1,y); 22 if (cnt==1) { 23 _swap(a+w[1],a+w[1]+step,step); 24 if (check(w[1],step)) dfs(x+1,y+1); 25 _swap(a+w[1],a+w[1]+step,step); 26 } 27 if (cnt==2) { 28 int *l1=a+w[1],*l2=a+w[2],*r1=a+w[1]+step,*r2=a+w[2]+step; 29 _swap(l1,l2,step); 30 if (check(w[1],step)&&check(w[2],step)) dfs(x+1,y+1); 31 _swap(l1,l2,step); 32 _swap(l1,r2,step); 33 if (check(w[1],step)&&check(w[2],step)) dfs(x+1,y+1); 34 _swap(l1,r2,step); 35 _swap(r1,l2,step); 36 if (check(w[1],step)&&check(w[2],step)) dfs(x+1,y+1); 37 _swap(r1,l2,step); 38 _swap(r1,r2,step); 39 if (check(w[1],step)&&check(w[2],step)) dfs(x+1,y+1); 40 _swap(r1,r2,step); 41 } 42 } 43 44 int main(){ 45 scanf("%d",&n); 46 f[0]=1; 47 for (int i=1;i<=n;i++) f[i]=f[i-1]*i; 48 for (int i=1;i<=(1<<n);i++) { 49 scanf("%d",a+i); 50 a[i]--; 51 } 52 dfs(1,0); 53 printf("%lld ",ans); 54 return 0; 55 }
T2：寻宝游戏（平衡树，dfn序）
题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3991
这道题真的想不出来啊= =
贴下同学的题解吧= =
大概就是这样子的，看上去还是非常的形象的，但我根本没想到啊QAQ
Code:
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<set> 6 #include<vector> 7 using namespace std; 8 typedef long long ll; 9 #define maxn 101000 10 #define maxk 23 11 struct edges{ 12 int to,next,dist; 13 }edge[maxn*2]; 14 int q[maxn],f[maxn][maxk],g[maxn],dfn[maxn]; 15 struct cmp{ 16 bool operator ()(int x,int y) {return dfn[x]<dfn[y];} 17 }; 18 set<int,cmp> ma; 19 int next[maxn],l; 20 inline void addedge(int x,int y,int z) { 21 edge[++l]=(edges){y,next[x],z};next[x]=l; 22 edge[++l]=(edges){x,next[y],z};next[y]=l; 23 } 24 int fa[maxn],dep[maxn],n,s[maxn]; 25 ll dis[maxn]; 26 inline void bfs(){ 27 q[1]=1; 28 for (int l=1,r=1,u=q[1];l<=r;u=q[++l]) { 29 f[u][0]=fa[u]; 30 for (int i=1;i<maxk;i++) { 31 if (f[f[u][i-1]][i-1]==0) break; 32 f[u][i]=f[f[u][i-1]][i-1]; 33 } 34 for (int i=next[u];i;i=edge[i].next) { 35 if (edge[i].to==fa[u]) continue; 36 fa[edge[i].to]=u;dis[edge[i].to]=dis[u]+edge[i].dist; 37 dep[edge[i].to]=dep[u]+1; 38 q[++r]=edge[i].to; 39 } 40 } 41 for (int i=n;i>1;i--) { 42 int u=q[i]; 43 s[u]++;s[fa[u]]+=s[u]; 44 } 45 s[1]++; 46 for (int i=1;i<=n;i++) { 47 int u=q[i]; 48 dfn[u]=g[fa[u]]+1; 49 g[fa[u]]+=s[u]; 50 g[u]=dfn[u]; 51 } 52 } 53 inline int up(int x,int y) { 54 for (int i=0;i<maxk;i++) if ((1<<i)&y) x=f[x][i]; 55 return x; 56 } 57 inline int lca(int x,int y) { 58 if (dep[x]<dep[y]) swap(x,y); 59 x=up(x,dep[x]-dep[y]); 60 if (x==y) return x; 61 for (int i=maxk-1;i+1;i--) { 62 if (f[x][i]==f[y][i]) continue; 63 x=f[x][i];y=f[y][i]; 64 } 65 return f[x][0]; 66 } 67 inline ll getdist(int x,int y) {return dis[x]+dis[y]-dis[lca(x,y)]*2;} 68 ll ans; 69 typedef set<int,cmp>::iterator iter; 70 inline void ins(int x) { 71 if (ma.size()==0) { 72 ma.insert(x);return ; 73 } 74 if (ma.size()==1) { 75 ans=getdist(x,*ma.begin()); 76 ma.insert(x); 77 return ; 78 } 79 iter it=ma.lower_bound(x); 80 iter last=it;it--; 81 if (last!=ma.end()&&last!=ma.begin()) ans-=getdist(*it,*last); 82 if (last!=ma.begin()) ans+=getdist(*it,x); 83 if (last!=ma.end()) ans+=getdist(x,*last); 84 ma.insert(x); 85 } 86 inline void del(int x){ 87 ma.erase(x); 88 if (ma.size()==0) return ; 89 if (ma.size()==1) { 90 ans=0;return ; 91 } 92 iter it=ma.lower_bound(x); 93 iter last=it;it--; 94 if (last!=ma.end()&&last!=ma.begin()) ans+=getdist(*it,*last); 95 if (last!=ma.begin()) ans-=getdist(*it,x); 96 if (last!=ma.end()) ans-=getdist(x,*last); 97 } 98 bool b[maxn]; 99 int main(){ 100 int m; 101 scanf("%d%d",&n,&m); 102 for (int i=1;i<n;i++) { 103 int x,y,z; 104 scanf("%d%d%d",&x,&y,&z); 105 addedge(x,y,z); 106 } 107 bfs(); 108 for (int i=1;i<=m;i++) { 109 int x; 110 scanf("%d",&x); 111 b[x]^=1; 112 if (b[x]) ins(x); 113 else del(x); 114 if (ma.size()>=2) printf("%lld ",ans+getdist(*ma.begin(),*ma.rbegin())); 115 else printf("0 "); 116 } 117 return 0; 118 }
题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3992
这道题分明就是原题好不好= =
首先我们可以很容易的写出状态转移f[i][[j*a[k]]+=f[i-1][j];
30%的分数可用矩阵乘法优化
我们取下离散对数（就是mod m意义下的），然后这个方程就变成了f[i][ind[j]+ind[a[k]]]+=sigma(f[i-1][ind[j]*cnt[inda[k]])
可以发现变成了卷积形式了，好像可以用fft优化了
但发现n很大
借鉴一下矩阵乘法的优化，可以发现多项式乘法满足结合律，那么我们可以愉快的学习快速幂的形式，变成f0*cnt^n次方了
时间复杂度是 mlogm logn完美解决本题
还有一件事，求离散对数可以不用大步小步法，因为p很小，可以直接p^2求出来
顺便提下原题是lydcjj(greenclouds)的kpmcup#1中的T1（ORZ），除了取离散对数其他都一模一样的
要不是做了MX的组合数和看过云神的题，还真不一定做得出来
总结一下：
作为省选题，还是很不错的
思考复杂度都不低（虽然有人说3道都是原题QAQ，自己还是太弱）但是编程复杂度并不高，前两道都能秒，第3道套个fft模板也能秒
还是这种考思维的比较好玩，像陈老师这种业界毒瘤的数据结构题真是丧心病狂(づ￣ 3￣)づ
Code:
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 typedef long long ll; 7 const int mod=1004535809; 8 #define maxn 80100 9 // template 10 inline int power(ll x,int y,int mod) { 11 ll t=1; 12 for (;y;y>>=1,(x*=x)%=mod) 13 if (y&1) (t*=x)%=mod; 14 return t; 15 } 16 int w[maxn]; 17 void fft(int *a,int n,int dep=0) { 18 if (n==1) return ; 19 static int tmp[maxn]; 20 int mid=n>>1; 21 fft(a,mid,dep+1);fft(a+(1<<dep),mid,dep+1); 22 for (int i=0;i<mid;i++) { 23 int s=a[(i<<1)<<dep]; 24 int t=a[(i<<1|1)<<dep]*1ll*w[i<<dep]%mod; 25 tmp[i]=(s+t)%mod; 26 tmp[i+mid]=(s-t)%mod; 27 } 28 for (int i=0;i<n;i++) a[i<<dep]=tmp[i]; 29 } 30 int fft_g=3; 31 int N; 32 inline void fft_init(){ 33 w[0]=1; 34 int step=power(fft_g,(mod-1)/N,mod); 35 for (int i=0;i<N-1;i++) w[i+1]=w[i]*1ll*step%mod; 36 } 37 int p; 38 bool isroot(int x) { 39 int sum=1; 40 for (int i=1;i<p-1;i++) { 41 (sum*=x)%=p; 42 if (sum==1) return 0; 43 } 44 return 1; 45 } 46 int n,X,S; 47 int ind[maxn]; 48 int f[maxn],g[maxn],invN; 49 inline void prepare(){ 50 scanf("%d%d%d%d",&n,&p,&X,&S); 51 int root=0; 52 for (int i=1;i<p&&!root;i++) if (isroot(i)) root=i; 53 54 for (int i=0,j=1;i<p-1;i++,(j*=root)%=p) ind[j]=i; 55 for (int i=1;i<=S;i++) { 56 int x; 57 scanf("%d",&x); 58 if (x) g[ind[x]]=1; 59 } 60 N=p<<1; 61 while (N&(N-1)) N++; 62 invN=power(N,mod-2,mod); 63 fft_init(); 64 } 65 inline void muil(int *x,int *g){ 66 static int y[maxn]; 67 for (int i=0;i<N;i++) y[i]=g[i]; 68 fft(x,N),fft(y,N); 69 for (int i=0;i<N;i++) x[i]=x[i]*1ll*y[i]%mod; 70 reverse(w+1,w+N); 71 fft(x,N); 72 reverse(w+1,w+N); 73 for (int i=0;i<N;i++) x[i]=x[i]*1ll*invN%mod; 74 for (int i=p-1;i<N;i++) (x[i%(p-1)]+=x[i])%=mod,x[i]=0; 75 } 76 inline int solve(){ 77 f[0]=1; 78 for (;n;n>>=1) { 79 if (n&1) muil(f,g); 80 muil(g,g); 81 } 82 return (f[ind[X]]+mod)%mod; 83 } 84 int main(){ 85 prepare(); 86 printf("%d ",solve()); 87 return 0; 88 }