The 19th Zhejiang Provincial Collegiate Programming Contest vp

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

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

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

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

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

感觉能7题啊

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

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

A. JB Loves Math

奇偶性分类讨论

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

题意：

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

思路：

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

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

Code：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#define int long long
using namespace std;
using i64 = long long;
const int mxn=1e5+10;
const int mxe=1e6+10;
const int mod=1e9+7;int a,b;
void solve(){cin>>a>>b;if(a<b){if((b-a)%2==1) cout<<1<<'\n';else {if(((b-a)/2)%2)cout<<2<<'\n';else cout<<3<<endl;}}else if(a>b){if((a-b)%2==1) cout<<2<<'\n';else cout<<1<<'\n';}else{cout<<0<<'\n';}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;cin>>__;while(__--)solve();return 0;
}

B JB Loves Comma

字符串模拟

直接放代码：

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

C. JB Wants to Earn Big Money

模拟

题意：

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

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

思路：

直接模拟

Code：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#define int long long
using namespace std;
using i64 = long long;
const int mxn=1e5+10;
const int mxe=1e6+10;
const int mod=1e9+7;int n,m,x;
int a[mxn],b[mxn];
void solve(){cin>>n>>m>>x;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++) cin>>b[i];int ans=0;for(int i=1;i<=n;i++){if(a[i]>=x) ans++;}for(int i=1;i<=m;i++){if(b[i]<=x) ans++;}cout<<ans<<'\n';
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;while(__--)solve();return 0;
}

L. Candy Machine

Problem - L - Codeforces

二分+贪心

题意：

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

思路：

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

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

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

Code：

#include<bits/stdc++.h>
using namespace std;
const int mxn=1e6+10;
#define ll long long
ll n,a[mxn],ans,b[mxn];
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+n+1);for(int i=1;i<=n;i++) b[i]=b[i-1]+a[i];for(int i=2;i<=n;i++){ll x=upper_bound(a+1,a+i+1,b[i]*1.0/(double)i)-a;ans=max(ans,i-x+1);}cout<<ans<<'\n';return 0;
}

M. BpbBppbpBB

大模拟 or 解方程

题意：

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

思路：

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

真 的 牛 逼

Code：

