首页 > 其他分享 >题解:AT_arc182_a [ARC182A] Chmax Rush!

题解:AT_arc182_a [ARC182A] Chmax Rush!

时间:2024-08-17 15:04:25浏览次数:11  
标签:tmp Rush arc182 int 题解 void 设为 Chmax

思路

因为前面不允许出现比这次的替换的值还要大的情况,所以如果我们知道下标 \(i,j\) 满足 \(i<j\) 且 \(V_i>V_j\) 的话,我们就必须把它们两次修改分开。具体地:

  1. 若 \(P_i<P_j\):
    此时,我们只能将 \([1,P_i]\) 的值设为 \(V_i\),将 \([P_j,n]\) 的值设为 \(V_j\)。
  2. 若 \(P_i>P_j\):
    此时,我们只能将 \([P_i,n]\) 的值设为 \(V_i\),将 \([1,P_j]\) 的值设为 \(V_j\)。
  3. 若 \(P_i=P_j\):
    此时,一定无解。

我们可以选择倒序枚举,逐渐推出前面的值一定不能是左边或一定不能是右边。

  • 对于两边都能选的情况,直接 \(ans\gets ans\times 2\)。
  • 对于两边只有一边能选的情况 \(ans\) 不变。
  • 对于两边都不能选的情况,直接无解。

代码

// Problem: A - Chmax Rush!
// Contest: AtCoder - AtCoder Regular Contest 182
// URL: https://atcoder.jp/contests/arc182/tasks/arc182_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
namespace gtx{
//	Fast IO
	void read(int &x){
		x = 0;int h = 1;char tmp;
		do{tmp=getchar();if(tmp=='-')h*=-1;}while(!isdigit(tmp));
		while(isdigit(tmp)) x*=10,x+=tmp-'0',tmp=getchar();
		x*=h;
	}
	void read(char &x){do{x=getchar();}while(x==' '||x=='\n'||x=='\r');}
	void write(char x){putchar(x);}
	void write(int x){
		if(x<0) putchar('-'),x=-x;int st[200]={0},tot=0;
		do{st[++tot]=x%10,x/=10;} while(x);
		while(tot){putchar(st[tot--]+'0');};
	}
	void write(int x,char y){write(x);write(y);}
	const int MAXN = 5100;
	const int MOD = 998244353;
	int n,q,p[MAXN],v[MAXN];
	bool can_be[2][MAXN];
	signed main(){
		read(n);read(q);
		for(int i = 1;i<=q;i++){
			read(p[i]);read(v[i]);
			can_be[0][i] = can_be[1][i] = 1;
		}
		int ans = 1;
		for(int i = q;i>=1;i--){
			for(int j = i-1;j>=1;j--){
				if(v[j]>v[i]){
					if(p[i]==p[j]) return puts("0"),0;
					if(p[i]<p[j]){
						can_be[1][i] = 0;
						can_be[0][j] = 0;
					}else{
						can_be[1][j] = 0;
						can_be[0][i] = 0;
					}
				}
			}
			ans = (ans*(can_be[0][i]+can_be[1][i]))%MOD;
		}
		write(ans);
		return 0;
	}
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
//	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T = 1;
//	gtx::read(T);
	while(T--) gtx::main();
	return 0;
}

tag

构造
AtcoderARC

标签:tmp,Rush,arc182,int,题解,void,设为,Chmax
From: https://www.cnblogs.com/gutongxing/p/18364430

相关文章

  • P8735 蓝跳跳 题解
    Statement给出\(k,p,L\),数序列\(a\),满足如下条件:\(1\lea_i\lek\)\(\sum_ia_i=L\)\(\nexistsi,a_i\gep\landa_{i+1}\gep\)答案对\(20201114\)取模,\(p\lek\le1000,L\le10^{18}\).Solution30pts注意到可以dp,记\(f(i,0/1)\)为凑出\(i\)的方案......
  • 信息学奥赛一本通编程启蒙题解(3011~3015)
    前言Hello大家好,我是文宇.正文3011#include<iostream>usingnamespacestd;intmain(){ inta,b,s; a=880; b=500; s=a*b; cout<<s; return0;}注:没有输入的都可以直接输出.3012#include<iostream>usingnamespacestd;inta,b,t;intmain(){ a=10;b=20......
  • 信息学奥赛一本通编程启蒙题解(3021~3025)
    前言hello大家好,我是文宇。正文3021#include<iostream>usingnamespacestd;inta,b,c,d;intmain(){ cin>>a>>b>>c>>d; cout<<a+b+c+d; return0;}3022#include<bits/stdc++.h>usingnamespacestd;intmain(){ inta,b,c; ......
  • CF704E Iron Man 题解
    Description“铁人”yyb在玩游戏。在一个\(n\)个点的树上,yyb放置了\(m\)个鸡贼。每个鸡贼有四个整数参数\(t_i,c_i,v_i,u_i\),表示这个鸡贼会在\(t_i\)时刻出现在点\(v_i\),并以每时刻\(c_i\)条边的速度向\(u_i\)点匀速移动,到达\(u_i\)点时立刻消失。如果一个时刻......
  • esp-toothbrush 硬件原理图介绍
    前言个人邮箱:[email protected]项目视频链接硬件介绍电池管理(1)我们项目采用TP4056电源芯片给锂电池充电。因为我们采用的是3.7V锂电池,通过插上USB接口5V供电。通过查看TP4056芯片手册的典型应用可知,该芯片是满足要求的。(2)通过典型应用,我们基本可以知道......
  • 【题解】「NOIP2012」疫情控制
    https://www.luogu.com.cn/problem/P1084这道题难在贪心的思路,实现比较简单可以直接看代码。首先二分。现在转化为判定问题。可以用倍增求出每个军队最上面能到哪。结论1:我们一定不会把在除了根节点以外的军队往下移动。否则肯定不优。所以我们把能走到根节点的先存在一起......
  • [题解] [HNOI2016] 序列
    原题链接题面给定长度为$n$的序列:$a_1,a_2,\cdots,a_n$,记为\(a[1\colonn]\)。类似地,\(a[l\colonr]\)($1\leql\leqr\leqN$)是指序列:$a_{l},a_{l+1},\cdots,a_{r-1},a_r$。若\(1\leql\leqs\leqt\leqr\leqn\),则称$a[s\colont]$是$a[......
  • 2024杭电多校第十场 1002树上询问(题解)
    题意给一棵树,每个节点有一个权值,并且权值是一个排列。接下来有多次操作,每次操作要么是交换两个节点权值,要么是询问一个权值区间\([L,R]\),判断是否存在树上的一个路径,使得路径上的权值恰好都在这个区间里分析由于询问的是树上的一个路径,联想到了树上莫队中对路径的处理。这里......
  • 洛谷p1717题解
    题目描述话说发源于小朋友精心设计的游戏被电脑组的童鞋们藐杀之后非常不爽,为了表示安慰和鼓励,VIP999决定请他吃一次“年年大丰收”,为了表示诚意,他还决定亲自去钓鱼。但是,因为还要准备NOIP2013,z老师只给了他 H 个小时的空余时间,假设有 n 个鱼塘都在一条水平路边,从左......
  • 洛谷p2580题解
    题目背景XS中学化学竞赛组教练是一个酷爱炉石的人。他会一边搓炉石一边点名以至于有一天他连续点到了某个同学两次,然后正好被路过的校长发现了然后就是一顿欧拉欧拉欧拉(详情请见已结束比赛CON900)。题目描述这之后校长任命你为特派探员,每天记录他的点名。校长会提供化学竞......