补一发A的题解。
A - Snuke's favorite YAKINIKU
题意：
输入字符串S，如果以YAKI开头输出Yes，否则输出No。
#include<bits/stdc++.h>
using namespace std;
int main()
{
char s[20];cin>>s;
int n=strlen(s);
if(n<4)puts("No");
else
{
if(s[0]=='Y'&&s[1]=='A'&&s[2]=='K'&&s[3]=='I')puts("Yes");
else puts("No");
}
return 0;
}
B - fLIP
题意：
一个N*M的网格，最开始全为白色，每次可以选一行或一列把颜色翻转，问能不能刚好有k个黑色格子。
N，M<=1000
枚举翻了i行j列，那么黑格子就是$i*m+j*i-2*i*j$
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m,k;cin>>n>>m>>k;
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
if(i*m+j*n-2*i*j==k)
{
puts("Yes");
return 0;
}
}
}
puts("No");
return 0;
}
C - Palindromic Matrix
题意：
给出N*M个小写字母，问把它们排到一个N*M的网格中能不能让每行每列都是一个回文串。
N，M<=100
先统计出每个小写字母的个数。
我们发现对每一个位置都有3个，1个或0个对应位置与这个位置上的字母必须相同，个数取决于是否在中心一行，中心一列，或整个网格的正中心。
对于N，M的奇偶分类讨论一下，看能不能把所有字母刚好分配完。
#include<bits/stdc++.h>
using namespace std;
int n,m;
char s[105];
int cnt[100];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>s;
for(int j=0;j<m;j++)
{
cnt[s[j]-'a'+1]++;
}
}
if(n%2==0&&m%2==0)
{
for(int j=1;j<=26;j++)
{
if(cnt[j]%4!=0)
{
puts("No");
return 0;
}
}
puts("Yes");
return 0;
}
else if(n%2==1&&m%2==1)
{
int tmp=0,tt=0;
for(int i=1;i<=26;i++)
{
if(cnt[i]%2==1)tt++;
tmp+=cnt[i]/4;
}
if(tt>1||tmp<(n-1)*(m-1)/4)puts("No");
else puts("Yes");
}
else
{
if(n%2==0)swap(n,m);
int tmp=0;
for(int i=1;i<=26;i++)
{
if(cnt[i]%2==1)
{
puts("No");
return 0;
}
else tmp+=cnt[i]/4;
}
if(tmp<(n-1)*m/4)puts("No");
else puts("Yes");
}
return 0;
}
D - Four Coloring
题意：
给出N，M和D，问能不能把一个N*M的网格(这套题怎么全是网格)四染色使得任何两个曼哈顿距离为D的格子不同色。
输出方案。
N,M<=500
曼哈顿距离不太好求，所以先把坐标转成(x+y,x-y),这样对于每一个点都有周围某一圈的点不能和它同色。
然后就好做了，把每一个D*D的格子看成一个大格子，这样只要保证一个大格子周围一圈没有相同颜色的大格子就行了，然后这么染：
12121212 12341234
34343434 或者 34123412
12121212 12341234
。。。。。 。。。。。
大概有这两类染法，显然符合要求。
ps:
这题让我想起曾经有个同学把一道数竞国集题伪装成OI题问我，大概是把一个N*M的网格四染色，让任意2*2的子矩形都有四种颜色，求方案数。
也是只有那两类染法，我算出来好像是$6(2^n+2^m)-24$
#include<bits/stdc++.h>
using namespace std;
int h,w,d;
int mp[2005][2005];
void ran()
{
for(int i=0;i<=2000;i++)
{
for(int j=0;j<=2000;j++)
{
int tmp=((i/(d))%2)*2+(j/(d))%2;
mp[i][j]=tmp;
// cout<<tmp<<endl;
}
}
}
int main()
{
cin>>h>>w>>d;
ran();
for(int i=1;i<=h;i++)
{
for(int j=1;j<=w;j++)
{
int x=i+j+500,y=i-j+500;
if(mp[x][y]==0)putchar('R');
else if(mp[x][y]==1)putchar('Y');
else if(mp[x][y]==2)putchar('G');
else putchar('B');
}
puts("");
}
return 0;
}
E - Modern Painting
不会做，留坑。
F - Squeezing Slimes
题意：
最开始有一个长度为A的序列，全是1.
每次可以把长度为偶数的连续一段合并，第1个和第2个合并，3和4合并.....这段长度变为原来一半，两个数合并完出来一个数大小为它们的和。
现在给出一个长度为N的序列，问最少几次操作能合出来这个序列。
N<=100000，ai<=10^9
如果只合出来一个数，那么次数显然是log(ai)的。
例如最开始有11个1。
11->8->4->2->1
现在考虑合并多个数，如果某个ai是2的整次幂，那么log次合并都可以穿过这个数，否则其中某一次只能向左给或向右给。
贪心去做，从左往右扫，记录当前前边的数往后给了几次，那多余的一次如果能往合并就向前合并，否则往后合并，可以证明往前给一定不会变劣。
#include<bits/stdc++.h>
#define N 100005
#define ll long long
using namespace std;
int n;
int a[N],b[N],c[N];
int main()
{
cin>>n;
int ans=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
int tmp=a[i];
while(tmp)
{
b[i]++;
tmp>>=1;
}
b[i]--;
if((a[i]&-a[i])!=a[i])c[i]=1;
ans+=b[i]+c[i];
}
int lst=0;
for(int i=1;i<=n;i++)
{
int tmp=min(b[i],lst);
ans-=tmp;lst-=tmp;
if(lst>0&&c[i]>0)
{
ans--;c[i]--;
}
lst=b[i]+c[i];
}
cout<<ans<<endl;
return 0;
}