The 19th Zhejiang Provincial Collegiate Programming Contest vp

Dear 丶 2024-03-26 18:01 193阅读 0赞

和队友冲了这场，极限6题，重罚时铁首

怎么说，前面的A题我贡献了太多的罚时，然后我的G题最短路调了一万年，因为太久没写了，甚至把队列打成了优先队列，没把head数组清空完全，都是我的锅呜呜呜

队友很给力，签到虽然卡了一会但是都开出来了，M题队友直接写了个两百多行的大模拟，太强了，虽然不是正解但是依然感觉很牛逼

I题因为时间原因直接去吃饭了，不然感觉肯定能开出来，其实就是个字符串哈希+签到难度 的博弈

vp的感觉就是：签到交的太快，应该让队友check一下再交，不差这点时间，不然罚时太多

感觉能7题啊

没关系，还有一个月，来得及！

Dashboard - The 19th Zhejiang Provincial Collegiate Programming Contest - Codeforces

49c495911394b6b2140b7f35881e77b0.png

A. JB Loves Math

奇偶性分类讨论

很重要的性质：加/减奇数次奇数奇偶性就会变，否则奇偶性都不变

题意：

给定a和b，让你选定一个奇数x和一个偶数y，每次操作可以让a加上x或让a减去y，问最少几次操作可以使a变成b

思路：

一开始想的是小分类讨论：

9ce83bb3462b40152bfdf0413325ae84.png

但是显然不是这样写的，当a<b时，当b-a是奇数时，直接加奇数即可，如果b-a是偶数的时候，如果b-a能被两个奇数表示，那么操作次数就是2次，否则就是加两次奇数使得a大于b，这样奇偶性就和b一样了，这样就能减个偶数了，这样子就是三次操作

Code：

  1. #include <iostream>
  2. #include <cstring>
  3. #include <cstdio>
  4. #include <vector>
  5. #include <map>
  6. #include <unordered_map>
  7. #include <queue>
  8. #include <set>
  9. #define int long long
  10. using namespace std;
  11. using i64 = long long;
  12. const int mxn=1e5+10;
  13. const int mxe=1e6+10;
  14. const int mod=1e9+7;
  16. int a,b;
  17. void solve(){
  18.     cin>>a>>b;
  19.     if(a<b){
  20.         if((b-a)%2==1) cout<<1<<'\n';
  21.         else {
  22.             if(((b-a)/2)%2)cout<<2<<'\n';
  23.             else cout<<3<<endl;
  24.         }
  25.     }else if(a>b){
  26.         if((a-b)%2==1) cout<<2<<'\n';
  27.         else cout<<1<<'\n';
  28.     }else{
  29.         cout<<0<<'\n';
  30.     }
  31. }
  32. signed main(){
  33.     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  34.     int __=1;cin>>__;
  35.     while(__--)solve();return 0;
  36. }

B JB Loves Comma

字符串模拟

a8017f1877935f81a614248859e1f213.png

直接放代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. char s[200005],x[]="cjb";
  4. int n,l,i,j,k,m;
  5. int main()
  6. {
  7.     cin>>s;
  8.     l=strlen(s);
  9.     for(i=0;i<=l-2;i++){
  10.         if(strncmp(s+i,x,3)==0){printf("%c%c%c,",s[i],s[i+1],s[i+2]);i+=2;}
  11.         else printf("%c",s[i]);
  12.     }
  13.     for(;i<l;i++)printf("%c",s[i]);
  14. }

C. JB Wants to Earn Big Money

模拟

题意：

如果a数组里元素小于x，答案++

如果b数组里面元素大于x，答案++

思路：

直接模拟

