【强校联盟】 CSP-S Round 0题解链接付费观看总结一下本场比赛。首先T1相当爆前后写了DP、greedy然后在这两个中间可能闪过了关于模拟的猜想然后不出意外地被自己否掉了。然后打的特殊性质挂了。其次关于T2场上竟然觉得这个不单调我吃饭的时候花了两秒钟想出来了。然后关于T3我可能会吗不过我直接打了特殊性质然后捆包里有一个n 1 n1n1把我送走了。最后关于T4我应该搜一下但是直接思考正解了然后设了一个假的状态直接起飞了如果不捆包我是不是还能活下来呢也就是说我读错了本场比赛中所有我提交拼正解代码的题。A 胖头鱼战士warrior原题链接【ptyb2024】胖头鱼战士分析然后这是一个模拟对因为这就不是一个最优化问题然后因为只与其中5 55个数相关而且都很小。所以我们记录一下对于s ≤ 1 e 18 s\le 1e18s≤1e18的可以找规律。为什么不是最优化问题呢很显然因为题中指出了操作的优先级以及这个很傻很不智慧的决策。如下图正解#includebits/stdc.h#defineintlonglongusingnamespacestd;constintMAXN10,MAXM15,MAXUA35,MAXUB20,MAXE85;pairint,intdp[MAXN][MAXM][MAXUA][MAXUB][MAXE];structnode{intn,m,e,ua,ub,t1,s;}a0,a1;intn,s;intE,m,ta,da,ua;intw,eb,tb,db,ub;intt[MAXN],d[MAXN],e[MAXN];signedmain(){freopen(warrior.in,r,stdin);freopen(warrior.out,w,stdout);cinns;a0.ss;cinEmtadaua;cinwebtbdbub;for(inti0;in;i){cint[i]d[i]e[i];}while(a0.s0){autotmpdp[a0.n][a0.m][a0.ua][a0.ub][a0.e];if(tmp.firsta0.stmp.second-a0.s){intvala0.s/(tmp.second-a0.s);a1a0;a1.t(a0.t-tmp.first)*val;a1.s-(tmp.second-a0.s)*val;}elseif(a0.eE!a0.ua){a1{0ll,m,0ll,ua,max(0ll,a0.ub-ta),a0.tta,a0.s-da};}elseif(!a0.ub){a1{0,a0.m,min(E,a0.eeb),max(0ll,a0.ua-tb-w),ub,a0.ttb,a0.s-db};}else{a1{(a0.n1)%n,max(a0.m-1,0ll),min(E,a0.ee[a0.n]),max(0ll,a0.ua-t[a0.n]),max(0ll,a0.ub-t[a0.n]),a0.tt[a0.n],a0.s-d[a0.n]*(a0.m?2:1)};}dp[a0.n][a0.m][a0.ua][a0.ub][a0.e]{a0.t,a0.s};a0a1;}couta0.t-1;return0;}B 武器展示weapon原题链接【ptyb2024】武器展示分析盯出来二分答案然后写。正解#includebits/stdc.husingnamespacestd;constintN200005;intn,m,w;inta[N],mxa;intb[N],mxb;intchecka(intwid){intres0;for(inti1,k0;in;i){if(a[i]k){res;kwid;}k-a[i];if(k0)return-1;}returnres;}intcheckb(intwid){intres0;for(inti1,k0;im;i){if(b[i]k){res;kwid;}k-b[i];if(k0)return-1;}returnres;}signedmain(){freopen(weapon.in,r,stdin);freopen(weapon.out,w,stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnmw;for(inti1;in;i){cina[i];mxamax(mxa,a[i]);}for(inti1;im;i){cinb[i];mxbmax(mxb,b[i]);}intlmxa,rw-mxb;intans0x3f3f3f3f;while(lr){intmid(lr)1;inttmp1checka(mid);inttmp2checkb(w-mid);ansmin(ans,max(tmp1,tmp2));if(tmp1tmp2)lmid1;elsermid-1;}coutans;return0;}C 角色配队team原题链接【ptyb2024】角色配队分析对的偏序然后按照a i a_iai排序则寻找b i b_ibi的最长上升子序列。为了防止出锅我们对于a i a_iai相同的按照b i b_ibi降序排序。然后我们记录最长上升子序列以及以每个位置开头或结尾的最长上升子序列的个数然后拼一下。那个树状数组做一下结束了。不是我打了两个Subtask结果都被n 1 n1n1卡飞了可以总结为对于存在偏序关系的题目我们先把一维排序然后按照另外一维做。正解#includebits/stdc.husingnamespacestd;constintN200005;intn;structnode{inta,b,id;}inp[N];boolcmp(node x,node y){if(x.ay.a)returnx.by.b;returnx.ay.a;}intpre[N],suf[N],len[N];intcnt[N];boolans[N];intc;signedmain(){// freopen(team.in, r, stdin);// freopen(team.out, w, stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;for(inti1;in;i){cininp[i].ainp[i].b;inp[i].idi;}sort(inp1,inpn1,cmp);memset(len,0x3f,sizeof(len));intmx0xc0c0c0c0c0;for(inti1;in;i){pre[i]lower_bound(len,lenn1,inp[i].b)-len;len[pre[i]]inp[i].b;mxmax(mx,pre[i]);}memset(len,0,sizeof(len));len[0]0x3f3f3f3f;for(intin;i1;i--){suf[i]lower_bound(len,lenn1,inp[i].b,greaterint())-len;len[suf[i]]inp[i].b;if(pre[i]suf[i]mx1)cnt[pre[i]];}for(inti1;in;i){if(pre[i]suf[i]mx1cnt[pre[i]]1){c;ans[inp[i].id]true;}}coutc\n;for(inti1;in;i){if(ans[i])couti ;}}D 深境方块cube原题链接【ptyb2024】深境方块分析不补了/ll
【强校联盟】 CSP-S Round 0
【强校联盟】 CSP-S Round 0题解链接付费观看总结一下本场比赛。首先T1相当爆前后写了DP、greedy然后在这两个中间可能闪过了关于模拟的猜想然后不出意外地被自己否掉了。然后打的特殊性质挂了。其次关于T2场上竟然觉得这个不单调我吃饭的时候花了两秒钟想出来了。然后关于T3我可能会吗不过我直接打了特殊性质然后捆包里有一个n 1 n1n1把我送走了。最后关于T4我应该搜一下但是直接思考正解了然后设了一个假的状态直接起飞了如果不捆包我是不是还能活下来呢也就是说我读错了本场比赛中所有我提交拼正解代码的题。A 胖头鱼战士warrior原题链接【ptyb2024】胖头鱼战士分析然后这是一个模拟对因为这就不是一个最优化问题然后因为只与其中5 55个数相关而且都很小。所以我们记录一下对于s ≤ 1 e 18 s\le 1e18s≤1e18的可以找规律。为什么不是最优化问题呢很显然因为题中指出了操作的优先级以及这个很傻很不智慧的决策。如下图正解#includebits/stdc.h#defineintlonglongusingnamespacestd;constintMAXN10,MAXM15,MAXUA35,MAXUB20,MAXE85;pairint,intdp[MAXN][MAXM][MAXUA][MAXUB][MAXE];structnode{intn,m,e,ua,ub,t1,s;}a0,a1;intn,s;intE,m,ta,da,ua;intw,eb,tb,db,ub;intt[MAXN],d[MAXN],e[MAXN];signedmain(){freopen(warrior.in,r,stdin);freopen(warrior.out,w,stdout);cinns;a0.ss;cinEmtadaua;cinwebtbdbub;for(inti0;in;i){cint[i]d[i]e[i];}while(a0.s0){autotmpdp[a0.n][a0.m][a0.ua][a0.ub][a0.e];if(tmp.firsta0.stmp.second-a0.s){intvala0.s/(tmp.second-a0.s);a1a0;a1.t(a0.t-tmp.first)*val;a1.s-(tmp.second-a0.s)*val;}elseif(a0.eE!a0.ua){a1{0ll,m,0ll,ua,max(0ll,a0.ub-ta),a0.tta,a0.s-da};}elseif(!a0.ub){a1{0,a0.m,min(E,a0.eeb),max(0ll,a0.ua-tb-w),ub,a0.ttb,a0.s-db};}else{a1{(a0.n1)%n,max(a0.m-1,0ll),min(E,a0.ee[a0.n]),max(0ll,a0.ua-t[a0.n]),max(0ll,a0.ub-t[a0.n]),a0.tt[a0.n],a0.s-d[a0.n]*(a0.m?2:1)};}dp[a0.n][a0.m][a0.ua][a0.ub][a0.e]{a0.t,a0.s};a0a1;}couta0.t-1;return0;}B 武器展示weapon原题链接【ptyb2024】武器展示分析盯出来二分答案然后写。正解#includebits/stdc.husingnamespacestd;constintN200005;intn,m,w;inta[N],mxa;intb[N],mxb;intchecka(intwid){intres0;for(inti1,k0;in;i){if(a[i]k){res;kwid;}k-a[i];if(k0)return-1;}returnres;}intcheckb(intwid){intres0;for(inti1,k0;im;i){if(b[i]k){res;kwid;}k-b[i];if(k0)return-1;}returnres;}signedmain(){freopen(weapon.in,r,stdin);freopen(weapon.out,w,stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnmw;for(inti1;in;i){cina[i];mxamax(mxa,a[i]);}for(inti1;im;i){cinb[i];mxbmax(mxb,b[i]);}intlmxa,rw-mxb;intans0x3f3f3f3f;while(lr){intmid(lr)1;inttmp1checka(mid);inttmp2checkb(w-mid);ansmin(ans,max(tmp1,tmp2));if(tmp1tmp2)lmid1;elsermid-1;}coutans;return0;}C 角色配队team原题链接【ptyb2024】角色配队分析对的偏序然后按照a i a_iai排序则寻找b i b_ibi的最长上升子序列。为了防止出锅我们对于a i a_iai相同的按照b i b_ibi降序排序。然后我们记录最长上升子序列以及以每个位置开头或结尾的最长上升子序列的个数然后拼一下。那个树状数组做一下结束了。不是我打了两个Subtask结果都被n 1 n1n1卡飞了可以总结为对于存在偏序关系的题目我们先把一维排序然后按照另外一维做。正解#includebits/stdc.husingnamespacestd;constintN200005;intn;structnode{inta,b,id;}inp[N];boolcmp(node x,node y){if(x.ay.a)returnx.by.b;returnx.ay.a;}intpre[N],suf[N],len[N];intcnt[N];boolans[N];intc;signedmain(){// freopen(team.in, r, stdin);// freopen(team.out, w, stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;for(inti1;in;i){cininp[i].ainp[i].b;inp[i].idi;}sort(inp1,inpn1,cmp);memset(len,0x3f,sizeof(len));intmx0xc0c0c0c0c0;for(inti1;in;i){pre[i]lower_bound(len,lenn1,inp[i].b)-len;len[pre[i]]inp[i].b;mxmax(mx,pre[i]);}memset(len,0,sizeof(len));len[0]0x3f3f3f3f;for(intin;i1;i--){suf[i]lower_bound(len,lenn1,inp[i].b,greaterint())-len;len[suf[i]]inp[i].b;if(pre[i]suf[i]mx1)cnt[pre[i]];}for(inti1;in;i){if(pre[i]suf[i]mx1cnt[pre[i]]1){c;ans[inp[i].id]true;}}coutc\n;for(inti1;in;i){if(ans[i])couti ;}}D 深境方块cube原题链接【ptyb2024】深境方块分析不补了/ll
