@

T5 由于保证了 $1 \le p_i < i$，所以其实还可以更短

#include "bits/stdc++.h"
using namespace std;

int n, s = 1;//最开始涂根节点

int p[1919810];
int c[1919810];

int main() {
    scanf ("%d", &n);
    for (int i = 2; i <= n; ++i) scanf ("%d", &p[i]);
    for (int i = 1; i <= n; ++i) scanf ("%d", &c[i]);
    for (int i = 2; i <= n; ++i) {
        if (c[i] != c[p[i]]) ++s;//子节点颜色不是父节点就进行操作
    }
    cout << s;
}

搭配 Mivik 压行机 珂以减少到 244B.

#include"bits/stdc++.h"using namespace std;int n,s=1;int p[1919810];int c[1919810];int main(){scanf("%d",&n);for(int i=2;i<=n;++i)scanf("%d",&p[i]);for(int i=1;i<=n;++i)scanf("%d",&c[i]);for(int i=2;i<=n;++i){if(c[i]!=c[p[i]])++s;}cout<<s;}

%%%

T5 由于根节点的更改会影响子节点，所以必须从根节点开始涂色

#include<bits/stdc++.h>
using namespace std;
long long n,a[50000],s,b[50000];
vector<long long> tr[50000];
inline void read(long long &x){
	x=0;char a='$';int p=1;
	while(a>'9'||a<'0'){if(a=='-') p=-p;a=getchar();}
	while(a>='0'&&a<='9'){x=x*10+(a-48);a=getchar();}
	x*=p;
}
inline void write(long long x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
inline void c(int o,int p){
	a[o]=p;//涂色 
	for(int i=0;i<tr[o].size();i++) c(tr[o][i],p);//遍历子树 
}
inline void dfs(int o){
	if(a[o]!=b[o]){//如果当前节点颜色不是目标颜色 
		s++;
		c(o,b[o]);//把他的所有子树全涂色 
	}
	for(int i=0;i<tr[o].size();i++) dfs(tr[o][i]);//遍历所有子树
}
int main(){
	read(n);//读入 
	long long x;
	for(int i=2;i<=n;i++){
		read(x);
		tr[x].push_back(i);//存储树 
	}
	for(int i=1;i<=n;i++) read(b[i]);//a[i]表示当前颜色，b[i]表示目标颜色 
	dfs(1);//开始遍历树 
	cout<<s;
}

T4

#include<bits/stdc++.h>
using namespace std;
long long n,c,d,md,l,r,a[1000000],z,mn=-1145141919810,mb=-111,ggg;
inline void read(long long &x){
	x=0;char a='$';int p=1;
	while(a>'9'||a<'0'){if(a=='-') p=-p;a=getchar();}
	while(a>='0'&&a<='9'){x=x*10+(a-48);a=getchar();}
	x*=p;
}
inline void write(long long x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
bool cmp(int x,int y){
	return x>y;
}
int main(){
	read(n),read(c),read(d);//先读入 
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=n&&i<=d;i++) ggg+=a[i];//统计出在任务不能刷新的情况下d天能赚多少钱 
	sort(a+1,a+n+1,cmp);//从大到小排序任务价值 
	if(ggg>=c){
		cout<<"Infinity";
		return 0;
	}//如果任务不刷新d天也能赚到c元，那k就没有任何用处了qwq 
	l=0,r=d;//二分答案 
	a[0]=a[n];//之前代码打错忘删了，这句代码没有用处qwq 
	while(l<=r){
		z=0;
		md=(l+r)/2;
		int y=d/(md+1),yy=d%(md+1);//y表示d天中有几个k天，yy表示剩余的天 
		for(int i=1;i<=md+1&&i<=n;i++) z+=a[i];//统计出k天能赚多少钱 
		y*=z;
		for(int i=1;i<=yy&&i<=n;i++){
			y+=a[i%n];//可直接写成a[i]，代码打错忘记改了qwq 
		}
		if(y>=c){//如果这个k的值满足的话 
			mb=max(md,mb);
			l=md+1;//找更大的k 
		}
		else r=md-1;//找更小的k 
	}
	if(mb!=-111){//如果mb不等于初始值就说明mb被修改过，所以程序一定找到了解 
		cout<<mb;
	}
	else cout<<"Impossible";//否则输出无解 
}

T3 ⑨的数组编排 这题就是一个贪心 首先我们要求的是an-a1的值 所以我们进行操作时必须带有a1或an 否则我们的操作都是无意义的 那就会有三种情况 1、只换an

for(int j=2;j<=n;j++) mx1=max(mx1,a[j]);
mx1-=a[1];

我们只需要找除a1外所有数的最大值就可以了 因为我们可以进行任意（k可以是任意值）次交换，所以最大值一定可以交换到an 2、只换a1

for(int j=1;j<n;j++) mx2=min(mx2,a[j]);
mx2=a[n]-mx2;

我们只需要找除an外所有数的最小值就可以了 因为我们可以进行任意（k可以是任意值）次交换，所以最小值一定可以交换到a1 3、全换

for(int j=1;j<n;j++) mx3=max(a[j]-a[j+1],mx3);
mx3=max(mx3,a[n]-a[1]);

我们可以发现，若有两个数a,b在某数组中相邻 那么若干次交换后a会处于an，b会处于a1 比如 g f d a b t y->f d a b t y g->d a b t y g f->a b t y g f d->b t y g f d a

进行完3次比较后，只要比较三次计算结果最大值即可

完整代码：

#include<bits/stdc++.h>
using namespace std;
long long n,m,mx1,mx2,mx3,a[114514];
inline void read(long long &x){
	x=0;char a='$';int p=1;
	while(a>'9'||a<'0'){if(a=='-') p=-p;a=getchar();}
	while(a>='0'&&a<='9'){x=x*10+(a-48);a=getchar();}
	x*=p;
}
inline void write(long long x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int main(){
	read(m);
	for(int i=1;i<=m;i++){
		mx1=-1145141919810,mx2=1145141919810,mx3=-1145141919810;
		read(n);
		for(int j=1;j<=n;j++){
			read(a[j]);
		}
		for(int j=2;j<=n;j++) mx1=max(mx1,a[j]);
		mx1-=a[1];
		for(int j=1;j<n;j++) mx2=min(mx2,a[j]);
		mx2=a[n]-mx2;
		for(int j=1;j<n;j++) mx3=max(a[j]-a[j+1],mx3);
		mx3=max(mx3,a[n]-a[1]);//也有可能一开始的情况就是最大值 
		write(max(mx1,max(mx2,mx3)));
		puts("");
	}
}

T2 ⑨的电脑游戏 该题我们可以发现数据很小，所以我们可以直接搜索

#include<bits/stdc++.h>
using namespace std;
long long n,m,f[3][2000],nx[8]={0,1,0,-1,1,1,-1,-1},ny[8]={1,0,-1,0,1,-1,1,-1};
string a[600];
bool h;
//nx,ny记录八个方向 
inline void read(long long &x){
	x=0;char a='$';int p=1;
	while(a>'9'||a<'0'){if(a=='-') p=-p;a=getchar();}
	while(a>='0'&&a<='9'){x=x*10+(a-48);a=getchar();}
	x*=p;
}
inline void dfs(int x,int y){
	f[x][y]=1;
	if(x==2&&y==n-1){//如果找到了终点 
		cout<<"YES"<<endl;//输出 
		h=0;//做标记 
		return ;//返回上一层 
	}
	for(int i=0;i<8;i++){
		int X=x+nx[i],Y=y+ny[i];//找下一个点 
		if(Y>=0&&Y<n&&X>0&&X<3&&f[X][Y]==0&&a[X][Y]=='0'){//如果该点没有找过且是安全 
			dfs(X,Y);//访问该点 
		}
	}
}
int main(){
    read(m);
    for(int i=1;i<=m;i++){
    	h=1;
    	memset(f,0,sizeof(f));
    	read(n);
    	for(int j=1;j<=2;j++) cin>>a[j];
		dfs(1,0);//从起点搜索 
		if(h) cout<<"NO"<<endl;//若无法到达就输出no 
	}
}

当然，我们发现这个电脑游戏的地图只有2*n 所以我们只要判断某一列上是否存在两个1就可以了 因为我们可以斜走，所以一列一旦有安全格就必定能到达 代码就不提供哩(绝不是因为懒)

T1 ⑨的简化

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[1000000];
inline void read(long long &x){
	x=0;char a='$';int p=1;
	while(a>'9'||a<'0'){if(a=='-') p=-p;a=getchar();}
	while(a>='0'&&a<='9'){x=x*10+(a-48);a=getchar();}
	x*=p;
}
int main(){
	freopen("simplify.in","r",stdin);
	freopen("simplify.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++) read(a[i]);//输入 
    for(int i=1;i<=n;i++){
    	long long s=0,p=0,j;
    	for(j=i;j<i+m&&j<=n;j++){//向后找m个数，同时确保j不大于n 
    		s+=a[j];//统计和 
    		p++;
		}
		i=j-1; //找m个数后面的第一个数 
		double pp=s*1.0/p;//求平均数 
		printf("%.1lf ",pp);//输出 
	}
}