Code：

  1. #include <iostream>
  2. #include <cstring>
  3. #include <cstdio>
  4. #include <vector>
  5. #include <map>
  6. #include <unordered_map>
  7. #include <queue>
  8. #include <set>
  9. #define int long long
  10. using namespace std;
  11. using i64 = long long;
  12. const int mxn=1e5+10;
  13. const int mxe=1e6+10;
  14. const int mod=1e9+7;
  16. int n,m,x;
  17. int a[mxn],b[mxn];
  18. void solve(){
  19.     cin>>n>>m>>x;
  20.     for(int i=1;i<=n;i++) cin>>a[i];
  21.     for(int i=1;i<=m;i++) cin>>b[i];
  22.     int ans=0;
  23.     for(int i=1;i<=n;i++){
  24.         if(a[i]>=x) ans++;
  25.     }
  26.     for(int i=1;i<=m;i++){
  27.         if(b[i]<=x) ans++;
  28.     }
  29.     cout<<ans<<'\n';
  30. }
  31. signed main(){
  32.     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  33.     int __=1;//cin>>__;
  34.     while(__--)solve();return 0;
  35. }

L. Candy Machine

Problem - L - Codeforces

二分+贪心

题意：

给定一个集合，让你选取一个子集，使得其子集中的元素大于平均值的元素个数尽可能多，问最多能有多少元素

思路：

因为是个集合，所以考虑排序或哈希

因为要使满足条件的元素个数尽可能多，那么就是让平均值尽可能小，那么就是尽可能选小的数，因此考虑从小到大排序去选，子集一定是前缀。

那么怎么统计出值大于平均值的个数，注意到这个问题具有二段性，右边的都大于，左边的都小于等于，因此直接去二分即可

Code：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int mxn=1e6+10;
  4. #define ll long long
  5. ll n,a[mxn],ans,b[mxn];
  6. int main(){
  7.     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  8.     cin>>n;
  9.     for(int i=1;i<=n;i++) cin>>a[i];
  10.     sort(a+1,a+n+1);
  11.     for(int i=1;i<=n;i++) b[i]=b[i-1]+a[i];
  12.     for(int i=2;i<=n;i++){
  13.         ll x=upper_bound(a+1,a+i+1,b[i]*1.0/(double)i)-a;
  14.         ans=max(ans,i-x+1);
  15.     }
  16.     cout<<ans<<'\n';
  17.     return 0;
  18. }

M. BpbBppbpBB

大模拟 or 解方程

题意：

就是让你count给定的图形里面有多少C Type 和 S Type

234e6d87e45770f161d22b04fb86a845.png

思路：

不知道怎么做啊，正解好像是解方程，还好队友是模拟天才，写了两百多行的大模拟就过了

真 的 牛 逼

