牛客周赛 Round 101 - 牛客题解 | 123hh2 = Keep moving forward

# 牛客周赛 Round 101

比赛链接

调用自带的 $log$ 函数，默认以 $e$ 为基底

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	signed main()
	{
	double k=read();
	cout<<fixed<<setprecision(6)<<150.0*log(k);
	return _123hh2;
	}

对每个要求考虑消耗量即可

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	signed main()
	{
	int n=read();
	cout<<2floor(n/5)<<" "<<floor((floor(n/5)+1)/2)<<" "<<3floor(n/20)<<" "<<2*(n-floor(n/20));
	return _123hh2;
	}

由于是按位异或操作，不难发现能得到的最大整数一定是从给定上界的最高位到最低位都赋值为 1

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	const int maxn=1e5+5;
	signed main()
	{
	int n=read();
	int maxx=0;
	while(n) n/=2,maxx++;
	cout<<(1ll<<maxx)-1;
	return _123hh2;
	}

既然需要每个区间的元素 $gcd$ 按位异或起来等于整数 $m$ ，不妨先将 $m$ 按二进制拆分

我们把拆出来的数分别看作一个区间，这些区间按位异或起来就是 $m$

如果 $m$ 是奇数，剩下的区间合并进拆出来的 1，否则剩下的区间必然会改变原有的状态，即无解

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	const int maxn=1e5+5;
	int awa[31],n,m;
	void pre()
	{
	awa[0]=1;
	for(int i=1;i<=30;i++) awa[i]=awa[i-1]*2;
	}
	int ans[31],vis[maxn];
	signed main()
	{
	n=read(),m=read();
	if(m%2==0) {cout<<-1;return 0;}
	pre();
	int cnt=0,f=1;
	for(int i=30;i>=1;i--)
	{
	if(m&(1ll<<i))

	if((1ll<<i)>n) {f=0;break;}
	else
	{
	ans[++cnt]=(1ll<<i);
	vis[(1ll<<i)]=1;
	}
	}
	}
	if(!f) {cout<<-1;return 0;}
	for(int i=1;i<=n;i++) if(vis[i]) cout<<i<<" ";
	for(int i=1;i<=n;i++) if(!vis[i]) cout<<i<<" ";
	cout<<endl;
	cout<<cnt+1<<endl;
	for(int i=1;i<=cnt;i++) cout<<i<<" "<<i<<endl;
	cout<<cnt+1<<" "<<n;
	return _123hh2;
	}

不难发现路径顺序是固定的，我们只需要关系每两个点之间的耗时

设缩放屏幕的时间为 $k$ ，那么距离变成 $\fracdis} {2(k)$ ，总时间花费为 $2 \times k + \fracdis} {2({k+1)} $

显然 / 求导看出这是一个单峰函数

用三分法解决即可

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	const int maxn=1e5+5;
	double x[maxn],y[maxn];
	double eps=1e-9;
	double f(double mid,double dis)
	{
	return 2.0mid+2dis/pow(2,mid);
	}
	signed main()
	{
	int n=read();double ans=0;
	for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
	for(int i=2;i<=n;i++)
	{
	double dis=sqrt((x[i]-x[i-1])(x[i]-x[i-1])+(y[i]-y[i-1])(y[i]-y[i-1]));
	double L=0,R=dis/2.0;
	while(R-L>eps)
	{
	double k=(R-L)/3.0;
	double mid1=L+k,mid2=R-k;
	if(f(mid1,dis)<f(mid2,dis)) R=mid2;
	else L=mid1;
	}
	ans+=f(L,dis);
	}
	cout<<fixed<<setprecision(9)<<ans;
	return _123hh2;
	}

本次计算的结果会变成下一次计算的指数，不难发现 $k$ 的值很大但是 $mod$ 的值被限定到了 $10^6$

从 $mod$ 入手，不难发现计算结果最多有 $mod$ 种

所以必然存在循环节

那么我们只需要暴力模拟最多 $10^6$ 次计算，找出循环节后根据循环节计算答案即可

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	const int maxn=1e6+5;
	int awa[maxn],vis[maxn];
	int ans[maxn],qzh[maxn];
	int base,c0,mod;
	int bg,ed;
	int fstpow(int n,int m)
	{
	if(m==0) return 1;
	int ans=1,base=n%mod;
	while(m)
	{
	if(m&1) ans*=base,ans%=mod;
	m>>=1,base*=base,base%=mod;
	}
	return ans;
	}
	void pre()
	{
	int cnt=0;
	while(1)
	{
	int c=fstpow(base,c0);
	if(vis[c])
	{
	bg=vis[c],ed=cnt;
	break;
	}
	awa[++cnt]=c;
	qzh[cnt]=qzh[cnt-1]+awa[cnt];
	qzh[cnt]%=mod;
	vis[c]=cnt;
	c0=c;
	}
	}
	int mul(int a,int b)
	{
	int ans=0;
	while(b)
	{
	if(b&1) ans+=a,ans%=mod;
	a<<=1,b>>=1,a%=mod;
	}
	return ans;
	}
	void deal(int q)
	{
	if(q<=ed)
	{
	write(qzh[q]),puts("");
	return;
	}
	else
	{
	int sum=qzh[ed];
	q-=ed;
	int c=q/(ed-bg+1);
	sum+=(c%mod)*((qzh[ed]-qzh[bg-1]+mod)%mod);
	sum%=mod;
	q-=c*(ed-bg+1);
	sum+=(qzh[bg+q-1]-qzh[bg-1]+mod)%mod;
	sum%=mod;
	write(sum),puts("");
	}
	}
	signed main()
	{
	base=read(),c0=read(),mod=read();
	pre();
	int t=read();
	while(t-->0)
	{
	int q=read();
	deal(q);
	}
	return _123hh2;
	}