ATC 做题记录

如果一场里出现了但是没有题解的题代表还没写或没做，否则代表太水了。

AGC and similar

AGC006

A

B

C

D

E

F - Blackout

将 \((x,y)\) 看作是一条有向边 \(x\to y\)，显然可以在一个弱连通块里考虑。

将这个若联通块三染色，\(u\to v,c_v=c_u+1\pmod 3\)。然后开始分类讨论。

  1. 如果存在三染色并且有的颜色没有用到，那么一定不能连新的边。

  2. 如果存在三染色并且每种颜色都用到了那么两两颜色之间都可以连。

  3. 如果不存在三染色，那么没对点之间都会连边，包括自环。

对于第三点，可以考虑一定会有一个环，那么就可以对于环上的一个点直接跳过它。

于是直接做即可，复杂度 \(O(n+m)\)。

AGC008

A

B

C

D. K-th K

我们按 x 从大到小考虑，要在前面放数，每次尽量往后放。然后再从前往后考虑，显然先把前面的空补齐，然后贪心尽量往前放即可。

E

F

AGC014

A

B

C

D

E. Blue and Red Tree

正推明显比反推好推。考虑先把红边对应到蓝边的路径上，然后每次必然是找到一条只经过一次的边，把经过这条边的路径找出来删掉。不断做这个过程直到所有路径删除，如果中间有一次不止一条边就是NO。

思路简单，代码细节不是很好想。考虑在每个节点记录4个信息，区间mn，加法标记，完全经过这个区间的路径数量，完全经过这个区间的路径编号和。然后每次找只需找到一个完全经过某个区间的路径数量为1 的区间即可。

F

AGC021

A

B - Holes

题目的范围即为告诉你这是个平面，所以如果到某个点的范围是有限的话就是 \(0\) 了。那么有值的点一定是在凸包上的，多点共线时在中间的点有一维是有限长度的，所以共线也是零。接下来考虑怎么求。对于一条线段肯定是从中垂线切开，那么把一个点连的两条线段的中垂线求一下交点，算出角度，可以近似成在这个圆的占比，就求出来了。

#include 
using namespace std;
const double pii = acos(-1.0);
const double eps = 1e-8;
struct node{
	double x, y;
	int id;
	friend bool operator < (node a, node b) {
		if (a.x != b.x) return a.x < b.x;
		return a.y < b.y;
	}
}p[105], stk[105];
int top, mid;
int n;
double ans[105];
double tim(node a, node b) {
	return a.x * b.x + a.y * b.y;
}
node mis(node a, node b) {
	return node{a.x - b.x, a.y - b.y};
}
double cross(node a, node b) {
	return a.x * b.y - a.y * b.x;
}
double dis(node a, node b) {
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lf%lf", &p[i].x, &p[i].y);
		p[i].id = i;
	}
	if (n == 1) {
		printf("%.16lf\n", 1.0);
		return 0;
	}
	sort(p + 1, p + 1 + n);
	for (int i = 1; i <= n; i++) {
		while (top > 1 && cross(mis(stk[top], stk[top - 1]), mis(p[i], stk[top])) <= 0) top--;
		stk[++top] = p[i];
	}
	mid = top;
	for (int i = n; i >= 1; i--) {
		while (top > mid && cross(mis(stk[top], stk[top - 1]), mis(p[i], stk[top])) <= 0) top--;
		stk[++top] = p[i];
	}
	top--;
	if (top == 2) {
		for (int i = 1; i <= top; i++) {
			ans[stk[i].id] = 0.5;
		}
	} else {
		for (int i = top; i >= 1; i--) {
			int j = i - 1, k = i + 1;
			if (j == 0) j = top;
			if (k == top + 1) k = 1;
			ans[stk[i].id] = (pii - acos(tim(mis(stk[k], stk[i]), mis(stk[j], stk[i])) / dis(stk[k], stk[i]) / dis(stk[j], stk[i]))) / (2.0 * pii);
		}
	}
	for (int i = 1; i <= n; i++) printf("%.16lf\n", ans[i]);
	return 0;
}

C

D

E

F

AGC023

A

B

C

D

E

F - 01 on Tree

考虑解决一个更强的问题：每个节点是一个非空的 \(01\) 串。

记 \(a_i\) 是节点 \(i\) 上 \(0\) 的个数，\(b_i\) 是节点 \(i\) 上 \(1\) 的个数，然后考虑将一个节点合并到它的父亲上。可以证明我们每次合并 \(c_i=\frac{a_i}{b_i}\) 最大的何其父亲合并。为什么是这样的？考虑最后的排列是 \(p\)，然后交换 \(p_i,p_{i+1}\)，此时有 \(b_i\times a_{i+1}\ge a_i\times b_{i+1}\Rightarrow \frac{a_i}{b_i} \le \frac{a_{i+1}}{b_{i+1}}\)。也就是说 \(c_i\) 越大，放在前面越好。用单调队列来模拟这个过程即可。

