Codeforces Round #639 Div. 2
- A. Puzzle Pieces
- B. Card Constructions
- C. Hilbert's Hotel
- D. Monopole Magnets
- E. Quantifier Question
- F. Résumé Review
A. Puzzle Pieces
思路：
规律题，
- 横列有一个值为1，另一个是多少都是合法的
- 行列的最小值为2的时候，行列的最大值必须也等于2才行，
- 其他情况都是非法的
代码：
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;
typedef double db;
int main()
{
int t; cin >> t;
while (t --)
{
int n, m; cin >> n >> m;
if(n == 1 || m == 1) puts("YES");
else if(n == 2 && m == 2) puts("YES");
else puts("NO");
}
return 0;
}
B. Card Constructions
思路：
观察可以发现第 p p p高的金字塔和第 p − 1 p-1 p−1高的金字塔有这个关系 s [ p ] = s [ p − 1 ] + 3 ∗ p − 1 s[p]=s[p-1]+3*p-1 s[p]=s[p−1]+3∗p−1。我们可以先预处理出高度为p的金字塔所需的字牌数。
对于n张牌，可以二分算出所需牌数小于 n n n的最大高度。然后一直循环直到 n < 2 n < 2 n<2即可
代码：
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;
typedef double db;
const int N = 1e5 + 5;
ll s[N];
int main()
{
s[1] = 2;
int p;
for (p = 2; ; ++ p)
{
s[p] = s[p - 1] + 3 * p - 1;
if(s[p] >= 1e9) break;
}
int t; cin >> t;
while (t --)
{
int n; cin >> n;
int ct = 0;
while (n >= s[1])
{
int l = 1, r = p;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if(s[mid] <= n) l = mid; else r = mid - 1;
}
ct ++;
n -= s[l];
}
cout << ct << endl;
}
return 0;
}
C. Hilbert’s Hotel
思路:
读半天题，没懂啥意思，T~T,
- 对于 i ∈ [ 0 , n − 1 ] i\in[0,n-1] i∈[0,n−1]房间的顾客，他们移去的位置是 i + a i i + a_i i+ai
- 对于 i ∈ [ n , 2 ∗ n − 1 ] i\in [n,2*n-1] i∈[n,2∗n−1]房间的顾客，他们移去的位置是 n + ( i % n ) + a ( i % n ) n + (i\%n) + a_{(i\%n)} n+(i%n)+a(i%n)
- 对于 i ∈ [ k ∗ n , ( k + 1 ) ∗ n − 1 ] i\in [k*n,(k+1)*n-1] i∈[k∗n,(k+1)∗n−1]房间的顾客，他们移去的位置是 k ∗ n + ( i % n ) + a ( i % n ) k*n + (i\%n) + a _ {(i\%n)} k∗n+(i%n)+a(i%n)
可以观察出他们他们呢相差仅仅是 k ∗ n k*n k∗n而已，所以，若 [ 0 , n − 1 ] [0,n-1] [0,n−1]房间的顾客移去位置 % n \%n %n后不会互相冲突（可以看作 [ 0 , n − 1 ] [0,n-1] [0,n−1]的每个位置都被一一占据），则 [ n − + ∞ ) [n-+\infty) [n−+∞)之后都不会冲突了
代码：
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;
typedef double db;
const int N = 2e5 + 5;
bool v[N];
int main()
{
int t; scanf("%d", &t);
while (t --)
{
int n; scanf("%d", &n);
for (int i = 0; i <= n; ++ i) v[i] = 0;
for (int i = 0; i < n; ++ i)
{
int j; scanf("%d", &j);
v[((i + j ) % n + n) % n] = 1;
}
int ok = 1;
for (int i = 0; i < n; ++ i)
if(!v[i])
{
ok = 0;
break;
}
if(ok) puts("YES");
else puts("NO");
}
return 0;
}
D. Monopole Magnets
思路:
分类讨论
- 从样例2可以看出，不能存在凹图，所以我们可以记录每行每列黑色格子出现的最小值于最大值，若存在一个白色格子在最小值与最大值之间，则就是凹图了，
- 对于一行没有一个黑色格子，但是这一行中必须放一个S，因此只能选一列没有黑色格子的列放置，（可以分析出放有黑色格子的列，一定会N移动到白色位置，所以不合法），所以一个位置，该行该列都没有白色格子，则可以放S
因此先判断是否合法，若合法，则可以用深搜求联通块的数量，联通块的数量即是最小的N的数量。
代码：
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;
typedef pair<int, int> pii;
typedef double db;
const int N = 1e3 + 5;
const int dir[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};
bool r[N], c[N], rr[N], cc[N], v[N][N];
char s[N][N];
int rf[N][2], cf[N][2];
int n, m;
void dfs(int x, int y)
{
v[x][y] = 1;
for (int i = 0; i < 4; ++ i)
{
int tx = x + dir[i][0], ty = y + dir[i][1];
if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && s[tx][ty] == '#' && !v[tx][ty])
dfs(tx, ty);
}
}
int solve()
{
int res = 0;
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= m; ++ j)
{
if(!v[i][j] && s[i][j] == '#')
{
dfs(i, j);
res ++;
}
}
return res;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++ i) cin >> s[i] + 1;
for (int i = 1; i <= n; ++ i) rf[i][0] = 0x3f3f3f3f;
for (int i = 1; i <= m; ++ i) cf[i][0] = 0x3f3f3f3f;
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= m; ++ j)
{
if(s[i][j] == '#')
{
r[i] = c[j] = 1;
rf[i][0] = min(rf[i][0], j);
rf[i][1] = max(rf[i][1], j);
cf[j][0] = min(cf[j][0], i);
cf[j][1] = max(cf[j][1], i);
}
}
int ok = 1 ;
for (int i = 1; i <= n; ++ i)
{
for (int j = 1; j <= m; ++ j)
{
if(s[i][j] == '.')
{
if(!r[i] && !c[j]) rr[i] = cc[j] = 1;
if(rf[i][1] && rf[i][0] < j && rf[i][1] > j || cf[j][1] && cf[j][0] < i && cf[j][1] > i)
{
ok = 0;
break;
}
}
}
if(!ok) break;
}
for (int i = 1; i <= n; ++ i) if(!r[i] && !rr[i]) ok = 0;
for (int i = 1; i <= m; ++ i) if(!c[i] && !cc[i]) ok = 0;
if(ok) printf("%d\n", solve());
else puts("-1");
return 0;
}
E. Quantifier Question
思路：
差分约束
若有 x i < x j x_i<x_j xi<xj,则可以看作 x j ≥ x i + 1 x_j\geq x_i+1 xj≥xi+1,是不是很像差分约束，因此我们可以连一条边 x i − > x j x_i->x_j xi−>xj，边权为1，对图跑最长路，即是每个变量的取值，若图中存在正环，则关系就是非法的了，因为边权全部都是1，所以只用判图是否有环即可。
- 先用判是否图是否存在环，存在环直接结束
- 一个不存在环的图，分析发现若一个点的值确定了，则和这个点是一条路径上的其他点都不能是任意值（只能比这个点的值小或者大），因此其他路径上的点都只能是E，
- 这里我们可以建一个正图，再建一个反图，从 1 − n 1-n 1−n,若这个点还没确定，则它可以是任意值，因此是A。然后在正图中，以这个点为起点，把大于它的点都标记为已确定，在反图在把小于它的点标记一遍，
- 然后就确定了
开始傻傻的还以为是所有入度为0点都可以标记为A，其余的点都是E，后来才发现变量的顺序是固定的，所以不能这么玩。
代码：
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;
typedef pair<int, int> pii;
typedef double db;
const int N = 2e5 + 5;
struct edge
{
int y, nxt;
}e[N], er[N];
int p[N], pr[N], dfn[N], low[N], stk[N];
int tot, tp, n, m, eid, eidr, ok = 1, cnt;
bool ins[N], vr[N], v[N];
char ans[N];
void add(int x, int y)
{
e[eid] = edge{y, p[x]}; p[x] = eid ++;
}
void addr(int x, int y)
{
er[eidr] = edge{y, pr[x]}; pr[x] = eidr ++;
}
void tarjan(int x)
{
if(!ok) return;
dfn[x] = low[x] = ++ tot;
stk[++ tp] = x; ins[x] = 1;
for (int i = p[x]; ~i; i = e[i].nxt)
{
int y = e[i].y;
if(!dfn[y])
{
tarjan(y);
low[x] = min(low[x], low[y]);
}
else if(ins[y])
{
ok = 0;
low[x] = min(low[x], dfn[y]);
}
}
if(low[x] == dfn[x])
{
++ cnt;
do
{
ins[stk[tp]] = 0;
}while (stk[tp --] != x);
}
}
void dfs(int x)
{
v[x] = 1;
for (int i = p[x]; ~i; i = e[i].nxt)
{
int y = e[i].y;
if(v[y]) continue;
dfs(y);
}
}
void dfsr(int x)
{
vr[x] = 1;
for (int i = pr[x]; ~i; i = er[i].nxt)
{
int y = er[i].y;
if(vr[y]) continue;
dfsr(y);
}
}
int main()
{
scanf("%d%d", &n, &m);
memset(p, -1, sizeof(p));
memset(pr, -1, sizeof(pr));
for (int i = 1; i <= m; ++ i)
{
int x, y; scanf("%d%d", &x, &y);
add(x, y);
addr(y, x);
}
for (int i = 1; i <= n; ++ i)
if(!dfn[i]) tarjan(i);
if(!ok) return puts("-1"), 0;
int ct = 0;
for (int i = 1; i <= n; ++ i)\
{
if(!vr[i] && !v[i])
ct ++, ans[i] = 'A';
else ans[i] = 'E';
dfs(i); dfsr(i);
}
printf("%d\n", ct);
for (int i = 1; i <= n; ++ i) putchar(ans[i]);
puts("");
return 0;
}
F. Résumé Review
二分，目前还补不动，贴个其它博客的题解吧
F题
