Noip 模拟练习3
- 满分300，本人100，修正后300
- 较易
栈
题目：
- 有图，转
题解：
- 其实这就是一个简单的卡特兰数。
- 吐槽，这是原题
- 证明过程转我写过的一篇
#include#include using namespace std;int n;int dp[25];int main(){ cin >> n; dp[0] = dp[1] = 1; for(int i = 2; i <= n; i++) for(int j = 0; j < i; j++) dp[i] += dp[j] * dp[i - j - 1]; cout << dp[n]; return 0;}
报名查询
Description
某市中考科目繁多，且记分方法特别，以至于总分最高可达 10的6次方。为了公平起见，教育局规定成绩公布后两天为报名时间，考生可以根据自己的成绩选择填报某所学校。
报名截止后，各校会将填报本校学生的分数从高到低排列，然后按招生计划指定的人数进行
录取，因此如果志愿填报不合理你就可能落选。为了方便考生及时了解报名情况，该市最牛
的 110 中学请你开发一个报名辅助软件，该软件主要有四个操作：
(1) 投档：操作符为“I”，用以处理某位考生报考本校；
(2) 查询：操作符为“C”，用以处理某位考生查询当前有多少考生总分比自己高；
(3) 退档：操作符为“D”，用以处理某位考生退出报考本校；
(4) 截止：操作符为“E”，表示报名截止，软件停止工作。
在前三个操作中，每个操作符后都会跟有一个分数，操作符和分数之间用一个空格分开。
如“I 10000”，表示有一名总分是 10000 的考生报考本校；“C 10000”表示当前有一名总分
是 10000 的考生进行查询，此时程序应返回当前报考本校的考生中有多少个总分超过 10000；
“D 10000”表示有一名总分是 10000 的考生退出报考本校。
你的程序应该对每个投档和退档的操作对考生数据库进行实时更新，对每个查询操作输
出正确的解答。
Input
输入文件 query.in 每行给出一个操作，最后一行是操作符“E”表示输入结束。
输入中每个操作符“I”、“C”、“D”后都跟有一个不超过 10的6次方
的正整数，表示参与该次操作
的考生总分。所有操作的总数不超过 10的6次方
Output
- 对于输入文件中的每个查询操作“C”，必须在输出文件中给出正确的回答。
Sample Input
I 10000
I 20000
C 20000
I 10000
C 10000
I 5000
D 10000
C 5000
E
Sample output
0
1
2
题解：
- 线段树 + 离散化
- 复杂度是可以接受的，如果树的深度是21亿，找一个结点只需30几下。所以logn的复杂度是十分优秀的。何况这里的数据最大才10的6次方。
- 区间修改 + 单点查询
- 如果有一个分数为x的学生投档，那么比x低的分数那一段区间+1。退档即-1。
- 查询直接查询那个分数位置即可。
- 坑点：查询的成绩可能在之前并没有出现过而且大小随机
#include#include #include #include #define maxn 1000005using namespace std;struct Tree {int l, r, val, tag;}tree[maxn * 4];struct A {int op, num;} a[maxn];int n, cnt;int b[maxn];int read(){ int x = 0; char c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} return x;}int find(int x) { return upper_bound(b + 1, b + 1 + cnt, x) - b - 1; //注意查询的元素是不一定出现且随机的}void build(int root, int l, int r){ tree[root].l = l, tree[root].r = r; if(l == r) return; int mid = (l + r) >> 1; build(root << 1, l, mid); build(root << 1 | 1, mid + 1, r);}void down(int root){ int son1 = root << 1, son2 = root << 1 | 1; tree[son1].tag += tree[root].tag, tree[son2].tag += tree[root].tag; tree[son1].val += (tree[son1].r - tree[son1].l + 1) * tree[root].tag; tree[son2].val += (tree[son2].r - tree[son2].l + 1) * tree[root].tag; tree[root].tag = 0;}void update(int root, int l, int r, int add){ if(tree[root].l >= l && tree[root].r <= r) { tree[root].tag += add; tree[root].val += (tree[root].r - tree[root].l + 1) * add; return; } if(tree[root].tag) down(root); int mid = (tree[root].l + tree[root].r) >> 1; if(l <= mid) update(root << 1, l, r, add); if(r > mid) update(root << 1 | 1, l, r, add); tree[root].val = tree[root << 1].val + tree[root << 1 | 1].val;}int ask(int root, int l, int r){ if(tree[root].l >= l && tree[root].r <= r) return tree[root].val; if(tree[root].tag) down(root); int mid = (tree[root].l + tree[root].r) >> 1, ans = 0; if(l <= mid) ans += ask(root << 1, l, r); if(r > mid) ans += ask(root << 1 | 1, l, r); return ans;}int main(){ while(1) { char c = getchar(); if(c == 'E') break; int num = read(); a[++n].num = num; if(c == 'I') b[++cnt] = num, a[n].op = 1; else if(c == 'C') a[n].op = 2; else if(c == 'D') a[n].op = 3; } b[++cnt] = 0; //细节！为了求出比最差成绩高的成绩个数 sort(b + 1, b + 1 + cnt); cnt = unique(b + 1, b + 1 + cnt) - b - 1; build(1, 1, cnt); for(int i = 1; i <= n; i++) { if(a[i].op == 1 && find(a[i].num) - 1 >= 1) update(1, 1, find(a[i].num) - 1, 1); else if(a[i].op == 3 && find(a[i].num) - 1 >= 1) update(1, 1, find(a[i].num) - 1, -1); else if(a[i].op == 2) { if(find(a[i].num) > cnt) printf("0\n"); else printf("%d\n", ask(1, find(a[i].num), find(a[i].num))); } } return 0;}
方格取数
Description
- 为了使漫长的星际旅行变得更加有趣，航天员发明了一种益智游戏：一个由 NN个格子组成的棋盘上，填上 N N个标有数字的棋子，并给定一个整数 M，若相邻两个格子 (即有公共边的格子)中的棋子所标的数字之差的绝对值不超过 M，则可以将这两个棋子从棋 盘中拿去，游戏的目标是使剩下的棋子最少。 你的任务是写一个程序，对于一个初始棋盘和给定的 M 值，求出剩余棋子最少的取子方案。
Input
输入文件 fgqs.in 的第一行给出 N 和 M 的值，这两个数之间用一个空格分开，其
中 1≤N,M≤100。20%的数据 1≤N,M≤10。
以下 N 行，每行有 N 个正整数，给出初始棋盘每个格子中棋子上所标的数，该数不超过
1000，同一行相邻两个整数之间用一个空格分开。
Output
- 输出文件 fgqs.out 仅有一个整数，即你得到的最佳取子方案中剩下的棋子数。
Sample Input
3 2
3 2 5
7 1 2
3 6 9
Sample Output
5
题解：
思路1：搜索。
- 考场上我就是这么做的。做的好的话20分。可是我爆掉了
思路2：联通块
- 第一次修正时是这样做的。即用搜索找出一个个互相间有关系的联通块。对于每个联通块，它所产生的贡献就是(int)(块里元素个数 / 2) * 2。最后ans就等于n * n - 所以块的贡献
- 这样乍一看没有错误。但其实有个长这样的联通块：
0
0
0
0 0
0
- 按理说这个块的贡献是3。但你手玩就会发现贡献是2
思路3：二分图匹配
- 看来我对二分图还是不够敏感啊，这是老师讲的正解
- 只要看到“两个东西匹配”这种字眼或者有这种感觉的题目，一定要联想到二分图！
- 跟以往不同的是，不用把图分成两部分，每个点都尝试匹配。不把图分成两部分的话就需要要更新mat时互相的mat都要更新
- 这题也告诉了我们二分图匹配不一定一定要把图分成两部分
- 你可能会问：怎么证明它时一个二分图？
- 证明如下：
#include#include #include #include #define maxn 105using namespace std;struct Mat {int x, y;} mat[maxn][maxn];int n, m, tot;int a[maxn][maxn];int dx[5] = {0, -1, 1, 0, 0};int dy[5] = {0, 0, 0, -1, 1};bool vis[maxn][maxn];bool dfs(int x, int y){ for(int i = 1; i <= 4; i++) { int xx = x + dx[i], yy = y + dy[i]; if(xx >= 1 && xx <= n && yy >= 1 && yy <= n) if(abs(a[x][y] - a[xx][yy]) <= m && !vis[xx][yy]) { vis[xx][yy] = 1; if(!mat[xx][yy].x || dfs(mat[xx][yy].x, mat[xx][yy].y)) { mat[xx][yy].x = x, mat[xx][yy].y = y; mat[x][y].x = xx, mat[x][y].y = yy; return 1; } } } return 0;}int main(){ cin >> n >> m; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cin >> a[i][j]; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(!mat[i][j].x && dfs(i, j)) { tot++; memset(vis, 0, sizeof(vis)); } cout << n * n - 2 * tot; return 0;}