2022csp复现赛

2025年10月8日 ooliver OI

2022csp复现赛

P8816 [CSP-J 2022] 上升点列

首先很容易想到对所有的点进行排序。设 $d p_{i, l}$ 表示以第 $i$ 个点为结尾，添加了 $l$ 个点的点序列最大长度。考虑从所有的 $j(0

#include
using namespace std;
#define int long long
const int N=505;
struct node{
	int x,y;
}a[N];
int n,k,ans=1;
int dp[N][N];
bool cmp(node b,node c){
	if(b.x==c.x) return b.y>n>>k;
	for(int i=1;i>a[i].x>>a[i].y;
	sort(a+1,a+1+n,cmp);
	memset(dp[0],0,sizeof dp[0]);
	for(int i=1;i=0&&l-sum

`#include
using namespace std;
#define int long long
const int N=505;
struct node{
	int x,y;
}a[N];
int n,k,ans=1;
int dp[N][N];
bool cmp(node b,node c){
	if(b.x==c.x) return b.yc.y;
	else return b.xc.x;
}
signed main(){
	memset(dp,-1,sizeof dp);
	cin>>n>>k;
	for(int i=1;i>a[i].x>>a[i].y;
	sort(a+1,a+1+n,cmp);
	memset(dp[0],0,sizeof dp[0]);
	for(int i=1;i
		for(int l=0;ldp[i][l]=l+1,ans=max(ans,dp[i][l]+(k-l));
		for(int j=1;j
			for(int l=0;l
				if(a[i].xa[j].x||a[i].ya[j].y) continue;
				int sum=(a[i].x-a[j].x+a[i].y-a[j].y-1);
				if(l-sum>=0&&l-sumdp[i][l]=max(dp[i][l],dp[j][l-sum]+sum+1);
				ans=max(ans,dp[i][l]+(k-l));
			}
		}
	}
	cout
	return 0;
} `

P8815 [CSP-J 2022] 逻辑表达式

添加一个短路标记，如果标记表示当前的被短路了，直接无视表达式的值，如果没有被短路，可以发现答案一定取决于当前值，再判断会不会短路后面。代码：

#include
using namespace std;
string s;
int ans,ans1,ans2,y;
int main(){
	cin>>s;
	for(int i=0;i

`#include
using namespace std;
string s;
int ans,ans1,ans2,y;
int main(){
	cin>>s;
	for(int i=0;is.size();i++){
		if(y){
			if(s[i]=='('){ 
				int x=1;
				while(x){
					i++;
					if(s[i]=='(') x++;
					if(s[i]==')') x--;
				}
			}
			else if(y==1&&s[i]=='|'||s[i]==')')	y=0;
			else if(y==1&&s[i]=='&') ans1++;
			else if(y==2&&s[i]=='|') ans2++;
		}
		else{
			if(s[i]=='1') ans=1;
			if(s[i]=='0') ans=0;
			if(s[i]=='&'&&ans==0) y=1,ans1++;
			if(s[i]=='|'&&ans==1) y=2,ans2++;
		}
	}
	cout"\n"" "
	return 0;
}
`

P8818 [CSP-S 2022] 策略游戏

使用线段树维护两个数组的：区间最大值，最小值，最大负数，最小正数，是否有 0。然后贪心出答案即可，贪心思路看注释。代码：

#include
using namespace std;
#define int long long
#define N (int)1e5+5
#define lc p0) tr[1][p].mnz=a[l];
            else tr[1][p].mnz=INF;
            if(a[l]==0) tr[1][p].h0=1;
            else tr[1][p].h0=0;
        } 
        else{
            tr[0][p].mx=tr[0][p].mn=b[l];
            if(b[l]0) tr[0][p].mnz=b[l];
            else tr[0][p].mnz=INF;
            if(b[l]==0) tr[0][p].h0=1;
            else tr[0][p].h0=0;
        } 
        return;
    }
    int mid=l+r>>1;
    build(id,lc,l,mid);
    build(id,rc,mid+1,r);
    pushup(id,p);
} 
node query(int id,int p,int l,int r){
    if(tr[id][p].l>=l&&tr[id][p].r>1;
    node res;
    res.mx=-INF,res.mn=INF,res.mxf=-INF,res.mnz=INF,res.h0=0;
    if(lmid){
        node right=query(id,rc,l,r);
        res.mn=min(res.mn,right.mn);
        res.mx=max(res.mx,right.mx);
        res.mxf=max(res.mxf,right.mxf);
        res.mnz=min(res.mnz,right.mnz);
        res.h0|=right.h0;
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i>a[i];
    for(int i=1;i>b[i];
    build(1,1,1,n);
    build(0,1,1,m);
    while(q--){
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        node n1=query(1,1,l1,r1),n2=query(0,1,l2,r2);
        int mx1=n1.mx,mn1=n1.mn,mxf1=n1.mxf,mnz1=n1.mnz,h01=n1.h0;
        int mx2=n2.mx,mn2=n2.mn,mxf2=n2.mxf,mnz2=n2.mnz,h02=n2.h0;
        if(mn2>=0){//B区间全为非负数
            if(mx1>=0) cout=0) cout

`#include
using namespace std;
#define int long long
#define N (int)1e5+5
#define lc p
#define rc p
const int INF = 1e18;
int n,m,q;
int a[N],b[N];
struct tree{
    int l,r;
    int mx,mn,mxf=-INF,mnz=INF,h0=0;
}tr[2][N2];
struct node{
    int mx,mn,mxf,mnz,h0;
};
void pushup(int id,int p){
    tr[id][p].mx=max(tr[id][lc].mx,tr[id][rc].mx);
    tr[id][p].mn=min(tr[id][lc].mn,tr[id][rc].mn);
    tr[id][p].mxf=max(tr[id][lc].mxf,tr[id][rc].mxf);
    tr[id][p].mnz=min(tr[id][lc].mnz,tr[id][rc].mnz);
    tr[id][p].h0=tr[id][lc].h0|tr[id][rc].h0;
}
void build(int id,int p,int l,int r){
    tr[id][p].l=l,tr[id][p].r=r;
    if(l==r){
        if(id==1){
            tr[1][p].mx=tr[1][p].mn=a[l];
            if(a[l]0) tr[1][p].mxf=a[l];
            else tr[1][p].mxf=-INF;
            if(a[l]>0) tr[1][p].mnz=a[l];
            else tr[1][p].mnz=INF;
            if(a[l]==0) tr[1][p].h0=1;
            else tr[1][p].h0=0;
        } 
        else{
            tr[0][p].mx=tr[0][p].mn=b[l];
            if(b[l]0) tr[0][p].mxf=b[l];
            else tr[0][p].mxf=-INF;
            if(b[l]>0) tr[0][p].mnz=b[l];
            else tr[0][p].mnz=INF;
            if(b[l]==0) tr[0][p].h0=1;
            else tr[0][p].h0=0;
        } 
        return;
    }
    int mid=l+r>>1;
    build(id,lc,l,mid);
    build(id,rc,mid+1,r);
    pushup(id,p);
} 
node query(int id,int p,int l,int r){
    if(tr[id][p].l>=l&&tr[id][p].r
        return (node){tr[id][p].mx,tr[id][p].mn,tr[id][p].mxf,tr[id][p].mnz,tr[id][p].h0};
    }
    int mid=tr[id][p].l+tr[id][p].r>>1;
    node res;
    res.mx=-INF,res.mn=INF,res.mxf=-INF,res.mnz=INF,res.h0=0;
    if(l
        node left=query(id,lc,l,r);
        res.mn=min(res.mn,left.mn);
        res.mx=max(res.mx,left.mx);
        res.mxf=max(res.mxf,left.mxf);
        res.mnz=min(res.mnz,left.mnz);
        res.h0|=left.h0;
    }
    if(r>mid){
        node right=query(id,rc,l,r);
        res.mn=min(res.mn,right.mn);
        res.mx=max(res.mx,right.mx);
        res.mxf=max(res.mxf,right.mxf);
        res.mnz=min(res.mnz,right.mnz);
        res.h0|=right.h0;
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i>a[i];
    for(int i=1;i>b[i];
    build(1,1,1,n);
    build(0,1,1,m);
    while(q--){
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        node n1=query(1,1,l1,r1),n2=query(0,1,l2,r2);
        int mx1=n1.mx,mn1=n1.mn,mxf1=n1.mxf,mnz1=n1.mnz,h01=n1.h0;
        int mx2=n2.mx,mn2=n2.mn,mxf2=n2.mxf,mnz2=n2.mnz,h02=n2.h0;
        if(mn2>=0){//B区间全为非负数
            if(mx1>=0) cout//A有非负数，选最大的非负数乘B的最小非负数
            else cout//A全为负数，选最大的负数乘B的最大非负数
        }
        else if(mx20){//B区间全为非正数
            if(mn10) cout//A有非正数，选最小的非正数乘B的最大非正数
            else cout//A全为正数，选最小的正数乘B的最小非正数
        }
        else{//B区间有正有负
            if(h01) cout0;//A有0，直接选0
            else if(mx10) cout//A全为负数，选最大的负数乘B的最大非正数
            else if(mn1>=0) cout//A全为正数，选最小的正数乘B的最小非正数
            else coutmax(mxf1*mx2,mnz1*mn2);//A有正有负，比较两种策略
        }
        cout
    }
    return 0;
}`