2021牛客暑期多校训练营1
A Alice and Bob
题目描述
Alice和Bob玩游戏,有两堆石头,每一次在其中一堆石头里拿K个(k>0),从另一堆石头里面拿s*k个石头(s>=0),Alice先拿,最后无法进行操作的人输掉比赛。
解题思路
这道题设d[i][j]=0为必败态,则转为必胜态只要(i+k,j+sk)或者
(i+sk,j+k),且i有且仅有唯一对应的j。
代码实现
#include<bits/stdc++.h> using namespace std; typedef long long ll; bool d[5005][5005]; void init(){ for(int i=0;i<=5000;i++){ for(int j=0;j<=5000;j++){ if(!d[i][j]){ for(int k=1;k+i<=5000;k++) for(int s=0;s*k+j<=5000;s++) d[i+k][j+s*k]=1; for(int k=1;k+j<=5000;k++) for(int s=0;s*k+i<=5000;s++) d[i+s*k][j+k]=1; } } } } int main(){ init(); int t; cin>>t; while(t--){ int n,m; cin>>n>>m; if(d[n][m]) cout<<"Alice"<<endl; else cout<<"Bob"<<endl; } return 0; }
B Ball Dropping
题目描述
平面几何计算
解题思路
相似三角形,等比
代码实现
#include<iostream> #include<algorithm> #include<string> #include<math.h> using namespace std; int main(){ double r,a,b,h; scanf("%lf %lf %lf %lf",&r,&a,&b,&h); double h1=b*h/(a-b); double h2=2*r*h1/b; if(b<2*r){ printf("Stuck\n"); printf("%.10lf\n",sqrt(h2*h2+r*r)-h1); } else printf("Drop\n"); return 0; }
C Cut the Tree
D Determine the Photo Position
题目描述
将长度为m的字符串插入n*n的图中,仅由0和1组成,插入字符串时不能覆盖1。算插法方式有多少种
解题思路
逐行扫描,连续0的长度l>=m的话,sum总和加上l-m+1,小于不计。
代码实现
#include<iostream> #include<algorithm> #include<string> using namespace std; int main(){ int n,m,sum=0; cin>>n>>m; string a; while(n--){ cin>>a; int l=0; for(int i=0;i<a.length();i++){ if(a[i]=='0') l++; else{ if(l>=m) sum=sum+l-m+1; l=0; } } if(l>=m) sum=sum+l-m+1; //cout<<sum<<endl; } cin>>a; cout<<sum<<endl; return 0; }
E Escape along Water Pipe
F Find 3-friendly Integers
题目描述
3-friendly:能整除3或者任意连续位数组成的整数可以整除3
给定范围,求该范围内3-friendly的个数
解题思路
一位数:3 6 9
两位数:对能整除3或者个位数能整除3的数标记
三位数可以验证:均满足3-friendly的条件
四位数包含三位数,所以也会满足,依次类推3位数以上的均满足条件
代码实现
#include<algorithm> #include<iostream> #include<string> #include<math.h> typedef long long ll; using namespace std; int f[100]; int main(){ f[0]=f[1]=f[2]=0; f[3]=f[4]=f[5]=1; f[6]=f[7]=f[8]=2; f[9]=3; for(int i=10;i<100;i++){ if((i%10)%3==0||(i/10)%3==0||i%3==0) f[i]=f[i-1]+1; else f[i]=f[i-1]; } int t; cin>>t; while(t--){ ll n,m; cin>>n>>m; if(m<100) cout<<f[m]-f[n-1]<<endl; else if(n>=100) cout<<m-n+1<<endl; else cout<<f[99]-f[n-1]+m-99<<endl; } return 0; }
G Game of Swapping Numbers
题目描述
给你两长度为n的数列a,b.可将数列a里的元素随意对调位置。求的最大值
解题思路
第一步:去掉绝对值
如果ai<bi,将ai和bi交换,不影响结果,因为差值不变且大于0.
第二步:
保证了ai>bi,那么a数列里面的元素的符号一定是‘+’,如何对调元素使得总和增加呢?
保证a1>a2,a2<b1,那么调换后总值sum=sum+2*(b1-a2)。
根据贪心的原则,将两数组排序,计算增加总值即可。
代码实现
#include <bits/stdc++.h> typedef long long ll; using namespace std; ll a[500005],b[500005],sum=0; int main(){ ll n,k; cin>>n>>k; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++){ cin>>b[i]; if(b[i]>a[i]) swap(a[i],b[i]); sum=sum+abs(a[i]-b[i]); } sort(a,a+n); sort(b,b+n); for(int i=1;i<=n&&i<=k;i++) if(b[n-i]>a[i-1]) sum+=2*(b[n-i]-a[i-1]); cout<<sum<<endl; return 0; }
H Hash Function
I Increasing Subsequence
J Journey among Railway Stations
k Knowledge Test about Match
题目描述
给定长度为n的数列a和b.a数列元素是1到n-1,b数列的元素由输入数据给出,现在可以任意排列数列b,使得它们的标准差小于%4.
解题思路
局部最优解求整体最优解,我感觉其实就是暴力,
最外层循环多于1小于11,至于为什么我试出来的,但是正确的应该是用KM算法进行本地模拟。
代码实现
#include <bits/stdc++.h> typedef long long ll; using namespace std; const int maxn = 1005; double w[maxn]; int n,b[maxn]; int main() { for (int i = 1; i < maxn; i++) w[i] = sqrt(i); int t; cin >> t; while (t--){ cin >> n; for (int i = 0; i < n; i++)cin>>b[i]; sort(b, b + n); for (int s = 0; s < 5; s++) for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (w[abs(b[i] - j)] + w[abs(b[j] - i)] < w[abs(b[i] - i)] + w[abs(b[j] - j)])swap(b[i], b[j]); for (int i = 0; i < n; i++) cout<<b[i]<<" "; cout<<endl; } return 0; }