这场比赛打的真糟心，幸亏不计分了，美滋滋的溜了。。。
A 只有一行或者只有一列是一定可以的，其他情况只有两行两列可以（首尾相连排一圈）。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200010;
int t,n,m;
int main()
{
cin>>t;
while(t--)
{
cin>>n>>m;
if(n==1||m==1||(n==2&&m==2)) puts("YES");
else puts("NO");
}
return 0;
}
B 可以推出来高度n的塔需要木棍的数量，然后二分就可以了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=30010;//暴力一遍 好像27000就超过1e9了
int t,n,m;
ll sum[N];
int main()
{
sum[1]=2;
for(int i=2;i<N;i++)
sum[i]=sum[i-1]+1ll*3*i-1;
cin>>t;
while(t--)
{
cin>>n;
int cnt=0;
while(n>1)
{
int l=upper_bound(sum+1,sum+N,n)-sum;
cnt++;
n-=sum[l-1];
}
cout<<cnt<<endl;
}
return 0;
}
C 题意好恶心人。。。
一个酒店有无数个房间，编号是任意整数（可以是正负或0）。
已知现在每个房间都一个人，要重新排序，排序规则是：给你一个长度为n的数组，然后让编号为k房间内的人去编号为 k+a[ k mod n]（k可以是正或负或0） 的房间，问排序后是否还是一人一个房间。
如果不满足那个一定存在两个数k1,k2 使得k1+a[k1 mod n]==k2+a[k2 mod n]成立 。
假如 k1，和k2都属于[0,n)，那么上式就是：k1+a[k1] = = k2+a[k2]。
假如k1属于[0,n),k2不属于[0,n)，那么上式就是：k1+a[k1] = = k2+a[k2 mod n]
令k2=m2n+s2，则可化简为 k1+a[k1] = = m2n+s2+a[s2]。
k1和k2相反情况是一样的。
假如k1和k2都不属于[0,n),那么上式就是：k1+a[k1 mod n] = = k2+a[k2 mod n];
再令k1=m1n+s1则化简为：m1n+s1+a[s1] = = m2*n+s2+a[s2];
移项后得 s1+a[s1]==(m2-m1)*n+s2+a[s2]。
综上可得：s1+a[s1] ≡ s2+a[s2](mod n) (s1,s2属于[0,n) )
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200010;
int t,n,m;
int a[N];
int main()
{
cin>>t;
while(t--)
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
map<ll,int> mp1,mp2;
bool flag=1;
for(int i=0;i<n;i++)
{
int x=((a[i]+i)%n+n)%n;
if(mp1[x])
{
flag=0;
break;
}
mp1[x]=1;
}
if(flag) puts("YES");
else puts("NO");
}
return 0;
}
D 看样例可以发现如果某一行或者某一列有1个以上的连续黑段，那么一定是-1；
如果存在某行全都是白色，那么是否可以将整体分为两部分来分治处理，这两部分应该是可行的，但是南磁极必须分布于每一行，这个全白行必须有一个南磁极，那就必须会有北磁极被吸引过来位于白块之上就不满足题意了，但是也有例外如果同时存在全白列呢，将南磁极放于行列交点，那么它的同行同列一定不会有北磁极，就一定不会有北磁极被吸到白块之上。
所以如果只有全白行或者全白列就是-1（观摩榜一代码得来的，分治是我臆想的(一本正经胡说八道)).
其余情况就是找北磁极的数量了，求连通块的数量即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
char s[N][N];
bool st[N][N];
int d[4][2]={0,1,0,-1,1,0,-1,0};
void dfs(int x,int y)
{
st[x][y]=1;
for(int i=0;i<4;i++)
{
int dx=x+d[i][0],dy=d[i][1]+y;
if(s[dx][dy]=='#'&&!st[dx][dy])
dfs(dx,dy);
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>s[i]+1;
bool flag1=1,flag2=1;//标记是否有全白行和全白列
for(int i=1;i<=n;i++)
{
int cnt=0;//记录变化次数
if(s[i][1]=='#') cnt++;//假设s[i][0]是'.'
for(int j=2;j<=m;j++)
if(s[i][j]!=s[i][j-1]) cnt++;
if(cnt>2)
{
puts("-1");
return 0;
}
if(!cnt) flag1=0;
}
for(int i=1;i<=m;i++)
{
int cnt=0;
if(s[1][i]=='#') cnt++;
for(int j=2;j<=n;j++)
if(s[j][i]!=s[j-1][i]) cnt++;
if(cnt>2)
{
puts("-1");
return 0;
}
if(!cnt) flag2=0;
}
if(flag1!=flag2)
puts("-1");
else
{
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(s[i][j]=='#'&&!st[i][j])
{
dfs(i,j);
ans++;
}
cout<<ans;
}
return 0;
}