首页 > 其他分享 >Codeforces Round 973 (Div. 2)

Codeforces Round 973 (Div. 2)

时间：2024-09-23 17:45:56浏览次数：1  
标签：973 int ll Codeforces long while Div getchar define

A. Zhan's Blender

有 \(n\) 个水果，每秒可以消耗 \(\min\{x, y\}\) 个，问需要多少时间。

整数除法的上取整操作即可。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

void solve()
{
	int n = read(), x = read(), y = read();
	int xx = min(x, y);
	printf("%d\n", (n + xx - 1) / xx);
}

int main()
{
	int T = read();
	while(T--) solve();
    return 0;
}

B. Battle for Survive

有 \(n\) 个人，每个人有一个分数 \(a_i\)，每次选择两个人 \(i, j\) 满足 \(i < j\)，\(i\) 被打败退役，\(j\) 的分数变为 \(a_j - a_i\)，问最后的冠军的分数最大为多少。

发现第 \(n\) 个人一定是冠军，第 \(n - 1\) 个人一定是要退役的，若 \(i < j < k\)，\(i\) 先和 \(j\) 打，\(j\) 再和 \(k\) 打，最终得分为 \(a_k - (a_j - a_i)\)，相当于给 \(() a_1 () a_2 \cdots () a_{n-2} - a_{n-1} + a_n\) 中前 \(n - 2\) 个数赋上正负号，使得最终和最大，显然都赋正号最大。

也就是先让前 \(n - 2\) 个人和 \(n - 1\) 个人打，然后让 \(n\) 去报仇。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 2e5 + 5;
int a[N];

void solve()
{
	int n = read();
	for(int i = 1; i <= n; ++i) a[i] = read();
	ll ans = a[n] - a[n - 1];
	for(int i = n - 2; i >= 1; --i) ans += a[i];
	printf("%lld\n", ans);
}

int main()
{
	int T = read();
	while(T--) solve();
    return 0;
}

C. Password Cracking

交互题，给定一个长度 \(n\)，答案是长度为 \(n\) 的 \(01\) 串，每次可以询问一个长度不大于 \(n\) 的 \(01\) 串是否是答案串的子串。询问次数不超过 \(2n\) 次。

如果已知一个串是答案串的子串，那么尝试在它后面加上 \(0\) 或者 \(1\)，如果都不能加说明这个串是答案串的一个后缀，再尝试在前面加。

注意到在前面加 \(0\) 或 \(1\) 时实际上只需要询问一次。

发现分为两个过程，如果只做第一个过程就可以找到串，询问次数最多不超过 \(2n\) 次。

当需要第二个过程时，设第 \(i\) 次无法从当前串后面加，那么询问最多不超过 \(2i + 1 + n - i + 1 = n + i + 2\) 次，实际上构造不出卡满询问次数的串。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long


void solve()
{
	int n;
	cin >> n;
	string s, t;
	s.clear(), t.clear();
	int len = 0, flag = 0;
	for(len = 1; len <= n; ++len)
	{
		t = s + "0";
		cout << "? " << t << '\n';
		cout.flush();
		int flag1;
		cin >> flag1;
		if(flag1){ s = s + "0"; continue; }
		t = s + "1";
		cout << "? " << t << '\n';
		cout.flush();
		int flag2;
		cin >> flag2;
		if(flag2){ s = s + "1"; continue; }
		flag = 1; break;
	}
	if(flag)
	{
		for(; len <= n; ++len)
		{
			t = "0" + s;
			cout << "? " << t << '\n';
			cout.flush();
			int flag1;
			cin >> flag1;
			if(flag1){ s = "0" + s; continue; }
			s = "1" + s;
		}
	}
	cout << "! " << s << '\n';
	cout.flush();
}

int main()
{
	int T;
	cin >> T;
	while(T--) solve();
    return 0;
}

D. Minimize the Difference

