FJNU_2010纳新赛
比赛地址
题目不分难易，即使题目很简单，不同的人也会有不同的做法，多看别人的程序，可以拓宽自己的思路
A:Phoenix的果园之再度归来
考察对单调队列的应用
以样例1 3 5 2 99 23 8 23 0 2来说，已知k=3,假设我们要求的是最小值，那么我们要维护一个单调递增的队列，同时记录每个元素的位置，一开始前3个元素都刚好递增，所以可以全部插入得到队列
1 3 5
0 1 2
下面是它们的位置，于是对于区间[0,2],其最小值就是1,接下来我们要插入第3个元素，为了保持单调递增的性质，则必须把3,5舍去，于是得
1 2
0 3
于是对于区间[1,3],因为第0个元素不在该区间内，所以舍去，所以该区间最小值为2,接下来插入第4个元素，由于99比2大，所以可以直接插入，得到（注意第0个元素已舍去）
2 99
3 4
于是对于区间[2,4],由于最头的元素2在该区间内，不用舍去，所以该区间最小值为2.
如此演算下去，求最大值的时候，换成单调递减的对列即可，所以最终复杂度为O(n)
#include <iostream> using namespace std; int a[1000002]; // true min, false max #define C1(a, b) ((a)>(b)) #define C2(a, b) ((a)<(b)) #define cmp(a, b, c) (c) == true ? C2(a, b) : C1(a, b) struct M { int f, t, s[1000002][2]; bool fl; M(bool tt) {f = t = 0, fl = tt;} void reset() {f = t = 0;} M() {} void ins(int v, int idx) { while(f != t && !(cmp(s[t-1][0], v, fl))) --t; s[t][0] = v, s[t++][1] = idx; } int del(int idx) { while(s[f][1] < 0idx) ++f; return s[f][0]; } } Min(true), Max(false); int main() { int n, k, i, j; while(scanf("%d%d", &n, &k) != EOF) { Min.reset(), Max.reset(); for(i = 0; i < n; ++i) scanf("%d", &a[i]); for(i = 0; i < k; ++i) Min.ins(a[i], i), Max.ins(a[i], i); printf("%d", Max.del(0)); for(i = 1, j = k; i + k <= n; ++i, ++j) {Max.ins(a[j], j); printf(" %d", Max.del(i));} printf("\n%d", Min.del(0)); for(i = 1, j = k; i + k <= n; ++i, ++j) {Min.ins(a[j], j); printf(" %d", Min.del(i));} puts(""); } return 0; }
B:数鸭子
对于某个m*n的矩阵mat，我们要先进行预处理，使得对于某个位置mat[i][j]的值，代表以0,0到i,j为对角线组成的矩形里的所有元素的和，比如对于矩阵
1 2
3 4
经过预处理必须变为
1 3
4 10
那么对于某个询问，我们假设所给的两点为从左上到右下的对角线，其中(a,b)代表左上的点，(c,d)代表右下的点，那么该对角线构成的矩形里元素的和为
mat[c][d] – mat[a-1][d] – mat[c][b-1] + mat[a-1][b-1]
经过预处理后，对于每次询问，即可在O(1)的复杂度下算出。
注意，题目给定的询问并不是一定是为从左上到右下的对角线，所以要经过一定的处理转换成从左上到右下的对角线，以方便统一处理
#include <stdio.h> int s[1002][1002]; #define SWAP(a,b) ((a)^=(b)^=(a)^=(b)) int cal(int a, int b, int c, int d) { if(a > c) { SWAP(a, c); SWAP(b, d); } if(b > d) SWAP(b, d); return s[c][d] - s[a-1][d] - s[c][b-1] + s[a-1][b-1]; } int main() { int a, b, c, d, t, i, j, n, m, k; scanf("%d", &t); while(t--) { scanf("%d%d", &m, &n); for(i = 1; i <= m; ++i) { for(j = 1; j <= n; ++j) scanf("%d", &s[i][j]); for(j = 1; j <= n; ++j) s[i][j] += s[i][j-1]; } for(i = 1; i <= m; i++) for(j = 1; j <= n; j++) s[i][j] += s[i-1][j]; scanf("%d", &k); while(k--) { scanf("%d%d%d%d", &a, &b, &c, &d); printf("%d\n", cal(a, b, c, d)); } puts(""); } }
C:Axis Bunker
由于最多只有4*4的大小，我们只要暴力搜索，对于每个没有建筑物的地方，一一试放，判断是否与已放的枪冲突即可
#include <stdio.h> int n, ans; char mp[5][5]; int check(int i, int j) { int it = i, jt = j; while(it >= 0 && mp[it][j] == '.') --it; if(it >= 0 && mp[it][j] != 'X') return 0; while(jt >= 0 && mp[i][jt] == '.') --jt; if(jt >= 0 && mp[i][jt] != 'X') return 0; return 1; } void dfs(int i, int j, int t) { int it = i, jt = j + 1; if(jt == n) ++it, jt = 0; if(it == n) { if(mp[i][j] != 'X' && check(i,j)) ++t; if(ans < t) ans = t; return; } if(mp[i][j] == 'X') dfs(it, jt, t); else if(check(i, j)) { mp[i][j] = 'Y'; dfs(it, jt, t+1); mp[i][j] = '.'; dfs(it, jt, t); } else dfs(it, jt, t); } int main() { int i; while(scanf("%d", &n)) { if(n == 0) break; for(i = 0; i < n; ++i) scanf("%s", mp[i]); ans = 0; dfs(0, 0, 0); printf("%d\n", ans); } return 0; }
D:Calling
这题由于数据量的关系，可以直接一个一个暴力匹配过去，但是正解是把这每个二进制串转成十进制，通过一个数组来判断出现次数
#include <stdio.h> short a[401]; int C(char *p) { char *q; int i, v = 0; for(q = p, i = (1<<9); *q; ++q, i >>= 1) if(*q == '1') v += i; return v; } int main() { int n1, n2, t, i; char buf[11]; scanf("%d", &t); while(t--) { scanf("%d", &n1); for(i = 0; i < n1; ++i) { scanf("%s", buf); a[i] = C(buf); } int v[1025] = {0}; scanf("%d", &n2); for(i = 0; i < n2; ++i) { scanf("%s", buf); ++v[C(buf)]; } for(i = 0; i < n1; ++i) printf("%d\n", v[a[i]]); puts(""); } }
E:黑白棋
这其实是一道简单的模拟题，只要对于每个没有放棋的位置，对其试放黑棋，然后判断其八个方向是否存在两个黑棋中间全是白棋的情况，如果存在，将这些白棋数计下，对于每个位置，一一测试即可取最大值即可
#include <stdio.h> char mp[9][9]; int dh[] = {-1, -1, 0, 1, 1, 1, 0, -1}; int dw[] = {0, 1, 1, 1, 0, -1, -1, -1}; int check() { int t1, t2, ans = 0, i, j, it, jt, k; for(i = 0; i < 8; ++i) for(j = 0; j < 8; ++j) if(mp[i][j] == '*') { t1 = t2 = 0; for(k = 0; k < 8; ++k) { it = i, jt = j, t1 = 0; do { it += dh[k], jt += dw[k]; ++t1; } while(it >= 0 && it < 8 && jt >= 0 && jt < 8 && mp[it][jt] == 'L'); if(it >= 0 && it < 8 && jt >= 0 && jt < 8 && mp[it][jt] == 'D') t2 += t1 - 1; } if(t2 > ans) ans = t2; } return ans; } int main() { int n, i, t; scanf("%d", &n); for(t = 1; t <= n; ++t) { for(i = 0; i < 8; ++i) scanf("%s", mp[i]); printf("Case %d: %d\n", t, check()); } }
F:统计数字
由于每个数字不超过150000，所以简单的开一个150001大小的数组来存放每个数字出现的次数，最后将次数不为0的数字输出即可
PS:如果数字很大，达到上亿的话，那么就要考虑通过hash来解决。后面写个hash的解决方法
#include <stdio.h> int c[150001] = {0}; int main() { int i, n, m = -1, t; scanf("%d", &n); for(i = 0; i < n; ++i) { scanf("%d", &t); if(t > m) m = t; ++c[t]; } for(i = 0; i <= m; ++i) if(c[i]) printf("%d %d\n", i, c[i]); return 0; }
G：密码翻译
此道题只要完全按照题目的意思做，就能做出来，不明白为啥现场比赛时过的人那么少，，
#include <iostream> using namespace std; char mp[][10] = { {}, {}, {0, 'A', 'B', 'C'}, {0, 'D', 'E', 'F'}, {0, 'G', 'H', 'I'}, {0, 'J', 'K', 'L'}, {0, 'M', 'N', 'O'}, {0, 'P', 'Q', 'R', 'S'}, {0, 'T', 'U', 'V'}, {0, 'W', 'X', 'Y', 'Z'} }; char t[256]; int main() { char *tmp = "QWERTYUIOPASDFGHJKLZXCVBNM"; char buf[2000]; char ans[2000]; char res[2000]; int m; for(int i = 0; i < 26; ++i) t[tmp[i]] = i + 'A'; while(scanf("%s", buf) != EOF) { memset(res, 0, sizeof(res)); int j = 0; for(int i = 0; buf[i]; i += 2, ++j) { ans[j] = t[mp[buf[i]-'0'][buf[i+1]-'0']]; } m = j / 2; if(j & 1) ++m; int x, k, y; for(x = 0, y = m, k = 0; x < m && y < j; ++x, ++y, k += 2) { res[k] = ans[x]; res[k+1] = ans[y]; } if(x < m) res[k++] = ans[m-1]; for(int i = j - 1; i >= 0; --i) putchar(res[i]); puts(""); } return 0; }
H:分数线划定
此题要是懂的用sort的话，将是一道非常简单的题目。。。
注意如果最低分数存在相同的人，那么这些人全部都要入选
#include <iostream> #include <algorithm> using namespace std; struct A { int k, s; }a[5001]; bool cmp(A a, A b) { return a.s > b.s || a.s == b.s && a.k < b.k; } int main() { int n, m, i; scanf("%d%d", &n, &m); m *= 1.5; for(i = 0; i < n; ++i) scanf("%d%d", &a[i].k, &a[i].s); sort(a, a+n, cmp); i = m-1; while(i < n && a[i].s == a[m-1].s) ++i; printf("%d %d\n", a[m-1].s, i); for(n = 0; n < i; ++n) printf("%d %d\n", a[n].k, a[n].s); return 0; }
I题就是A题的数据减弱版，就是为了让人水水更健康，用什么暴力的方法都能过。。
OOOOOOOOOOOOOrz
@Camey
敏哥把做法不同的题的代码发出来吧，比如A题，多看不同的想法拓展思路嘿嘿
凤凰王者归来了！
好。。
好强大的 单调队列
@小展
那是个神奇的东东..
千秋万代，一统江湖。
00000000000000000000rz
00000000000000000000rz
00000000000000000000rz
教主 00000000000000000000rz