企业官网建设流程全解析

【强校联盟】 CSP-S Round 0

题解链接：付费观看

总结一下本场比赛。
首先，T1相当爆，前后写了DP、greedy，然后在这两个中间，可能闪过了关于模拟的猜想，然后，不出意外地被自己否掉了。然后打的特殊性质挂了。
其次，关于T2，场上竟然觉得这个不单调！！！我吃饭的时候花了两秒钟想出来了。
然后，关于T3，我可能会吗？不过我直接打了特殊性质，然后，捆包里有一个n = 1 n=1n=1，把我送走了。
最后，关于T4，我应该搜一下，但是，直接思考正解了，然后设了一个假的状态直接起飞了，如果不捆包我是不是还能活下来呢？
😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭
也就是说，我读错了本场比赛中所有我提交拼正解代码的题。

A 胖头鱼战士（warrior）

原题链接：【ptyb2024】胖头鱼战士

分析

然后这是一个模拟，对，因为这就不是一个最优化问题！！！！！然后因为只与其中5 55个数相关，而且都很小。所以，我们记录一下，对于s ≤ 1 e 18 s\le 1e18s≤1e18的，可以找规律。

为什么不是最优化问题呢？很显然，因为题中指出了操作的优先级以及这个很傻很不智慧的决策。如下图：

正解

#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintMAXN=10,MAXM=15,MAXUA=35,MAXUB=20,MAXE=85;pair<int,int>dp[MAXN][MAXM][MAXUA][MAXUB][MAXE];structnode{intn,m,e,ua,ub,t=1,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);cin>>n>>s;a0.s=s;cin>>E>>m>>ta>>da>>ua;cin>>w>>eb>>tb>>db>>ub;for(inti=0;i<n;i++){cin>>t[i]>>d[i]>>e[i];}while(a0.s>0){autotmp=dp[a0.n][a0.m][a0.ua][a0.ub][a0.e];if(tmp.first&&a0.s>=tmp.second-a0.s){intval=a0.s/(tmp.second-a0.s);a1=a0;a1.t+=(a0.t-tmp.first)*val;a1.s-=(tmp.second-a0.s)*val;}elseif(a0.e==E&&!a0.ua){a1={0ll,m,0ll,ua,max(0ll,a0.ub-ta),a0.t+ta,a0.s-da};}elseif(!a0.ub){a1={0,a0.m,min(E,a0.e+eb),max(0ll,a0.ua-tb-w),ub,a0.t+tb,a0.s-db};}else{a1={(a0.n+1)%n,max(a0.m-1,0ll),min(E,a0.e+e[a0.n]),max(0ll,a0.ua-t[a0.n]),max(0ll,a0.ub-t[a0.n]),a0.t+t[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};a0=a1;}cout<<a0.t-1;return0;}

B 武器展示（weapon）

原题链接：【ptyb2024】武器展示

分析

盯出来二分答案，然后写。

正解

#include<bits/stdc++.h>usingnamespacestd;constintN=200005;intn,m,w;inta[N],mxa;intb[N],mxb;intchecka(intwid){intres=0;for(inti=1,k=0;i<=n;i++){if(a[i]>k){res++;k=wid;}k-=a[i];if(k<0)return-1;}returnres;}intcheckb(intwid){intres=0;for(inti=1,k=0;i<=m;i++){if(b[i]>k){res++;k=wid;}k-=b[i];if(k<0)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);cin>>n>>m>>w;for(inti=1;i<=n;i++){cin>>a[i];mxa=max(mxa,a[i]);}for(inti=1;i<=m;i++){cin>>b[i];mxb=max(mxb,b[i]);}intl=mxa,r=w-mxb;intans=0x3f3f3f3f;while(l<=r){intmid=(l+r)>>1;inttmp1=checka(mid);inttmp2=checkb(w-mid);ans=min(ans,max(tmp1,tmp2));if(tmp1>=tmp2)l=mid+1;elser=mid-1;}cout<<ans;return0;}

C 角色配队（team）

原题链接：【ptyb2024】角色配队

分析

对的，偏序，然后，按照a i a_iai​排序，则寻找b i b_ibi​的最长上升子序列。为了防止出锅，我们对于a i a_iai​相同的，按照b i b_ibi​降序排序。
然后我们记录最长上升子序列，以及以每个位置开头或结尾的最长上升子序列的个数，然后拼一下。那个树状数组做一下，结束了。

不是，我打了两个Subtask，结果都被n = 1 n=1n=1卡飞了😭
可以总结为，对于存在偏序关系的题目，我们先把一维排序，然后按照另外一维做。

正解

#include<bits/stdc++.h>usingnamespacestd;constintN=200005;intn;structnode{inta,b,id;}inp[N];boolcmp(node x,node y){if(x.a==y.a)returnx.b>y.b;returnx.a<y.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);cin>>n;for(inti=1;i<=n;i++){cin>>inp[i].a>>inp[i].b;inp[i].id=i;}sort(inp+1,inp+n+1,cmp);memset(len,0x3f,sizeof(len));intmx=0xc0c0c0c0c0;for(inti=1;i<=n;i++){pre[i]=lower_bound(len,len+n+1,inp[i].b)-len;len[pre[i]]=inp[i].b;mx=max(mx,pre[i]);}memset(len,0,sizeof(len));len[0]=0x3f3f3f3f;for(inti=n;i>=1;i--){suf[i]=lower_bound(len,len+n+1,inp[i].b,greater<int>())-len;len[suf[i]]=inp[i].b;if(pre[i]+suf[i]==mx+1)cnt[pre[i]]++;}for(inti=1;i<=n;i++){if(pre[i]+suf[i]==mx+1&&cnt[pre[i]]==1){c++;ans[inp[i].id]=true;}}cout<<c<<'\n';for(inti=1;i<=n;i++){if(ans[i])cout<<i<<" ";}}

D 深境方块（cube）

原题链接：【ptyb2024】深境方块

分析

不补了/ll