A
初始情况(1) ~ (n)堆分别有 (1) ~ (n) 个糖果，第(i)次操作给除了所选堆的糖果数 (+ i), 找到一种方案可以使得所有堆糖果数相同，输出操作次数和每次选定不变的堆.
选定当前堆不变，其他堆(+ i)等价于将选定堆(-i), 故只需要考虑如何将所有堆减到(0)即可, 即操作(n)次，第(i)次选择第(i)堆.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;
scanf("%d", &T);
while(T -- )
{
int n;
scanf("%d", &n);
printf("%d
", n);
for(int i = 1; i <= n; ++ i) printf("%d%c", i, i == n ? '
' : ' ');
}
return 0;
}
B
给一个矩阵，每次操作可以选中相邻的两个元素，将他们都乘(-1), 可以进行无限次操作， 问矩阵中所有元素和的最大值
负号可以两两抵消，故考虑负号的个数，如果是偶数，全部抵消，求所有元素绝对值的和；如果是奇数， 最后剩一个负号， 选择绝对值最小的为负数即可
#include <bits/stdc++.h>
using namespace std;
const int N = 10 + 3;
int n, m;
int main()
{
int T;
scanf("%d", &T);
while(T -- )
{
int x, sum = 0, num = 0, minx = 1e9;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j)
{
scanf("%d", &x);
sum += abs(x);
num += x < 0;
minx = min(minx, abs(x));
}
if(num & 1) printf("%d
", sum - 2 * minx);
else printf("%d
", sum);
}
return 0;
}
C
给(n)个数(a_1) ~ (a_n)，给定(W), 判断能否从中选出几个数使得它们的和(sum)满足: (leftlceildfrac{W}{2} ight ceil le sum le W),如果可以，输出选择的数的编号
从大到小枚举即可，若本身超过(W)跳过即可，若不足(leftlceildfrac{W}{2} ight ceil), 继续枚举求和, 两个(< leftlceildfrac{W}{2} ight ceil)的数求和不会超过(W)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 20;
int n;
LL W;
pair w[N];
int main()
{
int T;
scanf("%d", &T);
while(T -- )
{
scanf("%d%lld", &n, &W);
for(int i = 1; i <= n; ++ i)
{
scanf("%d", &w[i].first);
w[i].second = i;
}
sort(w + 1, w + n + 1, greater>());
vector vec;
LL sum = 0;
for(int i = 1; i <= n; ++ i)
{
if(w[i].first > W) continue;
sum += w[i].first; vec.push_back(w[i].second);
if(sum >= (W + 1) / 2) break;
}
if(sum < (W + 1) / 2) { printf("-1
"); continue; }
printf("%d
", vec.size());
for(auto x: vec) printf("%d ", x);
puts("");
}
return 0;
}
D
给两个字符串，定义(S(C, D) = 4 imes LCS(C, D) - left|C ight| - left|D ight|), 求两个字符串的子串(C, D)的最大(S)
定义(f[i][j])为以(A_i)和(B_j)作为结尾的最大值
当(A_i = B_j)时， (f[i][j]) 可以从 (f[i - 1][j - 1] + 4 - 2)转移
当(A_i e B_j)时, (f[i][j]) 可以从 (f[i - 1][j] - 1) 和 (f[i][j - 1] - 1)转移
#include <bits/stdc++.h>
using namespace std;
const int N = 5000 + 20;
char a[N], b[N];
int n, m, f[N][N];
int main()
{
scanf("%d%d", &n, &m);
scanf("%s%s", a + 1, b + 1);
int res = 0;
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j)
{
if(a[i] == b[j])
f[i][j] = max(f[i][j], f[i - 1][j - 1] + 2);
f[i][j] = max(f[i][j], max(f[i - 1][j], f[i][j - 1]) - 1);
res = max(f[i][j], res);
}
printf("%d
", res);
return 0;
}
E
对于第(i)个数来说，找到(a_i xor a_j)最小的连边((i, j))，只有最后形成一棵树才是合法的，问最少删去几个数，可以使得序列合法，(a_i)互不相同
01 trie建树，每次分叉的时候，只保留一个子树和另一个子树的一条链，递归求最大可保留点数即可.
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 * 31 + 10;
int son[N][2], idx, n;
void insert(int x)
{
int p = 0;
for(int i = 30; i >= 0; -- i)
{
int u = x >> i & 1;
if(!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
}
int query(int p)
{
if(!son[p][1] && !son[p][0]) return 1;
else if(!son[p][1]) return query(son[p][0]);
else if(!son[p][0]) return query(son[p][1]);
else return max(query(son[p][0]) + 1, query(son[p][1]) + 1);
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++ i)
{
int x;
scanf("%d", &x);
insert(x);
}
printf("%d
", n - query(0));
return 0;
}
2020.11.17