首页 > 其他分享 >2022 winter training.1

2022 winter training.1

时间:2022-12-29 10:22:05浏览次数:71  
标签:const winter int ll training.1 mid 2022 dp define

A - Searching Local Minimum

https://codeforces.com/problemset/problem/1480/C

题意

交互题 有一个1~n的序列 最多询问100次 问i位置上的数是什么 最后要找出一个局部最小值(极小值)的位置

思路

二分 每次询问mid 和 mid+1的位置上的值
如果mid位置上的值比mid+1位置上的值小 r->mid-1 记录答案 mid(这里存在边界问题)
如果mid位置上的值比mid+1位置上的值大 l->mid+1 记录答案 mid+1
因为每次都往值更小的方向缩 所以最后二分出来的肯定是比它两边都小的值

#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
#define int ll
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 3e5 + 5;
const int M = 5e5 + 5;
const ll mod = 1e9 + 7;

int n, a[N];

void query(int x){
	cout << "? " << x << "\n";
	cout.flush();
	cin >> a[x];
}

void solve()
{
	cin >> n;
	if(n == 1){
		cout << "! " << 1 << "\n";
		cout.flush();
		return;
	}

	query(1);
	query(2);
	query(n);
	query(n - 1);

	a[0] = a[n + 1] = n + 1;
	if(a[n] < a[n - 1]){
		cout << "! " << n << "\n";
		cout.flush();
		return;
	}

	if(a[1] < a[2]){
		cout << "! " << 1 << "\n";
		cout.flush();
		return;
	}

	int l = 2, r = n;
	int now = a[2], ans = 2;
	while(l <= r){
		int mid = (l + r) / 2;
		query(mid);
		if(!a[mid + 1]) query(mid + 1);
		if(a[mid + 1] > a[mid]){
			r = mid - 1;
			ans = mid;
			//now = a[mid];
		}
		else {
			l = mid + 1;
			//now = a[mid + 1];
			ans = mid + 1;
		}
	}

	cout << "! " << ans << "\n";
	cout.flush();
}


signed main()
{
	//IOS;
	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}
}

B - Painting the Array I

https://codeforces.com/problemset/problem/1480/D1

题意

给定一个长度为n的数组 将这个数组分成两个集合 数字按原顺序排列 然后合并两个集合中相邻且相同的数 问最后两个集合大小和最大是多少

思路

顺序遍历原数组 判断当前一个数放到那个集合中最优
每次让当前这个数与两集合中最后一个数比较
如果和一个数相同与另一个数不同 那就将这个数放到不同的那个数后面
如果都相同 就直接丢掉
如果都不相同 那就判断两个末尾数哪一个数下次出现最近 将当前这个数放到下一次出现更早的那个数后面,这样就保证更不容易出现相同的数

#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
#define int ll
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 3e5 + 5;
const int M = 5e5 + 5;
const ll mod = 1e9 + 7;

int n, a[N];

void solve()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];

	if(n <= 2){
		cout << n << "\n";
		return;
	}
	stack<int>st1, st2;

	for(int i = 1; i <= n; i++){
		int num1 = -1, num2 = -1;
		if(st1.size()) num1 = st1.top();
		if(st2.size()) num2 = st2.top();

		if(num1 < 0 && num2 < 0) {
			st1.push(a[i]);
			continue;
		}
		
		if(num1 < 0 && num2 > 0){
			if(a[i] != num2) st2.push(a[i]);
			else st1.push(a[i]);
			continue;
		}

		if(num1 > 0 && num2 < 0){
			if(a[i] != num1) st1.push(a[i]);
			else st2.push(a[i]);
			continue;
		}

		if(a[i] == num1 && a[i] == num2) continue;
		if(a[i] != num1 && a[i] == num2) st1.push(a[i]);
		else if(a[i] != num2 && a[i] == num1) st2.push(a[i]);
		else {
			if(i < n && a[i + 1] == st2.top()) st2.push(a[i]);
			else st1.push(a[i]);
		}
	}

	cout << (int)st1.size() + (int)st2.size() << "\n";
}


signed main()
{
	IOS;
	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}
}

C - Painting the Array II

上面b题的求最小值版 和上面b题的做法一样 就尽量让当前数与两个尾数相等

G - Destroyer Takahashi

题意

给n段区间
一个操作 选定一个定长len的区间 让部分或全部出现在选定区间范围内的所有区间都消失
问让所有区间都消失的最小操作次数

思路

n段区间 按右边界排序 然后将每段区间都放进按左边边界排序的优先队列中
遍历按右边界排好序的序列
每次选定的消失区间是 l = 最前面没有消失的序列的右边界, \(r = l + len - 1\),然后在队列中左边界小于消失区间右边界的都消失 标记消失
不用管右边界,因为是按右边界小到大排序的,队列中还没删的区间的右边界肯定>=l
最后计一下用了几个消失区间即可

#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
#define int ll
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 3e5 + 5;
const int M = 5e5 + 5;
const ll mod = 1e9 + 7;

int n, k, vis[N];
pair<int, int>p[N];
void solve()
{
	cin >> n >> k;
	for(int i = 1, l, r; i <= n; i++){
		cin >> l >> r;
		p[i] = {r, l};
	}

	sort(p + 1, p + 1 + n);

	priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, greater<pair<pair<int, int>, int>>>q;
	for(int i = 1; i <= n; i++){
		int l = p[i].second;
		int r = p[i].first;
		q.push({{l, r}, i});
	}

	int ans = 0;
	for(int i = 1; i <= n; i++){
		if(vis[i]) continue;
		ans++;
		int pos = p[i].first + k - 1;
		while(q.size()){
			auto now = q.top();
			int l = now.first.first;
			if(l <= pos){
				vis[now.second] = 1;
				q.pop();
			}
			else break;
		}
	}

	cout << ans << "\n";
}


