2024初三集训模拟测试1
\(T1\) edit \(100pts\)
-
字符串模拟即可。
-
貌似不能写成
while(cin>s)，因为每两个单词中可能不只有一个空格。点击查看代码
string s; int main() { freopen("edit.in","r",stdin); freopen("edit.out","w",stdout); getline(cin,s); cout<<s[0]; for(int i=1;i<s.size();i++) { if(('0'<=s[i-1]&&s[i-1]<='9'&&(('a'<=s[i]&&s[i]<='z')||('A'<=s[i]&&s[i]<='Z')))||((('a'<=s[i-1]&&s[i-1]<='z')||('A'<=s[i-1]&&s[i-1]<='Z'))&&'0'<=s[i]&&s[i]<='9')) { cout<<" "; } cout<<s[i]; } fclose(stdin); fclose(stdout); return 0; }
\(T2\) game \(50pts\)
- 感觉和 luogu P8818 [CSP-S 2022] 策略游戏 很像，但事实证明读假题了。
- 部分分
- 测试点 \(1\)
- \(10pts\) ：由于 \(n=1\) ，故 \(a_{1}\) 即为所求。
- 测试点 \(2 \sim 3\)
- \(20pts\) ：由于 \(0 \le a_{i} \le 10^{6}\) ，故 \(\sum\limits_{i=1}^{n}a_{i}\) 即为所求。
- 测试点 \(4 \sim 5\)
- \(20pts\) ：由于 \(-10^{6} \le a_{i} <0\) ，故 \(-\min\limits_{i=1}^{n} \{ a_{i} \}+\sum\limits_{i=1}^{n}a_{i}\) 即为所求。
- 测试点 \(1\)
- 正解
Alice一定只会在第一轮取大于等于 \(1\) 个数，且Alice会取完所有的非负数。然后两人轮流取最大值。- 贪心
-
对
Alice第一轮取负数进行分讨。-
赛时及发现 \(hack\) 数据前只有 @wang54321 的 \(DP\) 做法 幸免于难。
点击查看 hack 数据
input: 5 -5121313 -81 -713 -25 -479 ans: -819
点击查看代码
ll a[200000],b[200000]; int main() { freopen("game.in","r",stdin); freopen("game.out","w",stdout); ll n,m=0,ans=0,i; cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; if(a[i]<0) { m++; b[m]=a[i]; } ans+=(a[i]>=0)*a[i]; } sort(b+1,b+1+m,greater<int>()); if(n==m) { if(m%2==1)//取1 2 4 6 ... { ans+=b[1];//特判 for(i=2;i<=m;i++) { ans+=(i%2==0)*b[i]; } } else//取1 3 5 7 ... { for(i=1;i<=m;i++) { ans+=(i%2==1)*b[i]; } } } else { if(m%2==1)//取2 4 6 ... { for(i=1;i<=m;i++) { ans+=(i%2==0)*b[i]; } } else//取1 3 5 7 ... { for(i=1;i<=m;i++) { ans+=(i%2==1)*b[i]; } } } cout<<ans<<endl; fclose(stdin); fclose(stdout); return 0; } -
-
- \(DP\)
- 详见 2024初三集训模拟测试1 。
\(T3\) score \(50pts\)
-
简化题意：给定一个长度为 \(n\) 的序列 \(a\) ，求 \(\sum\limits_{l=1}^{n}\sum\limits_{r=l}^{n}[(\sum\limits_{k=l}^{r}a_{k}) \bmod (r-l+1)]\) 。
- 感觉和 普及模拟1 T1 Past \(d=3\) 的情况很像，但事实证明读假题了。
-
部分分
- 测试点 \(1 \sim 5\)
- \(50pts\) ：前缀和优化暴力枚举。时间复杂度为 \(O(n^{2})\) 。
- 测试点 \(6 \sim 7\)
- \(20pts\) ：由于 \(0 \le a_{i} \le 2\) ，故对于每段最长的一段连续区间 \([l,r]\) 满足 \(a_{l}=a_{l+1}=a_{l+2}= \dots =a_{r}\) ，则这段区间对答案产生的贡献为 \(\dbinom{r-l+1}{2}=\dfrac{(r-l+1)(r-l)}{2}\) 。
- 测试点 \(1 \sim 5\)
-
正解
- \(\sum\limits_{l=1}^{n}\sum\limits_{r=l}^{n}[(\sum\limits_{k=l}^{r}a_{k}) \bmod (r-l+1)]\) 等价于 \(\sum\limits_{l=1}^{n}\sum\limits_{r=l}^{n}[\sum\limits_{k=l}^{r}(a_{k}-\frac{\sum\limits_{k=l}^{r}a_{k}}{r-l+1})=0]\) 。
- 观察到 \(0 \le a_{i} \le 100\) ，考虑枚举 \(\frac{\sum\limits_{k=l}^{r}a_{k}}{r-l+1}=x(x \in [\min\limits_{i=1}^{n} \{ a_{i} \},\max\limits_{i=1}^{n} \{ a_{i} \}])\) 。
- 使用前缀和优化 \(\sum\limits_{k=l}^{r}(a_{k}-x)\) 。具体地，有 \(sum_{i}=\sum\limits_{k=1}^{i}(a_{k}-x)\) 。此时有 \(\begin{aligned} \sum\limits_{l=1}^{n}\sum\limits_{r=l}^{n}[\sum\limits_{k=l}^{r}(a_{k}-x)=0]=\sum\limits_{l=1}^{n}\sum\limits_{r=l}^{n}[sum_{r}-sum_{l-1}=0]=\sum\limits_{l=1}^{n}\sum\limits_{r=l}^{n}[sum_{r}=sum_{l-1}] \end{aligned}\) 。
- 用桶来记录 \(sum\) 出现的次数即可。
- 因存在负数的情况，故将得到的 \(sum\) 加上一个比较大的数。
- 要处理 \(sum_{0}\) 的情况。
点击查看代码
ll a[200001],sum[200001],vis[21000001]; int main() { freopen("score.in","r",stdin); freopen("score.out","w",stdout); ll n,ans=0,minn=0x7f7f7f7f,maxx=0,i,j; cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; minn=min(minn,a[i]); maxx=max(maxx,a[i]); } for(i=minn;i<=maxx;i++) { vis[sum[0]+maxx*n]=1; for(j=1;j<=n;j++) { sum[j]=sum[j-1]+a[j]-i; ans+=vis[sum[j]+maxx*n]; vis[sum[j]+maxx*n]++; } for(j=0;j<=n;j++) { vis[sum[j]+maxx*n]=0; } } cout<<ans<<endl; fclose(stdin); fclose(stdout); return 0; }
\(T4\) city \(60/75pts\)
- 部分分
- \(60pts\) ：输出
-1。 - 测试点 \(5 \sim 7\)
-
\(15pts\) ：由于 \(x=1\) ，故只有一个强连通分量（环）。此时 \(m\) 需满足 \(n \le m \le A_{n}^{2}=(n-1)n\) 时有解，构造时先拿出 \(n\) 条边使得 \(1 \sim n\) 构成一个环，剩下的随便构造即可（上界为完全图）；否则无解。
点击查看代码
if(x==1) { sum=0; if(n<=m&&m<=n*(n-1)) { for(i=1;i<=n-1;i++) { cout<<i<<" "<<i+1<<endl; } cout<<n<<" "<<1<<endl; sum=n; if(sum<m) { for(i=1;i<=n-1;i++) { for(j=1;j<=n;j++) { if(j!=i&&j!=i+1) { sum++; cout<<i<<" "<<j<<endl; if(sum==m) { break; } } } if(sum==m) { break; } } if(sum<m) { i=n; for(j=1;j<=n;j++) { if(j!=n&&j!=1) { sum++; cout<<i<<" "<<j<<endl; if(sum==m) { break; } } } } } } else { cout<<-1<<endl; } }
-
- 测试点 \(8 \sim 10\)
-
\(15pts\) ：由于 \(x=n\) ，故有 \(n\) 个强连通分量（孤立点）。此时 \(q,m\) 需满足 \(q=0,0 \le m \le \dbinom{n}{2}=\dfrac{(n-1)n}{2}\) 时有解，构造时随便构造；否则无解。
点击查看代码
if(x==n) { sum=0; if(q==0) { if(m<=(n-1+1)*(n-1)/2) { for(i=1;i<=n-1;i++) { for(j=i+1;j<=n;j++) { sum++; cout<<i<<" "<<j<<endl; if(sum==m) { break; } } if(sum==m) { break; } } } else { cout<<-1<<endl; } } else { cout<<-1<<endl; } }
-
- \(60pts\) ：输出
- 正解
总结
- 赛时估分 \(100+30+50+30=210pts\) ，实际得分 \(100+50+50+[60,75]=[260,275]pts\) 。
- 部分分造得很足。
- \(T2\) 贪心想假了。
- \(T3\) 测试点 \(6 \sim 7\) 的 \(20pts\) 没写。
后记
- 数据有点水，明显的 \(hack\) 数据没有加。
- \(T4\) 赛时没有
Special Judge，所以开的“文本比较”。赛后 @wkh2008 把Special Judge写了。但Special Judge很“脆弱”，放过了部分错解，但只要不太离谱就不会挂。