Code：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,l,j,i,k,m,h,g,f,x,y;
  4. char s1[1200][1200],a[20][20]={"##########","##########","##########","####..####","###....###","###....###","####..####","##########","##########","##########","####..####","###....###","###....###","####..####","##########","##########","##########"},b[20][20]={"#################","#################","#################","####..#####..####","###....###....###","###....###....###","####..#####..####","#################","#################","#################"},c[20][20]={"##########","##########","##########","####..####","###....###","###....###","####..####","##########","##########","##########"},d[]="###",e[]="####";
  5. int main()
  6. {
  7.     scanf("%d %d",&n,&m);
  8.     for(i=0;i<n;i++){
  9.         scanf("%s",s1[i]);
  10.         // strcpy(s1[i],s1[i]);
  11.     }
  12.     for(i=0;i<n-9;i++){
  13.         for(j=0;j<m-9;j++){
  14.             if(s1[i][j]==0)continue;
  15.             for(k=i;k<i+10;k++){
  16.                 if(strncmp(s1[k]+j,b[k-i],17))break;
  17.             }
  18.             if(k==i+10){
  19.                 x++;
  20.                 for(h=i;h<i+10;h++){
  21.                     memset(s1[h]+j,0,17);
  22.                 }
  23.                 j+=16;
  24.             }
  25.             else if(i+17<=n){
  26.                 for(k=i;k<i+17;k++){
  27.                     if(strncmp(s1[k]+j,a[k-i],10))break;
  28.                 }
  29.                 if(k==i+17){
  30.                     x++;
  31.                     for(h=i;h<i+17;h++){
  32.                         memset(s1[h]+j,0,10);
  33.                     }
  34.                     j+=9;
  35.                 }
  36.             }
  37.         }
  38.     }
  39.     for(i=0;i<n-9;i++){
  40.         for(j=0;j<m-9;j++){
  41.             if(s1[i][j]==0)continue;
  42.             for(k=i;k<i+10;k++){
  43.                 if(strncmp(s1[k]+j,c[k-i],10))break;
  44.             }
  45.             if(k==i+10){
  46.                 if(i-4>=0){
  47.                     for(h=i-4;h<i;h++){
  48.                         if(strncmp(s1[h]+j,d,3))break;
  49.                     }
  50.                     if(h==i){
  51.                         y++;
  52.                         for(h=i-4;h<i;h++){
  53.                             memset(s1[h]+j,0,3);
  54.                         }
  55.                         for(h=i;h<i+10;h++)memset(s1[h]+j,0,10);
  56.                         j+=9;
  57.                         continue;
  58.                     }
  59.                     for(h=i-4;h<i;h++){
  60.                         if(strncmp(s1[h]+j+7,d,3))break;
  61.                     }
  62.                     if(h==i){
  63.                         y++;
  64.                         for(h=i-4;h<i;h++){
  65.                             memset(s1[h]+j+7,0,3);
  66.                         }
  67.                         for(h=i;h<i+10;h++)memset(s1[h]+j,0,10);
  68.                         j+=9;
  69.                         continue;
  70.                     }
  71.                 }
  72.                 if(i+4<n){
  73.                     for(h=i+1;h<i+5;h++){
  74.                         if(strncmp(s1[h]+j,d,3))break;
  75.                     }
  76.                     if(h==i+5){
  77.                         y++;
  78.                         for(h=i+1;h<i+5;h++){
  79.                             memset(s1[h]+j,0,3);
  80.                         }
  81.                         for(h=i;h<i+10;h++)memset(s1[h]+j,0,10);
  82.                         j+=9;
  83.                         continue;
  84.                     }
  85.                     for(h=i+1;h<i+5;h++){
  86.                         if(strncmp(s1[h]+j+7,d,3))break;
  87.                     }
  88.                     if(h==i+5){
  89.                         y++;
  90.                         for(h=i+1;h<i+5;h++){
  91.                             memset(s1[h]+j+7,0,3);
  92.                         }
  93.                         for(h=i;h<i+10;h++)memset(s1[h]+j,0,10);
  94.                         j+=9;
  95.                         continue;
  96.                     }
  97.                 }
  98.                 if(j-4>=0){
  99.                     for(h=i;h<i+3;h++){
  100.                         if(strncmp(s1[h]+j-4,e,4))break;
  101.                     }
  102.                     if(h==i+3){
  103.                         y++;
  104.                         for(h=i;h<i+10;h++)memset(s1[h]+j,0,10);
  105.                         for(h=i;h<i+3;h++){
  106.                             memset(s1[h]+j-4,0,4);
  107.                         }
  108.                         j+=9;
  109.                         continue;
  110.                     }
  111.                     for(h=i+7;h<i+10;h++){
  112.                         if(strncmp(s1[h]+j-4,e,4))break;
  113.                     }
  114.                     if(h==i+10){
  115.                         y++;
  116.                         for(h=i;h<i+10;h++)memset(s1[h]+j,0,10);
  117.                         for(h=i+7;h<i+10;h++){
  118.                             memset(s1[h]+j-4,0,4);
  119.                         }
  120.                         j+=9;
  121.                         continue;
  122.                     }
  123.                 }
  124.                 if(j+4<m){
  125.                     for(h=i;h<i+3;h++){
  126.                         if(strncmp(s1[h]+j+10,e,4))break;
  127.                     }
  128.                     if(h==i+3){
  129.                         y++;
  130.                         for(h=i;h<i+10;h++)memset(s1[h]+j,0,10);
  131.                         for(h=i;h<i+3;h++){
  132.                             memset(s1[h]+j+10,0,4);
  133.                         }
  134.                         j+=9;
  135.                         continue;
  136.                     }
  137.                     for(h=i+7;h<i+10;h++){
  138.                         if(strncmp(s1[h]+j+10,e,4))break;
  139.                     }
  140.                     if(h==i+10){
  141.                         y++;
  142.                         for(h=i;h<i+10;h++)memset(s1[h]+j,0,10);
  143.                         for(h=i+7;h<i+10;h++){
  144.                             memset(s1[h]+j+10,0,4);
  145.                         }
  146.                         j+=9;
  147.                         continue;
  148.                     }
  149.                 }
  150.             }
  151.         }
  152.     }
  153.     // for(i=0;i<n;i++){
  154.     //     for(j=0;j<m;j++){
  155.     //         printf("%3d",s1[i][j]);
  156.     //     }
  157.     //     cout<<endl;
  158.     // }
  159.     printf("%d %d",x,y);
  160. }

