首页 > 其他分享 >Codeforces Round 988 (Div. 3) A~D

Codeforces Round 988 (Div. 3) A~D

时间：2024-11-18 16:33:45浏览次数：1  
标签：988 int typedef long Codeforces ____ Div ___ define

Codeforces Round 988 (Div. 3)

A. Twice

这个题就是简单的贪心题，在相同大小的元素里面，我们只能选择两个来对评分更新，所以最多能更新(相同元素的个数) / 2次，记录相同元素的个数就行了

// Problem: A. Twice
// Contest: Codeforces - Codeforces Round 988 (Div. 3)
// URL: https://codeforces.com/contest/2037/problem/0
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//by codeforcer ——
//  ____  _   _  _   _  _   _   ____    _ 
// / ___|| | | || | | || | | | |___  \ | |
//| |    | |_| || |_| || |_| |   __) | | |
//| |    |  _  ||  _  ||  _  |  |__  < | |
//| |___ | | | || | | || | | |  ___) | | |
// \____||_| |_||_| |_||_| |_| |____ / |_|


#include<bits/stdc++.h>
using namespace std;

typedef int E;
typedef long long LL;
typedef pair<int, int> PII;
typedef tuple<int, int, int> PIII;
typedef tuple<LL, LL, LL> PLLL;
typedef pair<long long, long long> PLL;
typedef unsigned long long ULL;

#define endl '\n'
#define vec vector
#define pb push_back
#define pob pop_back
#define fir first
#define sec second
#define maxINT 0x3f3f3f3f
#define maxLL 0x3f3f3f3f3f3f3f3fLL
#define umap unordered_map
#define uset unordered_set
#define maxheap priority_queue<E, vector<E>, less<E>>
#define minheap priority_queue<E, vector<E>, greater<E>>

#define prvec(a)                			\
    for (int i = 0; i < (a).size(); i++) {	\
        cout << (a)[i] << " ";   			\
    }                            			\
    cout << endl;

#define debug0(a)             		        \
    cout << #a << ": ";               		\
    for (int k = 0; k < (a).size(); k++) {  \
        cout << (a)[k] << " ";        		\
    }                                 		\
    cout << endl;							
    
    
#define debug1(a)             		        \
    cout << #a << ": ";               		\
    for (int k = 1; k <= (a).size(); k++) { \
        cout << (a)[k] << " ";        		\
    }                                 		\
    cout << endl;		                          
	