signed main()
{
	IOS;
	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}
}

H - Fraction Floor Sum

整除分块板子题 注意一下 k = n / l就是当前整除的值 用这个去找整除值相同的右边界即可

I - Predilection

https://atcoder.jp/contests/abc230/tasks/abc230_f?lang=en

题意

给定一个长度为n的序列
可以合并若干个连续的数 若干次 问你最后不同的数组有多少个
首先可以得出一个结论 对于一个全正长度为n的数组 你最多可以有\(2^(n - 1)\)个不同的序列
我们可以用dp来写
dp[i]: 1-i这段数组 经过合并操作最多可以形成不同数组的数量
那么 \(dp[i] = dp[i - 1] * 2\)
除此之外我们还要考虑 可能会有重复的情况:
就列如:
1 2 3 0 4
1 2 3+0 4 与 1 2 3 0+4重复了
所以对于某个和为0的区段 它下一位置的dp值得减去它上一位置的dp值(前面是重复的)
那么我们就要记录一下前缀 当某个位置的前缀在前面已经出现过 那它就会影响下一位置的dp值
即 \(dp[i] = dp[i] - dp[pos[pre[i - 1]]]\)

#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
#define int ll
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 3e5 + 5;
const int M = 5e5 + 5;
const ll mod = 998244353;

int n, a[N], pre[N], dp[N];

void solve()
{
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		pre[i] = pre[i - 1] + a[i];
	}

	map<int, int>pos;
	dp[1] = 1;
	for(int i = 2; i <= n; i++){
		dp[i] = dp[i - 1] * 2 % mod;
		if(pos[pre[i - 1]])
			dp[i] = (dp[i] - dp[pos[pre[i - 1]]] + mod) % mod;
		
		pos[pre[i - 1]] = i - 1;
	}

	cout << dp[n] << "\n"; 
}


signed main()
{
	IOS;
	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}
}

标签:const,winter,int,ll,training.1,mid,2022,dp,define
From: https://www.cnblogs.com/yaqu-qxyq/p/17011849.html

相关文章

  • 2022/12/28
    今天和爆破斗了一天...誓与爆破死磕到底写的加密有问题,还是不能自己写加密,跟个垃圾一样,明天去网上搜点简单的爆破例子写的代码和想要的代码得是一个意思不能构思的时候......
  • the seventh——2022.12.28
    %a.bf的含义%f是输出float(单精度浮点型)型变量,%m.nf中m代表输出数长,n代表小数点后的数长,即保留n位小数。如果小数点后的数大于n,例如12.4567按照%5.2f输出得12.46(四舍五入......
  • react 脚手架搭建项目 报错C:\Program Files\nodejs\node_cache\_logs\2022-12-2
    报错内容: 解决方法:第一步:删除C:\ProgramFiles\nodejs\node_cache\_logs目录下所有文件  第二步:切换镜像 npmconfigsetregistryhttps://registry.npm.tao......
  • 2022暑假刷题
    1038-长方体_牛客竞赛语法入门班顺序结构习题(nowcoder.com)本题需将长方体面积转化为边长。设长方体三边为x,y,z,边长和=4*(x+y+z),即求(x+y+z),而a=xy,b=yz,c=zx。由三......
  • 2022年总结-五年的时间才明白业务的重要性
    2022年总结-五年的时间才明白业务的重要性 一:因起​从事软件开发工作了几年了,总感觉缺少一些"灵魂"的东西,为此很纠结,困惑,一直彷徨不定,很苦恼,以前认为技术很重要,学......
  • Codeforces Round #841 (Div. 2) and Divide by Zero 2022
    Preface这场Div2怎么感觉难度和Div3一样,ABCD都是SB题一眼秒,可惜D下标\(n,m\)弄混挂了一发E本来也是秒出的正解,但是实现的时候一个细节挂了(自作聪明,后来结束前5min改出来......
  • Codeforces Round #841 (Div. 2) and Divide by Zero 2022
    《C.EvenSubarrays》异或和,前缀和  这道题如果用朴素的暴露解法为O(n^2),算出每一个子段的异或和,然后看一下这些异或和中哪个的除数是奇数个,但会超时 超时原因明......
  • 力扣每日一题2022.12.28---1750. 删除字符串两端相同字符后的最短长度
    给你一个只包含字符'a','b' 和'c' 的字符串 s ,你可以执行下面这个操作(5个步骤)任意次:   选择字符串s 一个非空的前缀,这个前缀的所有字符都相同。   选择......
  • 新华三“智・行中国2022”|大厂行动与大国战略的异曲同工之妙
    作者|曾响铃文|响铃说继农业经济、工业经济之后,数字经济登上历史的舞台,成为大国的主要经济形态。在我国,根据中国信息通信研究院发布的《中国数字经济发展白皮书(2022年)》......
  •   Codeforces Round #841 (Div. 2) and Divide by Zero 2022 -----C. Even Subarray
    题目链接:https://codeforces.com/contest/1731/problem/C  题目的大致意思是:给长度为n的数组,求 子数组的异或和  的结果的除数个数为偶数个的子数组有多......