20220806牛客第六场
Lcon Design
题目大意：
给定
请你按照输入的n来将其输出
解：
直接模拟就好了
#include <bits/stdc++.h>
using namespace std ;
int n,xx,yx;
int ma[1000][1000];
void pp() {
for(int i=1;i<=yx;i++) {
for(int j=1;j<=xx;j++) {
if(ma[j][i]==1) cout<<"*";
if(ma[j][i]==2) cout<<".";
if(ma[j][i]==3) cout<<"@";
if(ma[j][i]==0) cout<<".";
}
cout<<endl;
}
cout<<endl;
}
void solve(int x,int y,int i) {
x--;
y--;
for(int j=1;j<=2*n+3;j++) {
for(int k=1;k<=2*n+3;k++) {
if(i==1) {
if(j==k || (j==1 || j==2*n+3) )
ma[j+x][k+y]=3;
else ma[j+x][k+y]=2;
}
if(i==2) {
if(j==1) ma[j+x][k+y]=3;
if(k==1 || k==n+2) ma[j+x][k+y]=3;
}
if(i==3) {
if(j==1) ma[j+x][k+y]=3;
if(k==2*n+3) ma[j+x][y+k]=3;
}
if(i==4) {
if(k==1 || k==n+2 || k==2*n+3)
ma[j+x][y+k]=3;
if(j==1 &&k<=n+2) ma[j+x][y+k]=3;
if(j==2*n+3 && k>=n+3) ma[j+x][y+k] =3;
}
}
}
//pp();
}
void zz(int x,int y) {
x--;
y--;
for(int i=1;i<=n+1;i++) {
for(int j=1;j<=2*n+3;j++) {
ma[x+i][y+j]=2;
}
}
// pp();cout<<endl;
}
int main() {
// int ma[1000][1000];
memset(ma,0,sizeof(ma));
cin>>n;
xx=13*n+19,yx=4*n+5;
for(int i=1;i<=xx;i++) {
ma[i][1]=1;
ma[i][yx]=1;
}
for(int i=1;i<=yx;i++) {
ma[1][i]=1;
ma[xx][i]=1;
}
for(int i=2;i<xx;i++) {
for(int j=2;j<=n+1;j++) {
ma[i][j]=2;
}
for(int j=3*n+5;j<=yx-1;j++) {
ma[i][j]=2;
}
}
zz(2,n+2);
zz(3*n+6,n+2);
zz(6*n+10,n+2);
zz(9*n+14,n+2);
zz(12*n+18,n+2);
// pp();
solve(n+3,n+2,1);
solve(n+3+(3*n+4),n+2,2);
solve(n+3+2*(3*n+4),n+2,3);
solve(n+3+3*(3*n+4),n+2,4);
pp();
return 0;
}Number Game
题目大意：
给定三个数abc，有下面两种操作
1.将b变成a-b
2.将c变成b-c
再给定一个数x，能不能通过上面这两种操作将c变成x
解：
首先b只会有两种值，我们命名为b1=b和b2=a-b
假如先用b1对c去操作，接下来就是b2对c去操作才有意义，否则c不变，接着分操作次数去分析得到公式
然后用b2去对c去操作也是同理
#include <bits/stdc++.h>
using namespace std ;
int n,xx,yx;
int ma[1000][1000];
void pp() {
for(int i=1;i<=yx;i++) {
for(int j=1;j<=xx;j++) {
if(ma[j][i]==1) cout<<"*";
if(ma[j][i]==2) cout<<".";
if(ma[j][i]==3) cout<<"@";
if(ma[j][i]==0) cout<<".";
}
cout<<endl;
}
cout<<endl;
}
void solve(int x,int y,int i) {
x--;
y--;
for(int j=1;j<=2*n+3;j++) {
for(int k=1;k<=2*n+3;k++) {
if(i==1) {
if(j==k || (j==1 || j==2*n+3) )
ma[j+x][k+y]=3;
else ma[j+x][k+y]=2;
}
if(i==2) {
if(j==1) ma[j+x][k+y]=3;
if(k==1 || k==n+2) ma[j+x][k+y]=3;
}
if(i==3) {
if(j==1) ma[j+x][k+y]=3;
if(k==2*n+3) ma[j+x][y+k]=3;
}
if(i==4) {
if(k==1 || k==n+2 || k==2*n+3)
ma[j+x][y+k]=3;
if(j==1 &&k<=n+2) ma[j+x][y+k]=3;
if(j==2*n+3 && k>=n+3) ma[j+x][y+k] =3;
}
}
}
//pp();
}
void zz(int x,int y) {
x--;
y--;
for(int i=1;i<=n+1;i++) {
for(int j=1;j<=2*n+3;j++) {
ma[x+i][y+j]=2;
}
}
// pp();cout<<endl;
}
int main() {
// int ma[1000][1000];
memset(ma,0,sizeof(ma));
cin>>n;
xx=13*n+19,yx=4*n+5;
for(int i=1;i<=xx;i++) {
ma[i][1]=1;
ma[i][yx]=1;
}
for(int i=1;i<=yx;i++) {
ma[1][i]=1;
ma[xx][i]=1;
}
for(int i=2;i<xx;i++) {
for(int j=2;j<=n+1;j++) {
ma[i][j]=2;
}
for(int j=3*n+5;j<=yx-1;j++) {
ma[i][j]=2;
}
}
zz(2,n+2);
zz(3*n+6,n+2);
zz(6*n+10,n+2);
zz(9*n+14,n+2);
zz(12*n+18,n+2);
// pp();
solve(n+3,n+2,1);
solve(n+3+(3*n+4),n+2,2);
solve(n+3+2*(3*n+4),n+2,3);
solve(n+3+3*(3*n+4),n+2,4);
pp();
return 0;
}M.Z-game on grid
题目大意：
两个人在NbM.com的网格上轮流移动一个棋子。棋子初始位置为（1,1）。每次只能向右或者向上移动一格。每个网格上面都有一些标记，移到‘A’的点爱丽丝赢，移到‘B’的点爱丽丝输，没有移到特殊点并且不能再移动则为平局。
给出先手是否必胜，必平，必败
解：
考虑dp
对三种情况分三次进行求解，按照每种情况dp设值不同
拿是否能赢的情况举例，如果（n-1，m-1）的值为“A”，那么这个位置的dp值就是1，否则就是0
从右上往左下开始递推，当前来到了(i,j)位置
如果当前位置为“A”，那么这个位置dp值就是1，爱丽丝就赢了，如果当前位置是“B”，这个位置dp值就是0，因为在这个点爱丽丝是输得。
当前位置如果为“.”,那么就要分情况讨论，如果爱丽丝先手并且在（i+1，j）或者（i,j+1）位置有dp为1的值爱丽丝就可以走到那一步上去从而取得胜利。如果爱丽丝后手，那么就要保证（i+1,j）和（i,j+1）位置上dp值都为1，因为此时不论对手走哪一条路爱丽丝都能走到dp值为1的地方从而取得胜利。
对于其他的情况都是一样的分析这里就不赘述。
代码以及思想均来自fn学长
#include<bits/stdc++.h>
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=505;
ll n,m;
string s[N];
int f[4][N][N]; // f[1][i][j]表示考虑i,j右下角时的答案1
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t; cin>>t;
while(t--){
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>s[i];
}
for(int i=1;i<=3;i++){
for(int j=0;j<=n;j++){
for(int k=0;k<=m;k++){
f[i][j][k]=0; // 初始化
}
}
}
if(s[n-1][m-1]=='A'){
f[1][n-1][m-1]=1; // 可以赢
}
else if(s[n-1][m-1]=='.'){
f[2][n-1][m-1]=1; // 可以平局
}
else{ // 'B'
f[3][n-1][m-1]=1; // 可以输
}
// 转移f[1][j][k]，是否能赢
for(int j=n-1;j>=0;j--){
for(int k=m-1;k>=0;k--){
if(j==n-1 && k==m-1)continue;
if(s[j][k]=='A'){
f[1][j][k]=1;
}
else if(s[j][k]=='B'){
f[1][j][k]=0;
}
else{ // '.'
if((j+k)%2==0){ // 轮到Alice走
if(j+1<=n-1)f[1][j][k]=max(f[1][j][k],f[1][j+1][k]);
if(k+1<=m-1)f[1][j][k]=max(f[1][j][k],f[1][j][k+1]);
}
else{ // 轮到Bob走
f[1][j][k]=1;
if(j+1<=n-1)f[1][j][k]=min(f[1][j][k],f[1][j+1][k]);
if(k+1<=m-1)f[1][j][k]=min(f[1][j][k],f[1][j][k+1]);
}
}
}
}
// 转移f[3][j][k]，是否能输
for(int j=n-1;j>=0;j--){
for(int k=m-1;k>=0;k--){
if(j==n-1 && k==m-1)continue;
if(s[j][k]=='A'){
f[3][j][k]=0;
}
else if(s[j][k]=='B'){
f[3][j][k]=1;
}
else{ // '.'
if((j+k)%2==0){ // 轮到Alice走
if(j+1<=n-1)f[3][j][k]=max(f[3][j][k],f[3][j+1][k]);
if(k+1<=m-1)f[3][j][k]=max(f[3][j][k],f[3][j][k+1]);
}
else{ // 轮到Bob走
f[3][j][k]=1;
if(j+1<=n-1)f[3][j][k]=min(f[3][j][k],f[3][j+1][k]);
if(k+1<=m-1)f[3][j][k]=min(f[3][j][k],f[3][j][k+1]);
}
}
}
}
// 转移f[2][j][k]，是否能平局
for(int j=n-1;j>=0;j--){
for(int k=m-1;k>=0;k--){
if(j==n-1 && k==m-1)continue;
if(s[j][k]=='A'){
f[2][j][k]=0;
}
else if(s[j][k]=='B'){
f[2][j][k]=0;
}
else{ // '.'
if((j+k)%2==0){ // 轮到Alice走
if(j+1<=n-1)f[2][j][k]=max(f[2][j][k],f[2][j+1][k]);
if(k+1<=m-1)f[2][j][k]=max(f[2][j][k],f[2][j][k+1]);
}
else{ // 轮到Bob走
f[2][j][k]=1;
if(j+1<=n-1)f[2][j][k]=min(f[2][j][k],f[2][j+1][k]);
if(k+1<=m-1)f[2][j][k]=min(f[2][j][k],f[2][j][k+1]);
}
}
}
}
if(f[1][0][0])cout<<"yes "; // 可以赢
else cout<<"no ";
if(f[2][0][0])cout<<"yes "; // 可以平局
else cout<<"no ";
if(f[3][0][0])cout<<"yes"<<endl; // 可以输
else cout<<"no"<<endl;
}
return 0;
}
#ACM##菜鸡的求救#
投递字节跳动等公司10个岗位 >
查看8道真题和解析