LL gcd(LL a, LL b) { return (b) ? gcd(b, a % b) : a; }
LL exgcd(LL a, LL b, LL &x, LL &y) {if (b == 0) { x = 1, y = 0; return a; }LL gcd = exgcd(b, a % b, y, x);y -= a / b * x;return gcd;}
LL qmi(LL a, LL b, LL mod) {LL res = 1;while (b) {if (b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;}

const int N = 200010;

void solve() {
    int n;
    cin>>n;
    map<int,int> mp;
    for(int i = 0;i < n;i ++)
    {
    	int x;
    	cin>>x;
    	mp[x] ++;
    }
    long long ans = 0;
    for(auto p : mp)
    {
    	int l = p.first,r = p.second;
    	if(r >= 2)
    	{
    		ans += r / 2;
    	}
    }
    cout<<ans<<endl;
    
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	int n;cin>>n;while(n --)
	 solve();

    return 0;
}

B. Intercepted Inputs

这个题目的题意要理解清楚，他说的是输入已经给出来了，然后输入的数据被打乱了，也就是说题目需要的n m就在给的输入里面。输入n个数也就代表n * m = (n - 2) ，剩下的n - 2个数就是二维数组里面的数，所以我们只需要让(n - 2) % n == 0，然后看(n - 2) / n 在不在输入的n个数里面就行。注意有n = 6 ，然后给的数据是2 1 4 5 5 5的情况，这个直接枚举就会导致答案是2，因为(6 - 2) / 2 = 2但是2只出现了依次所以不是答案不是2 2应该是1 4

// Problem: B. Intercepted Inputs
// Contest: Codeforces - Codeforces Round 988 (Div. 3)
// URL: https://codeforces.com/contest/2037/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//by codeforcer ——
//  ____  _   _  _   _  _   _   ____    _ 
// / ___|| | | || | | || | | | |___  \ | |
//| |    | |_| || |_| || |_| |   __) | | |
//| |    |  _  ||  _  ||  _  |  |__  < | |
//| |___ | | | || | | || | | |  ___) | | |
// \____||_| |_||_| |_||_| |_| |____ / |_|


#include<bits/stdc++.h>
using namespace std;

typedef int E;
typedef long long LL;
typedef pair<int, int> PII;
typedef tuple<int, int, int> PIII;
typedef tuple<LL, LL, LL> PLLL;
typedef pair<long long, long long> PLL;
typedef unsigned long long ULL;

#define endl '\n'
#define vec vector
#define pb push_back
#define pob pop_back
#define fir first
#define sec second
#define maxINT 0x3f3f3f3f
#define maxLL 0x3f3f3f3f3f3f3f3fLL
#define umap unordered_map
#define uset unordered_set
#define maxheap priority_queue<E, vector<E>, less<E>>
#define minheap priority_queue<E, vector<E>, greater<E>>

#define prvec(a)                			\
    for (int i = 0; i < (a).size(); i++) {	\
        cout << (a)[i] << " ";   			\
    }                            			\
    cout << endl;

#define debug0(a)             		        \
    cout << #a << ": ";               		\
    for (int k = 0; k < (a).size(); k++) {  \
        cout << (a)[k] << " ";        		\
    }                                 		\
    cout << endl;							
    
    
#define debug1(a)             		        \
    cout << #a << ": ";               		\
    for (int k = 1; k <= (a).size(); k++) { \
        cout << (a)[k] << " ";        		\
    }                                 		\
    cout << endl;		                          
	
LL gcd(LL a, LL b) { return (b) ? gcd(b, a % b) : a; }
LL exgcd(LL a, LL b, LL &x, LL &y) {if (b == 0) { x = 1, y = 0; return a; }LL gcd = exgcd(b, a % b, y, x);y -= a / b * x;return gcd;}
LL qmi(LL a, LL b, LL mod) {LL res = 1;while (b) {if (b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;}

const int N = 200010;
void solve() {
    int n;
    cin>>n;
    vector<int> a(n + 1);
    map<int,int> mp;
    map<int,int> st;
    for(int i = 0; i <n;i ++)
    {
    	cin>>a[i];
    	st[a[i]] ++;
    	if((n - 2) % a[i] == 0)
    	{
    		mp[a[i]] = (n - 2)/a[i];
    	}
    }
    
    for(int i = 0;i < n;i ++)
    {

    	if(st[mp[a[i]]] != 0 )
    	{
    		if(mp[a[i]] == a[i] && st[a[i]] <= 1) continue;
    		cout<<a[i]<<" "<<mp[a[i]]<<endl;
    		return;
    	}
    }
    
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	int n;cin>>n;while(n --)
	 solve();

    return 0;
}

C. Superultra's Favorite Permutation

这个也是贪心题目，首先我们考虑奇数和偶数分开的情况

  • 奇数和奇数放一起有：奇数加奇数肯定是偶数，偶数一定不是质数
  • 偶数和偶数放一起有：偶数加偶数一定是偶数，偶数一定不是质数

所以我们只需要考虑偶数和奇数之间的分界点，我们需要找到一个偶数和一个奇数加在一起不是质数，最小的情况就是n = 5 的时候，排列是1 3 5 4 2，n逐渐增大奇数往排列的前面放，偶数往后面放

// Problem: C. Superultra's Favorite Permutation
// Contest: Codeforces - Codeforces Round 988 (Div. 3)
// URL: https://codeforces.com/contest/2037/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//by codeforcer ——
//  ____  _   _  _   _  _   _   ____    _ 
// / ___|| | | || | | || | | | |___  \ | |
//| |    | |_| || |_| || |_| |   __) | | |
//| |    |  _  ||  _  ||  _  |  |__  < | |
//| |___ | | | || | | || | | |  ___) | | |
// \____||_| |_||_| |_||_| |_| |____ / |_|


#include<bits/stdc++.h>
using namespace std;

typedef int E;
typedef long long LL;
typedef pair<int, int> PII;
typedef tuple<int, int, int> PIII;
typedef tuple<LL, LL, LL> PLLL;
typedef pair<long long, long long> PLL;
typedef unsigned long long ULL;

#define endl '\n'
#define vec vector
#define pb push_back
#define pob pop_back
#define fir first
#define sec second
#define maxINT 0x3f3f3f3f
#define maxLL 0x3f3f3f3f3f3f3f3fLL
#define umap unordered_map
#define uset unordered_set
#define maxheap priority_queue<E, vector<E>, less<E>>
#define minheap priority_queue<E, vector<E>, greater<E>>

#define prvec(a)                			\
    for (int i = 0; i < (a).size(); i++) {	\
        cout << (a)[i] << " ";   			\
    }                            			\
    cout << endl;

#define debug0(a)             		        \
    cout << #a << ": ";               		\
    for (int k = 0; k < (a).size(); k++) {  \
        cout << (a)[k] << " ";        		\
    }                                 		\
    cout << endl;							
    
    
#define debug1(a)             		        \
    cout << #a << ": ";               		\
    for (int k = 1; k <= (a).size(); k++) { \
        cout << (a)[k] << " ";        		\
    }                                 		\
    cout << endl;		                          
	
LL gcd(LL a, LL b) { return (b) ? gcd(b, a % b) : a; }
LL exgcd(LL a, LL b, LL &x, LL &y) {if (b == 0) { x = 1, y = 0; return a; }LL gcd = exgcd(b, a % b, y, x);y -= a / b * x;return gcd;}
LL qmi(LL a, LL b, LL mod) {LL res = 1;while (b) {if (b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;}

const int N = 200010;

void solve() {
	deque<int> a = {1,3,5,4,2};
    int n;
    cin>>n;
    if(n < 5)
    {
    	cout<< -1 <<endl;
    	return ;
    }
    while(n > 5)
    {
    	if(n % 2)
    	{
    		a.push_front(n);
    	}else
    	{
    		a.push_back(n);
    	}
    	n --;
    }
    
    for(int i = 0; i < a.size();i ++)
    {
    	cout<<a[i]<<" ";
    }
    cout<<endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	int n;cin>>n;while(n --)
	 solve();

    return 0;
}

D. Sharky Surfing

这个题目是一道数据结构模拟题，带一点贪心思想

首先我们在面对障碍之前肯定得有足够的能量跳过这段障碍，那么我们不考虑选哪个位置的能量增益，因为我们要让数量最小肯定是获取最大的，假如我们现在在障碍at[i]之前，能量为k小于right - left + 2，也就是不能跳过去，我们得想想前面哪些增益没拿到，从前面已经经过的路上取，简单点说我们让过去的自己获取这个增益来让现在的自己能跳过这个障碍，这就带了一点贪心思维，我们要跳过这个障碍肯定是得尽可能地拿能量增益来跳过障碍，最终我们只需要考虑以下两种情况：

  • 现在的能量k能跳过，就跳过
  • 现在的能量k不能跳过这个区间，那么我取前面没用取到的最大能量增益，如果还是不够就继续取，如果取完了还是不行就输出-1
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

#define maxheap priority_queue<int, vector<int>, less<int>>//大根堆，堆顶的第一个元素是这个堆里面的最大值

void solve() {
    int n, m, ed;
    cin >> n >> m >> ed;
    
    vector<pair<int, int>> at(n);
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        at[i] = {l, r};
    }
    
    deque<pair<int, int>> b(m); //双端队列
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        b[i] = {l, r};
    }
    
    LL k = 1, sum = 0;
    priority_queue<int, vector<int>, less<int>> heap;
    
    for (int i = 0; i < n; i++) { //枚举每一个障碍区间
        int l = at[i].first, r = at[i].second;
        while (!b.empty() && b.front().first < at[i].first) { //如果跳过之前的区间，在现在这个区间到之前的位置
        													 //之前有新的能量增益，放入大根堆备选
            heap.push(b.front().second);
            b.pop_front();
        }
        while (k < (r - l + 2) && !heap.empty()) {
            k += heap.top();
            sum++;
            heap.pop();//用了这个能量增益就得把这个从大根堆里面丢掉
        }
        if (k < (r - l + 2)) {
            cout << -1 << endl;
            return;
        }
    }
    cout << sum << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;
    while (n--) {
        solve();
    }

    return 0;
}

标签：988,int,typedef,long,Codeforces,____,Div,___,define
From： https://www.cnblogs.com/chhh31/p/18552935

相关文章

  • 题解：CF contest 2037 : [Codeforces Round 988 (Div. 3)] （A-E）
    ATwice题面Kinich醒来迎接新的一天的开始。他打开手机，查看邮箱，发现了一份神秘的礼物。他决定打开礼物的盒子。Kinich用\(n\)整数打开数组\(a\)。最初，Kinich的分数是\(0\)。他将执行任意次数的以下操作：—选择两个索引\(i\)和\(j\)\((1\leqi\lt;j\leqn)\)，确......
  • Codeforces Round 988 (Div. 3)
    CodeforcesRound988(Div.3)总结A没啥好说的，用桶存出现次数。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<vector>#include<queue>#include<map>usingnames......
  • Solution - Codeforces 1957E Carousel of Combinations
    首先这个\(C(i,j)\bmodj\)的形式就非常怪，于是首先肯定要先研究一下这个值。先考虑如何求\(C(i,j)\)。可以考虑先选出要用的\(j\)个数，再乘上其排列成环的方案数，那么有\(C(i,j)=\binom{i}{j}\times(j-1)!\)。那么就是来考虑\(\binom{i}{j}\times(j-1)!\bmod......
  • 【星航计划】2024.11 Div. 3 题解
    2024--星航计划--十一月份--基础算法A.分段每一段连续的\(1\)之间是独立的，我们只需要关心一段连续的1的结果。可以证明对于一段连续的\(1\)，最优策略是将其划分成多个单独的\(1\)以及可能余下的连续两个\(1\)。对于\(k\)个连续的\(1\)，如果\(k\)是奇数，......
  • Codeforces Round 987 (Div. 2) - 比赛总结
    Preface我是若只。A.PenchickandModernMonument先吃三发罚时。最优策略应当是把所有数都调成众数，然而我一开始就忙着往后面做，胡乱猜了个结论就WA了，又猜了一个又WA了，再猜了一个再WA了。点击查看代码constintN=105;intn,a[N];intmain(){ intT;read(T);......
  • Codeforces Round 986 (Div. 2)
    CodeforcesRound986(Div.2)总结A按题意模拟即可，因为\(n,a,b\)很小，可以多循环几遍来判断。只循环十遍的吃罚时qwq。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<vector>#include<queue&......
  • Refact.ai Match 1 (Codeforces Round 985)
    Refact.aiMatch1(CodeforcesRound985)总结A集合中的元素为\(l\lex\ler\)，有\(k\)个\(x\)的倍数在其中才可删，可以求出最大可删的元素，直接计算。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#inclu......
  • 第九章DIV+CSS布局
    9.1DIV+CSS概述9.1.1认识DIVdiv标签在Web标准网页中属于块级元素9.1.2DIV的宽高设置9.1.2.1宽高属性9.1.2.2div标签内直接设置宽高9.1.2.3div使用选择器设置宽高<!DOCTYPEhtml><html> <head> <metacharset="utf-8"/> <title></title> <styletype......
  • Codeforces Round 987 (Div. 2)
    好不容易的一次CF阳间赛，这次题目普遍较长。A-PenchickandModernMonument题目大意将一个非递增的序列通过操作某些数（可增大可减小），最终使得序列变成一个非递减的序列，求出最少要操作多少次？解题思路这个题也是想了不断时间，而且还提交错误一次，原因就是调试的代码没......
  • Codeforces Round 987 (Div. 2)
    训练记录CodeforcesRound987(Div.2)4/6前四题都是简单思维题A.PenchickandModernMonument这个题目最贪心的做法是找到出现最多的数，保留种数字不变，其他按照题目要求改大小就行//Problem:A.PenchickandModernMonument//Contest:Codeforces-CodeforcesRound......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99