2022csp复现赛

用户头像 发布于 2025-10-08 281 次阅读 OI

2022csp复现赛

P8816 [CSP-J 2022] 上升点列

首先很容易想到对所有的点进行排序。
设 $dp_{i,l}$ 表示以第 $i$ 个点为结尾，添加了 $l$ 个点的点序列最大长度。
考虑从所有的 $j(0<=j<i)$ 转移过来，
先判断是否满足单调性，
再判断要满足题意的单调性需要在两个点里面添加多少个点，
判断 $l$ 是否够用，转移即可。
代码：

#include<bits/stdc++.h>
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<c.y;
	else return b.x<=c.x;
}
signed main(){
	memset(dp,-1,sizeof dp);
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>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<=n;i++){
		for(int l=0;l<=k;l++) dp[i][l]=l+1,ans=max(ans,dp[i][l]+(k-l));
		for(int j=1;j<i;j++){
			for(int l=0;l<=k;l++){
				if(a[i].x<a[j].x||a[i].y<a[j].y) continue;
				int sum=(a[i].x-a[j].x+a[i].y-a[j].y-1);
				if(l-sum>=0&&l-sum<=k) dp[i][l]=max(dp[i][l],dp[j][l-sum]+sum+1);
				ans=max(ans,dp[i][l]+(k-l));
			}
		}
	}
	cout<<ans;
	return 0;
}

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

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

#include<bits/stdc++.h>
using namespace std;
string s;
int ans,ans1,ans2,y;
int main(){
	cin>>s;
	for(int i=0;i<s.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<<ans<<"\n"<<ans1<<" "<<ans2;
	return 0;
}

P8818 [CSP-S 2022] 策略游戏

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

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N (int)1e5+5
#define lc p<<1
#define rc p<<1|1
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][N<<2];
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<=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<=mid){
        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<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>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<<mx1*mn2;//A有非负数，选最大的非负数乘B的最小非负数
            else cout<<mx1*mx2;//A全为负数，选最大的负数乘B的最大非负数
        }
        else if(mx2<=0){//B区间全为非正数
            if(mn1<=0) cout<<mn1*mx2;//A有非正数，选最小的非正数乘B的最大非正数
            else cout<<mn1*mn2;//A全为正数，选最小的正数乘B的最小非正数
        }
        else{//B区间有正有负
            if(h01) cout<<0;//A有0，直接选0
            else if(mx1<=0) cout<<mx1*mx2;//A全为负数，选最大的负数乘B的最大非正数
            else if(mn1>=0) cout<<mn1*mn2;//A全为正数，选最小的正数乘B的最小非正数
            else cout<<max(mxf1*mx2,mnz1*mn2);//A有正有负，比较两种策略
        }
        cout<<endl;
    }
    return 0;
}