NOIP2024（欢乐）加赛3
\(T1\) CF2033B Sakurako and Water \(100pts\)
-
枚举主对角线取 \(\max\) 即可。
点击查看代码
ll a[510][510]; int main() { ll t,n,ans=0,maxx,i,j,k,h; cin>>t; for(h=1;h<=t;h++) { cin>>n; ans=0; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { cin>>a[i][j]; } } for(k=-n+1;k<=n+1;k++) { maxx=0; for(i=1,j=i+k;i<=n;i++,j++) { if(i<=n&&1<=j&&j<=n&&a[i][j]<0) { maxx=max(maxx,-a[i][j]); } } ans+=maxx; } cout<<ans<<endl; } return 0; }
\(T2\) CF2025B Binomial Coefficients, Kind Of \(100pts\)
-
观察样例加打表可知， \(2^{[k \ne n] \times k}\) 即为所求。
- 已知递推式 \(f_{i,j}=\begin{cases} 1 & j=0 \lor j=n \\ f_{n,k-1}+f_{n-1,k-1} & j \in [1,n) \end{cases}\) ，省去 \(j=n\) 的状态后有 \(f_{i,j}=f_{i+1,j}\) 。
- \(f_{i,j}\) 能更新到的值只有 \(\begin{cases} f_{i,j+1}=f_{i+1,j+1}=2f_{i,j} \end{cases}\) ，故 \(2^{[k \ne n] \times k}\) 即为所求。
点击查看代码
const ll p=1000000007; ll n[100010],m[100010],C[1010][1010]; ll qpow(ll a,ll b,ll p) { ll ans=1; while(b) { if(b&1) { ans=ans*a%p; } b>>=1; a=a*a%p; } return ans; } int main() { ll t,i; cin>>t; for(i=1;i<=t;i++) { cin>>n[i]; } for(i=1;i<=t;i++) { cin>>m[i]; if(m[i]==n[i]) { cout<<1<<endl; } else { cout<<qpow(2,m[i],p)<<endl; } } return 0; }
\(T3\) CF2030D QED's Favorite Permutation \(100pts\)
-
对于移动，我们可以无脑进行交换来保证移动，然后将中途交换的位置再交换回去。
-
通过手摸不难发现， \(p_{i}\) 能移动到 \(i\) 当且仅当 \(s_{\min(i,p_{i}) \sim \max(i,p_{i})}\) 中不含有
LR子串。 -
反向考虑，即
LR子串不被上述区间包含，差分判断即可。点击查看代码
ll a[200010],d[200010]; char s[200010]; int main() { ll t,n,m,x,sum,i,j; cin>>t; for(j=1;j<=t;j++) { cin>>n>>m; sum=0; for(i=1;i<=n;i++) { cin>>a[i]; d[min(a[i],i)]++; d[max(a[i],i)]--; } for(i=1;i<=n;i++) { d[i]+=d[i-1]; } cin>>(s+1); for(i=1;i<=n-1;i++) { if(s[i]=='L'&&s[i+1]=='R') { sum+=(d[i]!=0); } } for(i=1;i<=m;i++) { cin>>x; if(s[x]=='L') { s[x]='R'; if(x+1<=n&&s[x+1]=='R') { sum-=(d[x]!=0); } if(x-1>=1&&s[x-1]=='L') { sum+=(d[x-1]!=0); } } else { s[x]='L'; if(x+1<=n&&s[x+1]=='R') { sum+=(d[x]!=0); } if(x-1>=1&&s[x-1]=='L') { sum-=(d[x-1]!=0); } } if(sum!=0) { cout<<"No"<<endl; } else { cout<<"Yes"<<endl; } } for(i=1;i<=n;i++) { d[i]=0; } } return 0; }
\(T4\) CF2025E Card Game \(10pts\)
- 部分分
- \(10pts\) ：输出样例。
\(T5\) CF1967D Long Way to be Non-decreasing \(16pts\)
-
部分分
- \(16pts\)
- 考虑从 \(i\) 向 \(b_{i}\) 连一条有向边，那么 \(i\) 能到达的点就是经过若干次操作后可以成为的值。
- 答案上界显然为 \(m\) ，考虑二分答案。
- \(check\) 时选令 \(a_{i}\) 走到 \(mid\) 步能到达的范围内不小于 \(a_{i-1}'\) 的数 \(a_{i}\) ，主席树空间开不下遂写了暴力。
点击查看代码
int a[1000010],b[1000010],vis[1000010],tot=0; vector<int>e[1000010],s[1000010]; void dfs(int x,int rt) { s[rt].push_back(x); vis[x]=tot; for(int i=0;i<e[x].size();i++) { if(vis[e[x][i]]!=tot) { dfs(e[x][i],rt); } } } bool check(int mid,int n,int m) { int last=0,minn; for(int i=1;i<=n;i++) { minn=0x7f7f7f7f; for(int j=0;j<s[a[i]].size()&&j<=mid;j++) { if(s[a[i]][j]>=last) { minn=min(minn,s[a[i]][j]); } } last=minn; if(last==0x7f7f7f7f) { return false; } } return true; } int main() { int testcase,n,m,l,r,mid,ans,i,j; scanf("%d",&testcase); for(j=1;j<=testcase;j++) { scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { e[i].clear(); s[i].clear(); vis[i]=0; } for(i=1;i<=n;i++) { cin>>a[i]; } for(i=1;i<=m;i++) { cin>>b[i]; e[i].push_back(b[i]); } for(i=1;i<=m;i++) { tot++; dfs(i,i); } l=0; r=m; ans=-1; while(l<=r) { mid=(l+r)/2; if(check(mid,n,m)==true) { ans=mid; r=mid-1; } else { l=mid+1; } } printf("%d\n",ans); } return 0; } - \(16pts\)
-
正解
\(T6\) CF2023D Many Games \(9pts\)
-
部分分
- \(7pts\) ：爆搜。
- \(9pts\) ：背包。
点击查看代码
总结
- \(T4\) 的部分分没来得及写。
- \(T5\) 以为最终连成的一个环，破环为链后分前后缀考虑，然后就口胡了个假的势能线段树维护在线二维数点。基本全场都在写 \(T5\) 。