今天做的是山东第一届省赛，题目比昨天的容易，但是还是出了五道题，难道难题都只能叫大叔来做？
A: Phone Number
给出N个字符串，判断是否存在一个字符串是另一个字符串的前缀，之前做过一道类似的题，字典树判断前缀确实很方便。
#include#include #include typedef struct{ int next[10]; int alr, end;}Trie;Trie t[110000];int tp, n;int insert(char *x, int site){ if(t[site].end) return 1; if(*x) { t[site].alr = 1; if(!t[site].next[*x - '0']) t[site].next[*x - '0'] = tp ++; insert(x + 1, t[site].next[*x - '0']); } else { t[site].end = 1; return t[site].alr; }}int main(){ int T, flag; char s[11]; while( scanf("%d", &n), n ) { tp = 1; flag = 0; while(n --) { scanf("%s", s); if(!flag && insert(s, 0)) flag = 1; } if(flag) printf("NO\n"); else printf("YES\n"); memset(t, 0, sizeof(Trie) * (tp + 1)); } return 0;}
B： Balloons
这也是一道水题，简单的搜索，分别按照4个方向和八个方向找联通块的数目，然后输出这两种方式得到的结果，隽遒学弟敲的也很快，
也按照题目要求在每个样例之后输出了换行，结果PC^2返回了WA，我们把代码打印出来了，我帮他看了半天也没发现哪有错。后面
老大说试着样例之间输出换行就过了。
# include# include int n;bool m[103][103];bool f[103][103];const int go[4][2] = { 0,1, 1,0, 0,-1, -1,0}; //注意判断是否越界const int ju[8][2] = { 0,1, 1,0, 0,-1, -1,0, -1,1, 1,1, 1,-1, -1,-1};void f1(int x, int y){ int xx, yy, i; f[x][y] = 1; for ( i = 0; i < 4; ++i ) { xx = x + go[i][0]; yy = y + go[i][1]; if ( xx < 1 || xx > n || yy < 1 || yy > n || !m[xx][yy] || f[xx][yy] ) continue; f1(xx, yy); }}void f2(int x, int y){ int xx, yy, i; f[x][y] = 1; for ( i = 0; i < 8; ++i ) { xx = x + ju[i][0]; yy = y + ju[i][1]; if ( xx < 1 || xx > n || yy < 1 || yy > n || !m[xx][yy] || f[xx][yy] ) continue; f2(xx, yy); }}int t = 0;int main(){ int i, j; char s[107]; while ( scanf("%d", &n) != EOF ) { ++t; if ( n == 0 ) break; for ( i = 1; i <= n; ++i ) { scanf("%s", s+1); for ( j = 1; j <= n; ++j ) if ( s[j] == '0' ) m[i][j] = 0; else m[i][j] = 1; } int ans1 = 0, ans2 = 0; memset(f, 0, sizeof(f)); for ( i = 1; i <= n; ++i ) for ( j = 1; j <= n; ++j ) if ( m[i][j] && ! f[i][j] ) { ++ans1; f1(i, j); } memset(f, 0, sizeof(f)); for ( i = 1; i <= n; ++i ) for ( j = 1; j <= n; ++j ) if ( m[i][j] && ! f[i][j] ) { ++ans2; f2(i, j); } if ( t > 1 ) printf("\n"); printf("Case %d: %d %d\n", t, ans1, ans2); } return 0;}
C： Clockwise
看了题解是计算几何 + DP，不会，先放着。
D： Shopping
最水的一道题，结果又给我碰上了，输出给定序列最大值 - 最小值的结果的两倍。当时为了敲起来简单，还排序了...
#include#include #include #include using namespace std;const int MAXN = 100010;int a[MAXN];int main(){ int n; while(scanf("%d", &n), n) { for(int i = 0; i < n; i ++) { scanf("%d", &a[i]); } sort(a, a + n); printf("%d\n", (a[n - 1] - a[0]) * 2); } return 0;}
E： Emergency
这题是我敲的，之前做过几乎一模一样的题。给出一个图，N个点,M条有向边，Q次操作，M和Q都是10万，N是300，现在假设所有的点都被破坏了，有两
种操作，0 x，修复x结点，意味着我们可以从一个点到另一个点经过x结点。如果x结点已经被修复，则输出一句话。1 x y，输出从x到y的经过修复好的点
的最短路长度，如果x或者y依然是破坏状态也是输出一句话，否则则看最短路是否存在，存在就输出值。一个变化的floyd就可以搞定，每次修复一个点就把
这个点当成k，做k为中间点，任意两点间的最短路。
#include#include #include const int MAXN = 350;const int INF = 0x3f3f3f3f;int d[MAXN][MAXN];bool rec[MAXN];int N, M, Q;void ReadGraph(){ int x, y, z; for(int i = 0; i < N; i ++) for(int j = 0; j < N; j ++) { if(i == j) d[i][j] = 0; else d[i][j] = INF; } memset(rec, false, sizeof rec); while(M --) { scanf("%d%d%d", &x, &y, &z); if(d[x][y] > z) d[x][y] = z; }}void query(){ int op, x, y; while(Q --) { scanf("%d", &op); if(0 == op) { scanf("%d", &x); if(rec[x]) printf("City %d is already recaptured.\n", x); if(!rec[x]) { rec[x] = true; for(int i = 0; i < N; i ++) for(int j = 0; j < N; j ++) { if(d[i][j] > d[i][x] + d[x][j]) d[i][j] = d[i][x] + d[x][j]; } } } if(1 == op) { scanf("%d%d", &x, &y); if(rec[x] && rec[y]) { if(d[x][y] < INF) printf("%d\n", d[x][y]); else printf("No such path.\n"); } else { printf("City %d or %d is not available.\n", x, y); } } }}int main(){ freopen("emergency.in", "r", stdin); freopen("Edata.txt", "w", stdout); int t = 1; while(scanf("%d%d%d", &N, &M, &Q), N + M + Q) { ReadGraph(); if(t > 1) printf("\n"); printf("Case %d:\n", t ++); query(); //printf("\n"); } return 0;}
F：Fairy tale
模拟题，比赛时隽遒学弟在敲，当时没出，结束后交题过了。
# include# include # define rep(x) for ( x = 1; x <= n; ++x )const int go[4][2] = { 0,1, 0,-1, 1,0, -1,0}; //E,W,S,Nconst int pgo[4][2] = { 0,1, 0,-1, -1,0, 1,0}; //E,W,N,S prefer!const int inf = 2147483647;int n;int m[35][35];bool f[31][31][31][31][4];bool circle;int x, y, tx, ty, time;int abs(int x) { return x > 0 ? x: -x; }int sqr(int x) { return x * x; }bool inside(int x, int y){ return (x > 0 && x <= n && y > 0 && y <= n); }bool better(int x, int y, int xx,int yy){ return sqr(x-tx)+sqr(y-ty) < sqr(xx-tx)+sqr(yy-ty); }void Init(){ int i,j,k,l,p; char s[35]; rep(i) rep(j) rep(k) rep(l) for (p = 0; p < 4; ++p ) f[i][j][k][l][p] = false; rep(i) { scanf("%s", s+1); rep(j) if ( s[j] == 'E' ) m[i][j] = 0; else if ( s[j] == 'W' ) m[i][j] = 1; else if ( s[j] == 'S' ) m[i][j] = 2; else if ( s[j] == 'N' ) m[i][j] = 3; } x = y = 1; tx = ty = n; time = 0; circle = false;}int cnt = 0;int sec[103][5];bool check(){ int i; for ( i = 1; i < time; ++i ) if ( sec[i][0] == x && sec[i][1] == y && sec[i][2] == tx && sec[i][3] == ty && sec[i][4] == (time&3) ) { circle = true; return true; } sec[i][0] = x,sec[i][1] = y,sec[i][2]= tx, sec[i][3] = ty, sec[i][4]= (time&3); return false;}bool step(){ int f1 = (m[x][y]+time)&3, f2 = (m[tx][ty]+time)&3; if ( x == tx && y == ty ) return true; if ( check() ) return false; int xx = x + go[f1][0]; int yy = y + go[f1][1]; if ( inside(xx,yy) ) x = xx, y = yy; //自动走 xx = x, yy = y; for ( int i = 0; i < 4; ++i ) //喜好行走 { if ( !inside(x + pgo[i][0], y + pgo[i][1]) ) continue; if ( better(x + pgo[i][0],y + pgo[i][1], xx, yy) ) xx = x + pgo[i][0], yy = y + pgo[i][1]; } x = xx, y = yy; int txx = tx + go[f2][0]; int tyy = ty + go[f2][1]; if ( inside(txx, tyy) ) tx = txx, ty = tyy; //宝藏走 ++time; return false;}int main(){ int t = 0; while ( scanf("%d", &n), n ) { if ( ++t > 1 ) printf("\n"); Init(); printf("Case %d:\n", t); while ( time < 100 ) { if ( step() ) { printf("Get the treasure! At step %d.\n", time); break; } if ( circle ) { printf("Impossible. At step %d.\n", time); break; } if ( time == 99 ) printf("Not sure.\n"); } } return 0;}
G：Greatest Number
二分
H：Hello World!
一道水题，比赛的时候我和陈兴想多了，但还好陈兴用强大的STL功底过了。给出n个点x和y的值，找到每个点的行和列都比它大的点，优先选择行小的
作为结果，行相等则选择列小的。n^2可以暴力过。
我的代码：
#include#include #include const int MAXN = 1 << 10;const int INF = 0x3f3f3f3f;int x[MAXN], y[MAXN];int n;int main(){ //freopen("hello.in", "r", stdin); //freopen("hello1.out", "w", stdout); int t = 1; while(scanf("%d", &n), n) { for(int i = 1; i <= n; i ++) { scanf("%d%d", &x[i], &y[i]); } if(t > 1) printf("\n"); printf("Case %d:\n", t ++); int minx, miny; for(int i = 1; i <= n; i ++) { minx = miny = INF; for(int j = 1; j <= n; j ++) { if(i == j) continue; if(y[j] > y[i] && x[j] > x[i]) { if(minx > x[j]) { minx = x[j], miny = y[j]; } if(minx == x[j]) { if(miny > y[j]) { minx = x[j], miny = y[j]; } } } } if(minx < INF && miny < INF) { printf("%d %d\n", minx, miny); } else { puts("-1 -1"); } } } return 0;}
陈兴的代码：
#include#include #include #include using namespace std;const int MAXN = 1010;struct Node{ int row, colum; int order; bool operator<(const struct Node ans) const { return (row < ans.row || (row == ans.row && colum < ans.colum)); }}node[MAXN];struct Res{ int row, colum;}resl[MAXN];int n;set myset;bool cmp1(const struct Node ans1, const struct Node ans2){ return ans1.row > ans2.row;}bool cmp2(const struct Node ans1, const struct Node ans2){ return ans1.order < ans2.order;}void Init(){ for(int i = 0; i < n; i++) { scanf("%d%d", &node[i].row, &node[i].colum); node[i].order = i; } sort(node, node + n, cmp1);//行升序}void Solve(){ int tmp; myset.clear(); for(int i = 0; i < n; i++) { tmp = node[i].order; resl[tmp].row = -1; resl[tmp].colum = -1; set ::iterator it = myset.begin(); while(it != myset.end()) { if(it->row > node[i].row && it->colum > node[i].colum) { resl[tmp].row = it->row; resl[tmp].colum = it->colum; break; } it++; } myset.insert(node[i]); }}int main(){ int i = 1; while(scanf("%d", &n)!= EOF && n) { Init(); Solve(); if(i > 1) putchar('\n'); printf("Case %d:\n", i++); for(int j = 0; j < n; j++) { printf("%d %d\n", resl[j].row, resl[j].colum); } } return 0;}
I：Ivan comes again!
线段树离散化+set。
赛后殷神犇告诉我这道题我做过，我还不信，结果翻到了HDU 3627的代码，拍了下数据，0行差异，我只能表示呵呵。才多久就忘了做过这题...
/*Accepted 3627 1203MS 6848K 2698 B C++*/#include#include #include using namespace std;const int MAXN = 200010;struct TPoint{ int x, y, flag;}pre[MAXN], ans[MAXN], s;char op[10];int n, m;struct Segtree{ int l, r, maxy;}tree[MAXN << 2];bool cmp(TPoint a, TPoint b){ return a.x < b.x || ( a.x == b.x && a.y < b.y);}void build( int rt, int l, int r){ tree[rt].l = l, tree[rt].r = r, tree[rt].maxy = -1; if( l == r) return; int m = (l + r) >> 1; build( rt << 1, l, m); build( rt << 1 | 1, m + 1, r);}int BS( TPoint nd, int l, int r){ while( l <= r){ int m = (l + r) >> 1; if( nd.x == ans[m].x && nd.y == ans[m].y) return m; if( nd.x < ans[m].x || nd.x == ans[m].x && nd.y < ans[m].y) r = m - 1; else l = m + 1; } return -1;}void update( int rt, int l, int flag){ if( tree[rt].l == l && tree[rt].r == l) { if( 1 == flag) tree[rt].maxy = ans[l].y; if( 2 == flag) tree[rt].maxy = -1; return; } int m = (tree[rt].l + tree[rt].r) >> 1; if(l <= m) update( rt << 1, l, flag); else update( rt << 1 | 1, l, flag); tree[rt].maxy = max( tree[rt << 1].maxy, tree[rt << 1 | 1].maxy);}void query(int rt, TPoint nd){ if(tree[rt].maxy <= nd.y) return; if(ans[tree[rt].r].x <= nd.x) return; if( tree[rt].l == tree[rt].r){ s = ans[tree[rt].l]; return; } query(rt << 1, nd); if(s.x == -1) query(rt << 1 | 1, nd);}void prepare(){ int i; for( i = 1, m = 0; i <= n; i ++) { scanf( "%s%d%d", op, &pre[i].x, &pre[i].y); if('a' == op[0]) { pre[i].flag = 1; ans[++ m] = pre[i]; } else if( 'r' == op[0]) pre[i].flag = 2; else pre[i].flag = 3; } sort( ans + 1, ans + m + 1, cmp); build( 1, 1, m);}void operation(){ for( int i = 1; i <= n; i ++) { int cnt = BS(pre[i], 1, m); if( 3 == pre[i].flag) { s.x = s.y = -1; query( 1, pre[i]); if( s.x == -1) printf( "-1\n"); else printf( "%d %d\n", s.x, s.y); } else{ update( 1, cnt, pre[i].flag); } }}int main(){ //freopen("Ivan.in", "r", stdin); //freopen("Ii.out", "w", stdout); int cas = 0; while( scanf( "%d", &n), n) { if( cas ++) printf( "\n"); printf( "Case %d:\n", cas); prepare(); operation(); } return 0;}
J：Jerry Mouse
题目很长，当时没看，后面大神们说是并查集，其他队都在比赛中A掉了。