AGC020

A

B

C

D

E

F. Arcs on a Circle

给定一个长度为 \(C\) 的圆和 \(n\) 条弧，第 \(i\) 条弧的长度为 \(l_i\)，随机放置在圆上，求覆盖整个圆的概率。\(1\le n\le 6,1\le C\le 50\)。

标签：状压dp，概率

先考虑选定一条弧作为起点（一定要选最长的），然后我们发现相对位置关系只考虑小数的相对大小关系，这个可以暴力枚举。将每个区间 \([i,i+1]\) 分成 \(N\) 份，在 \([0,NC]\cup \Z\) 的范围内选整点，使用状压dp，\(f[i,j,s]\) 左端点坐标不大于 \(i\) 的已经放完，最远到 \(j\) 包含 \(S\) 范围内圆弧。转移从选与不选考虑即可。

AGC027

A

B

C

D

E

F. Grafting

枚举一个位置作为第一变换，然后以他为根，找到需要变父亲的点，他要比他A树上的父亲早断，比B树上的父亲晚断，于是出现有一张有向图，判断它是不是DAG即可。

AGC030

C - Coloring Torus

妙妙构造题，但感觉没有铜牌题的难度。

首先根据样例提示不难想到每一行填一种数字的方法。同理没一斜线上也可以填一种数字。我们又发现 \(K=2N\)，于是考虑交错填。如果采用第一种填法，对于相同颜色会有影响，而第二种显然就不会了（因为相邻的会变恰好一个）。于是我们还得到了一种套路：这种相邻考斜线，四个对角那种再考虑一整行。

AGC034

A

B

C

D

D - Manhattan Max Matching

拆曼哈顿距离的另一个套路，可以拆成几个东西的max，然后建立4个新点，分别连边表示4种情况，然后跑最大费用最大流即可。

F

AGC035

A

B

C - Skolem XOR Tree

题解

D

E

F

AGC036

E - ABC String

