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

Codeforces Round 803 (Div. 2)

时间:2023-12-10 18:44:36浏览次数:37  
标签:cnt int Codeforces 三元组 803 Div include fl

基本情况

A题秒了。

B题经典+2。(经典不开longlong)

C题读错题,没得思路。

B. Rising Sand

Problem - B - Codeforces

思路好想,分类讨论找规律就行。

这里还是要强调一下认真分析数据

Input

The second line of each test case contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)) — the sizes of the piles.

\(a_i\) 已经接近 int 的边界了,然后我还有一个这个语句:

if (a[i] > a[i - 1] + a[i + 1])

两个 \(a_i\) 相加是有可能爆 int 的!改成 long long 就AC了。

C. 3SUM Closure

Problem - C - Codeforces

纯暴力肯定是T,然后我又想不到啥结论。

而且,我读了个假题!

题目是所有三元组满足才是"YES"。我读成只要有三元组满足就 "YES"。

思路

既然要求所有三元组,那就有方向了。

因为最大三个值中必定不能全正,同理最小三个值中必定不能全负,而且若干个 \(0\) 与两个 \(0\) 是等价的,直接把多余的去掉。

之后可能符合条件的数列最多只剩下 \(6\) 个数,然后暴力判断。

只能说,读题不认真,思路根本不可能对。

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<map>
#define N 200005

using namespace std;

int T,n,tot;
int a[N],b[N];
map <int,bool> mp;
int cnt_1,cnt_2,fl_0;
bool fl;

int main(){
	scanf("%d",&T);
	
	while(T--){
		mp.clear();
		tot=0;
		fl=0;
		fl_0=cnt_1=cnt_2=0;
		scanf("%d",&n);
		
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			
			if(a[i]>0) ++cnt_1;
			else if(a[i]<0) ++cnt_2;
			else if(a[i]==0) fl_0=1; 
		} 
			
		if(cnt_1+fl_0>=3 || cnt_2+fl_0>=3){
			printf("NO\n");
			continue;
		} 
			
		sort(a+1,a+1+n);
		
		for(int i=1;i<=n;i++){
			if(!b[tot] && !a[i]) continue;
			b[++tot]=a[i];
			mp[b[tot]]=1;
		} 
		
		for(int i=1;i<=tot;i++)
			for(int j=i+1;j<=tot;j++)
				for(int k=j+1;k<=tot;k++)
					if(!mp[b[i]+b[j]+b[k]])
						fl=1;
		printf(fl?"NO\n":"YES\n");
	}
	
	return 0;
}

标签:cnt,int,Codeforces,三元组,803,Div,include,fl
From: https://www.cnblogs.com/kdlyh/p/17893048.html

相关文章

  • Codeforces Round 914 (Div. 2)
    基本情况脑子最卡的一集。A题读假题,卡了快一小时。B题代码太复杂,出错不好修改,一直调。虽然最后都出来了,但是没有剩下任何时间看后面题目了。A.Forked!Problem-A-Codeforces一开始不知道犯得什么病,觉得可以斜着走一格算作一步,然后情况就太多了,非常不好处理。后面突......
  • Codeforces Round 914 (Div. 2)
    C.ArrayGame题意:给定一个n的数组以及k的操作数,每次可以选择下表为i,j(i<j)得到一个abs(a[i]-a[j])的数放在数组末尾,问你k次操作后,数组中最小的数是多少?思路:首先k>=3选相同的下表两次,一定结果是0,是最小。k==1遍历出下表两两相减的绝对值最小以及本身数组中最小的即可k==2要将数......
  • CodeForces 1902F Trees and XOR Queries Again
    洛谷传送门CF传送门如果我们能把\(x\toy\)路径上的所有点权插入到线性基,那么可以\(O(\logV)\)查询。但是因为线性基合并只能\(O(\log^2V)\)(把一个线性基的所有元素插入到另一个),所以只能倍增做\(O((n+q)\logn\log^2V)\),过不了。考虑\(O(n\logV)\)预处理出......
  • Codeforces Round 904 (Div. 2)
    [CodeforcesRound904(Div.2)](https://codeforces.com/contest/1894)A.SimpleDesign暴力就行了1e9跑不满的#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;voidsolve(){intx,k;cin>>x>>......
  • 如何设置div内的模块靠左显示,模块内容按行显示?
    要设置一个div内的模块靠左显示,并且模块内容按行显示,你可以使用CSS中的flexbox布局来实现。以下是一种可能的解决方案:HTML结构:<divclass="container"><divclass="module">模块1</div><divclass="module">模块2</div><divclass="module"&g......
  • Codeforces Round 801 (Div. 2)
    基本情况A就开始犯病,导致+2.B、C都过样例了,但是都错。B.CircleGame赛时推出来奇数必输,也知道偶数不是必赢,但是思路不清楚。这里我没意识到一个很关键的性质。奇数堆拿的石堆会变,这也导致了必输,比如三个堆\(1,2,3\)。表粗的为JOE。123123显然JOE拿的石堆是变化的......
  • [Codeforces] CF1763B Incinerate
    CF1763BIncinerate题意为了消灭人类,怪物协会向地球表面派出了\(n\)只怪兽。第\(i\)只怪物有一个生命值\(h_i\)和一个攻击力\(p_i\).凭借他最后的一击,真螺旋焚烧炮,Genos可以对所有活着的怪物造成\(k\)点伤害。换句话说,Genos可以通过一次攻击降低所有怪物\(k\)点......
  • Codeforces Round 909 (Div. 3)
    https://codeforces.com/contest/1899  一个小游戏#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;intn;intmain(){cin>>n;while(n--){intx;......
  • [Codeforces] CF1704C Virus
    CF1704CVirus题意有一个长度为\(n\)的环,即对于\(1\leqi\leqn\),满足第\(i\)个与第\(i+1\)个房子相邻,特别地,第\(n\)个房子与第\(1\)个房子也相邻。一开始,这\(n\)个房子中有\(m\)个房子被病毒感染了。在之后的每天早上,都可以选择一个未被感染的房子并对其进行保护,被保......
  • [Codeforces] CF1703E Mirror Grid
    CF1703EMirrorGrid题意给定一个\(n\timesn\(n\le100)\)的01矩形,求至少修改多少次后能使矩形旋转0°,90°,180°,270°后所形成的矩形都完全相同。思路吸纳分为两种情况讨论:\(n\)为奇数那么会出现这种情况:(以\(5\times5\)为例)如上图,我们就可以将其分为五个部分,每个......