预计得分500，实际得分400，挂了20 + 50 + 30分。
T1 移动 move
题目描述：
\(n\)个二维向量\((X_{i}, Y_{i})\)，随便选择\(k\)个，其中\(0<=k<=n\)，起点是\((0, 0)\)，每次移动后的位置是\((s+x_{i},t+y_{i})\)，求终点\(|s| + |t|\)的最大值。
分析：
分类讨论。\((X_{i}, Y_{i})\)可以分到四个象限之中去，然后我们的\((s, t)\)也有在四种象限的情况。然后我们贪心的讨论，如果加入点的坐标和自己所属象限的全部相反，那么一定不用讨论，如果是完全一样的，那么直接加上，如果有一个不一样，那么我们可以讨论一下可以选的是谁，选择更优还是不选择更优。四个象限全部写完实在是太复杂了，所以我们用函数。
但是由于我的智慧，最后一个分类讨论是\(solve(-1, -1)\),我写得是\(solve(1, 1)\)居然还有八十分，我太感动了！！！
#include <bits/stdc++.h>
using namespace std;
const int N = 600005;
typedef long long ll;
int n;
ll x[N], y[N], sumx = 0, sumy = 0, ans = 0;
int pdx[N], pdy[N];
ll Abs(ll a) {return a < 0 ? -a : a; }
void solve(int a, int b)
{
sumx = 0, sumy = 0;
for (int i = 1; i <= n; ++ i)
{
if(pdx[i] != a && pdy[i] != b) continue;
if(pdx[i] == a && pdy[i] == b) sumx += x[i], sumy += y[i];
else if(pdx[i] == a && Abs(x[i]) > Abs(y[i])) sumx += x[i], sumy += y[i];
else if(pdy[i] == b && Abs(y[i]) > Abs(x[i])) sumx += x[i], sumy += y[i];
}
ans = max(ans, Abs(sumx) + Abs(sumy));
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++ i)
{
scanf("%lld %lld", &x[i], &y[i]);
if(x[i] < 0) pdx[i] = -1;
else pdx[i] = 1;
if(y[i] < 0) pdy[i] = -1;
else pdy[i] = 1;
}
solve(1, 1);
solve(1, - 1);
solve(- 1, 1);
solve(- 1, - 1);
printf("%lld", ans);
return 0;
}
T2 双色图案 bicoloring (CF 1051D)
分析：
这是一个dp，状态就是枚举前面的块是什么样子，可能是\(01\)，\(10\)，\(11\)，\(00\)，然后枚举后面的状态是什么样子，可能是\(01\)，\(10\)，\(11\)，\(00\).然后看\(16\)种匹配方式分别会造成怎么样的收益就可以了。Ca喜欢节约空间，所以Ca使用了滚动数组。显然数组应该是要开\(long long\)的，但是Ca为了节约空间，我们在计算过程中开\(long long\)，数组还是使用\(int\)类型。
计算时\((long long) + (int)\)类型计算出来的答案是\((long long)\),如果使用\((int) + (int) + (long long)\)，计算前面两个是\((int)\)，后面会成为\((long long)\),但你无法保证前面不会炸，\((long long)((int) + (int))\)，会先计算里面的\((int)\),再变成\((long long)\)，但是显然你无法保证里面的计算不会炸掉。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
const int mod = 998244353;
int dp[2][2105][2][2];
int main()
{
scanf("%d %d", &n, &k);
dp[1][2][0][1] = 1, dp[1][1][0][0] = 1, dp[1][1][1][1] = 1, dp[1][2][1][0] = 1;
for (int i = 2; i <= n; ++ i)
{
int x = (i & 1), y = x ^ 1;
for (int j = 1; j <= k; ++ j)
{
dp[x][j][0][0] = dp[x][j][0][1] = dp[x][j][1][0] = dp[x][j][1][1] = 0;
for (int a = 0; a <= 1; ++ a)
{
for (int b = 0; b <= 1; ++ b)
{
for (int c = 0; c <= 1; ++ c)
{
for (int d = 0; d <= 1; ++ d)
{
if(a != b)
{
if(c != a && d != b && j >= 2) dp[x][j][c][d] = (ll)(dp[x][j][c][d] + dp[y][j - 2][a][b]) % mod;
else dp[x][j][c][d] = (ll)(dp[x][j][c][d] + dp[y][j][a][b]) % mod;
}
else
{
if(c == a && d == b) dp[x][j][c][d] = (ll)(dp[x][j][c][d] + dp[y][j][a][b]) % mod;
else dp[x][j][c][d] = (ll)(dp[x][j][c][d] + dp[y][j - 1][a][b]) % mod;
}
}
}
}
}
}
}
printf("%lld", (((ll)dp[n & 1][k][0][1] + dp[n & 1][k][1][0] + dp[n & 1][k][1][1] + dp[n & 1][k][0][0]) % mod + mod) % mod);
return 0;
}
T3 星际货运 express
最小生成树 + 贪心。
最小生成树要选择代价最小的边，题目的性质也保证了是选择三元组中最小的，所以这两个是不冲突的，如果有重复，用并查集找一下就可以了。但是一口气放\(N^2\)条边显然是空间时间都去世，所以说我们要贪心一下。单独的\(x\),\(y\),\(z\)最小的肯定是优先产生贡献，所以可以把三种分别弄出来排序。大的减去小的一定是正数。这样选出来的后面减去前面一个的边一定可以围城一棵树，因为所有的点都有一个有关系的节点，并不是孤立的。
关于最小生成树的证明：假设\(T\)是一棵最小生成树，我们并不选择所有最小的可以选择的边构成它，也就是存在\((u, v)\),\(w[u][v] < w[u][r]\)，其中\((u, r)\in T\)，我们完全可以把\((u, r)\)断掉，因为是一棵树，所以u和r就不再联通，因为在满足之前选\((u, v)\), \(u\), \(v\)是不连通的，所以再连起来是完全可以的成为一棵新的树的，并且答案会更优秀。
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
typedef long long ll;
ll ans = 0;
int n, fa[N], cnt = 0, tot = 0;
int findset(int x)
{
if(fa[x] == x) return x;
return fa[x] = findset(fa[x]);
}
struct node
{
ll w;
int id;
}px[N], py[N], pz[N];
struct edge
{
int u, v;
ll w;
}e[N << 2];
bool cmp(node a, node b) {return a.w < b.w; }
bool ecmp(edge a, edge b) {return a.w < b.w; }
void Kruskal()
{
sort(e + 1, e + cnt + 1, ecmp);
for (int i = 1; i <= cnt; ++ i)
{
int x = findset(e[i].u), y = findset(e[i].v);
if(x == y) continue;
ans = ans + e[i].w;
fa[x] = y, tot ++;
if(tot == n - 1) break;
}
return ;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++ i)
{
fa[i] = i;
scanf("%lld %lld %lld", &px[i].w, &py[i].w, &pz[i].w);
px[i].id = py[i].id = pz[i].id = i;
}
sort(px + 1, px + n + 1, cmp);
sort(py + 1, py + n + 1, cmp);
sort(pz + 1, pz + n + 1, cmp);
for (int i = 2; i <= n; ++ i)
{
e[++ cnt].w = px[i].w - px[i - 1].w, e[cnt].u = px[i - 1].id, e[cnt].v = px[i].id;
}
for (int i = 2; i <= n; ++ i)
{
e[++ cnt].w = py[i].w - py[i - 1].w, e[cnt].u = py[i - 1].id, e[cnt].v = py[i].id;
}
for (int i = 2; i <= n; ++ i)
{
e[++ cnt].w = pz[i].w - pz[i - 1].w, e[cnt].u = pz[i - 1].id, e[cnt].v = pz[i].id;
}
Kruskal();
printf("%lld", ans);
return 0;
}
T4 圆数 round
分析：
其实不难发现是一个数位dp的模板(以前觉得数位dp好难，简直不是人做的)，但是就是不能理解这个奇怪的东西，其实它就是一个搜索的记忆化。我们定义\(dp[i][a][j][k][b]\)表示还剩下i个数字没有填；剩下的数字可不可以随便选择0可以，1不可以；一共填充了几个1；一共填充了几个0；前面有没有前导0。如果我们遇到了一样的情况就可以直接返回。一共有\(63 \times 63 \times 63\times 2\times2\)种情况，没遇到就更新，遇到了就返回，所以说复杂度就是这些状态的总数量。
对于此题中每一个不一样的数字，我们都需要重新更新，因为对应状态中是上限的条件会产生变化，因为不同的数字上限是不样的，所以答案也会产生一定的变化。
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
typedef __int128 ll;
void read(ll &x)
{
char c = getchar(); x = 0;
while(c < 48 || c > 57) {c = getchar(); }
while(c >= 48 && c <= 57) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }
return ;
}
void write(ll x)
{
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
return ;
}
ll l, r, ans = 0, dp[65][2][65][65][2];
int a[N], cnt = 0;
ll dfs(int pos, bool limit, int sm1, int sm0, bool pre)
{
if(dp[pos][limit][sm1][sm0][pre] != -1) return dp[pos][limit][sm1][sm0][pre];
if(pos + sm0 < sm1) return 0;
if(pos == 0)
{
if(sm0 >= sm1) return 1;
return 0;
}
ll sum = 0;
bool up = limit ? a[pos] : 1;
for (int i = 0; i <= up; ++ i)
{
sum += dfs(pos - 1, limit & (i == up), sm1 + (i == 1), sm0 + (i == 0 && !pre), pre & (i == 0));
}
if(dp[pos][limit][sm1][sm0][pre] == -1) dp[pos][limit][sm1][sm0][pre] = sum;
return sum;
}
ll solve(ll x)
{
cnt = 0;
for (int i = 0; i <= 63; ++ i)
{
for (int j = 0; j <= 63; ++ j)
{
for (int k = 0; k <= 63; ++ k)
{
for (int a = 0; a <= 1; ++ a)
{
for (int b = 0; b <= 1; ++ b) dp[i][a][j][k][b] = -1;
}
}
}
}
if(x == 1 || x == 0) return 1;
while(x)
{
a[++ cnt] = x & 1;
x >>= 1;
}
return dfs(cnt, true, 0, 0, true);
}
int main()
{
read(l), read(r);
write(solve(r) - solve(l - 1));
return 0;
}