ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

Codeforces Round #822 (Div. 2) A - D补题

2022年9月24日 247点热度 0人点赞 0条评论

比赛传送门:Dashboard - Codeforces Round #822 (Div. 2) - Codeforces

A. Select Three Sticks

枚举所有点,选择一个点作为基准,计算所有点与基准的差的绝对值,取最小的三个相加,再从所有结果中取小就可以了。时间复杂度\(O(t*n^2*logn)\)

B. Bright, Nice, Brilliant

这个构造太简单就不说了。

C. Removing Smallest Multiples

从1到N枚举所有数字x,再枚举这个数字x的所有倍数,如果遇到了要保留的数字(s[i] == ‘1’),那么就break,因为这个要保留的数字是x的最小倍数,无法被删除,后面也就无法删除了。类似于埃氏筛法。

调和级数\(\sum_{1}^{n}1 / i =ln(n) + y\),复杂度为\(O(t* n * logn)\)。

D. Slime Escape

先假定要从K到0,如果是要到N + 1只需要将序列反过来从N - K + 1到0即可。

我们把K右侧的点作为“补给站”,但是要求sum要大于等于一个阈值才能获取这个补给,然后一直往左边走,看看能不能走到终点、

反转数组改变起点再算一次。

这是一个很重要的思维,左右横跳的题可以转化为“补给站”。

代码 / Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
const int maxn = 2e5 + 9, inf = 8e18;

int a[maxn], N, K;

bool go(int k)
{
	vector<pair<int, int> > v;//补给站数组 
	for(int i = k + 1, sum = 0, mi = 0;i <= N; ++ i)//mi是过程中的代价,要减去mi依然非负才可以加上sum 
	{
		sum += a[i], mi = min(mi, sum);
		if(sum > 0)v.push_back({mi, sum}), mi = sum = 0;
	}
	
	for(int i = k - 1, j = 0, sum = a[k];i >= 1; -- i)//sum是过程中的值 
	{
		while(j < v.size() && sum + v[j].fi >= 0)sum += v[j ++].second;
		sum += a[i];
		if(sum < 0)return false;//如果中途出现负数就停 
	}
	return true;
}

void solve()
{
	cin >> N >> K;
	
	for(int i = 1;i <= N; ++ i)cin >> a[i];
	bool ans1 = go(K);
	reverse(a + 1,a + 1 + N);
	bool ans2 = go(N - K + 1);
	
	cout << ((ans1 || ans2) ? "YES" : "NO") << '\n';
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _;cin >> _;
	while(_ --)solve();
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ codeforces 思维 算法竞赛
最后更新:2022年9月24日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • A. Select Three Sticks
  • B. Bright, Nice, Brilliant
  • C. Removing Smallest Multiples
  • D. Slime Escape
    • 代码 / Code

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号