暑假集训CSP提高模拟17
组题人： @joke3579
\(T1\) P222. 符号化方法初探 \(70pts\)
-
部分分
- 测试点 \(1\) ：输出样例 \(1\) 。
- 测试点 \(11 \sim 15\) ：由于 \(\{ a \}\) 非负，所以对 \(\{ a \}\) 作前缀和即可。
- 随机 \(pts\) ：乱搞。
-
正解
- 当 \(\{ a \}\) 都是负数时，对 \(\{ a \}\) 作后缀和即可。
- 问题来到了怎么让 \(\{ a \}\) 的符号都相同。
- 取 \(\{ a \}\) 中绝对值最大的一个数，让其他数都加上这个数即可。
- 总次数为 \(2n-2\) 。
点击查看代码
int a[100010]; int main() { int n,maxx=0,pos=0,flag=1,i; cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; if(abs(a[i])>maxx) { maxx=abs(a[i]); pos=i; } if(i>=2) { flag&=((a[i]>=0&&a[i-1]>=0)||(a[i]<0&&a[i-1]<0)); } } if(flag==1) { cout<<n-1<<endl; if(a[1]>=0) { for(i=2;i<=n;i++) { cout<<i-1<<" "<<i<<endl; } } else { for(i=n-1;i>=1;i--) { cout<<i+1<<" "<<i<<endl; } } } else { cout<<2*n-2<<endl; for(i=1;i<=n;i++) { if(i!=pos) { cout<<pos<<" "<<i<<endl; } } if(a[pos]>=0) { for(i=2;i<=n;i++) { cout<<i-1<<" "<<i<<endl; } } else { for(i=n-1;i>=1;i--) { cout<<i+1<<" "<<i<<endl; } } } return 0; }
\(T2\) P223. 无标号 Sequence 构造 \(40pts\)
-
部分分
- \(25 \sim 50pts\) ：使用 \(O(n^{3})\) 的矩阵乘法暴力判断。
-
正解
- 发现仅需要判断相不相等，且只需要找到一个位置不同即可。
- 考虑随机化，随机选择 \(1\) 个点进行判断的正确率太低，那么我们可以随机一个 \(1 \times n\) 的矩阵 \(D\) ，判断 \(D \times A \times B\) 是否等于 \(D \times C\) 。
- 由秩-零化度定理可以知道这样判断错误的概率不超过 \(\frac{1}{998244353}\) ，不放心可以多随几次。
点击查看代码
const ll p=998244353; int a[3010][3010],b[3010][3010],c[3010][3010],d[2][3010],e[2][3010],f[2][3010]; int main() { ll t,n,flag,i,j,k,h; scanf("%lld",&t); srand(time(0)); for(k=1;k<=t;k++) { flag=0; scanf("%lld",&n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { scanf("%d",&a[i][j]); } } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { scanf("%d",&b[i][j]); } } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { scanf("%d",&c[i][j]); } } for(i=1;i<=n;i++) { d[1][i]=rand(); } for(i=1;i<=1;i++) { for(j=1;j<=n;j++) { e[i][j]=0; for(h=1;h<=n;h++) { e[i][j]=(1ll*e[i][j]+1ll*d[i][h]*a[h][j]%p)%p; } } } for(i=1;i<=1;i++) { for(j=1;j<=n;j++) { f[i][j]=0; for(h=1;h<=n;h++) { f[i][j]=(1ll*f[i][j]+1ll*e[i][h]*b[h][j]%p)%p; } } } for(i=1;i<=1;i++) { for(j=1;j<=n;j++) { e[i][j]=0; for(h=1;h<=n;h++) { e[i][j]=(1ll*e[i][j]+1ll*d[i][h]*c[h][j]%p)%p; } } } for(i=1;i<=1;i++) { for(j=1;j<=n;j++) { if(e[i][j]!=f[i][j]) { flag=1; break; } } if(flag==1) { break; } } if(flag==1) { printf("No\n"); } else { printf("Yes\n"); } } return 0; }
\(T3\) P224. 无标号 Multiset 构造 \(5pts\)
- 部分分
- \(5pts\) ：输出样例 \(1\) 。
- 正解
\(T4\) P225. 有限制的构造 \(40pts\)
- 原题： [ABC364E] Maximum Glutton
- 考虑求出要求玩过的游戏的画面质量之和 \(\le A\) 且不可玩度之和 \(\le B\) 的最多游戏数，然后多玩一个即可（若还有剩的）。
- 部分分
-
\(25 \sim 40pts\) ：设 \(f_{i,j,k}\) 表示处理到第 \(i\) 个游戏时玩过的游戏的画面质量之和 \(\le j\) 且不可玩度之和 \(\le k\) 的最多游戏数，状态转移方程为 \(f_{i,j,k}=\max(f_{i-1,j,k},f_{i-1,j-a_{i},k-b_{i}}+1)\)，跑一遍二维 \(01\) 背包 \(DP\) ，稍微压一下空间。
点击查看代码
int w[100],v[100]; short f[10010][6510]; int main() { int n,a,b,i,j,k; short sum; cin>>n>>a>>b; for(i=1;i<=n;i++) { cin>>w[i]>>v[i]; if(a<b) { swap(w[i],v[i]); } } if(a<b) { swap(a,b); } for(i=1;i<=n;i++) { for(j=a;j>=w[i];j--) { for(k=b;k>=v[i];k--) { sum=f[j-w[i]][k-v[i]]+1; f[j][k]=max(f[j][k],sum); } } } cout<<f[a][b]+(f[a][b]!=n)<<endl; return 0; }
-
- 正解
-
由 AT_dp_e Knapsack 2 | CF922E Birds 的经验，考虑优化状态设计。
-
设 \(f_{i,j,k}\) 表示前 \(i\) 个游戏中玩了 \(j\) 个游戏，画面质量之和 \(\le k\) 时不可玩度之和的最小值，状态转移方程为 \(f_{i,j,k}=\min(f_{i-1,j,k},f_{i-1,j-1,k-a_{i}}+b_{i})\) 。
点击查看代码
int w[100],v[100],f[2][100][10010]; int main() { int n,a,b,i,j,k; cin>>n>>a>>b; memset(f,0x3f,sizeof(f)); for(i=1;i<=n;i++) { cin>>w[i]>>v[i]; } f[0][0][0]=0; for(i=1;i<=n;i++) { for(j=0;j<=i;j++) { for(k=0;k<=a;k++) { f[i&1][j][k]=f[(i-1)&1][j][k]; if(j-1>=0&&k-w[i]>=0) { f[i&1][j][k]=min(f[i&1][j][k],f[(i-1)&1][j-1][k-w[i]]+v[i]); } } } } for(i=n;i>=0;i--) { for(k=0;k<=a;k++) { if(f[n&1][i][k]<=b) { cout<<i+(i!=n)<<endl; return 0; } } } }
-