2022csp复现赛 P8816 [CSP-J 2022] 上升点列 首先很容易想到对所有的点进行排序。 设 dp_{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; }`
2022csp复现赛
笔记