ABC 269 （A-G）

A

给定 \(a,b,c,d\)，输出 \((a+b)(c-d)\) 和 \(\texttt{Takahashi}\)。

模拟即可。

int a = read(), b = read(), c = read(), d = read();
writeln((a+b)*(c-d));
ToA(1);

t.c. \(O(1)\)

B

给定一个矩形图，求它的左上角和右下角。

注意到一个点 \((i,j)\) 是左上角 \(\iff S_{i-1,j} = S_{i,j-1} = S_{i-1,j-1} = \texttt{"."} \wedge S_{i,j} = \texttt{"#"}\)；一个点 \((i,j)\) 是右下角 \(\iff S_{i+1,j} = S_{i,j+1} = S_{i+1,j+1} = \texttt{"."} \wedge S_{i,j} = \texttt{"#"}\)。

Fi scanf("%s", c[i] + 1);
Fi Fj if (c[i][j] == '#') {
	if (c[i-1][j] != '#' && c[i][j-1] != '#' && c[i-1][j-1] != '#')
		l1 = i, l2 = j;
	if (c[i+1][j] != '#' && c[i][j+1] != '#' && c[i+1][j+1] != '#')
		r1 = i, r2 = j;
}
printf("%d %d\n%d %d\n", l1, r1, l2, r2);

t.c. \(O(n^2)\)

C

解方程 \(x \vee n = n\)。

1

枚举每一位取或不取。\(\tt dfs\)。

2

位运算板子。

ll x = read();
stack<ll> s;
for (ll i = x; i; i = (i-1) & x) s.push(i);
writeln(0);
while (!s.empty()) writeln(s.top()), s.pop();

t.c. \(O(2^{{\rm popcnt}(n)})\)

D

给定一个 \(01\) 矩阵 \(M\)，无向图 \(G\) 中点 \((i,j)\) 存在 \(\iff M_{i,j}\)，\((i,j)\) 点（如果在 \(G\) 中存在）连且仅连向 \((i−1,j−1),(i−1,j),(i,j−1),(i,j+1),(i+1,j),(i+1,j+1)\) 中所有在 \(G\) 中存在的点，求 \(G\) 的 SCC 数目。

进行 \(\tt dfs\)，\(\tt floodfill\)。

int n = read(), b[5005][5005], ans;
void dfs(int x, int y) {
	if (b[x][y] != 1) return;
	b[x][y] = 2;
	dfs(x-1, y-1);
	dfs(x-1, y);
	dfs(x, y-1);
	dfs(x, y+1);
	dfs(x+1, y);
	dfs(x+1, y+1);
}
int main() {
	Fi b[read() + 1010][read() + 1010] = 1;
	F(i, 1, 2050) F(j, 1, 2050)
		if (b[i][j] == 1) ans ++, dfs(i, j);
	writeln(ans);
	return 0;
}

t.c. \(O(n^2)\)

E

给定一个 \(01\) 矩阵 \(M\)，其中 \(\sum M_{i,x} \ne 1 \iff x = X\)，\(\sum M_{y,i} \ne 1 \iff y = Y\)，可以查询 \(\sum\limits_{i=a}^b \sum\limits_{j=c}^d M_{i,j}\)，求 \(X\) 和 \(Y\)。

二分 \(X,Y\)。

l1 = 1, r1 = n; l2 = 1, r2 = n;
for (;m1 = (l1 + r1) / 2, l1 < r1;) {
	printf("? %d %d %d %d\n", l1, m1, 1, n);
	fflush(stdout);
	int r = read();
	if (r != (m1 - l1 + 1)) r1 = m1;
	else l1 = m1 + 1;
}
for (;m2 = (l2 + r2) / 2, l2 < r2;) {
	printf("? %d %d %d %d\n", 1, n, l2, m2);
	fflush(stdout);
	int r = read();
	if (r != (m2 - l2 + 1)) r2 = m2;
	else l2 = m2 + 1;
}
printf("! %d %d\n", m1, m2);
fflush(stdout);

