首页 > 其他分享 >Codeforces Round 935 (Div. 3) A-G

Codeforces Round 935 (Div. 3) A-G

时间：2024-03-20 13:22:46浏览次数：18  
标签：std typedef return int ll Codeforces long Div 935

A

传送门

  先考虑无解情况，外在人的数量如果%3之后还剩下x人，只能靠第三类综合性人y来补充进去，如果x+y小于3则无解，有解只需要向上取整即可。

#include <bits/stdc++.h>

using ll = long long;
typedef std::pair<int, int> PII;
typedef std::array<int, 4> ay;
const int N = 2e5 + 10, M = N << 1;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
#define ls u << 1	
#define rs u << 1 | 1

int n, m;

inline void solve() {
	int a, b, c;
	std::cin >> a >> b >> c;
	
	if (b % 3 && c < (3 - b % 3)) std::cout << -1 << '\n';
	else std::cout << a + (b + c + 2) / 3 << '\n';
}

signed main(void) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	
	int _ = 1;
	
	std::cin >> _;
	while (_ --)
		solve();

	return 0;
}

B

传送门

  任何两个数字都存在最小公倍数，也就是a和b烟花总有一刻会同时上升，从此时之后的m开始统计一定会是最优。基于上述思路直接输出答案即可。

#include <bits/stdc++.h>

using ll = long long;
typedef std::pair<int, int> PII;
typedef std::array<int, 4> ay;
const int N = 2e5 + 10, M = N << 1;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
#define ls u << 1	
#define rs u << 1 | 1

int n, m;

inline void solve() {
	ll a, b, m;
	
	std::cin >> a >> b >> m;
	
	std::cout << (m + a) / a + (m + b) / b << '\n';
}

signed main(void) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	
	int _ = 1;
	
	std::cin >> _;
	while (_ --)
		solve();

	return 0;
}

C

传送门

  前缀和统计0和1的数量，然后枚举车的位置即可。需要注意的是题目中的村庄中央是直接n/2，也就是说当n为3的时候村庄中央不是2而是1.5。

#include <bits/stdc++.h>

using ll = long long;
typedef std::pair<int, int> PII;
typedef std::array<int, 4> ay;
const int N = 3e5 + 10, M = N << 1;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
#define ls u << 1	
#define rs u << 1 | 1

int n, m;

inline void solve() {
	std::cin >> n;
	
	std::string str;
	std::cin >> str;
	str = " " + str;
	std::vector<int> num0(n + 1), num1(n + 1);

	for (int i = 1; i <= n; i ++) {
		if (str[i] == '0') num0[i] ++;
		else num1[i] ++;
		
		num0[i] += num0[i - 1];
		num1[i] += num1[i - 1];
	}
	
	int pos = -1;
	
	if (num1[n] >= (n + 1) / 2) pos = 0;
	
	for (int i = 1; i <= n; i ++) {
		int suml = num0[i];
		int sumr = num1[n] - num1[i];
		
		if (suml >= (i + 1) / 2 && sumr >= (n - i + 1) / 2) {
			if (pos == -1) pos = i;
			else {
				double disi = std::abs(double(n) / 2 - i);
				double dispos = std::abs(double(n) / 2 - pos);
				if (disi < dispos) pos = i;
			}
		}
	}
	
	std::cout << pos << '\n';
}

signed main(void) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	
	int _ = 1;
	
	std::cin >> _;
	while (_ --)
		solve();

	return 0;
}

D

传送门

  当i > m 时 如果想跟第i个人换位是不影响第i+1个人的决策的，也就是说可以先和第i+1个人换位再换到i也可以直接换到i。以此类推大于m时直接取ai和bi的最小值即可。
  最终目标是要换进前m个人里面，此时只能跟其中一个人交换，枚举这个人i是谁并且支付i + 1 —— m之间人的b即可。

#include <bits/stdc++.h>

using ll = long long;
typedef std::pair<int, int> PII;
typedef std::array<int, 4> ay;
const int N = 2e5 + 10, M = N << 1;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
#define ls u << 1	
#define rs u << 1 | 1

int n, m;
ll a[N], b[N];

inline void solve() {
	std::cin >> n >> m;
	
	for (int i = 1; i <= n; i ++) std::cin >> a[i];
	
	for (int i = 1; i <= n; i ++) std::cin >> b[i];
	
	ll sum = 0;
	ll mx = inf;
	for (int i = m + 1; i <= n; i ++) sum += std::min(a[i], b[i]);
	for (int i = n - 1; i; i --) b[i] += b[i + 1];
	b[n + 1] = 0;
	
	for (int i = 1; i <= m; i ++) {
		mx = std::min(a[i] + b[i + 1] - b[m + 1] + sum, mx);
	}
	
	std::cout << mx << '\n';
}

signed main(void) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	
	int _ = 1;
	
	std::cin >> _;
	while (_ --)
		solve();

	return 0;
}

E

传送门

  观察发现整个过程中m一定不会等于1,因为只有当L=1,R=2时(L+R)/2才会等于1，但是R-L==1时会终止，所以把x换到位置1能保证x不不出现在二分的过程中。然后模拟一遍二分的过程找出最终的L，让1和L交换位置即可。整个过程刚好两次交换。