#include<bits/stdc++.h>
using namespace std;
int n,l,j,i,k,m,h,g,f,x,y;
char s1[1200][1200],a[20][20]={"##########","##########","##########","####..####","###....###","###....###","####..####","##########","##########","##########","####..####","###....###","###....###","####..####","##########","##########","##########"},b[20][20]={"#################","#################","#################","####..#####..####","###....###....###","###....###....###","####..#####..####","#################","#################","#################"},c[20][20]={"##########","##########","##########","####..####","###....###","###....###","####..####","##########","##########","##########"},d[]="###",e[]="####";
int main()
{scanf("%d %d",&n,&m);for(i=0;i<n;i++){scanf("%s",s1[i]);// strcpy(s1[i],s1[i]);}for(i=0;i<n-9;i++){for(j=0;j<m-9;j++){if(s1[i][j]==0)continue;for(k=i;k<i+10;k++){if(strncmp(s1[k]+j,b[k-i],17))break;}if(k==i+10){x++;for(h=i;h<i+10;h++){memset(s1[h]+j,0,17);}j+=16;}else if(i+17<=n){for(k=i;k<i+17;k++){if(strncmp(s1[k]+j,a[k-i],10))break;}if(k==i+17){x++;for(h=i;h<i+17;h++){memset(s1[h]+j,0,10);}j+=9;}}}}for(i=0;i<n-9;i++){for(j=0;j<m-9;j++){if(s1[i][j]==0)continue;for(k=i;k<i+10;k++){if(strncmp(s1[k]+j,c[k-i],10))break;}if(k==i+10){if(i-4>=0){for(h=i-4;h<i;h++){if(strncmp(s1[h]+j,d,3))break;}if(h==i){y++;for(h=i-4;h<i;h++){memset(s1[h]+j,0,3);}for(h=i;h<i+10;h++)memset(s1[h]+j,0,10);j+=9;continue;}for(h=i-4;h<i;h++){if(strncmp(s1[h]+j+7,d,3))break;}if(h==i){y++;for(h=i-4;h<i;h++){memset(s1[h]+j+7,0,3);}for(h=i;h<i+10;h++)memset(s1[h]+j,0,10);j+=9;continue;}}if(i+4<n){for(h=i+1;h<i+5;h++){if(strncmp(s1[h]+j,d,3))break;}if(h==i+5){y++;for(h=i+1;h<i+5;h++){memset(s1[h]+j,0,3);}for(h=i;h<i+10;h++)memset(s1[h]+j,0,10);j+=9;continue;}for(h=i+1;h<i+5;h++){if(strncmp(s1[h]+j+7,d,3))break;}if(h==i+5){y++;for(h=i+1;h<i+5;h++){memset(s1[h]+j+7,0,3);}for(h=i;h<i+10;h++)memset(s1[h]+j,0,10);j+=9;continue;}}if(j-4>=0){for(h=i;h<i+3;h++){if(strncmp(s1[h]+j-4,e,4))break;}if(h==i+3){y++;for(h=i;h<i+10;h++)memset(s1[h]+j,0,10);for(h=i;h<i+3;h++){memset(s1[h]+j-4,0,4);}j+=9;continue;}for(h=i+7;h<i+10;h++){if(strncmp(s1[h]+j-4,e,4))break;}if(h==i+10){y++;for(h=i;h<i+10;h++)memset(s1[h]+j,0,10);for(h=i+7;h<i+10;h++){memset(s1[h]+j-4,0,4);}j+=9;continue;}}if(j+4<m){for(h=i;h<i+3;h++){if(strncmp(s1[h]+j+10,e,4))break;}if(h==i+3){y++;for(h=i;h<i+10;h++)memset(s1[h]+j,0,10);for(h=i;h<i+3;h++){memset(s1[h]+j+10,0,4);}j+=9;continue;}for(h=i+7;h<i+10;h++){if(strncmp(s1[h]+j+10,e,4))break;}if(h==i+10){y++;for(h=i;h<i+10;h++)memset(s1[h]+j,0,10);for(h=i+7;h<i+10;h++){memset(s1[h]+j+10,0,4);}j+=9;continue;}}}}}// for(i=0;i<n;i++){//     for(j=0;j<m;j++){//         printf("%3d",s1[i][j]);//     }//     cout<<endl;// }printf("%d %d",x,y);
}

G. Easy Glide

Problem - G - Codeforces

最短路

题意：

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

思路：

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

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

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

是谁不会写最短路我不说

还好最后AC了

Code：

#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#define int long long
using namespace std;
using i64 = long long;
const int mxn=1e6+10;
const int mxe=1e6+10;
const int mod=1e9+7;
const double eps=1e-4;
struct Point{int x,y;
}p[mxn];
struct ty{int to,next;double w;
}edge[mxe<<1];
struct ty2{int x;double dis;bool operator<(const ty2 &a) const{return a.dis<dis;}
};
priority_queue<ty2> q;
int n,tot=0,v1,v2;
int head[mxn],vis[mxn];
double dis[mxn];
void add(int u,int v,double w){edge[tot].w=w;edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;
}
void init(){tot=0;for(int i=0;i<mxn;i++) head[i]=-1;
}
double dist(int a,int b){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));
}
void dij(int s,int t){for(int i=0;i<=n+2;i++) dis[i]=1e9;memset(vis,0,sizeof(vis));q.push({s,0});dis[s]=0;while(!q.empty()){ty2 u=q.top();q.pop();if(vis[u.x]) continue;vis[u.x]=1;//cout<<u.x<<'\n';for(int i=head[u.x];~i;i=edge[i].next){if(vis[edge[i].to]) continue;//if(u.x==3) cout<<edge[i].to<<'\n';if(dis[edge[i].to]>dis[u.x]+edge[i].w){dis[edge[i].to]=dis[u.x]+edge[i].w;if(dis[edge[i].to]-0.000412311<eps){int pp=1;}q.push({edge[i].to,dis[edge[i].to]});}}}
}
void solve(){cin>>n;init();for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y;cin>>p[n+1].x>>p[n+1].y>>p[n+2].x>>p[n+2].y;cin>>v1>>v2;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){add(i,j,max( dist(i,j)/(v2*1.0)  ,  (dist(i,j)-3*v2)/v1*1.0+3));add(j,i,max( dist(i,j)/(v2*1.0)  ,  (dist(i,j)-3*v2)/v1*1.0+3));//cout<<i<<" "<<j<<" "<<max( dist(i,j)/(v2*1.0)  ,  (dist(i,j)-3*v2)/v1*1.0+3)<<'\n';}}//cout<<'\n';for(int j=1;j<=n+2;j++){add(n+1,j,dist(n+1,j)/(v1*1.0));add(j,n+1,dist(n+1,j)/(v1*1.0));//cout<<n+1<<" "<<j<<" "<<dist(n+1,j)/(v1*1.0)<<'\n';}for(int i=1;i<=n+2;i++){if(i==n+1) continue;add(i,n+2,max( dist(i,n+2)/(v2*1.0)  ,  (dist(i,n+2)-3*v2)/v1*1.0+3));add(n+2,i,max( dist(i,n+2)/(v2*1.0)  ,  (dist(i,n+2)-3*v2)/v1*1.0+3));//cout<<i<<" "<<n+2<<" "<<max( dist(i,n+2)/(v2*1.0)  ,  (dist(i,n+2)-3*v2)/v1*1.0+3)<<'\n';}//cout<<'\n';dij(n+1,n+2);//cout<<dis[2]<<'\n';cout<<fixed<<setprecision(9)<<dis[n+2]<<'\n';
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;while(__--)solve();return 0;
}

I. Barbecue

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

Problem - I - Codeforces

题意：

思路：

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

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

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

Code：

#include <bits/stdc++.h>
using namespace std;
const int mxn=1e6+10;
const int P=131;
string s;
int n,q,l,r;
int p1[mxn],h1[mxn],h2[mxn];
int get2_hash(int l,int r){return h2[l]-h2[r+1]*p1[r-l+1];
}
int get1_hash(int l,int r){return h1[r]-h1[l-1]*p1[r-l+1];
}
void solve(){cin>>n>>q>>s;s=" "+s;p1[0]=1;for(int i=1;i<=n;i++){p1[i]=p1[i-1]*P;h1[i]=h1[i-1]*P+s[i];}for(int i=n;i>=1;i--){h2[i]=h2[i+1]*P+s[i];}while(q--){cin>>l>>r;if(get1_hash(l,r)==get2_hash(l,r)) cout<<"Budada"<<'\n';else{if((r-l+1)%2==1) cout<<"Putata"<<'\n';else cout<<"Budada"<<'\n';}}
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;while(__--)solve();return 0;
}