(T1)
题目描述
给出一个 (n × n) 的, 元素为自然数的矩阵.
这个矩阵有许许多多个子矩阵, 定义它的所有子矩阵形成的集合为 (S) .
对于一个矩阵 (k) , 定义 (f(k)) 为 (k) 中所有元素的 (AND) 值 (按位与).
对于一个矩阵 (k) , 定义 (g(k)) 为 (k) 中所有元素的 (OR) 值 (按位或).
请求出所有子矩阵的 (f(k)) 之和与所有子矩阵的 (g(k)) 之和, 即 (prod_{k∈S}f(k)) 与 (prod_{k∈S}g(k)) .
由于答案可能很大, 只需要输出答案对 (998244353) 取模的结果.
(Solution)
期望得分-(30pts)，结果错了三个地方：
(1.)文件输入输出把题目名字写错了...
(2.)把或看成了异或...
(3.)递推的顺序错误，推前面的用到了后面还没推的
这种令人降智的错误犯一次就不可以第二次了啊。。。
(100pts)做法：
把每个数拆成二进制，第 (k) 位上的数对答案贡献为 (2^k * ans)
(ans_{add}) 可以看作全 (1) 的矩阵个数，(ans_{or}) 可看作所有矩阵减去全 (0) 矩阵个数
枚举每一列，用单调栈更新这一列的矩阵个数
时间复杂度：(O(n^2))，但是有个 (31) 的常数（二进制位数）
(Code)
#include<bits/stdc++.h>
#define ll long long
#define F(i, x, y) for(int i = x; i <= y; ++ i)
using namespace std;
int read();
const int mod = 998244353;
const int N = 1e3 + 5;
int n, top;
int ma[N][N], mb[N][N];
ll sta[N], pos[N], s[N], f[N][N][2];
ll ans, ans1, ans2;
int main()
{
freopen("mob.in","r",stdin);
freopen("mob.out","w",stdout);
n = read();
F(i, 1, n) F(j, 1, n) mb[i][j] = read();
F(k, 0, 31)
{
F(i, 1, n) F(j, 1, n) ma[i][j] = mb[i][j] & 1, mb[i][j] >>= 1;
F(i, 1, n) F(j, 1, n)
if(ma[i][j]) f[i][j][1] = f[i][j - 1][1] + 1, f[i][j][0] = 0;
else f[i][j][1] = 0, f[i][j][0] = f[i][j - 1][0] + 1;
ans = 0;
F(j, 1, n)
{
top = 0;
F(i, 1, n)
{
while(top && f[i][j][1] <= sta[top]) -- top;
sta[++ top] = f[i][j][1], pos[top] = i;
s[top] = (s[top - 1] + (i - pos[top - 1]) * f[i][j][1] % mod) % mod;
ans = (ans + s[top]) % mod;
}
}
ans1 = (ans1 + ans * (1 << k) % mod) % mod;
ans = 0;
F(j, 1, n)
{
top = 0;
F(i, 1, n)
{
while(top && f[i][j][0] <= sta[top]) -- top;
sta[++ top] = f[i][j][0], pos[top] = i;
s[top] = (s[top - 1] + (i - pos[top - 1]) * f[i][j][0] % mod) % mod;
ans = (ans + i * j % mod + mod - s[top]) % mod;
}
}
ans2 = (ans2 + ans * (1 << k) % mod) % mod;
//printf("%lld
%lld", ans1, ans2);
}
printf("%lld
%lld", ans1, ans2);
return 0;
}
int read()
{
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
(T2)
题目描述
有 (n) 个人想要加入圣战, 每个人需要选择一个阵营加入.
但他们私下有 (m) 对敌对关系, 有敌对关系的两个人不会加入同一个阵营.
很快, 他们发现这会让他们难以加入到圣战中, 于是有一对敌人和好了, 即去除了一对敌对关系.
请找出去除哪一对关系后, 能找到一种加入阵营的方案, 使得剩余有敌对关系的人都不在同一个阵营.
为了避免输出文件过大, 你只需要输出所有符合题意的关系编号的异或和.
(Solution)
期望得分-(30pts)，错误：
(1.)要把 (next) 写作 (nxt) 之类，避免关键词
(2.) (dfs) 写错了
(90pts)做法：
根据观察分析可得出，拆去一条边后合法仅为剩下的图中无奇环
则做一个 (dfs) 找奇环，记录奇环数量 (K)，最后枚举边，若边被奇环覆盖数 (=) (K)，即合法
主要是在如何找奇环，我写的 (dfs) 少了一句关键的 (vis[x] = 0)，就是在搜完这个点后要将它复原，不然会有奇环搜不到
至于为什么是 (90pts)，emm有两个点一直不对，但是这个算法应该是没问题（题解和这个基本是一样的），还在搜索错误中
(upd(4/11):) 其实是对的，数据错了
(Code)
#include<bits/stdc++.h>
#define F(i, x, y) for(int i = x; i <= y; ++ i)
using namespace std;
int read();
const int N = 2e6 + 5;
int n, m, x, y;
int ans1, ans2, K;
int head[N], cnt = 1, ver[N << 1], nxt[N << 1];
int vis[N], dep[N], pre[N], kk[N];
void add(int x, int y)
{
ver[++ cnt] = y, nxt[cnt] = head[x], head[x] = cnt;
}
void dfs(int x, int ffa, int y)
{
if(vis[x] && (dep[ffa] - dep[x]) % 2 == 0)
{
++ K, ++ kk[y], ++ kk[y ^ 1];
while(ffa != x) ++ kk[pre[ffa]], ++ kk[pre[ffa] ^ 1], ffa = ver[pre[ffa] ^ 1];
return;
}
if(vis[x]) return;
dep[x] = dep[ffa] + 1, pre[x] = y, vis[x] = 1;
for(int i = head[x]; i; i = nxt[i])
if(ver[i] != ffa) dfs(ver[i], x, i);
vis[x] = 0;
}
int main()
{
freopen("crusade.in","r",stdin);
freopen("crusade.out","w",stdout);
n = read(), m = read();
F(i, 1, m) x = read(), y = read(), add(x, y), add(y, x);
F(i, 1, n) if(! vis[i]) dfs(i, 0, 0);
for(int i = 2; i <= cnt; i += 2) if(kk[i] == K) ++ ans1, ans2 ^= (i / 2);
printf("%d
%d
", ans1, ans2);
return 0;
}
int read()
{
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
(T3)
题目描述
有一个长度为 (n) 的正整数序列 (a) , 你需要进行 (m) 次操作, 每次操作有如下两种类型:
修改: ((L, R, x)) , 表示将区间 ([L, R]) 内的 (ai) 都乘上一个正整数 (x) .
询问: ((L, R)) , 询问区间 ([L, R]) 内每个数的乘积的欧拉函数值, 即 φ(∏Ri=Lai)
(Solution)
300以内只有62个质数，所以可以用 (long long) 类型的数记录包含的质数，用线段树维护
提前预处理好质数，逆元，一些欧拉函数相关
(Code)
调了两个多小时还是错的$kk$
总结
今天考试惨烈地暴零了，原因有以下几点：
(1.)菜，所以花时间想正解基本上等于浪费时间了
(2.)连续几次看错题，例如 (t2) 最开始看错题花了一个小时写错误的算法，(t1) 把或看作异或等，还是考试不够专注，没有全身心投入
(3.)破罐子破摔心理不可有，一旦开考就不要想有的没的，只要多拿分，不管情况是怎样，一定要尽可能拿更高得分
(4.)完整地搞定一道题（至少保证它能拿到想要的分数）后再去开下一道，今天就是 (t1) 暴力写完了，居然放在那里没调，打算把第三题写完一起调，最后都暴零了