#include <bits/stdc++.h>

using ll = long long;
typedef std::pair<int, int> PII;
typedef std::array<int, 4> ay;
const int N = 2e5 + 10, M = N << 1;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
#define ls u << 1	
#define rs u << 1 | 1

int n, m;
int a[N], pos[N];

inline void solve() {
	std::cin >> n >> m;
	
	for (int i = 1; i <= n; i ++) {
		std::cin >> a[i];
		pos[a[i]] = i;
	}
	
	std::cout << 2 << '\n';
	
	int l = 1, r = n + 1;
	int mid = l + r >> 1;

	std::cout << 1 << ' ' << pos[m] << '\n';
	std::swap(a[1], a[pos[m]]);
	
	while (r - l != 1) {
		mid = l + r >> 1;
		
		if (a[mid] <= m) l = mid;
		else r = mid;
	}
	
	std::cout << l << ' ' << 1 << '\n';
}

signed main(void) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	
	int _ = 1;
	
	std::cin >> _;
	while (_ --)
		solve();

	return 0;
}

F

传送门

  权值线段树上二分板子题，不想研究其他写法。

#include <bits/stdc++.h>

using ll = long long;
typedef std::pair<int, int> PII;
typedef std::array<int, 4> ay;
const int N = 2e5 + 10, M = N << 1;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;


int n, m;
PII a[N];
int num[N * 30];
int L[N * 30], R[N * 30], idx;

#define ls L[u]
#define rs R[u]

inline void insert(int u, int l, int r, int v, int x) {
	if (l == r) {
		num[u] += x;
		return ;
	}
	
	int mid = l + r >> 1;
	if (v <= mid) {
		if (!ls) ls = ++ idx;
		insert(ls, l, mid, v, x);
	} else {
		if (!rs) rs = ++ idx;
		insert(rs, mid + 1, r, v, x);
	}
	
	num[u] = num[ls] + num[rs];
}

inline void clear(int u) {
	if (ls) clear(ls);
	if (rs) clear(rs);
	
	ls = rs = num[u] = 0;
}

inline int query(int u, int l, int r, int k) {
	if (l == r) return l;
	int mid = l + r >> 1;
	if (num[rs] >= k) return query(rs, mid + 1, r, k);
	return query(ls, l, mid, k - num[rs]);
}

inline void solve() {
	clear(1);
	std::cin >> n;
	
	idx = 1;
	
	for (int i = 1; i <= n; i ++) std::cin >> a[i].second;
	
	for (int i = 1; i <= n; i ++) std::cin >> a[i].first;
	
	for (int i = 1; i <= n; i ++) insert(1, 1, 1e9, a[i].second, 1);
	
	ll ans = 0, sum = 0;
	for (int i = 1; i <= n; i ++) {
		if (num[1] < i) break;
		int t = query(1, 1, 1e9, i);
		if (1ll * t * i > ans) {
			ans = 1ll * t * i;
			sum = i;
		}
		insert(1, 1, 1e9, a[a[i].first].second, -1);
	}
	
	std::cout << ans << ' ' << sum << '\n';
}

signed main(void) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	//freopen("D:\\in.txt", "r", stdin);
	int _ = 1;
	
	std::cin >> _;
	while (_ --)
		solve();

	return 0;
}

G

传送门

  不知道为什么会被放在G感觉比F都简单。
  考虑已经吃饭之后回来的学生和还没有吃过饭的学生之间的关系，如果吃完饭回来继续排队的学生的优先级小于等于还没有吃过饭的学生的最大值，那么下一个打饭的一定是还没吃过饭的第一个学生。否则就是排队回来的学生里面优先级最大的。由于优先级可能相同，所以需要用一个额外的时间戳维护优先级相同的先后顺序，所以set里面存三个参数: 优先级，时间戳，编号。然后根据时间模拟一遍即可。

#include <bits/stdc++.h>

using ll = long long;
typedef std::pair<int, int> PII;
typedef std::array<int, 3> a3;
const int N = 2e5 + 10, M = N << 1;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;


int n, m;

inline void solve() {
	std::cin >> n >> m;
	
	std::vector<PII> p(n + 1);
	
	std::vector<int> suffixmax(n + 2, 0);
	for (int i = 1; i <= n; i ++) {
		std::cin >> p[i].first >> p[i].second;
		suffixmax[i] = p[i].first;
	}
	
	for (int i = n - 1; i; i --) suffixmax[i] = std::max(suffixmax[i], suffixmax[i + 1]);
	
	std::vector<std::vector<int>> pos(m + 1, std::vector<int>());
	std::set<a3> st;
	int tot = 0, l = 1;
	int tim = m + 1;
	
	for (int i = 1; i <= m; i ++) {

		int pe = 0;
		if (l <= n) pe = l;
		if (!st.empty()) {
			auto cur = *prev(st.end());
			if (suffixmax[l] < cur[0]) {
				pe = cur[2];
				st.erase(prev(st.end()));
			}	
		}
		
		if (pe == l) l ++;
		if (i + p[pe].second <= m) pos[i + p[pe].second].push_back(pe);
		
		if (l > n) {
			std::cout << i << '\n';
			return ;
		}

		if (pos[i].size()) std::sort(pos[i].begin(), pos[i].end(), [&](int x, int y) {
			return p[x].second < p[y].second;
		});
		
		for (auto x: pos[i]) {
			tim --;
			st.insert({p[x].first, tim, x});
		}
		tim --;
		
	}
	
	std::cout << -1 << '\n';
}

