A
题意：
给出一个数组，让你重新排序，\(\sum_{i=1}^{n-1}a_i-a_{i+1}\) 最大。
做法：
显然从小到大排序即可，答案就是最大值减去最小值。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,MOD=998244353;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;cin>>T;
while(T--)
{
int n,minn=0x3f3f3f3f,maxn=0;
cin>>n;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
minn=min(minn,x);
maxn=max(maxn,x);
}
cout<<maxn-minn<<endl;
}
}
B
题意：
给出一个的 \(n\times n\) 网格图，在所有的 \(4n-2\) 条对角线中，要求至少 \(k\) 条对角线上存在被涂黑的格子。问至少几个格子被涂黑。
做法：
使用优先涂第一行和最后一行（除第一列和最后一列）的方法可以做到每次涂都增加两个符合要求的对角线，最后两次涂色只增加 \(1\) 。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,MOD=998244353;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;cin>>T;
while(T--)
{
int n,k;cin>>n>>k;
int ans=(k+1)/2;
if(k==4*n-2) ans++;
cout<<ans<<endl;
}
}
C
题意：
假如你在进行一个赌注游戏，给定三个整数 \(k,m,n\) ，游戏有无限多局， \(k\) 表示赢下一局能翻 \(k\) 倍， \(m\) 表示连输的局数少于 \(m\)，\(n\) 表示初始的钱。问是否存在一种策略，使得在无限多局之后能够赚到无数多的钱。
做法：
电影《孤注一掷》中提到过，在一个赌局中，如果每赢一局钱翻倍，那么只要不断参加这个赌局，每次投入的前是上一次的两倍，直到赢下一局，就可以保证赚钱。（前提是可能赢）
所以这道题的策略其实就是保证自己如果赢了一局，就能把前面的亏损全部赚回来并且赚更多的钱。假设之前已经投入了 \(s\) 的钱，那么下一局就要投入 \(\lceil\frac{s+1}{k-1}\rceil\) 的钱。
计算自己的钱能否支撑到必定赢的第 \(m\) 局即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,MOD=998244353;
int n;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;cin>>T;
while(T--)
{
int n,x,k;cin>>k>>x>>n;
int ans=1,sum=1;
bool flag=1;
while(x--)
{
int tmp=ceil((sum+1.0)/(k-1));
sum+=tmp;
if(sum>n) flag=0;
}
cout<<(flag?"Yes":"No")<<endl;
}
}
D
题意：
给定一棵树，你可以给其中一些点标记（可以不标记），限制是对于每一条简单路径不存在三个被标记的点。求做标记的方案数。
做法：
dp，发现对于节点 \(x\) 的一棵以 \(y\) 为根子树中，只需要明确 \(y\) 子树中是否存在标记点，是否存在一对有祖先关系的标记点，就可以进行转移，与 \(y\) 子树内标记点的具体分布无关。
设 \(f[x][0/1/2]\) 表示以 \(x\) 为根的子树中，从 \(x\) 向下的一条链中标记点最多的链上有 \(0/1/2\) 个标记点的合法方案数。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,MOD=998244353;
vector<int> to[N];
int f[N][3];
void dfs(int x,int fa)
{
f[x][0]=1,f[x][1]=1,f[x][2]=0;
int mul1=1,mul2=1,sum1=0,sum2=0;
for(int y:to[x])
{
if(y==fa) continue;
dfs(y,x);
mul1=mul1*(f[y][1]+1)%MOD;
mul2=mul2*(f[y][2]+f[y][1]+1)%MOD;
sum1=(sum1+f[y][1])%MOD;
sum2=(sum2+f[y][2])%MOD;
}
f[x][1]=mul1;
f[x][2]=(sum1+sum2)%MOD;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;cin>>T;
while(T--)
{
int n;cin>>n;
for(int i=1;i<n;i++)
{
int u,v;cin>>u>>v;
to[u].push_back(v);
to[v].push_back(u);
}
dfs(1,0);
cout<<(f[1][0]+f[1][1]+f[1][2])%MOD<<endl;
for(int i=1;i<=n;i++) to[i].clear();
}
}
E
题意：
给定一棵树，和 \(m(m\leq 20)\) 对点对，要求标记一些边，使得每一对点对表示的简单路径上至少有一条边被标记。问最少要标记几条边。
做法：
由于 \(m\) 很小，想到点对集合可以压成一个二进制数。所以可以直接将 \(m\) 条简单路径覆盖到树上，再把每一条树边能覆盖到的点对集合拿出来，经过去重后不同的集合的数量和 \(m\) 同级，最后直接用 \(O(2^m m)\) 的状压dp求出即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,MOD=998244353;
int n;
vector<int> to[N];
int tag[N],f[1<<21],po[N],tot;
void dfs(int x,int pre)
{
for(int y:to[x])
{
if(y==pre) continue;
dfs(y,x);
tag[x]^=tag[y];
}
po[++tot]=tag[x];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
to[u].push_back(v);
to[v].push_back(u);
}
int m;cin>>m;
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
tag[u]^=(1<<i-1);
tag[v]^=(1<<i-1);
}
dfs(1,0);
sort(po+1,po+tot+1);
tot=unique(po+1,po+tot+1)-po-1;
for(int i=1;i<(1<<m);i++) f[i]=0x3f3f3f3f;
f[0]=0;
for(int i=0;i<(1<<m);i++)
for(int j=1;j<=tot;j++)
f[i|po[j]]=min(f[i|po[j]],f[i]+1);
cout<<f[(1<<m)-1]<<endl;
for(int i=1;i<=n;i++) to[i].clear(),tag[i]=0;
tot=0;
}
}