ABC337 A-G

Toyota Programming Contest 2024#1（AtCoder Beginner Contest 337） - AtCoder

手速五题之后看FG，一看榜G过的比F多...两题都有思路然后先开写了F像是大模拟写了一堆bug，赛后对拍调bug调完疯狂re，发现是对数组双倍操作了但数组长度没开两倍...

G赛时就看了眼猜了个动态开点权值线段树+树上启发式合并觉得不好写就先写F了，赛后才想起来可以用dfn序处理子树问题+主席树+容斥...

好消息是就算开局A读假题wa一发之后还能手速上分w

A - Scoreboard

题意：

判断?和?谁大，x大输出Takahashi，y大输出Aoki，平局Draw

代码：

void solve()
{
	int n, x = 0, y = 0;
	scanf("%d", &n);
	for (int i = 1, a, b; i <= n; ++i)
	{
		scanf("%d%d", &a, &b);
		x += a, y += b;
	}
	if (x > y)printf("Takahashi\n");
	if (x < y)printf("Aoki\n");
	if (x == y)printf("Draw");
}

B - Extended ABC

题意：

给出一个字符串，问改字符串是否为若干个连续的A，若干连续B，若干连续C拼接而成（可以为0个）

代码：

char ch[N];
void solve()
{
	scanf("%s", ch + 1);
	for (int i = 1, c = 'A'; ch[i]; ++i)
	{
		while (c <= 'C' && ch[i] != c)++c;
		if (c > 'C')
		{
			printf("No\n");
			return;
		}
	}
	printf("Yes\n");
}

C - Lining Up 2

题意：

N个人排队，第i个人排在第Ai个人后面，若Ai=-1说明这个人是排头，求队伍

题解：

记录每个人后面是谁然后dfs即可（因为只有一条路径所以可以直接写循环）

int p[N];
void solve()
{
	int n;
	scanf("%d", &n);
	for (int i = 1, x; i <= n; ++i)
	{
		scanf("%d", &x);
		if (x == -1)x = 0;
		p[x] = i;
	}
	for (int i = 1, x = 0; i <= n; ++i)
		x = p[x], printf("%d ", x);
}

D - Cheating Gomoku Narabe

题意：

给出一个N*M的由'x', '.', 'o'构成的字符矩阵，你可以将任意个'.'变成'o'，问最少进行多少次操作能使字符矩阵中存在某一行/列中存在连续K个'o'，若不能输出-1

题解：

二维前缀和秒了，枚举所有可能的区间，先判断这个范围内'x'的数量为0，若为0则这个区间变成全'o'的代价为这个区间内'.'的数量

vector<vector<char>>mp;
vector<vector<int>>s[2];
int get_sum(int f, int ux, int uy, int vx, int vy)
{
	return s[f][vx][vy] - s[f][ux - 1][vy] - s[f][vx][uy - 1] + s[f][ux - 1][uy - 1];
}
void solve()
{
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	mp.resize(n + 1);
	s[0].resize(n + 1);
	s[1].resize(n + 1);
	s[0][0].resize(m + 1);
	s[1][0].resize(m + 1);
	for (int i = 1; i <= n; ++i)
	{
		mp[i].resize(m + 1);
		s[0][i].resize(m + 1);
		s[1][i].resize(m + 1);
		getchar();
		for (int j = 1; j <= m; ++j)
		{
			mp[i][j] = getchar();
			s[0][i][j] = s[0][i - 1][j] + s[0][i][j - 1] - s[0][i - 1][j - 1] + (mp[i][j] == 'x');
			s[1][i][j] = s[1][i - 1][j] + s[1][i][j - 1] - s[1][i - 1][j - 1] + (mp[i][j] == '.');
		}
	}
	int ans = INF;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j + k - 1 <= m; ++j)
		{
			if (get_sum(0, i, j, i, j + k - 1) == 0)
				ans = min(ans, get_sum(1, i, j, i, j + k - 1));
		}
	}
	for (int j = 1; j <= m; ++j)
	{
		for (int i = 1; i + k - 1 <= n; ++i)
		{
			if (get_sum(0, i, j, i + k - 1, j) == 0)
				ans = min(ans, get_sum(1, i, j, i + k - 1, j));
		}
	}
	if (ans == INF)printf("-1\n");
	else printf("%d\n", ans);
}

E - Bad Juice

题意：

交互题。你有n瓶果汁，其中有一瓶果汁是坏果汁，喝了第二天会喷射，你想要在一天内知道到底哪瓶果汁不是好果汁，为此你找来m个朋友（需要最小化m），给第i个朋友试吃了ki份果汁，分别为Ai,1...Ai,ki，第二天每个朋友会向你汇报他窜没窜(0表示没窜, 1表示窜了)，然后你需要判断是哪瓶不是好果汁。

题目会先给你一个n，之后你需要输出一行一个整数m，之后m行每行先输出一个ki，之后跟ki个整数表示给第i个朋友喂了哪些果汁，之后评测机将会返回一个01串表示每位朋友是否吃坏肚子，之后你需要输出一个整数表示是哪一瓶果汁坏了。

