文章目录
传送门
挂一个题面的pdfpdfpdf下载链接
和huangyihuangyihuangyi神佬和g21glfg21glfg21glf神佬一起打了一次比赛被轻松带飞
10道题由于最后一道毒瘤大模拟大家都不想写因此咕掉了，谁知道A掉9道题我们队也能rank1rank1rank1,233333233333233333。
貌似高手都睡觉去了。
A. Bob and BoB
直接模拟即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int mod=1e9+7,N=1e5+5;
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,a=mul(a,a))if(p&1)ret=mul(ret,a);return ret;}
int n,a,b,c,d;
int main(){
for(ri tt=read();tt;--tt){
n=read(),a=read(),b=read(),c=read(),d=read();
if((a+b+c+d)*2<(n+1))puts("No");
else puts("Yes");
}
return 0;
}
B. Vibranium Gift
我猜了一个结论：用球形包表面积最小然后一不小心过了样例。
于是直接模拟即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int mod=1e9+7,N=1e5+5;
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,a=mul(a,a))if(p&1)ret=mul(ret,a);return ret;}
const double pi=acos(-1.0);
int main(){
for(ri tt=1,up=read();tt<=up;++tt){
double M,D,V,R,S;
M=read(),D=read();
V=M/D;
R=pow(3.0*V/4.0/pi,1.0/3);
S=4.0*pi*R*R;
cout<<"Case "<<tt<<": ";
printf("%.4lf\n",S);
}
return 0;
}
C. The Blood Moon
直接小学奥数算一下答案是r24\frac{r^2}44r2
By ldxoi, contest: 2018 Battle of Brains, problem: (C) The Blood Moon, Accepted, #
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int mod=1e9+7,N=1e5+5;
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
int main(){
for(ri tt=1,up=read();tt<=up;++tt){
double r;
scanf("%lf",&r);
printf("Case %d: %.4lf\n",tt,r*r/4.0);
}
return 0;
}
close
D. Palindrome and Chocolate
GLFGLFGLF为了装弱在我过了GGG题之后让我写。
然后我想了一个打表+搜索的方法写挂了。
感觉要玩。
仔细思考了一波发现这题非常普及组。
特判掉一位数的情况之后第nnn大的长度为奇数的回文串的第111~n+12\frac{n+1}22n+1个位置表示的数就是nnn，于是直接处理一下输出就完了。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int mod=1e9+7,N=1e5+5;
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,a=mul(a,a))if(p&1)ret=mul(ret,a);return ret;}
int top=0,num[30];
inline void solve(int n){
int pos;
if(n<10){cout<<n<<'\n';return;}
top=0;
while(n)num[++top]=n%10,n/=10;
reverse(num+1,num+top+1);
for(ri i=top-1;i;--i)num[++top]=num[i];
for(ri i=1;i<=top;++i)cout<<num[i];
puts("");
}
int main(){
for(ri tt=1,n,up=read();tt<=up;++tt){
n=read();
cout<<"Case "<<tt<<": ";
solve(n);
}
return 0;
}
E. Jumpy Robot
想的时候卡了一下。
我们先减掉所有往左走的贡献，然后转化成每次可以不走或者走原来走的距离*2（相当于抵消掉左边的贡献再向右走），然后枚举走几步分别checkcheckcheck一下即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int mod=1e9+7,N=1e5+5;
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,a=mul(a,a))if(p&1)ret=mul(ret,a);return ret;}
inline int solve(ll d,ll x,int t){
int cnt=0;
for(ri i=d;i>=t;--i){
if(x>=(1ll<<(i+1)))x-=1ll<<(i+1),++cnt;
}
return x?-1:cnt;
}
inline int check(ll d,ll x){
if(!x)return 0;
for(ri i=d;~i;--i){
x+=1ll<<i;
int tmp=solve(d,x,i);
if(~tmp)return d-i+1;
}
return -1;
}
int main(){
for(ri tt=1,up=read();tt<=up;++tt){
ll d,x;
d=read(),x=read();
int f=check(d,x);
if(~f)printf("Case %d: YES %d\n",tt,f);
else printf("Case %d: NO\n",tt);
}
return 0;
}
F. Special Birthday Card
可以发现选出来的数最后如果构成的是一棵树需要满足其因子数≤4\le4≤4，我们埃氏筛即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int mod=1e9+7,N=1e6+5;
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
int sum[N],cnt[N];
inline void init(){
for(ri i=2;i<=1000000;++i){
if(cnt[i]<=2)sum[i]=1;
if(!cnt[i])for(ri j=i+i;j<=1000000;j+=i){
int tmp=j;
while(tmp==tmp/i*i)tmp/=i,++cnt[j];
}
}
sum[1]=1;
for(ri i=2;i<=1000000;++i)sum[i]+=sum[i-1];
}
int main(){
init();
for(ri tt=1,up=read(),a,b,g;tt<=up;++tt){
a=sum[(b=read())],g=__gcd(a,b),a/=g,b/=g;
printf("Case %d: %d/%d\n",tt,a,b);
}
return 0;
}
G. Ainum’s Delusion
拆开考虑每个位置的贡献即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int mod=1e9+7,N=1e5+5;
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,a=mul(a,a))if(p&1)ret=mul(ret,a);return ret;}
char s[N];
inline int calc(int x){return (ll)x*(x+1)/2%mod;}
int main(){
for(ri sum,tt=1,n,up=read();tt<=up;++tt){
sum=0;
n=read();
scanf("%s",s+1);
for(ri i=1,x;i<=n;++i){
x=(int)s[i];
sum=add(sum,mul(x,mul(calc(i),n-i+1)));
sum=add(sum,mul(x,mul(i,calc(n-i+1))));
sum=dec(sum,mul(x,mul(i,n-i+1)));
}
cout<<"Case "<<tt<<": "<<sum<<'\n';
}
return 0;
}
H. String Game
O(∣S∣2)O(|S|^2)O(∣S∣2)暴力预处理出每段区间的sumsumsum，每次询问二分答案即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
char a[6005];
int ans[6005][6005],n;
inline void init(){
for(ri i=1;i<n;++i){
int sum=0;
for(ri l=i,r=i+1;l&&r<=n;--l,++r){
sum+=abs(a[l]-a[r]);
ans[l][r]=sum;
}
}
for(ri i=1;i<=n;++i){
int sum=0;
for(ri l=i-1,r=i+1;l&&r<=n;--l,++r){
sum+=abs(a[l]-a[r]);
ans[l][r]=sum;
}
}
}
int main(){
for(ri q,tt=read();tt;--tt){
scanf("%s",a+1),n=strlen(a+1);
init();
q=read();
while(q--){
int l=read(),r=read(),lim=read(),ll=0,rr=r-l,res=r-l;
while(ll<=rr){
int mid=ll+rr>>1;
if(ans[l+mid][r-mid]<=lim)rr=mid-1,res=mid;
else ll=mid+1;
}
cout<<r-l+1-res*2<<'\n';
}
}
return 0;
}
I. Freddie’s Time Dimension(s)
卡了好久去想怎么统计nnn维立方体的各种量，最后30min30min30min准备打表强行过的时候发现自己完全想偏了，过了样例之后因为__int128CE\_\_int128CE__int128CE了两次心态爆炸，结果最后longlonglong longlonglong能过？摔。
直接利用期望的线性性，考虑拆开算每一天的期望值加起来就是答案，然后我们把它们归类。
把天看成格子，用组合数学统计出有i(0≤i≤d)i(0\le i\le d)i(0≤i≤d)维是并没有相邻格子的方案数，然后分别加起来即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int mod=1e9+7,N=1e5+5;
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
inline ll ksm(ll a,int p){ll ret=1;for(;p;p>>=1,a=a*a)if(p&1)ret=ret*a;return ret;}
inline void hj(ll&a,ll&b){ll g=__gcd(a,b);a/=g,b/=g;}
ll C[8][8];
inline void update(ll&a,ll&b,ll c,ll d){
ll sum1=a*d+b*c,sum2=b*d;
hj(sum1,sum2);
a=sum1,b=sum2;
}
int main(){
for(ri i=1;i<=7;++i)C[i][0]=1,C[i][1]=i;
for(ri i=2;i<=7;++i)for(ri j=2;j<=i;++j)C[i][j]=C[i-1][j]+C[i-1][j-1];
for(ri a,b,c,tt=1,up=read();tt<=up;++tt){
ll d=read(),n=read();
ll ans1=0,ans2=1;
for(ri i=1;i<=d;++i){
ll a,b;
a=C[d][i]*(1<<i)*ksm(n-2,d-i),b=2*d-i+1;
hj(a,b);
update(ans1,ans2,a,b);
}
update(ans1,ans2,ksm(n-2,d),2*d+1);
cout<<"Case "<<tt<<": "<<((long long)ans1)<<"/"<<((long long)ans2)<<'\n';
}
return 0;
}
J. Judges Always Win
这是一个博主由于太菜并不想也不能让自己填的一个坑，希望zxyoi能切掉