2021.11.15-测试

前言

今天又做了冯巨的题，\(T4\)不开long long直接炸掉,一分没有，

哎，被同桌吊打，giao

T1-\(\color {red} 0\)

这不妙，冯巨说这是zz题，但我不会，我就是zz

结果一看题，发现是个大水题，介于这道题的欺骗性，我要给它取个难听的名，就叫做“F”好了(原题就叫“F”)

题目描述 ：

给定两个数列，需找到一个排列p，使得每个\(a_i\otimes b_{p_i}都相等\)，输出所有的\(x\)

论不看数据范围的下场

思路

因为n的范围很小，所以可以直接枚举出所有的\(x\)就可以了

话不多说，上代码;

#include<bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
int n;
int a[2005],b[2005];
unordered_map <int, int> mp;//哈希表
vector<int> ans;
//=================================================
inline int read(){
	int p=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){p=p*10+c-'0';c=getchar();}
	return p*f;
}
//=================================================
void ck(int x){
	unordered_map<int,int>c;
	for(int i=1;i<=n;i++)
		c[b[i]]++;
	for(int i=1;i<=n;i++){
		if(!c[a[i]^x])return ;
		--c[a[i]^x];
	}
	ans.pb(x);
}
//=================================================
int main(){
	n=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=1;i<=n;i++)
		b[i]=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			mp[a[i]^b[j]]++;
	for(auto x:mp)
		if(x.second>=n)	ck(x.first);
	cout<<ans.size()<<'\n';
	sort(ans.begin(),ans.end());
	for(int x:ans)
		cout<<x<<'\n';
	return 0;
}

T2\(\color {#39c5bb} {100}\)

第二题加了个特判就A了，虽然不是完全正解

题目描述

\(n\times n\)的网格，在一个\(3\times 3\)的范围内最多有两个相邻的被涂黑，求最多能有多少个被涂黑，n为偶数

我考试的代码：

#include<bits/stdc++.h>
#define ll long long
#define re register
using namespace std;
int n,type;
int q[1005][1005];
inline int read(){
	int p=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){p=p*10+c-'0';c=getchar();}
	return p*f;
}
ll solve(ll x){
	if(x==0)	return 0;
	if(x==2)	return 2;
	if(x==4)	return 8;
	if(x==6)	return 16;
	if(x==8)	return 26;
	if(x==10)	return 40;
	if(x==12)	return 56;
	if(x==14)	return 74;
	if(x==16)	return 96;
	if(x==18)	return 120;
	if(x==20)	return 146;//打表，虽然没用
	return 4*x-8+solve(x-6);
}
void init(int x,int a,int b){
	if(x==2){
		q[a][b]=1;q[a][b+1]=0;
		q[a+1][b]=0;q[a+1][b+1]=1;
		return ;
	}
	for(re int i=a;i<=a+x-1;i++){
		for(re int j=b;j<=b+x-1;j++){
			if(a%2!=0){
				if((j%2!=0&&i==a)||(i==a&&j==b+x-1)){
				q[i][j]=1;continue;
				}
				if(j%2!=0&&i==a+1&&j!=b+x-2){
				q[i][j]=1;continue;
				}
				if(i>=a+2&&i<=a+x-3&&i%2!=0&&j>b+x-3){
				q[i][j]=1;continue;
				}
				if(i>=a+2&&i<=a+x-3&&i%2==0&&(j==b||j==b+1)){
				q[i][j]=1;continue;
				}
				if(i==a+x-2&&j%2==0&&j!=b+1){
				q[i][j]=1;continue;
				}
				if((i==a+x-1&&j%2==0)||(i==a+x-1&&j==b)){
				q[i][j]=1;continue;
				}
			}
			else{
				if(((j+1)%2!=0&&i==a)||(i==a&&j==b+x-1)){
				q[i][j]=1;continue;
				}
				if((j+1)%2!=0&&i==a+1&&j!=b+x-2){
				q[i][j]=1;continue;
				}
				if(i>=a+2&&i<=a+x-3&&(i+1)%2!=0&&j>b+x-3){
				q[i][j]=1;continue;
				}
				if(i>=a+2&&i<=a+x-3&&(i+1)%2==0&&(j==b||j==b+1)){
				q[i][j]=1;continue;
				}
				if(i==a+x-2&&(j+1)%2==0&&j!=b+1){
				q[i][j]=1;continue;
				}
				if((i==a+x-1&&(j+1)%2==0)||(i==a+x-1&&j==b)){
				q[i][j]=1;continue;
				}
			}
		}
	}
	if(x>=8)init(x-6,a+3,b+3);
}
int main(){
	freopen("s.in","r",stdin);
	freopen("s.out","w",stdout);
	n=read(),type=read();
	if(type==0){
		if(n==1000000000){//怕超时，就先算出答案，直接特判
			cout<<333333334000000000;
			return 0;
		}
		cout<<solve(n)<<"\n";
	}
	else{
		int ans;
		cout<<solve(n)<<"\n";
		init(n,1,1);
		for(re int i=1;i<=n;i++){
			for(re int j=1;j<=n-1;j++){
				cout<<q[i][j]<<" ";
			}
			cout<<q[i][n];
			cout<<"\n";
		}
	}
	return 0;
}

思路

别管左边的
先把四个点取到，然后继续，中间的过程类似于套娃

void init(int x,int a,int b){
	.
	.
	.
    if(x>=8)init(x-6,a+3,b+3);//套娃
}

其实个数可以直接\(O(1)\)算，不用想我那样递归，如果不加特判我就T了