题解：

按二进制给每位朋友喂果汁，这样就只需要logn(向上取整)名朋友就能完成试毒，具体实现见代码

       第j位朋友
第     1  2  3
 i  1  0  0  0
瓶  2  1  0  0
果  3  0  1  0    0表示不喝1表示喝
汁  4  1  1  0 
    5  0  0  1
    6  1  0  1

vector<int>v[N];
void solve()
{
	int n;
	scanf("%d", &n);
	int m = 0, t = 1;
	while (t < n)++m, t <<= 1;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
			if (i >> j & 1)v[j].push_back(i + 1);
	}
	cout << m << endl;
	for (int i = 0; i < m; ++i)
	{
		printf("%d ", v[i].size());
		for (auto j : v[i])printf("%d ", j);
		cout << endl;
	}
	char ch[100];
	scanf("%s", ch);
	int ans = 0;
	for (int i = 0; ch[i]; ++i)
		if (ch[i] == '1')ans += 1 << i;
	cout << ans + 1 << endl;
}

F - Usual Color Ball Problems

题意：

给出N个球，颜色分别为Ci，有M个盒子，每个盒子最多可装K个球且仅能装同色球，你会从左往右依次尝试把球装到盒子里，若还有装了球且未装满的盒子则会优先把球装进装球且未装满的盒子里，若没有盒子能装下当前的球，则舍弃这个球。

你需要分别求出把0, 1, 2, ..., n - 1个最前面的球保持顺序放到最后面之后进行装球操作后装在盒子里的球的数量总数

题解：

仅提供我的做法，感觉挺屎的...讲也讲不太明白...

首先题目的n种情况肯定不是单独求的，需要对把第一个球丢到末尾连续操作n次并不断维护答案

经过思考我们可以发现在把头上的一个球放到末尾最多只会有一个盒子装的发生东西变化（第一个球占的盒子被最前面的没有盒子的球抢占），所以我们可以想办法维护一些东西使得我们能够判断是否会有变化。

首先我们需要用set维护每个没有装入盒子的点的下标以便找出第一个没有被装入盒子的球，这里如果维护每个球的下标的话应该会TLE，所以我们只维护每种颜色的第一个没有被装入盒子的球的下标。

设第一个没被装入的球的下标为t，第一个球的颜色为x，在把第一个球丢到末尾之后若在t前的颜色为x的球数量变为k的倍数，则说明此时x的一个盒子被c[t]抢走了（在此前t前面有cnt*k+1个x色球，占了cnt+1个盒子，此时去掉开头则被占用的盒子变为cnt个，刚好被c[t]抢占一个）。

对于求一段区间内x色球的数量，可以对每种颜色开个vector存所有这种颜色求的下标，然后二分即可求得。

大致思路是这样，具体做法见代码

const LL N = 4e5 + 10;
int c[N], f[N];//f[i]表示颜色为i的球的第一个没有被装入盒子的球的下标（为0表示不存在没被装入的球）
vector<int>v[N];//每种颜色的球的下标
deque<int>mp[N];//颜色i占据的盒子的每个盒子装球的个数
set<int>st;//每种颜色第一个没被装入的球的下标
void solve()
{
	int n, m, k, s = 0, ans = 0;
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d", &c[i]);
		v[c[i]].push_back(i);
	}
	for (int i = n + 1; i <= 2 * n; ++i)//二倍数组处理把第一个丢到最后的操作
	{
		c[i] = c[i - n];
		v[c[i]].push_back(i);
	}
	for (int i = 1; i <= n; ++i)//初始化，求初始情况的ans
	{
		if (mp[c[i]].size() && mp[c[i]].back() < k)
			++mp[c[i]].back(), ++ans;
		else if (s < m)
			mp[c[i]].push_back(1), ++s, ++ans;
		else if (!f[c[i]])
			st.insert(i), f[c[i]] = i;
	}
	for (int i = 1; i <= n; ++i)
	{
		printf("%d\n", ans);
		if (st.empty())continue;//没有球被扔掉
		int x = c[i], t = *st.begin();//被丢到后面的颜色，候选颜色的位置
		int l = upper_bound(v[x].begin(), v[x].end(), i) - v[x].begin();
		int r = lower_bound(v[x].begin(), v[x].end(), t) - v[x].begin();
		int sum = r - l;//删去首位之后t之前的x的个数
		if (sum % k == 0)//候补的能上来
		{
			//删除最后一个装x的盒子
			ans -= mp[x].back();
			mp[x].pop_back();
			int cnt = mp[x].size() * k;
			if (!f[x])//将颜色x加入候选名单
			{
				//printf("*%d ", l + cnt);
				st.insert(v[x][l + cnt]);
				f[x] = v[x][l + cnt];
			}
			else //重新求x的第一个没被装入的位置
			{
				st.erase(f[x]);
				st.insert(v[x][l + cnt]);
				f[x] = v[x][l + cnt];
			}
			//将候选加入新盒子
			int tl = lower_bound(v[c[t]].begin(), v[c[t]].end(), t) - v[c[t]].begin();
			int tr = upper_bound(v[c[t]].begin(), v[c[t]].end(), i + n) - v[c[t]].begin();
			//printf("%d %d %d ", t, tl, tr);
			int tsum = tr - tl;
			//printf("%d ", tsum);
			if (tsum <= k)//c[t]不再有候选
			{
				ans += tsum;
				f[c[t]] = 0;
				st.erase(t);
				mp[c[t]].push_back(tsum);
			}
			else
			{
				ans += k;
				st.erase(t);
				st.insert(v[c[t]][tl + k]);
				f[c[t]] = v[c[t]][tl + k];
				mp[c[t]].push_back(k);
			}
		}
		else if(f[x])//重新求x的第一个没被装入的位置
		{
			int cnt = mp[x].size() * k;
			int p = upper_bound(v[x].begin(), v[x].end(), i) - v[x].begin();
			st.erase(v[x][p + cnt - 1]);
			st.insert(v[x][p + cnt]);
			f[x] = v[x][p + cnt];
		}
	}
}

