思路
因为前面不允许出现比这次的替换的值还要大的情况,所以如果我们知道下标 \(i,j\) 满足 \(i<j\) 且 \(V_i>V_j\) 的话,我们就必须把它们两次修改分开。具体地:
- 若 \(P_i<P_j\):
此时,我们只能将 \([1,P_i]\) 的值设为 \(V_i\),将 \([P_j,n]\) 的值设为 \(V_j\)。 - 若 \(P_i>P_j\):
此时,我们只能将 \([P_i,n]\) 的值设为 \(V_i\),将 \([1,P_j]\) 的值设为 \(V_j\)。 - 若 \(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
构造
Atcoder
、ARC