A. Puzzle Pieces

思路：
规律题，

1. 横列有一个值为1，另一个是多少都是合法的
2. 行列的最小值为2的时候，行列的最大值必须也等于2才行，
3. 其他情况都是非法的
   代码：

#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-1$

p−1高的金字塔有这个关系
$s[p]=s[p-1]+3*p-1$

s[p]=s[p−1]+3∗p−1。我们可以先预处理出高度为p的金字塔所需的字牌数。
对于n张牌，可以二分算出所需牌数小于
$n$

n的最大高度。然后一直循环直到
$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,

1. 对于
   $iin[0,n-1]$

   i∈[0,n−1]房间的顾客，他们移去的位置是
   $i + a_i$

   i+ai​

2. 对于
   $iin [n,2*n-1]$

   i∈[n,2∗n−1]房间的顾客，他们移去的位置是
   $n + (i$

   n+(i%n)+a(i%n)​

3. 对于
   $iin [k*n,(k+1)*n-1]$

   i∈[k∗n,(k+1)∗n−1]房间的顾客，他们移去的位置是
   $k*n + (i$

   k∗n+(i%n)+a(i%n)​
   可以观察出他们他们呢相差仅仅是
   $k*n$

   k∗n而已，所以，若
   $[0,n-1]$

   [0,n−1]房间的顾客移去位置
   $\mathrm{\%}n$

   %n后不会互相冲突（可以看作
   $[0,n-1]$

   [0,n−1]的每个位置都被一一占据），则
   $[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

思路:
分类讨论

1. 从样例2可以看出，不能存在凹图，所以我们可以记录每行每列黑色格子出现的最小值于最大值，若存在一个白色格子在最小值与最大值之间，则就是凹图了，
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("%dn", solve()); else puts("-1"); return 0; } 

E. Quantifier Question

思路：
差分约束
若有
$x_i<x_j$

xi​<xj​,则可以看作
$x_jgeq x_i+1$

xj​≥xi​+1,是不是很像差分约束，因此我们可以连一条边
$x_i->x_j$

xi​−>xj​，边权为1，对图跑最长路，即是每个变量的取值，若图中存在正环，则关系就是非法的了，因为边权全部都是1，所以只用判图是否有环即可。

1. 先用判是否图是否存在环，存在环直接结束
2. 一个不存在环的图，分析发现若一个点的值确定了，则和这个点是一条路径上的其他点都不能是任意值（只能比这个点的值小或者大），因此其他路径上的点都只能是E，
3. 这里我们可以建一个正图，再建一个反图，从
   $1-n$

   1−n,若这个点还没确定，则它可以是任意值，因此是A。然后在正图中，以这个点为起点，把大于它的点都标记为已确定，在反图在把小于它的点标记一遍，

4. 然后就确定了
   开始傻傻的还以为是所有入度为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("%dn", ct); for (int i = 1; i <= n; ++ i) putchar(ans[i]); puts(""); return 0; } 

F. Résumé Review

二分，目前还补不动，贴个其它博客的题解吧
F题