G. Easy Glide

Problem - G - Codeforces

最短路

题意：

给定起点和终点，可以借助一些其他点进行加速，问你起点到终点最快能多久

de9e41826db2894aa7068027813c9b4e.png

思路：

应该一眼最短路板子题的，当时还犹豫了一下

直接按时间作为边权建图然后跑最短路就行了

但是我调了很久很久，甚至把优先队列写成了队列，还没把head数组清空完全

是谁不会写最短路我不说

还好最后AC了

Code：

  1. #include <bits/stdc++.h>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <math.h>
  6. #include <algorithm>
  7. #include <vector>
  8. #include <map>
  9. #include <unordered_map>
  10. #include <queue>
  11. #include <set>
  12. #define int long long
  13. using namespace std;
  14. using i64 = long long;
  15. const int mxn=1e6+10;
  16. const int mxe=1e6+10;
  17. const int mod=1e9+7;
  18. const double eps=1e-4;
  19. struct Point{
  20.     int x,y;
  21. }p[mxn];
  22. struct ty{
  23.     int to,next;
  24.     double w;
  25. }edge[mxe<<1];
  26. struct ty2{
  27.     int x;
  28.     double dis;
  29.     bool operator<(const ty2 &a) const{
  30.         return a.dis<dis;
  31.     }
  32. };
  33. priority_queue<ty2> q;
  34. int n,tot=0,v1,v2;
  35. int head[mxn],vis[mxn];
  36. double dis[mxn];
  37. void add(int u,int v,double w){
  38.     edge[tot].w=w;
  39.     edge[tot].to=v;
  40.     edge[tot].next=head[u];
  41.     head[u]=tot++;
  42. }
  43. void init(){
  44.     tot=0;
  45.     for(int i=0;i<mxn;i++) head[i]=-1;
  46. }
  47. double dist(int a,int b){
  48.     return sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y));
  49. }
  50. void dij(int s,int t){
  51.     for(int i=0;i<=n+2;i++) dis[i]=1e9;
  52.     memset(vis,0,sizeof(vis));
  53.     q.push({s,0});
  54.     dis[s]=0;
  55.     while(!q.empty()){
  56.         ty2 u=q.top();
  57.         q.pop();
  58.         if(vis[u.x]) continue;
  59.         vis[u.x]=1;
  60.         //cout<<u.x<<'\n';
  61.         for(int i=head[u.x];~i;i=edge[i].next){
  62.             if(vis[edge[i].to]) continue;
  63.             //if(u.x==3) cout<<edge[i].to<<'\n';
  64.             if(dis[edge[i].to]>dis[u.x]+edge[i].w){
  65.                 dis[edge[i].to]=dis[u.x]+edge[i].w;
  66.                 if(dis[edge[i].to]-0.000412311<eps){
  67.                     int pp=1;
  68.                 }
  69.                 q.push({edge[i].to,dis[edge[i].to]});
  70.             }
  71.         }
  72.     }
  73. }
  74. void solve(){
  75.     cin>>n;
  76.     init();
  77.     for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y;
  78.     cin>>p[n+1].x>>p[n+1].y>>p[n+2].x>>p[n+2].y;
  79.     cin>>v1>>v2;
  80.     for(int i=1;i<=n;i++){
  81.         for(int j=i+1;j<=n;j++){
  82.             add(i,j,max( dist(i,j)/(v2*1.0)  ,  (dist(i,j)-3*v2)/v1*1.0+3));
  83.             add(j,i,max( dist(i,j)/(v2*1.0)  ,  (dist(i,j)-3*v2)/v1*1.0+3));
  84.             //cout<<i<<" "<<j<<" "<<max( dist(i,j)/(v2*1.0)  ,  (dist(i,j)-3*v2)/v1*1.0+3)<<'\n';
  85.         }
  86.     }
  87.     //cout<<'\n';
  88.     for(int j=1;j<=n+2;j++){
  89.         add(n+1,j,dist(n+1,j)/(v1*1.0));
  90.         add(j,n+1,dist(n+1,j)/(v1*1.0));
  91.         //cout<<n+1<<" "<<j<<" "<<dist(n+1,j)/(v1*1.0)<<'\n';
  92.     }
  93.     for(int i=1;i<=n+2;i++){
  94.         if(i==n+1) continue;
  95.         add(i,n+2,max( dist(i,n+2)/(v2*1.0)  ,  (dist(i,n+2)-3*v2)/v1*1.0+3));
  96.         add(n+2,i,max( dist(i,n+2)/(v2*1.0)  ,  (dist(i,n+2)-3*v2)/v1*1.0+3));
  97.         //cout<<i<<" "<<n+2<<" "<<max( dist(i,n+2)/(v2*1.0)  ,  (dist(i,n+2)-3*v2)/v1*1.0+3)<<'\n';
  98.     }
  99.     //cout<<'\n';
  100.     dij(n+1,n+2);
  101.     //cout<<dis[2]<<'\n';
  102.     cout<<fixed<<setprecision(9)<<dis[n+2]<<'\n';
  103. }
  104. signed main(){
  105.     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  106.     int __=1;//cin>>__;
  107.     while(__--)solve();return 0;
  108. }

