写在前面
我TM期中考试直接爆炸啊啊啊啊啊啊啊啊啊啊啊啊
裂开来
题解
A
题目给出了一个由(n)种动物构成的圈，然后有(m)个小朋友，每个小朋友都有自己喜欢的动物和讨厌的动物，但是每个小朋友只能看到连续的(5)个围栏，当且仅当
至少有一个他喜欢的动物被保留 or 至少有一个他讨厌的动物被移走
他就会高♂性，现在你可以决定移走那些动物，使得高♂性的小朋友最多
我们考虑状压，看到题目中5这个数字特别小，可以拿来状压！
我们令(f[i][j])表示当(i,i+1,i+2,i+3,i+4)状态为(j)时的开心的小朋友的最大值
转移式子f[j][s]=max(f[j-1][(s&15)<<1],f[j-1][(s&15)<<1|1])+num[j][s]
之后我们要预处理出(num[i][j])表示(i,i+1,i+2,i+3,i+4)状态为(j)时开心的小朋友数
怎么处理，很简单
for (int i = 1; i <= m; i++) {
fear = 0; like = 0;
a = read (); b = read (); c = read ();
for (int j = 1; j <= b; j++) {
x = read (); x = (x - a + n) % n;
fear |= (1 << x); // 害怕的动物
}
for (int j = 1; j <= c; j++) {
x = read (); x = (x - a + n) % n;
like |= (1 << x); // 喜欢的动物
}
for (int j = 0; j < 32; j++) {
if ((j & fear) || (~j & like)) num[a][j]++; // 直接判断累加就行
}
}
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
int n, m, ans;
int num[N][35], f[N][35];
int a, b, c, like, fear, x;
inline int read () {
int tot = 0, f = 1; char c = getchar ();
while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar (); }
while (c >= '0' && c <= '9') { tot = tot * 10 + c - '0'; c = getchar (); }
return tot * f;
}
signed main () {
n = read (); m = read ();
for (int i = 1; i <= m; i++) {
fear = 0; like = 0;
a = read (); b = read (); c = read ();
for (int j = 1; j <= b; j++) {
x = read (); x = (x - a + n) % n;
fear |= (1 << x);
}
for (int j = 1; j <= c; j++) {
x = read (); x = (x - a + n) % n;
like |= (1 << x);
}
for (int j = 0; j < 32; j++) {
if ((j & fear) || (~j & like)) num[a][j]++;
}
}
for (int i = 0; i < 32; i++) {
memset (f[0], -0x3f, sizeof (f[0]));
f[0][i] = 0;
for (int j = 1; j <= n; j++) {
for (int s = 0; s < 32; s++) {
f[j][s] = max (f[j - 1][(s&15)<<1], f[j - 1][(s&15)<<1|1]) + num[j][s];
}
}
ans = max (ans, f[n][i]);
}
printf ("%d
", ans);
return 0;
}
B
给定一个(n*m)的矩阵，每个方格有花，现在这个矩阵上有一些地方已经被建造成建筑物，然后你要建造一些水泥路，使得这些建筑物都可以互相到达，现在要求毁掉最少的花，来完成这个任务，还要给出一种方案
考虑(DP)，看到(k)这么小，我们可以直接把(k)状压起来，令(f[i][j][k])表示当前楼房链接状态为(k)且水泥覆盖了(i,j)点的最小花费。
艹，之前写完没保存，TMD又要再写一遍题解
稍加思索即可得知最后形成的一定是一棵树
所以我们的每一步必定会从它的两个互不相交的子集中转移过来
[f[i][j][S]=max{f[i][j][sub]+f[i][j][S^sub]-a[i][j]}
]
为什么这里要减去(a[i][j])，是因为两个子集的值也包含这个(a[i][j])
但是这还没完，我们会发现，这只是将两个集合合并，并没有涉及到从上下左右四个方向转移过来，所以我们还要来一个转移
[f[i][j][S]=max{f[x][y][S]+a[i][j]}
]
值得一提的是，这里的最短路并非常规最短路，因为我们这是转移，对于每一个点都要保证转移到，所以需要对于每个点都进行(n*m)次转移，保证其正确性
接下来我们考虑怎么维护方案
显然，可以想到开一个前缀数组，记录前缀，记录方案时递归即可
但是这里的转移分两种，分别是最短路转移和子集的转移。
所以我们要用一种特殊的方法来记录。来看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 150;
int dx[5] = {0, 1, -1, 0, 0}, dy[5] = {0, 0, 0, 1, -1};
int f[N][N][N], n, m, k, x, y;
int a[N][N];
int pre[N][N][N][3];
/*
这个，就是我们用来记录方案的数组
pre[i][j][S][0]记录是从哪种方式转移过来的
pre[i][j][S][1]和pre[i][j][S][2]
如果是最短路转移，那就记录坐标
如果是两个子集转移，那就记录两个子集
*/
bool ans[N][N];
inline int read () {
int tot = 0, f = 1; char c = getchar ();
while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar ();}
while (c >= '0' && c <= '9') { tot = tot * 10 + c - '0'; c = getchar (); }
return tot * f;
}>
inline void print (int x, int y, int S) {
ans[x][y] = 1;
if (pre[x][y][S][0] == 0) {
print (pre[x][y][S][1], pre[x][y][S][2], S);
}
if (pre[x][y][S][0] == 1) {
print (x, y, pre[x][y][S][1]);
print (x, y, pre[x][y][S][2]);
}
}
signed main () {
n = read (); m = read (); k = read ();
memset (f, 0x3f, sizeof (f));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) a[i][j] = read ();
for (int i = 0; i < k; i++) {
int x = read () - 1, y = read () - 1;
f[x][y][1<<i] = a[x][y];
pre[x][y][1<<i][0] = 2;
}
for (int S = 0; S < (1 << k); S++) {
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
for (int subS = S; subS; subS = (subS - 1) & S) { // 合并两个子集的贡献
int tmp = f[i][j][subS] + f[i][j][S^subS] - a[i][j];
if (f[i][j][S] > tmp) {
f[i][j][S] = tmp;
pre[i][j][S][0] = 1;
pre[i][j][S][1] = subS; // 记录转移的子集
pre[i][j][S][2] = subS^S;
}
}
for (int T = 0; T < n * m; T++) { // 进行n*m次的最短路处理
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
for (int k = 1; k <= 4; k++) {
int ax = i + dx[k], ay = j + dy[k];
if (ax < 0 || ay < 0 || ax >= n || ay >= m) continue;
int tmp = f[ax][ay][S] + a[i][j]; // 上下左右直接转移过来
if (f[i][j][S] > tmp) {
f[i][j][S] = tmp;
pre[i][j][S][0] = 0;
pre[i][j][S][1] = ax; // 记录转移来自的坐标
pre[i][j][S][2] = ay;
}
}
}
}
int Ans = 1e9;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// cout<<f[i][j][(1 << k) - 1];
Ans = min (Ans, f[i][j][(1 << k) - 1]);
}
}
printf ("%d
", Ans);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (f[i][j][(1 << k) - 1] == Ans) {
print (i, j, (1 << k) - 1);
for (int x = 0; x < n; x++) {
for (int y = 0; y < m; y++)
putchar (ans[x][y] ? 'X': '.');
puts("");
}
return 0;
}
}
return 0;
}
C
D
E
F
G
这是一道神奇的题目......
题目(yjf)魔改，我都不知道变成什么样子了......
算了，直接讲一下某种典型例题的方法
给出一个序列，和一些操作，每次对于一个区间染色，然后所有操作完成后输出每个数被染色的color最大值，何为color最大值？每次给出的染色操作的颜色是一个数字，需要取(max)
我们要用(O(n))的复杂度做掉这题。
我们先考虑暴力做法：对于每一个操作，我们都暴力枚举区间，这样是(O(n^2*m))的
考虑将操作离线，每次维护左右端点，逐渐移动，最坏情况下还是可以卡到(O(n^2))
然后我们想办法让染过色的点不再被染色，当然，这之前需要将操作用桶排序将颜色从大到小排起来
然后我们对于每个点，开个并查集，一开始指向自己，并查集的根即为这个点（包括自己）右边第一个没有被染色的点
这样，我们每次操作就可以跳过被染色过的点，每个点只会被访问一次，所以复杂度是(O(n))的
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 5, MOD = 999983;
int n, m, k;
ll a[N];
int sum[N];
int fa[N], siz[N];
vector <pair <int, int> > bo[N];
inline int read () {
int tot = 0, f = 1; char c = getchar ();
while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar (); }
while (c >= '0' && c <= '9') { tot = tot * 10 + c - '0'; c = getchar (); }
return tot * f;
}
inline int qpow (ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
inline int find (int k) {
if (k == fa[k]) return k;
else return fa[k] = find (fa[k]);
}
int Ec[N];
inline void init () {
for (int i = 1; i <= 1000000; i++) {
for (int j = 1; j * i <= 1000000; j++) {
sum[i * j] ++;
}
}
for(int i = 1; i <= 500; ++i) Ec[i] = qpow(i, k);
}
signed main () {
n = read (); m = read (); k = read ();
init ();
for (int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1; fa[n + 1] = n + 1;
for (int i = 1; i <= m; i++) {
int l = read (), r = read (),k = read ();
bo[Ec[sum[k]]].push_back (make_pair (l, r));
}
for (int i = N - 1; i >= 1; i--) {
for (int j = 0; j < bo[i].size (); j++) {
int L = bo[i][j].first, R = bo[i][j].second;
int pos = find (L);
while (pos <= R) {
a[pos] = i;
int fx = find (pos), fy = find (pos + 1);
if (fx != fy) {
if (siz[fx] >= siz[fy]) {
fa[fx] = fy;
siz[fx] += siz[fy];
}
else {
fa[fy] = fx;
siz[fy] += siz[fx];
}
}
pos = find (pos);
}
}
}
for (int i = 1; i <= n; i++) {
printf ("%d ", a[i]);
}
return 0;
}