闲话
又是只有ABC的VP.D差一点就做完了.这个D主要就是想法稍微有点困难,情况没考虑完全就裂开了.本身这个题算不上多难.由于这场最后unrated了,所以评分也不太准确.
A. Puzzle Pieces
题目大意:给你一个有三个凸口一个凹口的拼图片,问你能不能拼出一个(n*m)的整块的拼图.
思路
显然只有一行或者一列的时候必然可以,如果多扩展,只有(2*2)的可以做出来,其他的都不行.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int a,b;scanf("%d%d",&a,&b);
if(a == 1 || b == 1) puts("YES");
else if(a == 2 && b == 2) puts("YES");
else puts("NO");
}
return 0;
}
B. Card Constructions
原题大意:让你用纸牌磊一个塔出来.塔的形式如下图.受伤一开始有(n)个牌,每次都会摆出最大能摆出的塔,直到不能摆任何一个塔为止,问最多能摆出多少个塔.
思路
递推式子很好想,先打个暴力看一下大概(10^9)有多少种塔.算出来也就两万多个,数量很小.显然可以直接把所有的都打出来,算出要的数量,之后一直迭代二分出离(n)最近的塔的数量是多大,直到(n)没有结果为止.顺便记个数,答案就做完了.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+7,M = 1e9 + 1e5;
vector<ll> cost;
void init()
{
cost.push_back(2);
ll cur = 5;
while(cost.back() + cur <= M)
{
cost.push_back(cost.back() + cur);
cur += 3;
}
// cout << cur << endl;
}
int main()
{
init();
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
vector<ll>::iterator iter;
int res = 0;
while((iter = upper_bound(cost.begin(),cost.end(),n)) != cost.begin())
{
--iter;
// cout << (*iter) << endl;
++res;
n -= (*iter);
}
printf("%d
",res);
}
return 0;
}
C. Hilbert's Hotel
原题大意:有无穷多个整数,且存在负数.给你(n)个数的数列(a)并且从(0)开始.对于每个整数(k),让每个整数变成(i+a_{i\%n}).问是否存在两个不同的整数(i,j)在这样移动之后值相等了.
数据范围:
(1 leq n leq 2*10^5)
(-10^9 leq a_i leq 10^9)
思路
显然就是要求一个不定方程(i + a_{i%n} = j +a_{j%n})是否存在一个整数解,并且两边不同.由于整个表达式里存在一个取余的式子,这很不牛逼,先把取余的拆掉,变成一个牛逼的好做的形式.对于(i\%n)设(i\%n=x)进而可以把(i)表示成(k_1*n+x)其中(k_1)是一个整数,同理,也可以这样把(j)替换掉,那么之后可以得到一个形式牛逼的式子:((k_1-k_2)*n=(a_y+y)-(a_x+x)).显然这个式子如果要成立,也就是要有整数解的话,因为((k_1-k_2))肯定就是一个整数没什么,那么就得满足右边的是整除(n)的才行,如果设(c_x=x+a_x)的话,那么等式的判据实际上就是(n|(c_y-c_x))也即(c_yequiv c_x(mod n)).只要存在一组(c_x)和(c_y)在模(n)的意义下同余就说明存在两个数最后会相等.
这个题分析到这里,最后就写个(set)保存所有的余数,看有没有相同的就可以了.不过要防范负数取模,因为这里(a_i)是存在负数的,因此要特殊处理.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+7;
int a[N];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
for(int i = 0;i < n;++i) scanf("%d",&a[i]);
set<int> tlb;
int ok = 1;
for(int i = 0;i < n;++i)
{
int b = ((a[i] + i) % n + n) % n;
if(tlb.count(b))
{
ok = 0;
break;
}
tlb.insert(b);
}
if(ok) puts("YES");
else puts("NO");
}
return 0;
}
D. Monopole Magnets
原题大意:太难翻了,去洛谷看吧链接
思路
假如这个图是合法的,那么答案应该就是整个图里黑色的联通块的数量,这个直接(dfs)就可以轻松解决了.难就难在这个题判断无解比较麻烦.
首先比较容易看到的,第二个样例给出的一种情况,即如果一行一列里出现了两个被隔开的黑色块,那么就无解,这是因为一行一列里必须要有一个不动块,那个不动块在这一行或者列里必须也有一个,可以发现不管怎么放都必然使一边的黑色块被吸引到一个白色块上(就是被夹着的白色块部分).
还有一种,样例没有明显的给出,可以手画想到的:如果一行或列是全白的,那么如果除此之外没有一个全白的列或行就会无解.这个结论说的是:要么存在全白的行和列,要么都不存在.假如只存在一个,那么必然会导致旁边的有黑色块的部分被吸引过去,因为那一行或列的纯白区域也至少要放一个不动块,这导致了矛盾.但是如果存在另外一个,情况就不一样了,可以完全照着对角线的斜线方向放,既可以避免把黑色块吸引过去,又可以保证每行每列至少一个的条件.至此,判断无解的部分就完了.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
char g[N][N];
const int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
int allwr[N],allwc[N],exbr[N],exbc[N];
int n,m;
void dfs(int x,int y)
{
g[x][y] = '$';
for(int i = 0;i < 4;++i)
{
int a = x + dx[i],b = y + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m || g[a][b] != '#') continue;
dfs(a,b);
}
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> m;
for(int i = 0;i < n;++i) cin >> g[i];
int ok = 1;
//row
for(int i = 0;i < n;++i)
{
int cur = 0;
for(int j = 0;j < m;++j)
{
if(cur == 2 && g[i][j] == '#')
{
ok = 0;
break;
}
if(g[i][j] != '#' && cur == 1) cur = 2;
if(g[i][j] == '#' && cur == 0) cur = 1;
}
if(!cur) allwr[i] = 1;
else exbr[i] = 1;
}
//col
for(int i = 0;i < m;++i)
{
int cur = 0;
for(int j = 0;j < n;++j)
{
if(cur == 2 && g[j][i] == '#')
{
ok = 0;
break;
}
if(g[j][i] != '#' && cur == 1) cur = 2;
if(g[j][i] == '#' && cur == 0) cur = 1;
}
if(!cur) allwc[i] = 1;
else exbc[i] = 1;
}
int exr = 0,exc = 0;
for(int i = 0;i < n;++i)
if(allwr[i])
exr = 1;
for(int i = 0 ;i < m;++i)
if(allwc[i])
exc = 1;
if(exr && !exc || exc && !exr) ok = 0;
if(!ok) puts("-1");
else
{
int res = 0;
for(int i = 0;i < n;++i)
for(int j = 0;j < m;++j)
if(g[i][j] == '#')
{
++res;
dfs(i,j);
}
printf("%d
",res);
}
return 0;
}