Codeforces Round #831 (Div. 1 + Div. 2)——A、B、C、D、E

A：

 题意：给一个质数n，求得一个数m，使得n+m不为素数。 

解析：质数n+本身，为2*n，其一定不为质数。所以答案可以是它本身

#include
using namespace std;
const int N=2e6+10;
 
void solve(){
	int n;cin>>n;
	cout<"\n";
}
 
int main(){
	int T;cin>>T;
	while(T--) solve();
}

B: 

题意：给定N个n*m的长方形，要求每个长方形的一条边都必须与x轴重合，长方形的边可以重合，但不允许长方形重叠。问怎样放才能使得拼后的长方形周长最小。

分析：贪心。我们发现，重合于x轴的边，是固定的，所以我们只需要把每个长方形最小的边于x重合，这里所得的宽一定是最小的，同理我们可以发现，最终所得的高一定是等于最大的边的。这里给个图方便读者理解。（所求的周长，即为红色长方形的周长）

#include
#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(xswap(x,y);
		maxx=max(maxx,x);
		b+=y;
	}
	cout<"\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
#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<"\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
#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 
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";
}