首页 > 代码库 > NOIP模拟 6.26
NOIP模拟 6.26
T1 子矩阵
题目描述
小A有一个N×M的矩阵，矩阵中1~N*M这(N*M)个整数均出现过一次。现在小A在这个矩阵内选择一个子矩阵，其权值等于这个子矩阵中的所有数的最小值。小A想知道，如果他选择的子矩阵的权值为i(1<=i<=N×M)，那么他选择的子矩阵可能有多少种？小A希望知道所有可能的i值对应的结果，但是这些结果太多了，他算不了，因此他向你求助。
输入格式：
第一行，两个整数N, M。
接下来的N行，每行M个整数，表示矩阵中的元素。
输出格式：
N×M行，每行一个整数，其中第i行的整数表示如果小A选择的子矩阵权值为i，他选择的子矩阵的种类数。
输入样例#1：
2 3
2 5 1
6 3 4
输出样例#1：
6
4
5
1
1
1
题解：
部分枚举，扫描列的典型模型
枚举两个行数i,j（规定i <= j）,寻找[i,j]行内的矩形
递推可得[i,j]行内每一列的最小值
维护单调递增的栈，计算L[k]（在[i,j]行内选择第k列，则向左最远能够选到L[k]列）,R[i]（在[i,j]行内选择第k列，则向右最远能够选到R[k]列）
乘法原理得到左右行数在[i,j]内的、包含第k列的子矩阵
代码：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>inline void read(int &x){x = 0;char ch = getchar();char c = ch;while(ch > ‘9‘ || ch < ‘0‘)c = ch, ch = getchar();while(ch <= ‘9‘ && ch >= ‘0‘)x = x * 10 + ch - ‘0‘,ch = getchar();if(c == ‘-‘)x = -x;}inline void swap(int &a, int &b){int tmp = a;a = b;b = tmp;}inline int max(int a, int b){return a > b ? a : b;}inline int min(int a, int b){return a < b ? a : b;}const int INF = 0x3f3f3f3f;const int MAXN = 5000 + 10;const int MAXM = 100000;int n,m,num[MAXN][MAXN];int stack[MAXM], top;int mi[MAXM];int L[MAXM],R[MAXM];int ans[MAXM];int main(){ read(n);read(m); for(int i = 1;i <= n;++ i) for(int j = 1;j <= m;++ j) read(num[i][j]); //枚举上面的行i for(register int i = 1;i <= n;++ i) { //注意清为最大值 memset(mi, 0x3f, sizeof(mi)); //枚举i以下的行j for(register int j = i;j <= n;++ j) { //求得行[i,j]范围内的每一列的最小值 for(register int k = 1;k <= m;++ k) mi[k] = min(mi[k], num[j][k]); //正向扫描求R，维护一个递增（或相等）单调栈 for(register int k = 1;k <= m;++ k) { while(top && mi[k] < mi[stack[top]]) { R[stack[top]] = k - 1; -- top; } stack[++top] = k; } while(top) { R[stack[top]] = m; -- top; } //反向扫描求L，维护一个递增（或相等）单调栈 for(int k = m;k >= 1;k --) { while(top && mi[k] < mi[stack[top]]) { L[stack[top]] = k + 1; -- top; } stack[++top] = k; } while(top) { L[stack[top]] = 1; -- top; } //扫描列，累加答案 for(register int k = 1;k <= m;k ++) { ans[mi[k]] += (k - L[k] + 1) * (R[k] - k + 1); } } } register int tmp = n * m; for(register int i = 1;i <= tmp;++ i) { printf("%d\n", ans[i]); } return 0;}
T2 序列操作
题目描述
小B有一个整数序列a[1..N]，初始时序列中所有元素均为0。他会在序列上进行下面两种操作，操作共M个：
1、A l r x：将a[l..r]均加上x。
2、Q l r：询问a[l..r]中的最大值。
输入格式：
第一行，两个整数N, M。
接下来的M行，每行一个操作。
输出格式：
设询问操作有T个，则输出T行，每行一个整数，表示询问操作对应的答案。
输入样例#1：
5 5
A 1 4 1
A 2 5 2
Q 1 4
A 3 4 -2
Q 3 5
输出样例#1：
3
2
题解：线段树裸题
代码：
#include <iostream>#include <cstdio>#include <cstdlib>#include <string>#include <algorithm>inline void read(int &x){x = 0;char ch = getchar();char c = ch;while(ch > ‘9‘ || ch < ‘0‘)c = ch, ch = getchar();while(ch <= ‘9‘ && ch >= ‘0‘)x = x * 10 + ch - ‘0‘,ch = getchar();if(c == ‘-‘)x = -x;}inline void swap(int &a, int &b){int tmp = a;a = b;b = tmp;}inline int max(int a, int b){return a > b ? a : b;}inline int min(int a, int b){return a < b ? a : b;}const int INF = 0x3f3f3f3f; const int MAXN = 100000 + 10;const int MAXM = 100000 + 10;int sgtmax[MAXN];int sgtlazy[MAXN];int n,m;inline void putdown(int& o, int& l, int& r){ sgtmax[o << 1] += sgtlazy[o]; sgtlazy[o << 1] += sgtlazy[o]; sgtlazy[o << 1 | 1] += sgtlazy[o]; sgtmax[o << 1 | 1] += sgtlazy[o]; sgtlazy[o] = 0;}void modify(int ll, int rr, int k, int o = 1, int l = 1, int r = n){ if(ll <= l && rr >= r) { sgtmax[o] += k; sgtlazy[o] += k; return; } int mid = (l + r) >> 1; if(sgtlazy[o])putdown(o, l, r); if(mid >= ll)modify(ll, rr, k, o << 1, l, mid); if(mid < rr)modify(ll, rr, k, o << 1 | 1, mid + 1, r); sgtmax[o] = max(sgtmax[o << 1], sgtmax[o << 1 | 1]);}int ask(int ll, int rr, int o = 1, int l = 1, int r = n){ if(ll <= l && rr >= r) { return sgtmax[o]; } int mid = (r + l) >> 1; if(sgtlazy[o])putdown(o, l, r); int ans = -INF; if(mid >= ll)ans = max(ans, ask(ll, rr, o << 1, l, mid)); if(mid < rr)ans = max(ans, ask(ll, rr, o << 1 | 1, mid + 1, r)); return ans;}int main(){ read(n);read(m); register int i,tmp1,tmp2,tmp3; register char c; for(i = 1;i <= m;i ++) { c = getchar(); while(c != ‘A‘ && c != ‘Q‘)c = getchar(); if(c == ‘A‘) { read(tmp1);read(tmp2);read(tmp3); modify(tmp1, tmp2, tmp3); } else { read(tmp1);read(tmp2); printf("%d\n", ask(tmp1, tmp2)); } } return 0;}
T3 议案决定
题目描述
小C在玩一个游戏，在游戏中他扮演国王的角色。国王手下有M个大臣，他们有一天对国王要处理的N件事务进行投票。 每个大臣可以对两件事务进行投票（赞成或反对），格式如下：x c_x y c_y（x, y为整数，c_x, c_y为“Y”（表示赞成）或“N”（表示反对）（不含双引号），表示这个大臣对事务x的态度为c_x，对事务y的态度为c_y）。这些大臣非常难以对付，如果国王的决定和某个大臣的两个意见都不同，那么这个大臣就会离开国王。小C认为不能让任何一个大臣离开国王，否则国王就无法正常地处理自己的事务。 请你帮助小C做个决定。
输入格式：
第一行，两个整数N, M。
接下来的M行，每行表示一个大臣的投票。
输出格式：
如果小C无论如何都只能让至少一个大臣离开国王，则输出“IMPOSSIBLE”（不含双引号），否则输出一个长度为N的字符串 ，如果第i件事务必须赞成，则第i个字符为“Y”；如果第i件事务必须反对，则第i个字符为“N”，否则第i个字符为“?”。
输入样例#1：
3 4
1 Y 2 N
1 N 2 N
1 Y 2 Y
输出样例#1：
YN?
题解：
经典2-SAT问题
点u->v代表u发生则v必然发生
每一个条件可以拆为这样的两个条件
如1 Y 2 N 对应的是 1N->2N 2Y->1Y
我们把1Y 1N称为对立节点
符合条件的情况是，从节点i出发找一条路径，路径上不会遇到i的对立节点。
#include <cstdio>#include <iostream>#include <cstring>#include <cstdlib>#include <algorithm>const int MAXN = 80000 + 10;inline void read(int &x){x = 0;char ch = getchar();char c = ch;while(ch > ‘9‘ || ch < ‘0‘)c = ch, ch = getchar();while(ch <= ‘9‘ && ch >= ‘0‘)x = x * 10 + ch - ‘0‘, ch = getchar();if(c == ‘-‘)x = -x;}inline void read(char& x){x = 0;while(x != ‘Y‘ && x != ‘N‘)x = getchar();}struct Edge{int u,v,next;}edge[MAXN << 1];int head[MAXN << 1],cnt;void insert(int a, int b){edge[++cnt] = Edge{a,b,head[a]};head[a] = cnt;}int n,m;int ans[MAXN];//Y:ou shu N:ji shu int match[MAXN << 1];int dfs(int u){ for(int pos = head[u];pos;pos = edge[pos].next) { int v = edge[pos].v; if(!v || v == 1)continue; if(v & 1) { if(match[v - 1])return 0; if(match[v])continue; match[v] = 1; int tmp = dfs(v); if(!tmp) return 0; } else { if(match[v | 1])return 0; if(match[v])continue; match[v] = 1; int tmp = dfs(v); if(!tmp)return 0; } } return 1;}inline int check(int i){ memset(match, 0, sizeof(match)); match[i] = 1; return dfs(i);}const char a[3] = {‘?‘, ‘Y‘, ‘N‘};int main(){ read(n);read(m); register char c1,c2;register int tmp1, tmp2; register int i; for(i = 1;i <= m;++ i) { read(tmp1);read(c1);read(tmp2);read(c2); if(c1 == ‘Y‘ && c2 == ‘N‘) { insert(tmp1 << 1 | 1, tmp2 << 1 | 1); insert(tmp2 << 1, tmp1 << 1); } else if(c1 == ‘Y‘ && c2 == ‘Y‘) { insert(tmp2 << 1 | 1, tmp1 << 1); insert(tmp1 << 1 | 1, tmp2 << 1); } else if(c1 == ‘N‘ && c2 == ‘N‘) { insert(tmp2 << 1, tmp1 << 1 | 1); insert(tmp1 << 1, tmp2 << 1 | 1); } else if(c1 == ‘N‘ && c2 == ‘Y‘) { insert(tmp2 << 1 | 1, tmp1 << 1 | 1); insert(tmp1 << 1, tmp2 << 1); } } for(i = 1;i <= n;i ++) { tmp1 = check(i << 1); tmp2 = check(i << 1 | 1); if(tmp1 && tmp2)ans[i] = 0; else if(tmp1)ans[i] = 1; else if(tmp2)ans[i] = 2; else { printf("IMPOSSIBLE"); return 0; } } for(int i = 1;i <= n;i ++) { printf("%c", a[ans[i]]); } return 0;}
NOIP模拟 6.26