G - Tree Inversion

题意：

题目给出一个n个节点的无根树，对每个点u求f(u)：符合以下条件的点对(w,v)的数量:u到v的简单路径经过w。（w可以为u）

题解：

很容易想到换根DP，难点在于求以任意u为根时，其子节点w的子树中编号小于u的点v的数量。

这里可以通过dfn序把子树变成线性之后用主席树+容斥处理，具体做法见代码

从严鸽鸽那里改来的主席树板子数据结构学习笔记(7) 主席树 - 知乎 (zhihu.com)，挺好用的，知道原理其实还挺好手搓的

const LL N = 2e5 + 10, M = N;
//主席树
#define ls(x) (tr[x].ls)
#define rs(x) (tr[x].rs)
#define s(x) tr[x].s
struct node
{
	int ls, rs, s;
}tr[32 * N];//logM * N
int root[N], tot;
void push_up(int i)
{
	s(i) = s(ls(i)) + s(rs(i));
}
void updata(int pos, int data, int l, int r, int last, int now)
{
	if (l == r)
	{
		s(now) = s(last) + data;
		return;
	}
	ls(now) = ls(last), rs(now) = rs(last);
	int mid = l + r - 1 >> 1;
	if (pos <= mid)
		updata(pos, data, l, mid, ls(last), ls(now) = ++tot);
	else
		updata(pos, data, mid + 1, r, rs(last), rs(now) = ++tot);
	push_up(now);
}
void updata(int pos, int data, int last, int now)
{
	updata(pos, data, -M, M, last, now);
}
int query_kth(int k, int l, int r, int last, int now)
{
	if (l == r)return l;
	int mid = l + r - 1 >> 1, dt = s(ls(now)) - s(ls(last));
	if (dt >= k)return query_kth(k, l, mid, ls(last), ls(now));
	return query_kth(k - dt, mid + 1, r, rs(last), rs(now));
}
//求区间第k大用的，这里没用上
int query_kth(int k, int last, int now)
{
	return query_kth(k, -M, M, last, now);
}
int query_range(int ql, int qr, int l, int r, int last, int now)
{
	if (ql <= l && r <= qr)return s(now) - s(last);
	int mid = l + r - 1 >> 1, res = 0;
	if (ql <= mid)res += query_range(ql, qr, l, mid, ls(last), ls(now));
	if (qr > mid)res += query_range(ql, qr, mid + 1, r, rs(last), rs(now));
	return res;
}
//求数组在下标last+1到now之间，大小在ql到qr之间的数的数量
int query_range(int ql, int qr, int last, int now)
{
	return query_range(ql, qr, -M, M, last, now);
}
//
int dfn[N], ed[N], idx;
vector<int>e[N];
LL dp[N];
void build(int u, int f)//处理dfn序
{
	dfn[u] = ++idx;
	root[idx] = ++tot;
	updata(u, 1, root[idx - 1], root[idx]);
	for (auto v : e[u])if (v != f)
		build(v, u);
	ed[u] = idx;
}
void dfs0(int u, int f)//预处理f(1)
{
	for (auto v : e[u])if (v != f)
	{
		dfs0(v, u);
		dp[u] += dp[v] + query_range(1, v - 1, root[dfn[v] - 1], root[ed[v]]);
	}
}
void dfs(int u, int f)//换根dp
{
	for (auto v : e[u])if (v != f)
	{
		dp[v] = dp[u] - query_range(1, v - 1, root[dfn[v] - 1], root[ed[v]]);
		dp[v] += u - 1 - query_range(1, u - 1, root[dfn[v] - 1], root[ed[v]]);
		dfs(v, u);
	}
}
void solve()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i < n; ++i)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	build(1, 0);
	dfs0(1, 0);
	dfs(1, 0);
	for (int i = 1; i <= n; ++i)
		printf("%lld ", dp[i] + i - 1);
}