暑假集训CSP提高模拟24
\(T1\) P268.与和 \(100pts\)
-
\(x,y\) 下界显然为 \(a\) ，不妨让 \(y=a,x=s-a\) 然后进行 \(check\) 。正确性由下一种做法可以进一步推导。
点击查看代码
int main() { freopen("and.in","r",stdin); freopen("and.out","w",stdout); ll t,a,s,i; scanf("%lld",&t); for(i=1;i<=t;i++) { scanf("%lld%lld",&a,&s); if(2*a<=s&&((s-a)&a)==a) { printf("Yes\n"); } else { printf("No\n"); } } fclose(stdin); fclose(stdout); return 0; } -
一个更通用且容易证明的方法是 \(s-2a\) 在二进制表示下 \(1\) 的位置只能出现 \(a\) 在二进制表示下 \(0\) 的位置上，以此来进行 \(check\) 。
- \(1\) 的位置不妨都让 \(x\) 这一位为 \(1\) ，接着便有了上面第一种做法。
点击查看代码
int main() { freopen("and.in","r",stdin); freopen("and.out","w",stdout); ll t,a,s,i; scanf("%lld",&t); for(i=1;i<=t;i++) { scanf("%lld%lld",&a,&s); if(2*a<=s&&((s-2*a)&(~a))==(s-2*a)) { printf("Yes\n"); } else { printf("No\n"); } } fclose(stdin); fclose(stdout); return 0; }
\(T2\) P239.函数 \(10pts\)
-
部分分
-
\(30pts\) ：状压。
点击查看代码
ll a[200010],b[200010],f[2][(1<<20)+10]; int main() { freopen("func.in","r",stdin); freopen("func.out","w",stdout); ll n,k,maxx,ans=0,s,i,j; cin>>n>>k; for(i=1;i<=n;i++) { cin>>a[i]>>b[i]; } for(s=0;s<=(1<<n)-1;s++) { f[0][s]=1; } for(i=1;i<=k;i++) { for(s=0;s<=(1<<n)-1;s++) { maxx=0; for(j=1;j<=n;j++) { if((s>>(j-1))&1) { maxx=max(maxx,a[j]*f[(i-1)&1][s^(1<<(j-1))]+b[j]); } } f[i&1][s]=maxx; } } for(s=0;s<=(1<<n)-1;s++) { ans=max(ans,f[k&1][s]); } cout<<ans<<endl; fclose(stdin); fclose(stdout); return 0; }
-
-
正解
- 观察到 \(DP\) 式子很容易想，但选择顺序貌似很难处理。
- 考虑推式子，假设 \(f_{j}(f_{i}(x))>f_{i}(f_{j}(x))\) ，式子展开后有 \(a_{j}b_{i}+b_{j}>a_{i}b_{j}+b_{i}\) ，移项后有 \(\dfrac{b_{i}}{a_{i}-i}>\dfrac{b_{j}}{a_{j}-i}\) 。
- 将 \(\{ f \}\) 按 \(\dfrac{b}{a-1}\) 降序排序，实际排序时将除法转成乘法。
- 设 \(f_{i,j}\) 表示处理到第 \(i\) 个数时选择了 \(j\) 个数的最大值，状态转移方程为 \(f_{i,j}=\max(f_{i-1,j},a_{i}f_{i-1,j-1}+b_{i})\) ，边界为 \(f_{0,0}=1\) 。
- 最终有 \(f_{n,k}\) 即为所求。
点击查看代码
struct node { ll a,b; }c[200010]; ll f[200010][15]; bool cmp(node a,node b) { return a.b*(b.a-1)>b.b*(a.a-1); } int main() { ll n,k,i,j; cin>>n>>k; for(i=1;i<=n;i++) { cin>>c[i].a>>c[i].b; } sort(c+1,c+1+n,cmp); f[0][0]=1; for(i=1;i<=n;i++) { for(j=0;j<=k;j++) { f[i][j]=f[i-1][j]; if(j-1>=0) { f[i][j]=max(f[i][j],c[i].a*f[i-1][j-1]+c[i].b); } } } cout<<f[n][k]<<endl; return 0; }
\(T3\) P238.袋鼠 \(6pts\)
- 原题： luogu P5999 [CEOI2016] kangaroo
- 部分分
-
\(6pts\) ：爆搜。
点击查看代码
const ll p=1000000007; ll vis[2010],ans=0; void dfs(ll now,ll prev,ll sum,ll t,ll n) { if(now==t) { ans=(ans+(sum==n))%p; } else { if(prev<now) { for(ll i=1;i<now;i++) { if(vis[i]==0) { vis[i]=1; dfs(i,now,sum+1,t,n); vis[i]=0; } } } else { for(ll i=now+1;i<=n;i++) { if(vis[i]==0) { vis[i]=1; dfs(i,now,sum+1,t,n); vis[i]=0; } } } } } int main() { freopen("kang.in","r",stdin); freopen("kang.out","w",stdout); ll n,s,t,i; cin>>n>>s>>t; for(i=1;i<=n;i++) { if(i!=s) { memset(vis,0,sizeof(vis)); vis[i]=vis[s]=1; dfs(i,s,2,t,n); } } cout<<ans<<endl; fclose(stdin); fclose(stdout); return 0; }
-
- 正解
\(T4\) P240.最短路 \(8pts\)
- 原题： CF464E The Classic Problem
- 部分分
-
\(1 \sim 2\) ：直接跑最短路，最后再取模。
点击查看代码
const ll p=1000000007; struct node { ll nxt,to,x,w; }e[400010]; ll head[400010],dis[400010],vis[400010],u[400010],v[400010],x[400010],cnt=0; void add(ll u,ll v,ll x,ll w) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; e[cnt].x=x; e[cnt].w=w; head[u]=cnt; } void dijstra(ll s,ll n) { fill(dis+1,dis+1+n,1e18); memset(vis,0,sizeof(vis)); priority_queue<pair<ll,ll> >q; dis[s]=0; q.push(make_pair(-dis[s],-s)); while(q.empty()==0) { ll x=-q.top().second; q.pop(); if(vis[x]==0) { vis[x]=1; for(ll i=head[x];i!=0;i=e[i].nxt) { if(dis[e[i].to]>dis[x]+e[i].w) { dis[e[i].to]=dis[x]+e[i].w; q.push(make_pair(-dis[e[i].to],-e[i].to)); } } } } } int main() { freopen("hellagur.in","r",stdin); freopen("hellagur.out","w",stdout); ll n,m,s,t,flag=1,i; cin>>n>>m; for(i=1;i<=m;i++) { cin>>u[i]>>v[i]>>x[i]; flag&=(x[i]<=30); } cin>>s>>t; if(flag==1) { for(i=1;i<=m;i++) { add(u[i],v[i],x[i],(1ll<<x[i])); add(v[i],u[i],x[i],(1ll<<x[i])); } dijstra(s,n); if(dis[t]==1e18) { cout<<-1<<endl; } else { cout<<dis[t]%p<<endl; } } else { cout<<"-1"<<endl; } fclose(stdin); fclose(stdout); return 0; } -
\(8 \sim 9\) ：观察到 \(x_{i}\) 互不相同，在最短路的更新过程一定不会产生进位（若产生了说明这条边重复走过，显然不优），且比较时只按二进制下最高位比较即可。具体实现时用二进制表示到每个点的最短路长度，可能需要一些诸如
short方法来保证空间复杂度正确。
-
总结
- \(T2\) 赛前 \(5 \min\) 把原状压改成了爆搜想节省空间，结果挂了 \(20pts\) 。
- \(T4\) 赛前 \(10 \min\) 发现把
freopen("hellagur.out","w",stdout);写成了freopen("hellagur.out","r",stdin);。 - 感觉自己偏随机化和乱搞做法的题不是很敢写，明知没有正确性的做法被自己 \(Pass\) 掉就没尝试写过看实际能拿多少分。
后记
- \(T4\) 原属于 HZOI2024 冲刺 NOIP2024 400pts 计划 2.图论专题 A ，结果被搬到模拟赛了。