这次的abc打的很愉快，记录下。

传送门->
abc422

A

A题就是输入输出题，直接模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

int a,b;
char c;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> a >> c >> b;
	if(b==8)cout << a+1 << c << 1;
	else cout << a << c << b+1;

	return 0;
}

B

B题是求一个H*W的方格中，涂上黑色#、白色.的点，输出对于每个黑色#点是否满足：

  • 水平或垂直相邻的被涂成黑色的单元格的数目是2或4

Constraints:

  • $1\le H\le 20$
  • $1\le W\le 20$
  • $H$ and $W$ are integers.
  • $S _ i$ is a string of length $W$ consisting of . and # $(1\le i\le H)$.

思路

思路很简单，遍历所有的黑色#点，然后判断其周围（上下左右）有多少个黑色#点，如果不为2或4则输出No并break。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
int h,w;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> h >> w;
	vector<vector<int> > g(h+1,vector<int> (w+1,0));
	for(int i=1;i<=h;i++)
	{
		for(int j=1;j<=w;j++)
		{
			char c; cin >> c;
			if(c=='#')g[i][j]=1;
			else g[i][j]=0;
		}
	}
	for(int i=1;i<=h;i++)
	{
		for(int j=1;j<=w;j++)
		{
			if(g[i][j]==1)
			{
				int cnt=0;
				for(int k=0;k<4;k++)
				{
					int nx=i+dx[k],ny=j+dy[k];
					if(nx>=1&&nx<=h&&ny>=1&&ny<=w&&g[nx][ny]==1)cnt++;
				}
				if(cnt!=2&&cnt!=4)
				{
					cout << "No" << endl;
					return 0;
				}
			}
		}
	}
	cout << "Yes" << endl;
	return 0;
}

C

给出 $n_A$ 个字母A、 $n_B$ 个字母B、$n_C$ 个字母C，这些字母取三个可以组成一个比赛：

  • 取两个A和一个C取组成AAC
  • 分别取一个A、B、C可以组成ABC
  • 取一个A和两个C可以组成ACC

求用这些字母最多可以组成多少个比赛。

Constraints:

  • $1\le T\le2\times10 ^ 5$
  • For each test case,
    • $0\le n _ A\le10 ^ 9$
    • $0\le n _ B\le10 ^ 9$
    • $0\le n _ C\le10 ^ 9$
  • All input values are integers.

思路

我们欲组合成最多的比赛，首先注意到这三个比赛对于A和C的消耗是最大的，我们不妨先用min(nA,nB,nC)作为比赛ABC的贡献，那么剩下的A和C就可以组成AAC或ACC，分别取min(nA,nC/2)和min(nA/2,nC)（先组成ACC再AAC或者先AAC再ACC），然后再加上min()即可。

1
2
3
4
5
6
7
8
9
ll ans=min({nA, nB, nC});
nA-=ans, nB-=ans, nC-=ans;
ll s1=min(nA,nC/2);
ll nnA=nA-s1, nnC=nC-2*s1;
s1+=min(nnA,nnC/2);
ll s2=min(nA/2,nC);
nnA=nA-2*s2, nnC=nC-s2;
s2+=min(nnA,nnC/2);
ans+=max(s1,s2);

但是这样一定对吗？（作者因为这个不正确的贪心已经wa4发才发现反例😫）我们很容易举个反例，当nA=7, nB=0, nC=5时，我们按照sol函数的逻辑，那么只能取得AAC=3即一共三个比赛，但是如果我们这样取ACC=1, AAC=3一共四场比赛。

稍加思考，注意到在选择极大的ABC后（即nA-=min(nA,nB,nC), nC-=min(nA,nB,nC)），如果我们取x个AAC、y个ACC，一定满足以下关系：

考虑在这个区域内，找到 $M=(x+y)_{max}$，即找到直线 $x+y-M=0$ 在区域内整点使得 $M$ 最大，可以参考下图：

abc422c.gi

我们考虑对于直线 $x+y-M=0$ 的坐标变换，将坐标系逆时针旋转45°得到该直线水平放置，不难想到当M取到最大时，恰好在规划区域的顶点 $(\frac{2n_A-n_C}{3},\frac{2n_C-n_A}{3})$ 取道最大值 $M=\frac{n_A+n_C}{3}$ ，整点取其下取整即可。

一定要注意这个图上的前提，$n_A,\ n_B \ge 0$ ，代码应该是ans+=max({(nA+nC)/3, nA, nC})

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define ll long long

void sol()
{
	ll nA, nB, nC;cin >> nA >> nB >> nC;
	ll ans=min({nA, nB, nC});
	nA-=ans, nB-=ans, nC-=ans;
	ans+=min({(nA+nC)/3, nA, nC});
	cout << ans << endl;	
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t; cin >> t;
	while(t--)sol();

	return 0;
}

D

对于一个长度为 $2^N$ 的非负整数组 $A={a1,a_2, \cdots a{2^N-1}, a_{2^N}}$ ，我们定义不平衡度 $X$ ，满足以下规则：

  • 起初 $X:=0$
  • 接下来 $X:=\max(X,\max(A)-\min(A))$
  • 然后选择 $i<2^N-1, \ ai:=a_i+a{i+1}$ 即依次选择两个相邻的元素，合并这两个元素
  • 重复上述步骤直到只剩下一个元素，此时的 $X$ 就是不平衡度

给出 $N$ 和 $K$ （数组A元素和），求不平衡度最小时数组 $A$。

Constraints:

  • $1 \leq N \leq 20$
  • $0 \leq K \leq 10^9$
  • $N$ and $K$ are integers.

思路

显然地，这题又是一个均摊的经典问题，我们只需要将 $K$ 均摊到每个元素上，一个很显然的就是直接 $a_i=\frac{K}{2^N}$ 。但是考虑到这里是整数，考虑下取整后剩下的 $r = K\pmod{2^N}$ ，当r不为0时，我们可以证明总存在一个数组可以使得不平衡度最小为1，反则可以直接均摊不平衡度为0。

下面我们来考虑这个r应该如何分配：我们希望整个合并过程中任意时刻 $\max - \min \le 1$，所以必须保证任意一段连续区间的元素和最多只比另一段大 $1$。为此，我们将 $r$ 个 $+1$ 尽可能均匀地分布在 $2^N$ 个位置上。

具体的做法是：

设 $M=2^N$ 此时令每个位置为：

其中 $t_i$ 满足：

这样总能保证：

  • 总共有 $r$ 个位置是 $p+1$，其余是 $p$；
  • 任意长度为 $2^k$ 的连续区间内的 +1 数量与其长度成比例，误差不超过 1；
  • 因此在整个合并过程中，所有区间的和之差始终 $\le 1$，即不平衡度 $X = 1$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'

ll n,k;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	ll N=(ll)1<<n;
	ll p=k/N, q=k%N;
	ll u=(q==0? 0:1);
	cout << u << endl;
	for(ll i=0; i<N; i++)
	{
		ll t=((i+1)*q/N)-((i*q)/N);
		cout << p+t << " ";
	}
	return 0;
}