Codeforces Round #644 (Div. 3)（A~G）
Codeforces Round #644 (Div. 3)
A. Minimal Square
题意：
给定一个矩形，长宽分别是a,b。求一个最小的正方形，使得其能够包含两个这样的矩形。求出其面积。
思路：
假设长是a，宽是b，考虑2b和a之间的大小关系即可。因为要可以包含两个矩形，所以不难推出max（2*b,a）就是正方形的边长。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=50;
void AC(){
int n;cin>>n;
while(n--){
int a,b;
cin>>a>>b;
if(a>b) swap(a,b);
int tmp=max(2*a,b);
cout<<tmp*tmp<<endl;
}
}
int main(){
AC();
return 0;
}
B. Honest Coach
题意：
给一个数组，求两个元素的最小差值。
思路：
排序后遍历输出最小值即可。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=55;
int a[maxn],n;
void AC(){
int t;cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
int minn=0x3f3f3f3f;
for(int i=1;i<n;i++)
minn=min(minn,abs(a[i+1]-a[i]));
cout<<minn<<endl;
}
}
int main(){
AC();
return 0;
}
C. Similar Pairs
题意：
定义类似对是两个数具有相同的奇偶性或者是差值的绝对值为1.判断一个数组的元素是否能两两对应分为类似对。
思路：
当元素为奇数的个数和元素为偶数的个数都是偶数时一定可以。
否则的话，当存在任意一对元素差值的绝对值为1时也可以。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=55;
int a[maxn],n;
void AC(){
int t;cin>>t;
while(t--){
cin>>n;
int l=0,r=0;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]%2) r++;
else l++;
}
if(l%2==0&&r%2==0){
puts("YES");
continue;
}
sort(a+1,a+1+n);
bool flag=0;
for(int i=2;i<=n;i++)
if(a[i]-a[i-1]==1){
flag=1;
break;
}
if(flag) puts("YES");
else puts("NO");
}
}
int main(){
AC();
return 0;
} D. Buying Shovels
题意：
给定n和k，你可以从1~k中选择一个数m，使得n%m==0并且n/m最小。
思路：
万恶之源，一开始先开的D然后思路跑偏导致错失一次上分机会。
先说一开始的思路，因为要使得n/m最小，所以当m大的时候，n/m就会小。所以倒着遍历，就可以得到最小的n/m。
但是这样会造成一个问题，比如样例中的999999733 999999732，1~k里没有n的因子，这样就会造成TLE。
一直纠结如何解决这个问题，然后就自己把自己卡死了。反思反思。
正解应该是枚举2~sqrt（n）中n的因子，因为大于sqrt(n)的因子都可以由前者得到。然后暴力跑一遍求min就好。
可以考虑特判n<=k的情况,这时候可以直接取m=n，答案就是1。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=55;
int a[maxn],n;
void AC(){
int t;cin>>t;
while(t--){
int n,k;
cin>>n>>k;
if(n<=k) cout<<"1"<<endl;
else{
int res=1;
for(int i=2;i*i<=n&&i<=k;i++){
if(n%i==0)
if(n/i<=k) res=max(res,n/i);
else res=max(res,i);
}
cout<<n/res<<endl;
}
}
}
int main(){
AC();
return 0;
}
E. Polygon
题意：
在矩阵的左侧和上侧都有大炮，最开始矩阵的元素都是0。子弹可以一直往前走直到碰到边界或是碰到1。子弹最后停留的格子会变成1。问给出的矩阵是否可以得到。
思路：
考虑一下性质。
子弹肯定是先到达每一行的最右端和每一列的最下端。所以直接遍历。如果一个格子是1，但是他的右面或下面都为0的话，就不能得到。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=55;
int a[maxn][maxn],n;
void AC(){
int t;cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%1d",&a[i][j]);
bool flag=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j]){
if(i==n||j==n) continue;
else{
if(!a[i+1][j]&&!a[i][j+1]){
flag=0;
goto A;
}
}
}
A:
if(flag) puts("YES");
else puts("NO");
}
}
int main(){
AC();
return 0;
}
F. Spy-string
题意：
给定一个字符串数组，找到一个字符串使得该字符串与给出的每一个字符串最多有一个相同位置上的不同字母。
思路：
一个很巧妙的构造题。
因为数据范围很小，可以以数组里的任意一个字符串作为基准，分别把他的每一位改为a~z，然后逐个与数组里剩下的字符串相比较，判断该字符串是否满足题意。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int cul(string a,string b){
int res=0;
for(int i=0;i<a.size();i++)
if(a[i]!=b[i]) res++;
return res;
}
void AC(){
string s[12];
int t;cin>>t;
while(t--){
bool flag=0;
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>s[i];
string tmp=s[1];
for(int i=0;i<m;i++){
string qian=tmp.substr(0,i);
string hou=tmp.substr(i+1,m-i-1);
for(int j=0;j<26;j++){
int res=0;
string tt=qian;
tt+=(j+'a');
tt+=hou;
for(int k=2;k<=n;k++)
if(cul(tt,s[k])<=1) res++;
if(res>=n-1){
flag=1;
cout<<tt<<endl;
goto A;
}
}
}
A:
if(!flag) puts("-1");
}
}
int main(){
AC();
return 0;
}
G. A/B Matrix
题意：
给定n,m,a,b;
是否可以构造出一个n*m的矩阵，使得每一行都有a个1，每一列都有b个1.
思路；
又是一个很巧妙的构造题。
根据题意可以知道，按照行来计算1的个数和按照列来计算1的个数，最后的答案一定是相同的。
所以一旦na!=mb时，就一定无法构造出这个矩阵。
然后就直接枚举每一行中1放的地方，用一个tot存这个1在哪一列，对tot%m即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void AC(){
int t;cin>>t;
while(t--){
int n,m,a,b;
cin>>n>>m>>a>>b;
if(a*n!=b*m){
puts("NO");
continue;
}
int tot=0;
int q[55][55];
memset(q,0,sizeof q);
for(int i=0;i<n;i++)
for(int j=0;j<a;j++){
q[i][tot++]=1;
tot%=m;
}
puts("YES");
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
cout<<q[i][j];
if(j==m-1) puts("");
}
}
}
int main(){
AC();
return 0;
}