signed main(void) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	//freopen("D:\\in.txt", "r", stdin);
	int _ = 1;
	
	std::cin >> _;
	while (_ --)
		solve();

	return 0;
}

标签：std,typedef,return,int,ll,Codeforces,long,Div,935
From： https://www.cnblogs.com/qdhys/p/18084782

相关文章

  • codeforce Round 935 div3 个人题解（A-E）
    A.SettingupCamp时间限制：每个测试1秒内存限制：每个测试256兆字节输入：标准输入输出：标准输出组委会计划在游览结束后带领奥林匹克运动会的参赛选手进行徒步旅行。目前，正在计算需要搭帐篷的数量。已知每顶帐篷最多可容纳3人。在参赛选手中，有a个内向型，b个外向型和c个综合型：......
  • CodeForces 1945H GCD is Greater
    洛谷传送门CF传送门感觉是这场唯一比较有趣的题？首先明确一点：先手只会选\(2\)个数，因为数多了\(\gcd\)会变小，而且对方的\(\text{and}\)会变大。所以对于某一位，若\(0\)的个数\(\ge3\)那么对方的按位与这一位一定是\(0\)。所以若\(0\)的个数\(\le2\)，那么可能会......
  • Codeforces Round 923 (Div. 3) D. Find the Different Ones!
    写点简单的思维题https://codeforces.com/problemset/problem/1927/D思路：用两个数组，一个存储原始数据，一个用nex存该位置第一次不一样的下标#include<iostream>#include<vector>#include<algorithm>#include<math.h>#include<sstream>#include<string>#include<str......
  • CF1935 A-C题解
    A设\(s\)翻转后的字符串为\(t\)，考虑进行\(n\)次操作可能生成出哪些字符串：只进行翻转操作——\(s\)；先复制再\(n-1\)次翻转——\(s+t\)；先翻转，再复制，再翻转\(n-2\)次，\(t+s\)；多次复制的情况。情况2显然劣于情况1；情况4得到的字符串的开头一定是\(s\)或者\(t\)......
  • 1948.Educational Codeforces Round 163 - sol
    202403补题效率低下。场上发挥并不是很好，A~E都是简单的，而场上没有去推F的式子，只是找了找规律，然后发现是一个不可做的东西就下播了。如果直接推式子就会很快地做出来，还是非常可惜。A.SpecialCharactersYouaregivenaninteger\(n\).Yourtaskistobuildast......
  • Codeforces Round 920 (Div. 3)-----＞E. Eat the Chip
    一，思路：1.这是一道博弈论的题目（两个人都绝顶聪明，所以每个人都会按最优方案进行）。这题你会发现，两个人从一开始就已经确定了结局。2.如假如他们俩的棋子在竖直方向上距离相差的值是偶数，那么一定就两个结果Alice赢或者平局，反之奇数则是Bob赢或者平局（仔细分析一下就能得知）。3.所......
  • CF933-Div3
    D-RudolfandtheBallGame深搜+减枝点击查看代码#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintN=1005;intT,n,m,x;boolans[N];intu[N],v[N],tot;boolstep[N][N];voiddfs(intnow,intpos){ if(step[now][pos]==1) { re......
  • Codeforces Round 918 (Div. 4)-----＞E. Romantic Glasses
    一，思路：这题是一道前缀和的扩展题。题目要我们求是否有一个区间内的奇偶之和是否相等，我们可以对数组重新赋值，奇数位赋值为负数，偶数位不变。这样我们后面求前缀和，只要看有没有一段区间和为零的。二，代码：#include<iostream>#include<cstring>#include<algorithm>#include<vec......
  • CodeForces 1943D2 Counting Is Fun (Hard Version)
    洛谷传送门CF传送门被自己的赛时智障操作气笑了。谁告诉你容斥钦定了几个要记到状态里面的。。。/tuu显然先找“好数组”的充要条件。对原数组\(a\)差分，设\(b_i=a_i-a_{i-1}\)。那么一次可以选择一对\((i,j)\)满足\(i\lej-2\)，然后给\(b_i\)减\(1\)，给\(b_......
  • Codeforces Round 933 G. Rudolf and Subway
    原题链接：Problem-G-Codeforces思路：根据题意可知相同颜色的边一定是联通的，那么就可以设置虚点，例如1-2，2-3，3-4边的颜色都是相同的，那么就可以设置一个特殊的点例如设置为10，那么这三条边就可以改成1-10，10-2，2-10，10-3，3-10，10-4，从点到虚点需要1的代价，但是从虚点到其他点不需要代价，......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99