I. Barbecue

简单博弈+字符串哈希判回文

Problem - I - Codeforces

题意：

0c5526ed66aab6c3ef5de7d397eed6ee.png

思路：

谁是赢家肯定和字符串size的奇偶性有关，那么剩下的问题在于怎么快速判断一个字符串是回文串

一个常用的套路就是字符串哈希判回文串

我们队无人会串串，该加训串串题了

Code：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int mxn=1e6+10;
  4. const int P=131;
  5. string s;
  6. int n,q,l,r;
  7. int p1[mxn],h1[mxn],h2[mxn];
  8. int get2_hash(int l,int r){
  9.     return h2[l]-h2[r+1]*p1[r-l+1];
  10. }
  11. int get1_hash(int l,int r){
  12.     return h1[r]-h1[l-1]*p1[r-l+1];
  13. }
  14. void solve(){
  15.     cin>>n>>q>>s;
  16.     s=" "+s;
  17.     p1[0]=1;
  18.     for(int i=1;i<=n;i++){
  19.         p1[i]=p1[i-1]*P;
  20.         h1[i]=h1[i-1]*P+s[i];
  21.     }
  22.     for(int i=n;i>=1;i--){
  23.         h2[i]=h2[i+1]*P+s[i];
  24.     }
  25.     while(q--){
  26.         cin>>l>>r;
  27.         if(get1_hash(l,r)==get2_hash(l,r)) cout<<"Budada"<<'\n';
  28.         else{
  29.             if((r-l+1)%2==1) cout<<"Putata"<<'\n';
  30.             else cout<<"Budada"<<'\n';
  31.         }
  32.     }
  33. }
  34. int main(){
  35.     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  36.     int __=1;//cin>>__;
  37.     while(__--)solve();return 0;
  38. }

发表评论

表情：
评论列表 （有 0 条评论，193人围观）

还没有评论，来说两句吧...

相关阅读