Living-Dream 系列笔记 第18期

Problem

T1

/*
思路：令N个整数以字符串形式读入，
判断其末尾是否为0、2、4、6、8，若是则为偶数，不是则为奇数。
*/
#include<bits/stdc++.h>
using namespace std;

int n;
string x; //以字符串形式读入

int main(){
	cin>>n;
	while(n--){
		cin>>x;
		if(x[x.size()-1]=='0'||x[x.size()-1]=='2'||x[x.size()-1]=='4'||x[x.size()-1]=='6'||x[x.size()-1]=='8') cout<<"even\n"; //判断末尾
		else cout<<"odd\n";
	}
	return 0;
}

T2

/*
思路：为了使组成的数最大，则需要使这个数的为数最多；
因此我们尽量采用使用木棍最少的数1来组成数字；
但1需要两根木棍，若n为奇数时全用1是不行的；
所以我们需要在n为奇数时是用木棍次少的7来开头。
*/
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
    cin>>n;
    if(n%2==1) cout<<7,n-=3; //特判
    while(n) cout<<1,n-=2; //连续输出1
    return 0;
}

T3

/*
思路：不难发现答案只有可能在0~3之间（因为最少切0刀，最多为每人切一刀）；
因此考虑分类讨论：
切0刀：仅当a,b,c仅有1个非0时。
切1刀：仅当a,b,c有2个非0且这两个数相等时。
切2刀：仅当a,b,c有2个非0且这两个数不相等，或者a,b,c中有两个数相等，又或者a,b,c中两数之和等于另一个数时。
切3刀：其他情况均切3刀。
*/
#include<bits/stdc++.h>
using namespace std;

int T,a[3];

int main(){
	cin>>T;
	while(T--){
		int t=0; //a,b,c中0的个数
		for(int i=0;i<3;i++)
			cin>>a[i],t+=(!a[i]);
		sort(a,a+3); //排序
		if(t==2) cout<<"0\n"; //切0刀
		else if(t==1&&a[1]==a[2]) cout<<"1\n"; //切1刀
		else if(t==1||a[1]==a[2]||a[0]+a[1]==a[2]||a[0]==a[1]) cout<<"2\n"; //切2刀
		else cout<<"3\n"; //切3刀
	}
	return 0;
}

T4

/*
思路：我们进行四次旋转，
把每次旋转后的邮票看作新的邮票，放入画布进行涂色，
对四种邮票都涂完色后判断画布与目标是否一致即可。
*/
#include<bits/stdc++.h>
using namespace std;

int T,n,k;
char a[31][31],b[31][31],c[31][31],t[31][31];

void rotate(){ //顺时针90度旋转
    for(int i=1;i<=k;i++)
    	for(int j=1;j<=k;j++)
    		t[i][j]=b[k-j+1][i];
    for(int i=1;i<=k;i++)
    	for(int j=1;j<=k;j++)
    		b[i][j]=t[i][j];
}
bool check(){ //判断c画布与目标是否一致
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(a[i][j]=='*'&&c[i][j]!='*')
                return 0;
    return 1;
}
void paint(int x,int y){ //涂色
    for(int i=1;i<=k;i++)
        for(int j=1;j<=k;j++)
            if(a[x+i-1][y+j-1]=='.'&&b[i][j]=='*') //若目标是'.'而邮票是'*'，则无法涂色
                return;
    
    for(int i=1;i<=k;i++) //对c画布进行染色
        for(int j=1;j<=k;j++)
            if(b[i][j]=='*')
                c[x+i-1][y+j-1]=b[i][j];
}

string work(){
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j],c[i][j]='.'; //需要清空c画布
    cin>>k;
    for(int i=1;i<=k;i++)
        for(int j=1;j<=k;j++)
            cin>>b[i][j];
    
    for(int i=1;i<=4;i++){
        rotate(); //进行4次旋转
        for(int i=1;i+k-1<=n;i++)
            for(int j=1;j+k-1<=n;j++)
                paint(i,j); //枚举左上角进行涂色
    }
    
    return check()?"YES":"NO"; //根据比对情况返回结果
}

int main(){
    cin>>T;
    while(T--) cout<<work()<<'\n';
    return 0;
}

T5

/*
思路：将4个立方体看作4个格子，进行dfs搜索；
在搜索过程中记录参数s，表示目前选择的字符所拼接成的字符串；
每次dfs之前先进行更新，循环目标字符串数组，
若s==当前目标字符串，则标记；
接着循环4个立方体，若当前的未被访问过，则标记，
并且循环6个面，令s加上当前字符进行下一层搜索；
最后循环目标字符串数组，若当前字符串已被标记，则输出YES，反之输出NO。
*/
#include<bits/stdc++.h>
using namespace std;

int n;
bool ans[31],vis[31];
char a[31][31];
string s[31];

void update(string x){
	for(int i=1;i<=n;i++)
		if(x==s[i]) ans[i]=1; //标记答案数组
}

void dfs(int x,string ss){
	update(ss); //更新
	if(x==5) return; //填完了
	for(int i=1;i<=4;i++){ //循环4个立方体
		if(!vis[i]){ //未被标记
			for(int j=1;j<=6;j++){ //循环6个面
				vis[i]=1; //标记
				dfs(x+1,ss+a[i][j]); //下一层搜索
				vis[i]=0; //回溯
			}
		}
	}
}

int main(){
	cin>>n;
	for(int i=1;i<=4;i++)
		for(int j=1;j<=6;j++)
			cin>>a[i][j];
	for(int i=1;i<=n;i++) cin>>s[i];
	dfs(1,"");
	for(int i=1;i<=n;i++){
		if(ans[i]) cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}