和隊(duì)友沖了這場(chǎng)，極限6題，重罰時(shí)鐵首

怎么說(shuō)，前面的A題我貢獻(xiàn)了太多的罰時(shí)，然后我的G題最短路調(diào)了一萬(wàn)年，因?yàn)樘脹](méi)寫(xiě)了，甚至把隊(duì)列打成了優(yōu)先隊(duì)列，沒(méi)把head數(shù)組清空完全，都是我的鍋嗚嗚嗚

隊(duì)友很給力，簽到雖然卡了一會(huì)但是都開(kāi)出來(lái)了，M題隊(duì)友直接寫(xiě)了個(gè)兩百多行的大模擬，太強(qiáng)了，雖然不是正解但是依然感覺(jué)很牛逼

I題因?yàn)闀r(shí)間原因直接去吃飯了，不然感覺(jué)肯定能開(kāi)出來(lái)，其實(shí)就是個(gè)字符串哈希+簽到難度 的博弈

vp的感覺(jué)就是：簽到交的太快，應(yīng)該讓隊(duì)友check一下再交，不差這點(diǎn)時(shí)間，不然罰時(shí)太多

感覺(jué)能7題啊

沒(méi)關(guān)系，還有一個(gè)月，來(lái)得及！

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

A. JB Loves Math

奇偶性分類討論

很重要的性質(zhì)：加/減奇數(shù)次奇數(shù)奇偶性就會(huì)變，否則奇偶性都不變

題意：

給定a和b，讓你選定一個(gè)奇數(shù)x和一個(gè)偶數(shù)y，每次操作可以讓a加上x(chóng)或讓a減去y，問(wèn)最少幾次操作可以使a變成b

思路：

一開(kāi)始想的是小分類討論：

但是顯然不是這樣寫(xiě)的，當(dāng)a<b時(shí)，當(dāng)b-a是奇數(shù)時(shí)，直接加奇數(shù)即可，如果b-a是偶數(shù)的時(shí)候，如果b-a能被兩個(gè)奇數(shù)表示，那么操作次數(shù)就是2次，否則就是加兩次奇數(shù)使得a大于b，這樣奇偶性就和b一樣了，這樣就能減個(gè)偶數(shù)了，這樣子就是三次操作

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數(shù)組里元素小于x，答案++

如果b數(shù)組里面元素大于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

二分+貪心

題意：

給定一個(gè)集合，讓你選取一個(gè)子集，使得其子集中的元素大于平均值的元素個(gè)數(shù)盡可能多，問(wèn)最多能有多少元素

思路：

因?yàn)槭莻€(gè)集合，所以考慮排序或哈希

因?yàn)橐節(jié)M足條件的元素個(gè)數(shù)盡可能多，那么就是讓平均值盡可能小，那么就是盡可能選小的數(shù)，因此考慮從小到大排序去選，子集一定是前綴。

那么怎么統(tǒng)計(jì)出值大于平均值的個(gè)數(shù)，注意到這個(gè)問(wèn)題具有二段性，右邊的都大于，左邊的都小于等于，因此直接去二分即可

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

思路：

不知道怎么做啊，正解好像是解方程，還好隊(duì)友是模擬天才，寫(xiě)了兩百多行的大模擬就過(guò)了

真 的 牛 逼

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

最短路

題意：

給定起點(diǎn)和終點(diǎn)，可以借助一些其他點(diǎn)進(jìn)行加速，問(wèn)你起點(diǎn)到終點(diǎn)最快能多久

思路：

應(yīng)該一眼最短路板子題的，當(dāng)時(shí)還猶豫了一下

直接按時(shí)間作為邊權(quán)建圖然后跑最短路就行了

但是我調(diào)了很久很久，甚至把優(yōu)先隊(duì)列寫(xiě)成了隊(duì)列，還沒(méi)把head數(shù)組清空完全

是誰(shuí)不會(huì)寫(xiě)最短路我不說(shuō)

還好最后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

簡(jiǎn)單博弈+字符串哈希判回文

Problem - I - Codeforces

題意：

思路：

誰(shuí)是贏家肯定和字符串size的奇偶性有關(guān)，那么剩下的問(wèn)題在于怎么快速判斷一個(gè)字符串是回文串

一個(gè)常用的套路就是字符串哈希判回文串

我們隊(duì)無(wú)人會(huì)串串，該加訓(xùn)串串題了

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;
}