t.c. = q.c. \(O(\log n)\)

F

求 \(\sum\limits_{i=a}^b \sum\limits_{j=c}^d ((i-1)m+j) \times ((i+j-1) \bmod 2)\)。

设函数 \(g(x,y) = \sum\limits_{i=1}^x \sum\limits_{j=1}^y ((i-1)m+j) \times ((i+j-1) \bmod 2)\)，则答案为 \(g(b,d) - g(a-1,c) - g(b,c-1) + g(a-1,c-1)\)。
如果我们要求 \(g(x,y)\)，首先求出 \(g(2,y)\)，因为 \(a_i = g(2i,y) - g(2i - 2,y)\) 是一个 \(d=2mx\) 的等差数列。于是 \(\sum\limits_{i=1}^{x/2} a_i\) 可以用等差数列求和公式求出。
于是我们在 \(x \bmod 2 = 1\) 的情况下，只剩最后一排。最后一排是一个 \(d=2\) 的等差数列，分类讨论求出即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int n,m,q,inv=mod/2+1;
int f(int y,int x) 
{
	if(x*y==0||max(x,y)<0)return 0;
	int twoL=(((x/2)*m%mod)+(x*(x+1)%mod*inv%mod))%mod;
	int d=2*m%mod*x%mod;int MX=0;
	if(y/2>=1)MX=(twoL+d*(y/2-1)%mod)%mod;
	int R=(twoL+MX)*(y/2)%mod*inv%mod;
	x++;
	if(y&1)R=(R+(x/2)*(x/2-1)%mod+(x/2)*(((y-1)*m+1)%mod)%mod)%mod;
	return (R%mod+mod)%mod;
}
signed main()
{
	cin>>n>>m>>q;	
	while(q--)
	{
		int a,b,c,d;cin>>a>>b>>c>>d;
		cout<<(f(b,d)-f(b,c-1)-f(a-1,d)+f(a-1,c-1)+mod+mod)%mod<<endl;
	}
	return 0;
}

t.c. \(O(q)\)

G

对于每一个 \(k \in [0,m]\)，\(C_i := \left\{\begin{matrix} A_i & D_i \\ B_i & \neg D_i \end{matrix}\right.\)，要求 \(\sum C = k\)，求 \(\min \sum D\)。
特殊限制：\(\sum A + \sum B = m\)。

定义 \(\delta_i := B_i - A_i, \sigma = \sum A\)。则有朴素 DP：\(f_{0,\sigma} = 0; f_{0,x} = \infty(x \ne \sigma); f_{i,x} = \min\{f_{i-1,x}, f_{i-1,x+\delta_j}+1\}\)。

定理 \(1\)：\(\sum |\delta_i| \le m\)
证明：\(|\delta_i| \le |B_i| + |-A_i| = B_i + A_i\)，\(\sum |\delta_i| \le \sum B_i + \sum A_i = m\)。

定理 \(2\)：\(\delta\) 的不同元素数量最多为 \(O(\sqrt m)\)。
证明：考虑构造不同元素数量最高的 \(\delta\)，显然 \(\delta\) 为不可重集。所以 \(\sum |\delta_i| = 0+1+1+2+2+\dots\) 于是 \(f(|\delta|) = \sum |\delta_i|\) 是 \(O(n^2)\) 的，\(f^{-1}(\sum |\delta_i|) = f^{-1}(m) = O(\sqrt m)\)。

定理 \(3\)：\(\forall x \in [0,n] \exists S \subseteq \{2^0,2^1,\dots,2^{\lfloor \log (n+1) \rfloor -1}, n - 2^{\lfloor \log (n+1) \rfloor} + 1\}\)
证明（非严格）：取最后一个元素和不取最后一个元素所可能造成的集合的并集恰好是 \([0,n]\)。

艹，不会，去补微积分去了。