给定长度为 \(n\) 的序列，每次操作选择位置 \(i\) 使得 \(a_i = a_i - 1, a_{i + 1} = a_{i + 1} + 1\)，可以操作任意次，求最终序列 \(\max\{ a_1, a_2, \cdots a_n \} - \min\{ a_1, a_2, \cdots a_n \}\) 的最小值。

最理想的想法就是均摊总和，但是每次只能从低位向高位加 \(1\)，设 \(pre_i, suf_i\) 分别表示前缀和和后缀和。

在均摊的情况下：

前 \(i\) 个数中，最小的数不会小于 \(\lfloor \frac{pre_i}{i} \rfloor\)，可以求出整个的序列的最小值的最大值。

后 \(i\) 个数中，最大的数不会超过 \(\lceil \frac{suf_{n-i+1}}{i} \rceil\)，可以求出整个序列的最大值的最小值。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

ll read()
{
    ll x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 2e5 + 5;
int n;
ll a[N], sum1[N], sum2[N];

void solve()
{
	n = read();
	for(int i = 1; i <= n; ++i) a[i] = read(), sum1[i] = sum1[i - 1] + a[i];
	sum2[n + 1] = 0;
	for(int i = n; i >= 1; --i) sum2[i] = sum2[i + 1] + a[i];
	ll mx = 0, mn = 0x7fffffffffffffff;
	for(int i = 1; i <= n; ++i) mn = min(mn, sum1[i] / (ll)i), mx = max(mx, (sum2[i] + n - i) / (ll)(n - i + 1));
	// printf("mx = %lld, mn = %lld\n", mx, mn);
	printf("%lld\n", mx - mn);
}

int main()
{
	int T = read();
	while(T--) solve();
    return 0;
}

E. Prefix GCD

给一个长度为 \(n\) 的序列重新排列，使得前缀 \(\operatorname{gcd}\) 的和最小。

每次选择一个可以使 \(\operatorname{gcd}\) 最小的数加入，直到等于 \(\operatorname{gcd}\{ a_1, a_2, \cdots a_n \}\)时停止操作。

由于值域的和不超过 \(10^5\)，每次加入一个数至少使 \(\operatorname{gcd} / 2\)，做 \(\log\) 次即可。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int N = 1e5 + 5;
int n, a[N];

int gcd(int x, int y)
{
	if(!x || !y) return x | y;
	return gcd(y, x % y);
}

void solve()
{
	n = read();
	int GCD = 0, nowgcd = 0;
	for(int i = 1; i <= n; ++i) a[i] = read(), GCD = gcd(GCD, a[i]);
	ll ans = 0;
	for(int i = 1; ; ++i)
	{
		int mn = 0x7fffffff;
		for(int j = 1; j <= n; ++j) mn = min(mn, gcd(nowgcd, a[j])); 
		nowgcd = mn, ans += nowgcd;
		if(nowgcd == GCD){ ans += 1ll * (n - i) * GCD; break; }
	}
	printf("%lld\n", ans);
}

int main()
{
	int T = read();
	while(T--) solve();
    return 0;
}

F1. Game in Tree (Easy Version)

有一个以 \(1\) 为根节点的树，最初Alice在 \(1\) 点，Bob在 \(u\) 点，两个人轮流走，每一步只能选择走向一个没有被走过的节点，不能走的人输，Alice先走，每个人都采用最优策略，问最后的获胜者。

将 \(1\) 到 \(u\) 路径上的点取出，即为 \(p_1, p_2, \cdots , p_{m}\)，\(p_1\) 即为 \(1\)，\(p_m\) 即为 \(u\)。

设 \(dp[x]\) 表示从节点 \(x\) 向子树走，且不经过 \(1\) 到 \(u\) 路径上的点（\(x\) 可以在路径上），能经过的最大点数。

记 \(a_i = dp[p_i] + depth[p_i] - 1\)（根节点深度为 \(1\)）。

记 \(b_i = dp[p_i] + depth[u] - depth[p_i]\)。

容易发现 \(a_i, b_i\) 就是Alice和Bob走到 \(p_i\) 并走向某一颗不在路径上的子树的能经过的最大点数。

考虑当两个人分别在 \(p_i, p_j\) 时，到Alice先走，如何有必胜策略？

当 \(a_i > \max\{ b_{i+1}, \cdots , b_{j} \}\) 时，无论Bob怎么走都会输掉比赛。

同理，当 \(b_j \ge \max{a_i, \cdots, a_{j-1}}\) 时，无论Alice怎么走都会输掉比赛。

（由于Alice比Bob先走，所以当两个人能经过的点数相同时，Bob会胜利）。

若当前步没有必胜策略时，说明对方有绝杀我的方法，所以我要沿着路径走，尽可能抢占对方的决胜点。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const int inf = 0x7fffffff;
const int N = 2e5 + 5;
int n;
vector<int> V[N];
int f[N], depth[N], vis[N], dp[N];

void DFS(int k, int fa)
{
    f[k] = fa, depth[k] = depth[fa] + 1;
    for(auto v : V[k]) if(v != fa) DFS(v, k);
}

void dfs(int k, int fa)
{
	dp[k] = 1;
	for(auto v : V[k])
    {
        if(v == f[k]) continue;
        dfs(v, k);
        if(!vis[v]) dp[k] = max(dp[k], dp[v] + 1);
    }    
}

int sta[N], top;
int lg[N], stA[20][N], stB[20][N];

int get(int l, int r, int d)
{
    int k = lg[r - l + 1];
    if(d == 0) return max(stA[k][l], stA[k][r - (1 << k) + 1]);
    else return max(stB[k][l], stB[k][r - (1 << k) + 1]);
}

void solve()
{
	n = read();
	for(int i = 1; i <= n; ++i) V[i].clear(), vis[i] = 0;
	for(int i = 1; i < n; ++i)
	{
		int u = read(), v = read();
		V[u].emplace_back(v);
		V[v].emplace_back(u);
	}
    DFS(1, 0);
	int x = read(), y = read();
	while(top) sta[top] = 0, --top;
	while(y) vis[y] = 1, sta[++top] = y, y = f[y];
	dfs(1, 0);

    stA[0][1] = -inf, stB[0][top] = -inf;
    for(int i = 2; i <= top; ++i) stA[0][i] = dp[sta[i]] + depth[sta[i]] - 1;
    for(int i = 1; i < top; ++i) stB[0][i] = dp[sta[i]] + depth[x] - depth[sta[i]];
    
    for(int i = 1; i <= 19; ++i)
        for(int j = 1; j + (1 << i) - 1 <= top; ++j)
            stA[i][j] = max(stA[i - 1][j], stA[i - 1][j + (1 << (i - 1))]),
            stB[i][j] = max(stB[i - 1][j], stB[i - 1][j + (1 << (i - 1))]);

    // 0是Alice,1是Bob
    int op = 0, Apos = top, Bpos = 1;
    while(Bpos < Apos)
    {
        if(op == 0)
        {
            if(get(Apos, Apos, 0) > get(Bpos, Apos - 1, 1))
            {
                printf("Alice\n"); return ;
            }else Apos--;
        }else
        {
            if(get(Bpos, Bpos, 1) >= get(Bpos + 1, Apos, 0))
            {
                printf("Bob\n"); return ;
            }else Bpos++;
        }
        if(Apos == Bpos)
        {
            if(op == 0) printf("Bob\n");
            else printf("Alice\n");
            return ;
        }
        op ^= 1;
    }
}

int main()
{
    lg[0] = -1;
    for(int i = 1; i <= 200000; ++i) lg[i] = lg[i >> 1] + 1;
	int T = read();
	while(T--) solve();
    return 0;
}

F2. Game in Tree (Hard Version)

有点神，先咕着。

标签：973,int,ll,Codeforces,long,while,Div,getchar,define
From： https://www.cnblogs.com/wenqizhi/p/18426943

相关文章

  • Codeforces Round 972（Div.2）题解
    CodeforcesRound972（Div.2）题解A.SimplePalindrome贪心贪心，尽可能元素数量平均，并且相同字母放在一起。#include<bits/stdc++.h>usingnamespacestd;#definefffirst#definesssecond#definepbpush_back#defineall(u)u.begin(),u.end()#defineendl'\n'#de......
  • Codeforces Round 973 (Div.2) A-E题解
    CodeforcesRound973(Div.2)A-E题解比赛传送门A.Zhan'sBlender数学显然答案为\(\lceil\frac{n}{min(x,y)}\rceil\)。#include<bits/stdc++.h>usingnamespacestd;#definefffirst#definesssecond#definepbpush_back#defineall(u)u.begin(),u.en......
  • codeforces 1041 C. Coffee Break
    题意第一行输入三个整数\(n,m,d(1\leqn\leq2*10^5,n\leqm\leq10^9,1\leqd\leqn)\)，第二行输入\(n\)个整数，保证每个数均不大于\(m\)。在每一天你都可以任意选择一个未选过的数\(a_i\)，随后可以继续选任意一个大于\(a_i+d\)的数\(a_j\)；接下来可以再选任意......
  • Codeforces Round 974 (Div. 3)
    CodeforcesRound974(Div.3)A-RobinHelps按题目要求一步步计算就行#include<bits/stdc++.h>usingnamespacestd;intn,k;voidsolve(){ cin>>n>>k; intsum=0,num,ans=0; for(inti=1;i<=n;++i){ cin>>num; if(num&g......
  • Codeforces Round 974 (Div. 3)
    A.RobinHelps模拟即可。B.RobinHoodandtheMajorOak注意到\(i^i\equivi\pmod2\)，因此\(\sumi^i\equiv\sumi\pmod2\)。等差数列求和即可。C.RobinHoodinTown二分答案即可。D.RobertHoodandMrsHood枚举区间\([l,l+d-1]\)。此时我们需要快速......
  • Codeforces Round 974 (Div. 3)
    A：按题意模拟。B：\(i^i\)与\(i\)奇偶性相同，求\((n-k,n]\)的奇数个数。C：二分答案。D：即求每个\((i-d,i]\)有多少线段覆盖。扫到\(i\)时加入所有\(i=l\)的，弹出所有\(r\lei-d\)的。E：枚举相遇点，答案就是\(\min\big(\max(d_1,d_2)\big)\)，最短路时记录状态......
  • Codeforces Round 973 (Div. 2)
    CodeforcesRound973(Div.2)A-Zhan'sBlender由于总量固定因此只用计算两个处理时间最大值即是所求#include<bits/stdc++.h>usingnamespacestd;intn;doublex,y;voidsolve(){ cin>>n; cin>>x>>y; inttim1=ceil(n*1.0/x); inttim2......
  • Codeforces Round 974 (Div. 3)
    A.RobinHelps题意:Robin一开始的钱为0,每个人都有ai个金币,如果ai>=k则Robin会拿着它的金币, 如果ai==0且手上有金币，Robin会送出1金币,输出Robin送了几次思路:按照题意Code:#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;usingi6......
  • Codeforces Round 973 (Div. 2)
    SolCF2013A每次最多操作\(\min(x,y)\)，故答案为\(\lceil\frac{n}{\min(x,y)}\rceil\)。#include<bits/stdc++.h>usingnamespacestd;usingu32=unsigned;usingi64=longlong;usingu64=unsignedlonglong;usingi128=__int128;#defineIOS#de......
  • Codeforces Round 973 (Div. 2) B. Battle for Survive
    题目链接：题目大意：把题目的操作翻译一下就是拿一个数去减后面的一个数，然后前面这个数会消掉。最小化最后剩下的数。思路：容易看出，最后剩下的一定是最后一个数，因为最后一个数一定不会被消去，又已知最后只剩下一个数，那么就是最后一个数。前面的所有数都要被消去，最差的情况就......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99