2015-10-08 19:14:54
总结：赛后补的一场。题目蛮有意思的。
A：DFS
思路：搜一下几个环然后判断一下即可。
#include <cstdio> #include <ctime> #include <cstring> #include <cstdlib> #include <cmath> #include <vector> #include <map> #include <set> #include <stack> #include <queue> #include <string> #include <iostream> #include <algorithm> using namespace std; #define getmid(l,r) ((l) + ((r) - (l)) / 2) #define MEM(a,b) memset(a,b,sizeof(a)) #define MP(a,b) make_pair(a,b) #define PB push_back typedef long long ll; typedef pair<int,int> pii; const double eps = 1e-8; const int INF = (1 << 30) - 1; const int MAXN = 100010; int T; int n,ans,cnt; int A[MAXN],B[MAXN],pos[MAXN]; int vis[MAXN]; void Dfs(int p){ if(vis[p]) return; cnt++; vis[p] = 1; Dfs(pos[p]); } int main(){ scanf("%d",&T); while(T--){ MEM(vis,0); scanf("%d",&n); for(int i = 1; i <= n; ++i) scanf("%d",A + i); for(int i = 1; i <= n; ++i){ int a; scanf("%d",&a); B[A[i]] = a; pos[a] = A[i]; } ans = 0; for(int i = 1; i <= n; ++i) if(vis[i] == 0){ cnt = 0; Dfs(i); if(cnt == 1) ans++; else ans += cnt - 1; } printf("%d\n",ans); } return 0; }
B：DP
题意：给出n个数，算出所有子序列去掉连续相同数（只保留一个）后的总和。
思路：总的思路就是总数 - 重复的计数。我们可以枚举每个数，算出其贡献，比如对于第i个数vi。先算左边的数，可取可不取，但是与vi相同的数一定不取，方案数为L，同理算出右边的方案数（算右边时可以取与vi相同的数），那么贡献就是vi×L×R。
#include <cstdio> #include <ctime> #include <cstring> #include <cstdlib> #include <cmath> #include <vector> #include <map> #include <set> #include <stack> #include <queue> #include <string> #include <iostream> #include <algorithm> using namespace std; #define getmid(l,r) ((l) + ((r) - (l)) / 2) #define MEM(a,b) memset(a,b,sizeof(a)) #define MP(a,b) make_pair(a,b) #define PB push_back typedef long long ll; typedef pair<int,int> pii; const double eps = 1e-8; const int INF = (1 << 30) - 1; const int MAXN = 100010; const ll mod = 1e9 + 7; int T; int n,A[MAXN]; ll pw[MAXN],pre[MAXN],val[MAXN]; map<int,ll> S1; int main(){ pw[0] = pre[0] = 1; for(int i = 1; i <= 100000; ++i){ pw[i] = pw[i - 1] * 2LL % mod; pre[i] = (pre[i - 1] + pw[i]) % mod; } scanf("%d",&T); while(T--){ S1.clear(); scanf("%d",&n); for(int i = 1; i <= n; ++i) scanf("%d",A + i); for(int i = 1; i <= n; ++i){ if(i == 1) val[i] = 1; else val[i] = (1 + pre[i - 2] - S1[A[i]]) % mod; val[i] = (val[i] + mod) % mod; S1[A[i]] += pw[i - 1]; } for(int i = n - 1; i >= 1; --i){ val[i] = (val[i] * (1 + pre[n - i - 1])) % mod; } ll ans = 0; for(int i = 1; i <= n; ++i){ ans = (ans + A[i] * val[i] % mod) % mod; } printf("%lld\n",ans); } return 0; }
C：树状数组
题意：n个数删除连续的m个数，算出最小逆序数。
思路：用两个树状数组模拟一个删除框即可。
#include <cstdio> #include <ctime> #include <cstring> #include <cstdlib> #include <cmath> #include <vector> #include <map> #include <set> #include <stack> #include <queue> #include <string> #include <iostream> #include <algorithm> using namespace std; #define getmid(l,r) ((l) + ((r) - (l)) / 2) #define MEM(a,b) memset(a,b,sizeof(a)) #define MP(a,b) make_pair(a,b) #define PB push_back typedef long long ll; typedef pair<int,int> pii; const double eps = 1e-8; const int INF = (1 << 30) - 1; const int MAXN = 100010; int T,n,m; int A[MAXN],fk[2][MAXN]; void Update(int id,int x,int d){ while(x <= n){ fk[id][x] += d; x += x & (-x); } } int Getsum(int id,int x){ int res = 0; while(x){ res += fk[id][x]; x -= x & (-x); } return res; } int main(){ scanf("%d",&T); while(T--){ MEM(fk,0); scanf("%d%d",&n,&m); for(int i = 1; i <= n; ++i) scanf("%d",A + i); ll inv = 0; for(int i = m + 1; i <= n; ++i){ inv += (i - m - 1) - Getsum(1,A[i]); Update(1,A[i],1); } ll ans = inv; // fk0 : pre , fk1 : suf for(int i = 1; i + m <= n; ++i){ inv -= (i - 1) - Getsum(0,A[i + m]); inv -= Getsum(1,A[i + m] - 1); Update(1,A[i + m],-1); inv += (i - 1) - Getsum(0,A[i]); inv += Getsum(1,A[i] - 1); Update(0,A[i],1); ans = min(ans,inv); } printf("%lld\n",ans); } return 0; }
D：DP+矩阵快速幂+生成树计数
思路：q轮选出n-1条边（构成一棵树）的方案数为cnt。对于每个生成树，构成其的方案数都是cnt。用dp[i][j]表示i轮选了j种边的方案数，转移方程：dp[i][j] = dp[i - 1][j - 1] * (n - j) + dp[i - 1][j] * j 用矩阵快速幂算出cnt。下面就是生成树计数，算出生成树种类num，那么答案就是cnt × num。
#include <cstdio> #include <ctime> #include <cstring> #include <cstdlib> #include <cmath> #include <vector> #include <map> #include <set> #include <stack> #include <queue> #include <string> #include <iostream> #include <algorithm> using namespace std; #define getmid(l,r) ((l) + ((r) - (l)) / 2) #define MEM(a,b) memset(a,b,sizeof(a)) #define MP(a,b) make_pair(a,b) #define PB push_back typedef long long ll; typedef pair<int,int> pii; const double eps = 1e-8; const int INF = (1 << 30) - 1; const int MAXN = 110; int T,n,m,p,q,mod; int D[MAXN][MAXN],G[MAXN][MAXN]; ll Det(int n){ ll A[MAXN][MAXN]; for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) A[i][j] = D[i][j]; ll res = 1; for(int i = 1; i <= n; ++i){ for(int j = i + 1; j <= n; ++j){ while(A[j][i]){ ll t = A[i][i] / A[j][i]; for(int k = i; k <= n; ++k) A[i][k] = (A[i][k] - A[j][k] * t) % mod; for(int k = i; k <= n; ++k) swap(A[i][k],A[j][k]); res = -res; } } if(!A[i][i]) return 0; res = res * A[i][i] % mod; } return (res + mod) % mod; } struct Mx{ ll a[MAXN][MAXN]; void clear(){ MEM(a,0); } void stand(){ clear(); for(int i = 1; i <= n; ++i) a[i][i] = 1; } Mx operator * (const Mx &b){ Mx c; c.clear(); for(int k = 1; k <= n; ++k) for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j){ c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j]) % mod; } return c; } }; Mx t; Mx Q_pow(int v){ Mx res; res.stand(); while(v){ if(v & 1) res = res * t; t = t * t; v >>= 1; } return res; } int main(){ scanf("%d",&T); while(T--){ MEM(D,0); MEM(G,0); scanf("%d%d%d%d",&n,&m,&p,&q); mod = p; for(int i = 1; i <= m; ++i){ int a,b; scanf("%d%d",&a,&b); D[a][a]++; D[b][b]++; G[a][b] = G[b][a] = 1; } for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) D[i][j] -= G[i][j]; ll val = Det(n - 1); //structure Mx t t.clear(); for(int i = 1; i <= n; ++i){ t.a[i][i] = i; t.a[i][i - 1] = n - i; } Mx ans; ans.clear(); ans.a[1][1] = n - 1; ans = Q_pow(q - 1) * ans; printf("%lld\n",(val * ans.a[n - 1][1]) % mod); } return 0; }
原文：http://www.cnblogs.com/naturepengchen/p/4862132.html
