初中信息奥赛模拟测试
\(T1\) ZEW 玩扫雷 \(100pts\)
- 原题：luogu P2670 [NOIP2015 普及组] 扫雷游戏
- 本题修改：本题的非地雷地区为
.。
- 本题修改：本题的非地雷地区为
- 正解
char a[1010][1010]; int main() { //freopen("mine.in","r",stdin); //freopen("mine.out","w",stdout); int n,m,i,j,sum; cin>>n>>m; for(j=0;j<=m+1;j++) { a[0][j]=a[n+1][j]='.'; } for(i=1;i<=n;i++) { a[i][0]='.'; for(j=1;j<=m;j++) { cin>>a[i][j]; } a[i][m+1]='.'; } for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(a[i][j]=='*') { cout<<"*"; } else { sum=(a[i-1][j-1]=='*')+(a[i-1][j]=='*')+(a[i-1][j+1]=='*')+(a[i][j-1]=='*')+(a[i][j+1]=='*')+(a[i+1][j-1]=='*')+(a[i+1][j]=='*')+(a[i+1][j+1]=='*'); cout<<sum; } } cout<<endl; } //fclose(stdin); //fclose(stdout); return 0; }
\(T2\) ZEW 的游戏 \(100pts\)
- 原题：luogu P2665 [USACO08FEB] Game of Lines S
- 正解
- 因为一个点可以引多条直线，求互不平行直线个数等价于求不同斜率的个数。
- 另外的一些细节：因存在精度误差，求出斜率后不用
double去存，而是存其对应的最简分式的分子和分母；注意要处理平行于坐标轴的情况，以免导致除法运算时除数为 \(0\) 导致 \(RE\) ；题目中没说是否有重合的点，建议特判，然而并没有构造重点的数据。- @xrlong 等人因此挂分。
bitset<500>vis[500];//bitset可用bool数组代替 map<int,map<int,int> >a; int x[500],y[500]; int main() { //freopen("game.in","r",stdin); //freopen("game.out","w",stdout); int n,i,j,d,ans=0,p,q,pd,pd1=0,pd2=0;//pd1存是否有平行于y轴，pd2存是否有平行于x轴 cin>>n; for(i=1;i<=n;i++) { cin>>x[i]>>y[i]; } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(i!=j&&vis[i][j]==0) { if(x[i]==x[j]&&y[i]==y[j])//题目没有说是否存在重点 { continue; } vis[i][j]=1; p=y[i]-y[j]; q=x[i]-x[j]; pd=(p<0)*(q<0); if(pd==1)//同时消去分子、分母的负号 { p=-p; q=-q; } else { if(q<0)//如果斜率为负数，规定分子为负数，分母为正数 { p=-p; q=-q; } } if(q==0) { ans+=(pd1==0); pd1=1; } else { if(p==0) { ans+=(pd2==0); pd2=1; } else { d=__gcd(abs(p),abs(q));//先取abs再求gcd不再多说 ans+=(a[p/d][q/d]==0); a[p/d][q/d]=1; } } } } } cout<<ans<<endl; //fclose(stdin); //fclose(stdout); return 0; }
- @xrlong 等人因此挂分。
\(T3\) ZEW 学分块 \(40pts\)
- 强化版：luogu P1182 数列分段 Section II | luogu P2884 [USACO07MAR] Monthly Expense S
- 本题修改：本题规定 \(m=3\) 。
- 部分分
- \(40pts\) ：枚举左右端点，没什么好说的。
- \(80pts\) ： @hly_shen 的一个假了的贪心做法，具体做法自己去问吧。
- 正解
- 二分答案，时间复杂度为 \(O(n\log_{2}(\sum\limits_{i=1}^{n}a_{i}))\) 。
ll a[5000010]; bool check(ll mid,ll n) { ll num=0,ans=0,i; for(i=1;i<=n;i++) { if(num+a[i]<=mid) { num+=a[i]; } else { num=a[i]; ans++; } } return (ans>=3); } int main() { //freopen("divide.in","r",stdin); //freopen("divide.out","w",stdout); ll n,i,l=0,r=0,mid; scanf("%lld",&n); for(i=1;i<=n;i++) { scanf("%lld",&a[i]); l=max(l,a[i]); r+=a[i]; } while(l<=r) { mid=(l+r)/2; if(check(mid,n)==true) { l=mid+1; } else { r=mid-1; } } printf("%lld\n",l); //fclose(stdin); //fclose(stdout); return 0; } - 因本题规定 \(m=3\) ，故也可使用双指针做法，时间复杂度为 \(O(n)\) 。
- 注：赛时 \(AC\) 的只有 @wang54321 使用了该做法。
- 将原序列分成 \(1 \sim l,l+1 \sim r,r+1 \sim n\) 三个部分。固定 \(r\) 不动，此时已知 \(sum_{n}-sum_{r}\) ，从贪心的角度分析，若要使 \(\max(sum_{l},sum_{r}-sum_{l},sum_{n}-sum_{r})\) 尽可能的小，便要使 \(sum_{l}\) 和 \(sum_{r}-sum_{l}\) 尽可能接近。类似 2022年普及组3 T2 特 ，使用双指针维护第一个 \(sum_{l}>sum_{r}-sum_{l}\) 的位置 \(l\) ，并可以得到最后一个 \(sum_{l} \le sum_{r}-sum_{l}\) 的位置 \(l\) ，分别对三者取 \(\max\) 然后取 \(\min\) 即可。
ll a[5000010],sum[5000010]; int main() { //freopen("divide.in","r",stdin); //freopen("divide.out","w",stdout); ll n,i,l,r,ans=0x7f7f7f7f; scanf("%lld",&n); for(i=1;i<=n;i++) { scanf("%lld",&a[i]); sum[i]=sum[i-1]+a[i]; } for(l=1,r=2;r<=n-1;r++) { while(sum[l]<sum[r]-sum[l]) { l++; } ans=min(ans,min(max(sum[l],max(sum[r]-sum[l],sum[n]-sum[r])),max(sum[l-1],max(sum[r]-sum[l-1],sum[n]-sum[r])))); } printf("%lld\n",ans); //fclose(stdin); //fclose(stdout); return 0; }
- 二分答案，时间复杂度为 \(O(n\log_{2}(\sum\limits_{i=1}^{n}a_{i}))\) 。
\(T4\) ZEW 玩 thd \(10pts\)
- 部分分
- \(10pts\) ：输出
0。 - \(20pts\) ：输出 \(\sum\limits_{i=1}^{n}g_{i}\) 。
- \(10pts\) ：输出
- 正解
- 背包 \(DP\) 。
- 不是严格意义上的背包 \(DP\) ，只是利用了背包 \(DP\) 的思想。
- 一个比较显然的贪心思想：如果我们想要得到一个小兵的金币，应该让塔攻击这个小兵尽可能多的次数，然后人来进行补刀。
- 不一定只能补刀 \(1\) 次。
- 观察到塔和人的攻击可以看作是同步进行的，转化为人可以留着攻击次数。
- 令 \(ta_{i}(1 \le i \le n)\) 表示关于 \(x\) 的不等式 \(qx<h_i\) 的最小正整数解， \(ren_{i}= \left\lceil\dfrac{h-ta_{i}q}{p}\right\rceil\) 。即 \(ren_{i}(1 \le i \le n)\) 表示在塔打出最高伤害后，为击杀小兵人需要的补刀次数。
- 令 \(f_{i,j}\) 表示塔攻击第 \(i\) 个小兵时，留着 \(j\) 次攻击次数的得到的最大金币数。转移过程中有两种操作：不攻击该小兵，，消耗 \(0\) 次攻击次数，让塔将其击杀，获得 \(0\) 个金币；进行补刀，消耗 \(ren_{i}\) 次攻击次数，获得 \(g_i\) 个金币。
- 枚举攻击次数 \(j\) ，消耗 \(0\) 次攻击次数，有 \(f_{i,j+ta_{i}+1}= \max(f_{i,j+ta_{i}+1},f_{i-1,j}+0)\) ；在 \(j \ge ren_{i}-ta_{i}\) 时，消耗 \(ren_{i}-ta_{i}\) 次攻击次数，有 \(f_{i,j-(ren_{i}-ta_{i})}= \max(f_{i,j-(ren_{i}-ta_{i})},f_{i-1,j}+g_i)\) 。
ll h[101],g[101],ren[101],ta[101],f[101][20001];//因本题数据过于逆天，所以不要吝啬于枚举值域的大小 int main() { //freopen("thd.in","r",stdin); //freopen("thd.out","w",stdout); ll p,q,n,i,j,k,ans=0; cin>>p>>q>>n; memset(f,-0x3f,sizeof(f)); for(i=1;i<=n;i++) { cin>>h[i]>>g[i]; ta[i]=(h[i]%q==0)?(h[i]/q-1):(h[i]/q); ren[i]=(ll)(ceil((1.0*(h[i]-q*ta[i])/p))); } f[0][1]=0; for(i=1;i<=n;i++) { for(j=0;j<=10000;j++) { f[i][j+ta[i]+1]=max(f[i][j+ta[i]+1],f[i-1][j]+0); if(j-(ren[i]-ta[i])>=0) { f[i][j-(ren[i]-ta[i])]=max(f[i][j-(ren[i]-ta[i])],f[i-1][j]+g[i]); } } } for(i=0;i<=20000;i++) { ans=max(ans,f[n][i]); } cout<<ans<<endl; //fclose(stdin); //fclose(stdout); return 0; }
- 背包 \(DP\) 。
总结
没有挂分，挺好的。
\(20:40\) 之后基本就在罚坐了，头脑一片空白。
及时使用 \(Geany\) 查 \(RE\) 。
\(T3\) 告诉我们，有时候可以选择从一般到特殊的思考方向，不要拘泥于某一种方法。而且犯了和 普及模拟1 T1 Past 一样的问题，没有意识到是原题。之所以出现这个问题，是因为对题目本质的认识不清楚，或者说是没有一个相对模块化的思想。
\(T4\) 告诉我们：在时间足够的情况下，不要吝啬于枚举值域的大小；在内存足够的情况下，不要吝啬于数组空间的大小。因为你无法保证，你赌的值域能不被恶心的数据卡掉。
后记
题目没有 \(\LaTeX\) ，差评。
\(T4\) 第 \(10\) 个点不符合数据范围，差评。
比赛的时候机房人比平常人多了不少。从奥赛宣讲后，已经过了多半年了，甚至还有人没学文件读写来打 \(OI\) 赛制比赛，难评。\(feifei\) 因有人没学文件读写，而把文件读写删了，导致删后没有重交（误以为 \(OI\) 赛制只能提交一次）的人爆零了，虽然赛后的确安排了重测，但这属实不应该出现在校内考试中。
标签：freopen,int,sum,ren,奥赛,初中,ll,模拟,ta From： https://www.cnblogs.com/The-Shadow-Dragon/p/17962486