A. Madoka and Math Dad
题意：
已知一个数字字符串构成的位数和为n的长度，求能构造出字典序最长的字符串，并且相邻的数字不能相等且不能含0
思路：
既然不能含0，那肯定是用最小的1和2去不断的构成，且字典序要最长，所以应该优先2121这种，但是如果长度是4,21之后还少1，那么明显211违法了要求，所以要121，就是反转再添加1
#include<bits/stdc++.h> using namespace std; int main() { int n,i,j,t; cin>>t; while(t--) { cin>>n; int flag=0; string ss=""; while(n>=2) { if(flag==0) { flag=1; n-=2; ss+="2"; } else { flag=0; n--; ss+="1"; } } if(n>=1&&flag==0) { reverse(ss.begin(),ss.end()); ss+="1"; reverse(ss.begin(),ss.end()); } else if(n>=1&&flag==1) { ss+="1"; } cout<<ss<<endl; } return 0; }
B. Madoka and the Elegant Gift
题意：
没有被包含的矩阵叫nice矩阵，如果一个图标里的任意两个nice矩阵相交那就输出NO，否则输出yes
思路：
简单来说如果该矩阵没被包含，那么就可以理解为最大的矩阵，或者是突出来的矩阵就像这样,很明显第一行的蓝色框柱的矩阵没有被任何包裹，那么他就是个nice矩阵，而紫色同理也没被任何矩阵框柱，它也是nice矩阵，但是很明显，他们有交集，是相交的，所以其实就是去找整个图里没有矩阵具有突出的点，有就是no，代码的话，我就是去找1的位置，然后横着找到连续的设定为它的长，竖着找宽，然后判断矩阵外的一周有没有0,
#include<bits/stdc++.h> using namespace std; const int maxn=105; char m1[maxn][maxn]; bool vis[maxn][maxn]; int n,m; bool check(int x,int y) { int x1=x,y1=y,i,j,flag=0; for(i=x+1;i<n;i++) { if(m1[i][y]=='1') x1++; else break; } for(j=y+1;j<m;j++) { if(m1[x][j]=='1') y1++; else break; } for(i=x;i<=x1;i++) { for(j=y;j<=y1;j++) { vis[i][j]=1; if(m1[i][j]!='1') flag=1; if(i==x||i==x1||j==y||j==y1) { if(i==x) { if(i-1>=0) { if(m1[i-1][j]=='1') flag=1; } } if(i==x1) { if(i+1<n) { if(m1[i+1][j]=='1') flag=1; } } if(j==y) { if(j-1>=0) { if(m1[i][j-1]=='1') flag=1; } } if(j==y1) { if(j+1<m) { if(m1[i][j+1]=='1') flag=1; } } } } } if(flag==1) return false; return true; } int main() { int i,j,t; cin>>t; while(t--) { cin>>n>>m; for(i=0;i<n;i++) { for(j=0;j<m;j++) cin>>m1[i][j],vis[i][j]=0; } int f1=0; for(i=0;i<n;i++) { for(j=0;j<m;j++) { if(m1[i][j]=='1'&&vis[i][j]==0) { if(!check(i,j)) f1=1; } if(f1==1) break; } if(f1==1) break; } if(f1==1) { cout<<"NO"<<endl; } else { cout<<"YES"<<endl; } } return 0; }
C. Madoka and Childish Pranks
题意：
给你一个需要构成的图，黑色是1，白色是0，要求你操作n*m次之内从全是0的图得到目标图，操作是选择一个任意长度和宽度的矩阵，把左上角变成0，然后和0相邻的全是1，和1相邻的全是0，这样涂。
思路：
不难想到先从小的矩阵开始涂观察能否涂一个格子这样，我的思路是从最后一层最后一个开始涂起，如果当前位置应要黑色，就把位置涂黑，然后把上面的位置涂白，一直这样到第一层再从右边往左涂，涂到第一个就无法动了，所以只要第一个不是1，那么就有方案；
#include<bits/stdc++.h> using namespace std; const int maxn=105; char m1[maxn][maxn]; bool vis[maxn][maxn]; int n,m; bool check(int x,int y ) { if(x-1>=1&&m1[x-1][y]=='0') return true; if(y-1>=1&&m1[x][y-1]=='0') return true; return false; } int main() { int i,j,t; cin>>t; while(t--) { cin>>n>>m; vector<pair<int,int >>mo,ans; for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { cin>>m1[i][j]; } } int flag=0; for(i=n;i>=1;i--) { for(j=m;j>=1;j--) { if(m1[i][j]=='1') { if(i-1>=1) { ans.push_back({i-1,j}); ans.push_back({i,j}); } else if(j-1>=1) { ans.push_back({i,j-1}); ans.push_back({i,j}); } else { flag=1; } } } } if(flag==1) { cout<<-1<<endl; } else { cout<<ans.size()/2<<endl; for(i=0;i<ans.size();i+=2) { cout<<ans[i].first<<" "<<ans[i].second<<" "<<ans[i+1].first<<" "<<ans[i+1].second<<endl; } } } return 0; }
