NOIP 模拟考记录

封面

T1

【题目描述】
给你一个 n 行 m 列的国际象棋棋盘。最初棋盘上有 k 个红色骑士，你需要在每个
格子中放置一个白色或黑色的骑士。
骑士是一种国际象棋棋子，如果它在 (x1, y1) 这个格子上，则它可以攻击 (x2, y2) 这
个格子上的棋子，当且仅当满足以下任一条件：
• |x1 − x2| = 2 且 |y1 − y2| = 1
• |x1 − x2| = 1 且 |y1 − y2| = 2
“骑士对决”是指一对不同颜色的骑士互相攻击。你需要在其余格子中放置一个骑士（白色或黑色），使得骑士对决的数量尽可能多。输出这个最大值。
【输入格式】
从文件 chess.in 中读入数据。
第一行输入一个整数 t，表示测试数据的组数。
对于每组测试数据：
第一行输入三个整数 n, m, k，表示国际象棋棋盘的大小为 n 行 m 列，初始时棋盘上有 k 个红色骑士。
接下来 k 行，每行输入两个整数 x, y，表示一个红色骑士在 (x, y) 这个格子上。
【输出格式】

输出到文件 chess.out 中。
对于每组测试数据，输出一个整数，表示最多可以有多少对骑士对决。

【代码】
预期得分 100100。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ull unsigned long long
int T,n,m,k;
int dx[]={1,2,-2,-1,2,1,1,2},dy[]={2,1,1,2,1,2,-2,-1};
vector<vector<int>>jz(120,vector<int>(120));
//LL check(){
	