先把相邻的相同的缩起来，然后数个数，不妨设 \(cnt_a，盲猜上界 \(3cnt_a\) 大概可以达到，先找到 \(ACB,BCA\) 这种把 \(C\) 删掉，如果没删完就找 \(AC,CA\) 这种删掉，然后必然出现 \(cnt_b=cnt_c\)，接下来删 \(BC,CB\)，但是注意不能有 \(ABCA,ACBA\) 这种，使用链表维护即可。

AGC037

E - Reversing and Concatenating

显然只会出现存在的字符，所以考虑把最小的移到开头。然后又因为是反转，所以我们不妨把最小的挪到末尾然后长度就可以倍增了。所以如果 \(2^{K}\) 比较大的时候直接这么做就行了。

我们再给出一个更具体的贪心，除了最后一次操作是选字典序最小的，其余全部选倒序字典序最小的，这样就可以在拼起来的时候将最小子串倍增了。

#include 
int N,K;
char S[10005],T[10005];
bool cmp(int a,int b){
	for(int i=1;i<=N;i++)
		if(S[a-i+1]S[b-i+1])return 0;
	return 1;
}
bool cmp2(int a,int b){
	for(int i=N;i>=1;i--)
		if(S[a-i+1]S[b-i+1])return 0;
	return 1;
}
void print(int a){
	for(int i=N;i>=1;i--)putchar(S[a-i+1]);
	putchar('\n');
}
int main(){
	scanf("%d%d%s",&N,&K,S+1);
	K=std::min(K,17);K--;
	for(int i=1;i<=K;i++){
		for(int i=N+1;i<=2*N;i++)
			S[i]=S[2*N-i+1];
		int pos=N;
		for(int i=N+1;i<=2*N;i++)
			if(cmp(i,pos))
				pos=i;
		for(int i=N;i>=1;i--)
			T[N-i+1]=S[pos-i+1];
		for(int i=1;i<=N;i++)
			S[i]=T[i];
	}
	for(int i=N+1;i<=2*N;i++)
		S[i]=S[2*N-i+1];
	int pos=N;
	for(int i=N+1;i<=2*N;i++)
		if(cmp2(i,pos))
			pos=i;
	print(pos);
	return 0;
}

ARC and similar

ARC072

F. Dam

我们发现那个公式可以扩展到 \(n\) 个，枚举最后一段没有倒水，\(dp_i*L=dp_j*(L-sv_i+sv_j)+svt_i-svt_j\)，然后cdq斜率优化。

其实还可以贪心，如果后面比前面热，一定是前面先到后面再加，否则是后面先加前面再到，所以维护一个单调队列即可。

ARC075

D - Mirrored

小清新输入输出题

设最后的数 \(n\) 的位数为 \(m\)，\(a_i=n/10^i \bmod 10\)。反转后的答案是 \(\sum\limits_{i=0}^{\lceil\frac{m}{2}\rceil}(10^{m-i}-10^i)(a_{i}-a_{m-i})=\sum\limits_{i=0}^{\lceil\frac{m}{2}\rceil}\overline{99\dots900\dots0}\cdot(a_{i}-a_{m-i})\)，有 \(i\) 个 \(0\)，\(m-2i\) 个 \(9\)。于是我们发现这一定是一个 \(9\) 的倍数，我们不妨直接除以一个 \(9\)。

\[\sum\limits_{i=0}^{\lceil\frac{m}{2}\rceil}\overline{11\dots100\dots0}\cdot(a_{i}-a_{m-i}) \]

然后我们又发现个位数之和 \(a_{m-i}-a_i\) 有关。于是个位就确定了而且只有两种可能，暴力枚举即可。而后面都有公因数 \(10\)，一起除掉即可。如果最后都算完发现数变成了 \(0\) 就合法。复杂度 \(O(m2^{m})\)。\(m\) 是枚举的位数。 根据尝试知道 \(n\) 是个 longlong 范围内的数，所以 \(m\) 枚举到 \(18\) 即可。

代码也非常小清新。

#include 
typedef long long ll;
using namespace std;
ll D, ans, m, pw[30], a, b;
void dfs(int i, ll num, ll now) {
	if (i > m / 2) { ans += num * (now == 0); return; }
	a = (now % 10 + 10) % 10, b = m - 2 * i;
	if ((now - (a * pw[b])) % 10 == 0)
		dfs(i + 1, i == 0 ? num * (10 - a - 1) : num * (10 - a), (now - (a * pw[m - 2 * i])) / 10);
	if ((now - (a - 10) * pw[b]) % 10 == 0)
		dfs(i + 1, num * a, (now - (a - 10) * pw[m - 2 * i]) / 10);
}
int main() {
	for (int i = 1; i <= 18; i++) pw[i] = pw[i - 1] * 10 + 1;
	cin >> D;
	if (D % 9) { puts("0"); return 0; }
	for (m = 1; m <= 18; m++) dfs(0, 1, D / 9);
	cout << ans << endl;
	return 0;
}

ARC077

F. SS

神仙结论题

ARC084

F - XorShift

不妨把这些数看成 \(\text{F}_2\) 下的多项式，两种操作可以定义为加法和 \(\times x\)。于是我们可以找到 \(\gcd A_i=D\)，显然最后的答案是 \(D\) 的倍数。多项式 gcd 可以通过辗转相除法实现。然后所求极为 \(KD\le M\)，类似数位dp，钦定前 \(k\) 位，如果 \(k>deg(D)\) 且第 \(k\) 位为 \(1\)，\([deg(D),k-1]\) 这些位置可以随便选，否则 \(k\) 比较小的时候 \(\mod D\) 可以得到唯一值，那么直接多项式取模然后判断即可。

#include 
const int maxn = 4005, mod=998244353;
template 
void read(T &x) {
	T flag = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') flag = -1;
	for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	x *= flag;
}
struct Poly{
	std::bitset<4005> F;
	int m;
	friend Poly operator%(Poly a,Poly b){
		while(a.m>=b.m){
			a.F^=b.F<<(a.m-b.m);
			while(a.m&&a.F[a.m-1]==0)a.m--;
		}return a;
	}
	void print(){
		for(int i=0;i=1;i--)
		if(s[i]=='1')
			ret.F.set(len-i);
	return ret;
}
Poly gcd(Poly a,Poly b){
	while(a.F.any()&&b.F.any()){
		if(a.mM.m)return puts("1"),0;
	for(int k=M.m-1;k>=D.m-1;k--)
		if(M.F[k])
			ans=(ans+pw[k-D.m+1])%mod;
	Poly now;now.F.reset();now.m=M.m;
	for(int i=D.m-1;i=0;j--){
		if(now.F[j]>M.F[j]){flag=0;break;}
		else if(now.F[j]

ARC087

F - Squirrel Migration

根据套路选重心会得到最大的距离，当这棵树有两个重心答案就是 \({(\frac{n}{2})!}^2\)。考虑只有一个重心，那么就是把子树拉出来，然后要求每个 \((i,p_i)\) 不在同一课子树内。我们设 \(g_i\) 代表钦定有 \(i\) 对 \((i,p_i)\) 在同一棵子树内，\(f_i\) 代表恰好有 \(i\) 个，那么 \(g_i=\sum_{j\ge i}\binom{j}{i}f_j\)，二项式反演得 \(f_i=\sum_{j\ge i}(-1)^{j-i}\binom{j}{i}g_j\)。答案即为 \(f_0\)。

考虑 \(g_i\) 怎么求。考虑 \(dp[i,j]\) 代表前 \(i\) 棵子树有 \(j\) 对被钦定了，转移考虑枚举第 \(i\) 棵子树有几对被钦定了。

#include
#define pb push_back
#define mp std::make_pair
#define pii std::pair
#define F first
#define S second
typedef long long ll;
typedef unsigned long long ull;
namespace _name{
	const int maxn=5005,mod=1e9+7,inf=0x3f3f3f3f;
	template
	inline void read(T &x){
		T flag=1;
		char ch=getchar();
		for(;!isdigit(ch);ch=getchar())if(ch=='-')flag=-1;
		for(x=0;isdigit(ch);ch=getchar())x=x*10+ch-'0';
		x*=flag;
	}
	template
	inline void write(T x){
		if(x==0)return putchar('0'),void();
		int sstk[20],ttop=0;
		while(x)sstk[++ttop]=x%10,x/=10;
		for(int i=ttop;i;i--)putchar(sstk[i]+'0');
	}
	template
	inline void print(T x,char End='\n'){
		if(x<0)x=-x,putchar('-');
		write(x);putchar(End);
	}
	inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
	inline int dec(int a,int b){return a-b<0?a-b+mod:a-b;}
	inline int mul(int a,int b){return 1ll*a*b%mod;}
	inline int ksm(int a,int b=mod-2){int ret=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ret=mul(ret,a);return ret;}
}using namespace _name;
int n,sz[maxn],stk[3],top,fac[maxn],ifac[maxn],son[maxn],m,f[maxn],dp[maxn][maxn],s,ans;
std::vectorvec[maxn];
int C(int x,int y){
	if(x<0||y<0||x=2)return print(mul(fac[n/2],fac[n/2])),0;
	for(int v:vec[stk[1]])son[++m]=v;
	for(int i=1;i<=m;i++)if(sz[son[i]]>sz[stk[1]])sz[son[i]]=n-sz[stk[1]];sz[stk[1]]=n;
	dp[0][0]=1;
	for(int i=1;i<=m;s+=sz[son[i++]]){
		for(int j=0;j<=s+sz[son[i]];j++)
			for(int k=0,now=1;k<=std::min(j,sz[son[i]]);now=mul(now,sz[son[i]]-k),k++)
				dp[i][j]=add(dp[i][j],mul(mul(dp[i-1][j-k],C(sz[son[i]],k)),now));
	}
	for(int i=1;i<=m;i++)for(int j=0;j<=s;j++)dp[i][j]=mul(dp[i][j],fac[n-j]);
	for(int i=0;i<=n;i++)ans=i&1?dec(ans,dp[m][i]):add(ans,dp[m][i]);
	printf("%d\n",ans);
	return 0;
}

ARC091

C - Flip,Flip, and Flip......

只需要考虑每个位置被翻了几次，特判只有一行或一列，否则边界都会被翻偶数次等于没变，中间都会被翻奇数次，所以答案是 \((n-2)(m-2)\)。

D - Remainder Reminder

枚举 \(b\) 以及其倍数，\(a\) 只能在 \([bx+k,b(x+1)-1]\) 内，注意边界。

E - LISDL

LIS 与 LDS 最多只有一个交点，所以 \(A+B\) 的上界是 \(N+1\)，然后手玩一下发现如果最后 A 个上升，然后 B-1 个下降，然后 A-1 个上升...... 这样是最优的，最后判一下如果这样都不行就无解了。

F - Strange Nim

神仙打表题。显然的求sg函数。查看题解打出表后发现如下规律：

\[sg(n)= \begin{cases} 0,n

然后我们考虑对相同的一段 \(\lfloor\frac{n}{k}\rfloor\) 一起算，设这个值为 \(x\)，考虑有 \(y\) 段，那么需要满足 \(n-y(x+1)\ge kx \Rightarrow y\le \lfloor\frac{n-kx}{x+1}\rfloor\)。

考虑时间复杂度，当 \(k\le \sqrt n\) 时 \(n\) 每次都会减少 \(\sqrt n\)，所以是 \(O(\sqrt n)\) 的；否则 \(x\) 每次减少 \(1\)，而 \(x\) 是 \(O(\sqrt{n})\) 的所以总复杂度也是 \(O(\sqrt{n})\) 的。

#include
#define pb push_back
#define mp std::make_pair
#define pii std::pair
#define F first
#define S second
typedef long long ll;
typedef unsigned long long ull;
namespace _name{
	const int maxn=200005,mod=998244353,inf=0x3f3f3f3f;
	template
	inline void read(T &x){
		T flag=1;
		char ch=getchar();
		for(;!isdigit(ch);ch=getchar())if(ch=='-')flag=-1;
		for(x=0;isdigit(ch);ch=getchar())x=x*10+ch-'0';
		x*=flag;
	}
	template
	inline void write(int x){
		int stk[20],top=0;
		while(x)stk[++top]=x%10,x/=10;
		for(int i=top;i;i--)putchar(stk[i]+'0');
	}
	template
	inline void print(T x,char End='\n'){
		if(x<0)x=-x,putchar('-');
		write(x);putchar(End);
	}
	inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
	inline int dec(int a,int b){return a-b<0?a-b+mod:a-b;}
	inline int mul(int a,int b){return 1ll*a*b%mod;}
	inline int ksm(int a,int b=mod-2){int ret=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ret=mul(ret,a);return ret;}
}using namespace _name;
ll a,k,ans;
int calc(int n){
	if(n

ARC133

ABC and similar

ABC224

E - Integers on Grid

贪心考虑连到比其大且最小的数上，但由于这样的数可能很多，所以对每行列相同值的数建一个虚点，最后跑拓扑排序即可。

F - Problem where +s Separate Digits

考虑每个位置的贡献，容易发现答案即为 \(\sum_{i=1}^{n}s_i\sum_{j=0}^{n-i}10^{j}2^{\max(n-1-i-j,0)}\)，后面那个提一个 \(2^{-i}\) 出来后可以预处理，于是就 \(O(n)\) 了。

G

H

ABC216

G - 01Sequence

以为是什么差分约束，结果发现有环 /kk

其实只需要贪心即可，按 r 排序，从小到大，枚举，每次不够了就往后填。用 bit 维护前缀和，set 维护数列。

H - Random Robots

一开始觉得神仙，但其实做多了发现也就那样。可以看成二维平面上的点，要不向右一定一格，要不向右上移动一个，最后会到达 \((N, X)\)，并且路径不能有交。显然求方案数最后除以总方案数即可。考虑 LGV。但是发现数据范围不太能 高斯消元。于是直接考虑行列式，发现答案就是 \(\sum (-1)^{w(p)}\prod \binom{N}{y_i-x_i}\)，其中 \(y_i\) 是第 \(i\) 个点最后到了什么位置。注意这里 \(y_i\) 也必须有序（思考一下 lgv 在干啥？）

然后考虑对这个计数，发现不太能枚举排列，但是我们只关心逆序对数，考虑一个一个将数字加入排列 \(p\)，只关心当前 \(p\) 中有哪些元素，所以可以状态。设 \(f[s,k]\) 代表当前加入元素为集合 \(s\)，\(y_i\) 的最大值最多为 \(k\) 的权值和，这个最大值一定是在加入最后一个元素时得到的。这里把 \(-1\) 的贡献也考虑进去，转移就考虑会产生多少个逆序对。复杂度 \(O(k2^kn)\)。感觉有 \(O(poly(k)N)\) 的做法。最后答案就是 \(f[U][MAX]\)

int main(){
	read(K);read(N);
	fac[0]=ifac[0]=1;for(int i=1;i<=2000;i++)fac[i]=mul(fac[i-1],i),ifac[i]=mul(ifac[i-1],ksm(i));
	for(int i=1;i<=K;i++)read(x[i]),x[i]++,mx=std::max(mx,x[i]);
	for(int j=0;j<=mx+N;j++)f[0][j]=1;
	for(int s=1;s<(1<=1;k--){
				if(s&(1<<(k-1))){
					f[s][j]=tp?add(f[s][j],mul(f[s^(1<<(k-1))][j-1],C(N,j-x[k]))):dec(f[s][j],mul(f[s^(1<<(k-1))][j-1],C(N,j-x[k])));
					tp^=1;
				}
			}
		}
	}
	printf("%d\n",mul(f[(1<
杂题

相关

异或相关的杂题

XXII Open Cup, Grand Prix of IMO【杂题】

hs-black 杂题选讲

标签

一品网 冀ICP备14022925号-6