正文

atcodergrandcontest009题解

anzhewang  anzhewang  2022-12-31  629

关键词：

A - Multiple Array

倒着算要加多少就好了。

//waz
#include <bits/stdc++.h>
 
using namespace std;
 
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
 
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
 
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
 
int F()

	char ch;
	int x, a;
	while (ch = getchar(), (ch < ‘0‘ || ch > ‘9‘) && ch != ‘-‘);
	if (ch == ‘-‘) ch = getchar(), a = -1;
	else a = 1;
	x = ch - ‘0‘;
	while (ch = getchar(), ch >= ‘0‘ && ch <= ‘9‘)
		x = (x << 1) + (x << 3) + ch - ‘0‘;
	return a * x;

 
const int N = 1e5 + 10;
 
int n;
 
long long a[N], b[N];
 
int main()

	gi(n);
	for (int i = 1; i <= n; ++i)
		gii(a[i], b[i]);
	long long add = 0;
	for (int i = n; i; --i)
	
		a[i] += add;
		if (a[i] % b[i]) add += b[i] - a[i] % b[i], a[i] += b[i] - a[i] % b[i];
	
	printf("%lld
", add);
	return 0;

B - Tournament

树形dp，把所有儿子的轮数从小到大排序，算一下自己最少要多少轮即可。

//waz
#include <bits/stdc++.h>
 
using namespace std;
 
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
 
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
 
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
 
int F()

	char ch;
	int x, a;
	while (ch = getchar(), (ch < ‘0‘ || ch > ‘9‘) && ch != ‘-‘);
	if (ch == ‘-‘) ch = getchar(), a = -1;
	else a = 1;
	x = ch - ‘0‘;
	while (ch = getchar(), ch >= ‘0‘ && ch <= ‘9‘)
		x = (x << 1) + (x << 3) + ch - ‘0‘;
	return a * x;

 
int n, a[100010];
 
VI edge[100010];
 
int rd[100010];
 
void dfs(int u)

	VI p;
	for (auto v : edge[u])
	
		dfs(v);
		p.pb(rd[v]);
	
	sort(ALL(p));
	for (auto x : p)
		rd[u] = max(rd[u], x), ++rd[u];

 
int main()

	gi(n);
	for (int i = 2; i <= n; ++i) gi(a[i]), edge[a[i]].pb(i);
	dfs(1);
	printf("%d
", rd[1]);
	return 0;

C - Division into Two

列出dp方程，令A>=B，把可以取的位置丢进树状数组维护一下dp即可。

//waz
#include <bits/stdc++.h>
 
using namespace std;
 
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
 
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
 
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
 
int F()

	char ch;
	int x, a;
	while (ch = getchar(), (ch < ‘0‘ || ch > ‘9‘) && ch != ‘-‘);
	if (ch == ‘-‘) ch = getchar(), a = -1;
	else a = 1;
	x = ch - ‘0‘;
	while (ch = getchar(), ch >= ‘0‘ && ch <= ‘9‘)
		x = (x << 1) + (x << 3) + ch - ‘0‘;
	return a * x;

 
const int N = 1e5 + 10, mod = 1e9 + 7;
 
int n;
 
int64 A, B, S[N];
 
int lf[N], f[N], g[N];
 
int t[N];
 
void add(int x, int v)  for (++x; x <= n + 1; x += x & -x) t[x] = (t[x] + v) % mod; 
 
int query(int x)  int v = 0; for (++x; x; x -= x & -x) v = (v + t[x]) % mod; return v; 
 
int main()

	gi(n);
	scanf("%lld%lld", &A, &B);
	if (A < B) swap(A, B);
	for (int i = 1; i <= n; ++i) scanf("%lld", S + i); S[0] = -A;
	++n; S[n] = S[n - 1] + A;
	lf[1] = 1;
	for (int i = 2; i <= n; ++i) if (S[i] >= S[i - 1] + B) lf[i] = lf[i - 1]; else lf[i] = i;
	f[0] = 1;
	add(0, f[0]);
	for (int i = 1; i <= n; ++i)
	
		int k = upper_bound(S + 1, S + i + 1, S[i] - A) - S - 1;
		int j = lf[i - 1] - 1;
		if (S[i] - S[i - 1] >= A) f[i] = f[i - 1];
		if (i >= 2 && min(i - 2, k) >= j - 1) (f[i] += (query(min(i - 2, k)) - query(j - 1) + mod) % mod) %= mod;
		if (i < n && S[i + 1] - S[i - 1] >= B) add(i, f[i]);
	
	printf("%d
", f[n]);
	return 0;

D - Uninity

树分治是上界，也就是log，当有两个点是第k次标号，中间肯定要有一个k+1，用这个进行dp，算一下每个点的所有儿子令它最大是多少就好了。

//waz
#include <bits/stdc++.h>
 
using namespace std;
 
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
 
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
 
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
 
int F()

	char ch;
	int x, a;
	while (ch = getchar(), (ch < ‘0‘ || ch > ‘9‘) && ch != ‘-‘);
	if (ch == ‘-‘) ch = getchar(), a = -1;
	else a = 1;
	x = ch - ‘0‘;
	while (ch = getchar(), ch >= ‘0‘ && ch <= ‘9‘)
		x = (x << 1) + (x << 3) + ch - ‘0‘;
	return a * x;

 
const int N = 1e5 + 10;
 
VI edge[N];
 
int n, bit[N], f[N];
 
void dfs(int u, int fa)

	int l = 0;
	for (auto v : edge[u])
	
		if (v == fa) continue;
		dfs(v, u);
		l |= bit[u] & bit[v];
		bit[u] |= bit[v];
	
	if (!bit[u]) bit[u] = 1;
	else
	
		while ((1 << f[u]) < l || ((1 << f[u]) & bit[u])) ++f[u];
		bit[u] = ((bit[u] >> f[u]) << f[u]) | (1 << f[u]);
	
	f[0] = max(f[0], f[u]);

 
int main()

	gi(n);
	for (int i = 1; i < n; ++i)
	
		int u, v;
		gii(u, v);
		edge[u].pb(v);
		edge[v].pb(u);
	
	dfs(1, 0);
	printf("%d
", f[0]);
	return 0;

E - Eternal Average

转换为k叉树模型，发现最后要求的是一个符合条件序列的个数，dp一下即可。

//waz
#include <bits/stdc++.h>
 
using namespace std;
 
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
 
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
 
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
 
int F()

	char ch;
	int x, a;
	while (ch = getchar(), (ch < ‘0‘ || ch > ‘9‘) && ch != ‘-‘);
	if (ch == ‘-‘) ch = getchar(), a = -1;
	else a = 1;
	x = ch - ‘0‘;
	while (ch = getchar(), ch >= ‘0‘ && ch <= ‘9‘)
		x = (x << 1) + (x << 3) + ch - ‘0‘;
	return a * x;

 
const int mod = 1e9 + 7;
 
int n, m, k, ans;
 
int f[2][2010][2], sum[2010];
 
int main()

	giii(n, m, k);
	--m, --k;
	for (int i = 1; i <= k; ++i) f[0][i][1] = 1;
	f[0][0][0] = 1;
	for (int i = 0; i <= n; ++i) 
		if (k - i <= m && i % k == n % k && (k - i) % k == m % k) ans = (ans + f[0][i][1]) % mod;
	int now = 0;
	for (int i = 2; i <= max(n, m) * 2; ++i)
	
		now ^= 1;
		for (int j = 0; j <= n; ++j) sum[j + 1] = (sum[j] + (f[now ^ 1][j][0] + f[now ^ 1][j][1]) % mod) % mod;
		for (int j = 0; j <= n; ++j)
		
			f[now][j][0] = (sum[j + 1] - sum[j] + mod) % mod;
			f[now][j][1] = (sum[j] - sum[max(0, j - k)] + mod) % mod;
		
		for (int j = 0; j <= n; ++j)
			if (k * i - j <= m && j % k == n % k && (k * i - j) % k == m % k) ans = (ans + f[now][j][1]) % mod;
		//cerr << ans << endl;
	
	printf("%d
", ans);

atcodergrandcontest002题解

A-RangeProduct经过0答案肯定是0，都是正数肯定是正数，都是负数的话就奇负偶正。//waz#include<bits/stdc++.h>usingnamespacestd;#definempmake_pair#definepbpush_back#definefifirst#definesesecond#defineALL(x)(x).begin(),(x).end()#de 查看详情

atcodergrandcontest003题解

A-Wannagobackhome如果有S就必须要有N，反之亦然，如果有E必须要有W，反之亦然。判断一下就好了。//waz#include<bits/stdc++.h>usingnamespacestd;#definempmake_pair#definepbpush_back#definefifirst#definesesecond#defineALL(x)(x).begin(),(x 查看详情

atcodergrandcontest013题解(代码片段)

A-SortedArrays贪心，看看不下降和不上升最长能到哪，直接转移过去即可。1//waz2#include<bits/stdc++.h>34usingnamespacestd;56#definempmake_pair7#definepbpush_back8#definefifirst9#definesesecond10#defineALL(x)(x).begin(),(x).en 查看详情

atcodergrandcontest015题解(代码片段)

A-A+...+BProblem可以取到的值一定是一段区间。所以答案即为max-min+11//waz2#include<bits/stdc++.h>34usingnamespacestd;56#definempmake_pair7#definepbpush_back8#definefifirst9#definesesecond10#defineALL(x)(x).begin(),(x 查看详情

每日亿题#12atcodergrandcontest021（a~f）全部题解(代码片段)

整理的算法模板合集：ACM模板点我看算法全家桶系列！！！实际上是一个全新的精炼模板整合计划文章目录AtCoderGrandContest021题解A.DigitSum2B.HolesC.TilingD.ReversedLCSE.BallEatChameleonsF.TrinityAtCoderGrandContest021题解比赛链接查看详情

每日亿题#12atcodergrandcontest021（a~f）全部题解(代码片段)

atcodergrandcontest007题解(代码片段)

传送门$A$咕咕咕//quming#include<bits/stdc++.h>#defineRregister#definefp(i,a,b)for(Rinti=(a),I=(b)+1;i<I;++i)#definefd(i,a,b)for(Rinti=(a),I=(b)-1;i>I;--i)#definego(u)for(inti=head[u],v=e[i].v; 查看详情

atcodergrandcontest027题解(代码片段)

被暴虐，还是自己太弱了。有一定影响是因为自己太想打一个好名次了，很多idea没有经过深入的思考就去实现。好几次都是因为错误的思路浪费了一些时间。但是主要还是自己的实力不太够。B-GarbageCollector一开始猜了一个连续... 查看详情

atcodergrandcontest054题解(代码片段)

[套题记录]思维题神仙场，蒟蒻切不动直接爬了（那天晚上由于毕业晚会与同学吃饭喝酒没打AGC，第二天稍微补了下题，目前补到了E，显然AGC的F对于我来说都是不可做题就没补了（bushiA简单题，不难发现如果我们通过三次及以... 查看详情

atcodergrandcontest043部分题解(代码片段)

这场打的好爽，rank(299)，涨了(141)AGC043A乍一看有点不知所措。BFS？暴力？让我们冷静分析一下。要达成目标，必须有至少一条从左上到右下的路径。感受一下：xxx....x....xx....x....xx注意到操作是同时对一个矩形区域操作。不难发... 查看详情

atcodergrandcontest020题解(代码片段)

传送门怎么又是(tourist)神仙的题……(A)咕咕intn,a,b;intmain()scanf("%d%d%d",&n,&a,&b);puts(((b-a-1)&1)?"Alice":"Borys");return0;(B)考虑从后往前做，假设考虑到(a_i)，且只考虑第(a_i+1)到(a_n)的答案为(s)，那么考虑... 查看详情

atcodergrandcontest045(代码片段)

Preface这场比赛真的是鸽了太久了的说，一来题挺难的，二来中间因为ZJOI和市统测占用了不少时间所以题目都记不太得了随便胡一下吧PS：太菜了所以只做了ABCD，其中BCD都是看一半题解才会的菜哭A-XorBattle首先肯定考虑倒着做，... 查看详情

atcodergrandcontest020(agc020)e-encodingsubsets动态规划(代码片段)

原文链接www.cnblogs.com/zhouzhendong/p/AGC020E.html前言真\$\\cdot\$信仰型动态规划题解我们可以采用信仰型动态规划解决此题。设\$dp[S]\$表示S这个字符串的所有子集可以被编码成多少种。那么分两种情况转移：不编码，答案是子集总... 查看详情

atcodergrandcontest044题解(代码片段)

为了不误人子弟，以后我在开头写出目前我做了哪些题，以防一些搜到这篇博客的人没找到想要的内容而产生负面情绪。目前进度：A,B,C（你问我为什么不放在标题里面？因为看着难看啊）开场看A，不会。看B，不会。不打算了... 查看详情

atcodergrandcontest020c-mediansum(代码片段)

题目：here题解：要转化一下，找所有子集的中间值，等价于找一个子集，满足这个子集的和最接近整个序列的和的一半。也就是一个背包判断可行性的问题。重点来了，bitset优化，至于为什么？我也不懂啊啊啊啊！！！注... 查看详情

题解pta团体程序设计天梯赛l1-009n个数求和(20分)go语言|golang(代码片段)

L1-009N个数求和(20分)Go语言|Golang本题的要求很简单，就是求N个数字的和。麻烦的是，这些数字是以有理数分子/分母的形式给出的，你输出的和也必须是有理数的形式。输入格式:输入第一行给出一个正整数N（≤100&... 查看详情

agc009duninity(代码片段)

一些无关紧要的事：似乎很久没写题解了……象征性地更一篇。另外很多blog都设了私密，不是很敢公开，不过说不定哪天会公开的。 link 题意：最优树的点分治：使得点分最大层数最小。（听说是经典问题）$nleq10^5.$ ... 查看详情