//}
void upt(int x,int y){
	for(int i=0;i<8;i++){
		int tx=dx[i]+x,ty=dy[i]+y;
		if(tx>n||ty>m||tx<1||ty<1||jz[tx][ty]!=-1)continue;
		jz[tx][ty]=!jz[x][y];
		upt(tx,ty);
	}
}
void upt2(int x,int y,vector<vector<int>>&jz){
	for(int i=0;i<8;i++){
		int tx=dx[i]+x,ty=dy[i]+y;
		if(tx>n||ty>m||tx<1||ty<1||jz[tx][ty]!=-1)continue;
		jz[tx][ty]=!jz[x][y];
		upt2(tx,ty,jz);
	}
}
void K0(){
	jz[0][1]=1;
	for(int i=1;i<=n;i++){
		jz[i][1]=!jz[i-1][1];
		for(int j=2;j<=m;j++){
			jz[i][j]=!jz[i][j-1];
		}
	}
	//for(int i=1;i<=n;i++){
	//	for(int j=1;j<=m;j++){
	//		cout<<jz[i][j]<<" ";
	//	}cout<<"\n";
	//}
	
	int cnt=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=0;k<4;k++){
				int tx=dx[k]+i,ty=dy[k]+j;
				if(tx>n||ty>m||tx<1||ty<1)continue;
				if(jz[i][j]!=jz[tx][ty])cnt++;
			}
		}
	}
	cout<<cnt<<"\n";
	return;
}
void solve(){
	jz[0][1]=1;
	for(int i=1;i<=n;i++){
		jz[i][1]=!jz[i-1][1];
		for(int j=2;j<=m;j++){
			jz[i][j]=!jz[i][j-1];
		}
	}
	for(int i=1;i<=k;i++){
		int u,v;cin>>u>>v;
		jz[u][v]=2;
	}
	int cnt=0,a1=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=0;k<4;k++){
				int tx=dx[k]+i,ty=dy[k]+j;
				if(tx>n||ty>m||tx<1||ty<1)continue;
				if(jz[i][j]!=jz[tx][ty])cnt++;
				//if(jz2[i][j]!=jz2[tx][ty])a1++;
			}
		}
	}
	//solve2();
	cout<<cnt<<"\n";
	return;
}
int main(){
	freopen("chess.in","r",stdin);
	freopen("chess.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	//T=1;
	cin>>T;
	while(T--){
		cin>>n>>m>>k;
		if(k==0){
			K0();
		}
		else{
			solve();
		}
	}
}

T2

【题目描述】
小杨有一个由整数构成的数组 aa。最开始，这个数组是空的。
小杨对这个数组执行了三种操作：

  • 选择一个整数，将其添加到数组末尾。每次执行这种操作时，小杨会写下一个字符 +；
  • 移除数组的最后一个元素。每次执行这种操作时，小杨会写下一个字符 −。小杨从不会在空数组上执行此操作；
  • 检查数组是否为非递减排序，即 a1≤a2≤⋅⋅⋅≤aka_1 ≤ a_2 ≤ · · · ≤ a_k，其中 k 是当前数组的元素个数。任何元素个数小于 22 的数组都被认为是有序的。如果数组在执行该操作时是有序的，小杨会写下字符 1，否则写下字符 0。
    现在给定一个长度为 qq 的字符串 ss，由 0、1、+ 和 − 组成。这是小杨按顺序写下的字符序列。
    你需要判断，这个序列是否是可能的，也就是说，小杨是否有可能通过上述操作，写下恰好为 ss 的字符序列。
    【输入格式】
    从文件 array.in 中读入数据。
    • 输入的第一行包含一个整数 t，表示测试用例的数量。
    • 每个测试用例包含一行字符串 s。该字符串由 0、1、+ 和 − 组成，表示小杨按顺序写下的字符序列。
    • 输入还满足以下额外约束：
    ◦ 对于 s 的每一个前缀，字符 + 的数量不少于字符 − 的数量。换句话说，小杨不会在空数组上执行移除操作；
    ◦ 所有测试用例中 |s| 的总和不超过 2 × 10^5。
    【输出格式】
    输出到文件 array.out 中。
    于每个测试用例，如果存在一种操作方式使得小杨写下的字符序列恰好为 s，输出YES，否则输出 NO。
    【代码】
    预期得分 100100。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ull unsigned long long
int T;
string s;
int main(){
	freopen("array.in","r",stdin);
	freopen("array.out","w",stdout);
	//T=1;
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		cin>>s;
		bool NO=0;
		int siz=0,n=s.size();
		int can_be_no2=1e9,can_be_yes=0,can_be_no1=1e9;
		bool can_change=1;
		char las='2';
		int idx=0;
		for(int i=0;i<n;i++){
			//cout<<i<<" ";
			if(s[i]=='+'){++siz,idx++;if(siz<can_be_no1)can_be_no1=siz;}
			else if(s[i]=='-'){siz--,idx--;if(siz<can_be_no2)can_be_no2=1e9;if(siz<can_be_yes)can_be_yes=siz;}
			else if(s[i]=='0'){
				//idx=0;
				if(siz<=can_be_yes){
					NO=1;break;
				}
				if(siz<can_be_no1){
					NO=1;break;
				}
				las=s[i];
				can_be_no2=min(can_be_no2,siz);
				can_be_yes=min(can_be_yes,siz-1);
				if(siz<2){
					NO=1;break;
				}
			}
			else{
				idx=0;
				if(siz>=(can_be_no2)){
					//cout<<can_be_no2<<"\n";
					NO=1;break;
				}
				can_be_yes=min(can_be_yes,siz-1);can_be_no2=1e9;
				can_be_no1=siz+1;
				las=s[i];
			}
		}
		if(NO)cout<<"NO\n";
		else cout<<"YES\n";
	}
}
/*

1+11+-11-++--++++++0+00+++-0+++-+0+++++0-0-++++++---++----+++1+++0-+0-++--0--+++++-+++++0-++++-00++-0-++00-0--+-+0+0+++++00+++----++-+0+++000+

*/

T3

预期得分 00。

T4

预期得分 44。

总

预期总分 204204。