2008年成都网络赛训练总结
本次训练赛由我、DTen和sssplk完成，三台机子同时进行。
本次训练我们发挥得并不好，只A了一题，但是第一题是很快的1A.然后我就开始卡题，4个小时半卡在B题-矩阵乘法，而DTen则对剩下的题目不知所措，sssplk负责几何也对那道几何无可奈何。这场比赛我能做的题比较多，但是因为坑爹的杭电只提供十分渺小的系统栈，导致我的矩阵二分时递归RE,，然后找各种模板来取代递归版，咳，都是RE.
赛后我一共A了7道题，一道几何比较简单但没去敲，现在说下这场比赛的题目：
A、Stars 水题。因为是正方形，那么枚举两点，如果它们同线，另外两点的坐标也确定了。用hash来存坐标，然后直接判定那两点是否存在就好，秒杀之。
B、Word Game 矩阵乘法，给定n个串，当某串的末尾字符等于其他串的首字符时表示他们可以相连，用这些串可以组成一个表示是否能相连的矩阵，也是一个有向图。然后问走不大于n步并且步数为奇数后是目标T串的总方法数。设矩阵是A,那么我们求的就是A^1 + A^3 + ...A^n，再转换变成A1+A1 *( (A^2)^1 + (A^2)^2...(A^2)^k)，然后跑矩阵乘法n…n^3log（k）的复杂度解决。杭电改版后系统栈特别小，这题不能用递归式算法，并未那个k特别大。详细解题报告见Here.
C、Beans 很多方法都可以过，我用单调队列做。有n坨豌豆，每坨都有w[i]个，现在要从中选择连续的若干坨，然后用一个能装p个豌豆的背包装豆子，直到剩下的豌豆数量<=p为止，还要求剩下的豌豆数量少于k，问最多能装多少包。那么选择连续的一段和为sum，使得max(sum/p) 且sum%p<=k，这个sum可以用sum[i] - sum[j]来表示，那么确定了i，就是找最小的j使得(sum[i] - sum[j]) % p <= k,这时和最大。将每个和对p取余得到一个余数r数组，然后按余数大小优先位置其次的顺序排序。排完序之后就可以根据ri - k <= rj <= ri来往前找那个最小的j。遍历数组r，因为r是有序的，我用单调队列储存r小于当前的最小下标。详细解题报告见Here
D、Counting Problem 很难转换模型，但是转换后就是水题，训练没做出来，智商是硬伤啊。每次固定左上方边长为n-2，n-3...n-k的子正方形(n-k >= k)，剩下边长为2,3....k的子正方形随意放，设答案是dp[n]，dp[n] = dp[n-2] + dp[n-3] +..dp[n-k] (n-k<=k).这式子看起来不好写，但实际上用两个for循环就可以，第一位表示这个k，然后每次都加上dp[j-i]。具体见代码。
E、Farey Sequence Again 数论。第一次听到这种法雷级数，算见了市面。因为k<n这个条件的约束使得本题特别简单，因为小于n个的话分子要么是1，要么是2，要么是3，为什么，打表打几个看下然后YY即可得。得到上面的yy结论后，用O（1）的复杂度判断到底第k个法雷级数分子是1还是2还是3，n个可以分成1/2，1/3，以及剩下来的，1/2并不是严格的，而是(1+n) / 2,1/3是（n+2）/3，也就是上取整。第1部分分子是1，第2部分分子是2，第3部分比较难想，有1有2有3，那么将分子搞成6的话分母又是连续的，每6个连续的分母里面有2个是和6互质，那么就有4个分母可以进行约分。这样就找第几个4以及判断是4个中的第几个即可。
F、Travel 很好的搜索题。给定n个点m条边的无向连通图，Sum表示每个点到其他所有点的最小距离和，问我们删去某条边之后的Sum。朴素做法是枚举每条边，然后进行n次BFS，复杂度是O（n*m^2)。这个复杂度太高了，我们为了降低复杂度把枚举边转换成和点相关的操作，那么复杂度就有可能是O(n^2*m)，这样就应该能过。我们先预处理，做n次BFS,把每个点到其他所有点的最短距离求出来，并求出都经过哪些边，叫它关键边，如果某条边是这点的关键边，那么就要更新一次，再做一次BFS,否则直接用之前预处理求出的Sum即可。本题很值得学习的是这个预处理，我觉得和炮兵阵地的预处理一样漂亮，极大地降低了复杂度。
J、Jerboas 拓朴排序+DP,好题。给定一个n个点m条边的有向无环图，每个点表示一个洞，洞有临时和永久之分，从临时洞开始找一个永久洞结束，要求距离为k的倍数并要求距离最小。也就是说我们要找一个点，他的距离对k取模余数为0并且除数最小，这样到每个点最多1000种状态，我们设个Dp[i][j]，表示到i点状态j时对k的最小除数dp[i][j]*k+j就是最小距离。这样状态转移方程就是: Dp[next][j+(j+len)%k] = min(Dp[next][j+(j+len)%k],Dp[i][j]+(j+len)/k）（i有边连向next，边权为len),复杂度是O(n*m)
本次训练状态确实不好，很多题目并不难，看到那些约束条件就可以轻松地转换模型，然后就可以做了。卡题卡得死死的，悲剧了...下不为例，一题最多卡1个半小时。
这次比赛还是学到挺多东西，比如法雷级数，比如当复杂度过高时考虑预处理，比如枚举某个变量复杂度过高时考虑枚举另一个变量，还有J题我也很喜欢，喜欢那种表示状态的方式。
最后给源代码。后面的三题过几天再做，网络流没学，模拟题又巨恶心。
A ：
#include <stdio.h>#include <string.h>#include <map>#include <stack>#include <vector>#include <queue>#include <algorithm>using namespace std;#define MAX 1200struct node { int x,y;}arr[MAX];int n,m,ans,cnt;bool vis[MAX*2][MAX*2];map<int,int> hash;int cmp(node a,node b) { if (a.x == b.x) return a.y > b.y; else return a.x > b.x;}int main(){ int i,j,k,t; scanf("%d",&t); while (t--) { scanf("%d",&n); ans = cnt = 0; hash.clear(); memset(vis,false,sizeof(vis)); for (i = 1; i <= n; ++i) { scanf("%d%d",&arr[i].x,&arr[i].y); //hash[arr[i]] = ++cnt; if (hash.find(arr[i].x) == hash.end()) hash[arr[i].x] = ++cnt; if (hash.find(arr[i].y) == hash.end()) hash[arr[i].y] = ++cnt; vis[hash[arr[i].x]][hash[arr[i].y]] = true; } sort(arr+1,arr+1+n,cmp); for (i = 1; i <= n; ++i) for (j = i + 1; j <= n; ++j) if (arr[i].x == arr[j].x){ int len = arr[i].y - arr[j].y; len = abs(len); node cur; cur.x = arr[i].x + len; cur.y = arr[i].y; if (hash.find(cur.x) != hash.end() && hash.find(cur.y) != hash.end()) { if (vis[hash[cur.x]][hash[cur.y]] == 0) continue; cur.x = arr[j].x + len; cur.y = arr[j].y; if (hash.find(cur.x) != hash.end() && hash.find(cur.y) != hash.end()) if (vis[hash[cur.x]][hash[cur.y]] == 1) ans++; } } printf("%d\n",ans); }}B：
#pragma comment(linker, "/STACK:1024000000,1024000000")#include <stdio.h>#include <string.h>#define MAX 100#define MOD 10001#define int64 int//long long//__int64int n, begin, end;int64 m,final[MAX][MAX];char str[MAX][MAX],tp[MAX];struct Mat { int mat[MAX][MAX], size; Mat() {size = MAX;}; Mat(int n) { size = n; memset(mat, 0, sizeof (mat)); } friend Mat operator *(Mat a, Mat b); friend Mat operator +(Mat a, Mat b); friend Mat operator ^(Mat a, int64 k);} E;Mat operator *(Mat a, Mat b) { Mat c; c.size = a.size; memset(c.mat, 0, sizeof (c.mat)); for (int i = 0; i < c.size; ++i) for (int j = 0; j < c.size; ++j) for (int k = 0; k < c.size; ++k) if (a.mat[i][k] && b.mat[k][j]) c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % MOD; return c;}Mat operator +(Mat a, Mat b) { Mat c; c.size = 2 * n; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) c.mat[i][j] = (a.mat[i][j] + b.mat[i][j]) % MOD; return c;}Mat operator ^(Mat a, int64 k) { Mat c = E; c.size = a.size; while (k) { if (k & 1) c = c * a; a = a * a, k >>= 1; } return c;}Mat sum1(Mat A,int k) {//空间复杂度为O（n*n),时间复杂度为O（log（k）*n^3）if (k == 1) return A;if (k & 1) return sum1(A,k-1) + (A^k);return sum1(A,k/2) * ((A^(k / 2)) + E);}Mat sum2(Mat A, int64 k) { int i,j; Mat c = A; c.size = 2 * A.size; for (i = 0; i < n; ++i) c.mat[i][i+n] = c.mat[i+n][i+n] = 1; c = c^(k+1); Mat temp; temp.size = n; for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) temp.mat[i][j] = (i==j?c.mat[i][j+n]-1:c.mat[i][j+n]); return temp;}int Solve() { int i, j; Mat c; E.size = c.size = n; memset(c.mat, 0, sizeof (c.mat)); memset(E.mat, 0, sizeof (E.mat)); for (i = 0; i < 2 * n; ++i) E.mat[i][i] = 1; for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) if (str[i][strlen(str[i]) - 1] == str[j][0]) c.mat[i][j] = 1; if (m % 2 == 0) m--; int cnt = (m - 1) / 2; Mat c2 = c * c; int ans = 0; c = c + c * sum2(c2,cnt); ans = (ans + c.mat[begin][end]) % MOD; return ans;}int main(){ int i, j, k,t; scanf("%d", &t); while (t--) { scanf("%d", &n); for (i = 0; i < n; ++i) scanf("%s",str[i]); scanf("%s",tp); for (i = 0; i < n; ++i) if (strcmp(tp,str[i]) == 0) begin = i; scanf("%s",tp); for (i = 0; i < n; ++i) if (strcmp(tp,str[i]) == 0) end = i; scanf("%d",&m); int ans = Solve(); printf("%d\n",ans%MOD); }}C：
#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;#define MAX 1000010#define max(a,b) (a)>(b)?(a):(b)struct node { int x,in;}r[MAX];int sum[MAX],mmin[MAX];int n,p,k,ans,hash[MAX];int cmp(node a,node b) { if (a.x == b.x) return a.in > b.in; else return a.x < b.x;}int main(){ int i,j,t; int cas = 0,mmin; scanf("%d",&t); while (t--) { scanf("%d%d%d",&n,&p,&k); for (i = 1; i <= n; ++i) { scanf("%d",&sum[i]); r[i].in = i; sum[i] += sum[i-1]; r[i].x = sum[i] % p + k; } sort(r+1,r+1+n,cmp); //for (i = 1; i <= n; ++i) // printf("%d in = %d\n",r[i].x,r[i].in); mmin = n + 1; for (i = n; i >= 1; --i) { hash[r[i].in] = i; int temp = r[i].in; r[i].in = mmin; if (temp < mmin) mmin = temp; } //for (i = 1; i <= n; ++i) //printf("i = %d r[i] = %d\n",i,r[i].in); ans = -1; for (i = 1; i <= n; ++i) { int index = r[hash[i]].in; if (sum[i] % p <= k) ans = max(ans,sum[i] / p); if (r[index].in < i) ans = max(ans,(sum[i] - sum[r[index].in])/ p); //printf("i = %d ans = %d\n",i,ans); } printf("Case %d: %d\n",++cas,ans); }}
D：
#include <stdio.h>#include <string.h>#define MAX 510#define MOD 1000007int main(){ int i,j,k,n,t; int dp[MAX] = {0}; dp[0] = 1; for (i = 2; i < MAX; ++i) for (j = i; j < MAX; ++j) dp[j] = (dp[j] + dp[j-i]) % MOD; scanf("%d",&t); while (t--) { scanf("%d",&n); printf("%d\n",dp[n]); }}E：
#include <stdio.h>#include <string.h>int Gcd(int x,int y) { int r = x % y; while (r) { x = y,y = r; r = x % y; } return y;}int main(){ int i,j,k,t; int n,rest,bigest; scanf("%d",&t); while (t--) { scanf("%d%d",&n,&k); rest = (n + 1) / 2;//上取整 if (k <= rest) { //前半部分，分子为1，分母递减 printf("1/%d\n",n-k+1); continue; } k = k - rest; rest = (n + 2) / 3; if (k <= rest) { //中间部分，分子为2，分母递减 j = Gcd(2,n-k+1); printf("%d/%d\n",2/j,(n-k+1)/j); continue; } k = k - rest; rest = (k - 1) % 4 + 1; bigest = n * 2 - (k - 1) / 4 * 6; while (1) { j = Gcd(6,bigest); if (j == 1) { //最大公约数为1，不是法雷级数 bigest--; continue; } else if (rest == 1) { //最后一个法雷级数 printf("%d/%d\n",6/j,bigest/j); break; } bigest--,rest--; } }}F：
#include <stdio.h>#include <string.h>#include <vector>#include <algorithm>using namespace std;#define MIN 110#define MAX 3300struct bnode { //广搜用的node int dis,v;}qu[MAX];struct mnode { //建图用的node int v,in; mnode *next;}map[MAX*2],*Head[MIN];bool vis[MIN][MAX],used[MIN][MAX];//广搜用的判点是否搜过,判某点是否在最小路径树上int x[MAX],y[MAX],ans,flag;int ptr,n,m,sum[MAX],head,tail;void Initial() { ptr = 0; memset(vis,0,sizeof(vis)); memset(used,0,sizeof(used)); memset(Head,NULL,sizeof(Head));}void AddEdge(int x,int y,int z) { map[ptr].v = y,map[ptr].in = z; map[ptr].next = Head[x],Head[x] = &map[ptr++];}int Bfs_AC(int cur,int index) { int cnt = 0; bnode now,next; sum[index] = 0; head = tail = 0; now.v = cur,now.dis = 0; qu[++head] = now; vis[index][cur] = true; while (tail < head) { cnt++; now = qu[++tail]; sum[index] += now.dis; mnode *p = Head[now.v]; while (p != NULL) { int v = p->v,in = p->in; if (!vis[index][v] && !used[index][in]) { next.v = v; vis[index][v] = true; used[index][in] = true; next.dis = now.dis + 1; qu[++head] = next; } p = p->next; } } return cnt;}int main(){ int i,j,k,t,ta,tb; while (scanf("%d%d",&n,&m) != EOF) { Initial(); for (i = 1; i <= m; ++i) { scanf("%d%d",&x[i],&y[i]); AddEdge(x[i],y[i],i),AddEdge(y[i],x[i],i); } for (i = 1; i <= n; ++i) Bfs_AC(i,i); //Debug_Input for (j = 1; j <= m; ++j) { ans = flag = 0; for (i = 1; i <= n && !flag; ++i) { if (!used[i][j]) ans += sum[i]; else { memset(vis[n+1],false,sizeof(vis[n+1])); memset(used[n+1],false,sizeof(used[n+1])); used[n+1][j] = true; ta = Bfs_AC(i,n+1); if (ta < n) flag = 1; else ans += sum[n+1]; } } if (flag) printf("INF\n"); else printf("%d\n",ans); } }}J：
#include <stdio.h>#include <string.h>#include <vector>using namespace std;#define MAX 1001#define INF 2147483647#define min(a,b) ((a)<(b)?(a):(b))struct node { int v,len;}cur,next,qu[MAX];vector<node> map[MAX];char str[MAX];int top,st[MAX],cnt;int count[MAX],topo[MAX];int s,k,n,m,ans,ansi,dp[MAX][MAX];void Initial() { ansi = ans = -1; for (int i = 0; i <= n; ++i) { map[i].clear(); count[i] = 0; for (int j = 0; j <= k; ++j) dp[i][j] = INF; }}void ToooPooo() { int i,j,v,size; cnt = top = 0; for (i = 1; i <= n; ++i) if (count[i] == 0) st[++top] = i; while (top > 0) { i = st[top--]; topo[++cnt] = i; size = map[i].size(); for (j = 0; j < size; ++j) { cur = map[i][j]; count[cur.v]--; if (count[cur.v] == 0) st[++top] = cur.v; } }}void Debug_Input() { int i,j,t; for (i = 1; i <= n; ++i) for (j = 0; j < k; ++j) printf("i = %d j = %d dp[i][j] = %d\n",i,j,dp[i][j]);}int Solve_AC() { int i,j,t,size,v,tp; dp[s][0] = 0; for (i = 1; i <= cnt; ++i) { v = topo[i]; size = map[v].size(); for (j = 0; j < size; ++j) { next = map[v][j]; for (t = 0; t < k; ++t) if (dp[v][t] != INF) { tp = (t + next.len) % k; dp[next.v][tp] = min(dp[next.v][tp],dp[v][t] + (t+next.len)/k); } } } for (i = 1; i <= n; ++i) if (str[i] == 'P' && dp[i][0] != INF && (ans == -1 || dp[i][0] * k < ans)) ansi = i,ans = dp[i][0] * k; return ansi;}int main(){ int i,j,t; int cas = 0,a,b,c; scanf("%d",&t); while (t--) { scanf("%d%d%d%d",&n,&m,&s,&k); scanf("%s",str+1); Initial(); for (i = 1; i <= m; ++i) { scanf("%d%d%d",&a,&b,&c); count[b]++; cur.v = b,cur.len = c; map[a].push_back(cur); } ToooPooo(); Solve_AC(); printf("Case %d: %d %d\n",++cas,ans,ansi); }}本文ZeroClock原创，但可以转载，因为我们是兄弟。