A：
?题意：给一个质数n，求得一个数m，使得n+m不为素数。?
解析：质数n+本身，为2*n，其一定不为质数。所以答案可以是它本身
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
void solve(){
int n;cin>>n;
cout<<n<<"\n";
}
int main(){
int T;cin>>T;
while(T--) solve();
}B:?
题意：给定N个n*m的长方形，要求每个长方形的一条边都必须与x轴重合，长方形的边可以重合，但不允许长方形重叠。问怎样放才能使得拼后的长方形周长最小。
分析：贪心。我们发现，重合于x轴的边，是固定的，所以我们只需要把每个长方形最小的边于x重合，这里所得的宽一定是最小的，同理我们可以发现，最终所得的高一定是等于最大的边的。这里给个图方便读者理解。（所求的周长，即为红色长方形的周长）
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+10;
void solve(){
int n;cin>>n;
int maxx=-1;int b=0;
for(int i=1;i<=n;i++){
int x,y;cin>>x>>y;
if(x<y) swap(x,y);
maxx=max(maxx,x);
b+=y;
}
cout<<maxx+maxx+b+b<<"\n";
}
signed main(){
int T;cin>>T;
while(T--) solve();
}题意：给定n个石头和三个空背包，将n个石头放入三个背包中。从三个背包中拿出三个石头，假设冲三个包中拿出的石头的质量为 a,b,c ，最终的分数为 |a?b|+|b?c| ，取石头的人会最小化这个值，请问如何分配石头可以使得最终的分数最大。
分析：我们对这个分数公式进行分析，会发现，区间[a,c]，b是到两个端点距离的和。但是我们发现，另一个人会最小化这个分数。因此对于所有的石头我们先排好序。假如我们在b中放入了质量最小的石头，如果希望最大，在a背包中放入质量最大的石头，我们至少会获得 max?min 的权值，但是另一边 b?c 我们只能获得?次小值?最小值 的贡献。b背包作为权值的源点，其取值必然是一个极值。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+10;
int a[N];
void solve(){
int n;cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
int res=0;
//case 1:前缀
for(int i=1;i<=n-2;i++)
res=max(res,a[n]-a[i]+a[i+1]-a[i]);
//case 2:后缀
for(int i=n;i>=3;--i)
res=max(res,a[i]-a[i-1]+a[i]-a[1]);
cout<<res<<"\n";
}
signed main(){
int T;cin>>T;
while(T--) solve();
}?D：
?（这个图是GIF....见谅一下..）
题意：给定一个 n?m 的矩阵，在 [1,1]的位置放置了 k 个棋子， k 个棋子是 1?k 的排列，给定这些棋子从上到下放置的顺序。每次可以移动最顶端的一个棋子到相邻的位置，棋子除了在起点和终点都不能重叠。求 k 个棋子最终能够在 [n,m] 处从上到下以 1?k 的顺序叠放好。
分析：我们把不能一次放到终点的棋子先放在一边。然后每次遇到能放的棋子就直接过去。我们能够停放的位置一共有 n?m?2 个，所以，最终我们只需要判断，目前所停靠棋子的数量是否大于n*m-2个即可。这里选择用树状数组维护这个值
简要解释：因为起点终点位置不能进行重叠，所以其余可以重叠的位置个数就肯定是：n*m-2个，除开起点和终点，那么一定是可以通过操作到达目的的！
代码：?
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+10;
int a[N],tree[N];
int n,m,k;
int lowbit(int x){
return x&(-x);
}
int query(int x) {
int res = 0;
for(x; x ; x -= lowbit(x))
res += tree[x];
return res;
}
void add(int x, int v) {
for(x; x <= k ; x += lowbit(x))
tree[x] += v;
}
void solve(){
cin >> n >> m >> k;
for(int i = 1; i <= k ; i ++ ) cin >> a[i], tree[i] = 0;
bool pd = true;
for(int i = 1; i <= k ; i ++ ) {
if(query(a[i]) >= n * m - 3) pd = false;
add(a[i], 1);
}
if(pd) cout << "YA\n";
else cout << "TIDAK\n";
}
signed main(){
int T;cin>>T;
while(T--) solve();
}?E：
题意：给定一个树，我们的目标是构造树的点权。每次操作可以选择一个叶子节点，并且摘掉这个叶子节点并且获得叶子节点的权值。每次摘叶子的时候，如果你摘的叶子的权值比他的父节点小，那么父节点的权值就会变成这个叶子的权值，一直进行到树被摘完。最终我们会获得摘叶子的序列，起价值是该序列的最长非下降子序列。请合理的构造树上的权值，最大化操作后的价值。
分析：我们首先考虑如何摆放叶子是最优的。因为求的是最长的非下降子序列，因此深度越深的节点一定点权越小。我们从叶子开始摘，最小的叶子会不断影响其父节点。根节点必然放最大的权值，因此最小的那个权值最终一定会影响到根节点。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> e[N];
int n;
int f[N][2];//定义：0为不选当前节点，不把当前节点作为递增序列的情况，1则反之
void dfs(int u){
if (e[u].size() == 0){//如果不存在子树，则长度就是1（本身）
f[u][1] = 1;
return;
}
for (auto x : e[u]){//枚举子树
dfs(x);
f[u][0] +=max(f[x][0], f[x][1]);//不选：则可以选择所有子树
f[u][1] = max(f[u][1], f[x][1] + 1);//选：则序列的长度会受限
}
}
int main(){
ios ::sync_with_stdio(false);cin.tie(0);
cin >> n;
for (int i = 2; i <= n; i++){//建树
int x;
cin >> x;
e[x].push_back(i);
}
dfs(1);
cout << max(f[1][0], f[1][1]) << "\n";
}?
?