Defuse the Bombs
听说是公司面试题，答案满足二分性质，直接二分check（对于每个ai***桶在x的时间段，要么有ti时间一直在降低，x-ti时间在保持不变.贪心让不变的时间尽可能少。)
本题坑点：二分右边界设置1e10(设置太大直接爆long long WA)
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
typedef long long ll;
ll a[maxn],b[maxn];
ll n;
bool check( ll x )
{
ll t1=0;
for( int i=1;i<=n;i++ )
{
if( a[i]<x ) t1+=x-a[i];
}
return t1<=x;
}
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
ll t;
scanf("%lld",&t);
int cas=1;
while( t-- )
{
scanf("%d",&n);
ll l=0,r=1e10;
for( int i=1;i<=n;i++ ) scanf("%lld",&a[i]);
// sort(a+1,a+1+n);
ll ans=0;
while( l<=r )
{
ll mid=l+r>>1;
if( check(mid) )
{
ans=mid,l=mid+1;
}
else r=mid-1;
}
printf("Case #%d: %lld\n",cas++,ans+1);
}
}
Game of Cards
博弈没思路就上sg，三维sg分别记录0,1,2的个数。
看着sg表推规律，具体看代码~~.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=50+10;
int sg[maxn][maxn][maxn];
void init()
{
sg[0][0][1]=0;
sg[0][1][0]=0;
sg[1][0][0]=0;
sg[0][0][0]=0;
for( int i=0;i<=maxn-1;i++ )
{
for( int j=0;j<=maxn-1;j++ )
{
for( int k=0;k<=maxn-1;k++ )
{
bool vis[100]={false};
if( i>=1 ) vis[sg[i-1][j][k]]=true;
if( j>1 ) vis[sg[i][j-2][k+1]]=true;
if( j && k ) vis[sg[i][j-1][k-1]]=true;
int t=0;
while( vis[t] ) t++;
sg[i][j][k]=t;
}
}
}
for( int i=0;i<=20;i++ )
{
for( int j=0;j<=20;j++ )
{
for( int k=0;k<=2;k++ )// k<=2 因为 k>=2 的sg值都相同
{
cout<<i<<" "<<j<<" "<<k<<" "<<sg[i][j][k]<<"\n";
}
}
}
}
int main()
{
// init(); //此打表 默认0在任何时候都可以减一
int t,cas=1;
scanf("%d",&t);
while( t-- )
{
ll a,b,c,d;
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
printf("Case #%d: ",cas++);
if( a+b+c+d<2 )
{
printf("Horse\n");
continue;
}
if( b==0 && c==0 && d==0 )
{
if( a&1 ) puts("Horse");
else puts("Rabbit");
continue;
}
int f=1;
if( a%2==0 )
{
if( b%3==0 ) f=0;
else if( b%3==1 && c==0 ) f=0;
}else
{
if( b%3==1 && c>0 ) f=0;
else if( b%3==2 && c<=1 ) f=0;
}
if( f ) puts("Rabbit");
else puts("Horse");
}
return 0;
}
Joy of Handcraft
稍微算一下用线段树暴力区间更新和单点查询，复杂度为O(nlognlogn)可以过。直接码。
#include<bits/stdc++.h>
using namespace std;
#define ls cur<<1
#define rs cur<<1|1
#define lowbit(x) x&(-x)
const int maxn=1e6+10;
const int inf=0x3f3f3f3f;
typedef long long ll;
ll lazy[maxn],mx[maxn],sum[maxn];
ll a[maxn],b[maxn];
void pushup( int cur )
{
mx[cur]=max(mx[ls],mx[rs]);
}
void pushdown( int cur )
{
if( lazy[cur]==0 ) return;
mx[ls]=max(mx[ls],lazy[cur]);lazy[ls]=max(lazy[cur],lazy[ls]);
mx[rs]=max(mx[rs],lazy[cur]);lazy[rs]=max(lazy[cur],lazy[rs]);
lazy[cur]=0;
}
void build( int cur,int l,int r )
{
lazy[cur]=0;
if( l==r )
{
mx[cur]=0;
return;
}
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(cur);
}
void update( int cur,int l,int r,int ql,int qr,ll c )
{
if( ql<=l && r<=qr )
{
mx[cur]=max(c,mx[cur]);
lazy[cur]=max(c,lazy[cur]);
return;
}
pushdown(cur);
int mid=l+r>>1;
if( ql<=mid ) update(ls,l,mid,ql,qr,c);
if( qr>mid ) update(rs,mid+1,r,ql,qr,c);
pushup(cur);
}
ll query( int cur,int l,int r,int ql,int qr )
{
if( ql<=l && r<=qr ) return mx[cur];
pushdown(cur);
ll res=-1e18;
int mid=l+r>>1;
if( ql<=mid ) res=max(res, query(ls,l,mid,ql,qr) );
if( qr>mid ) res=max( res , query(rs,mid+1,r,ql,qr) );
return res;
}
int mp[100005];
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
int t,cas=1;
scanf("%d",&t);
while( t-- )
{
int n,m;
scanf("%d%d",&n,&m);
build(1,1,m);
for( int i=1;i<=m;i++ ) mp[i]=0;
for( int i=1;i<=n;i++ )
{
int ti,xi;
scanf("%d%d",&ti,&xi);
if( ti>=m ) ti=m;
mp[ti]=max(mp[ti],xi);
}
for( int i=1;i<=m;i++ )
{
if( mp[i] )
{
int j;
for( j=i;j<=m;j+=2*i )
{
update(1,1,m,j-i+1,j,mp[i]);
}
if( j-i+1<=m )
{
update(1,1,m,j-i+1,m,mp[i]);
}
}
}
printf("Case #%d: ",cas++);
for( int i=1;i<=m;i++ )
{
printf("%d",query(1,1,m,i,i));
if( i==m )puts("");
else printf(" ");
}
}
}
Knowledge is Power
这道题很多做法是找规律，我是直接暴力分两个数或者三个数，直接搜更新。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
typedef long long ll;
ll a[maxn],b[maxn];
int main()
{
a[2]=-1,a[3]=-1,a[4]=-1,a[5]=1,a[6]=-1,a[7]=1;
int n;
int t,cas=1;
scanf("%d",&t);
while( t-- )
{
scanf("%d",&n);
if( n<=7 ) printf("Case #%d: %d\n",cas++,a[n]);
else
{
if( n&1 )
{
printf("Case #%d: 1\n",cas++);
}
else
{
if( (n/2)%2==0 )
{
printf("Case #%d: 2\n",cas++);
}
else
{
int ans=1e9;
for( int i=max(n/2-5,2);i<=min(n/2+5,n-2);i++ )
{
if( __gcd(n,n-i)==1 ) ans=min( ans,abs(n-2*i) );
}
int l1=max(n/3-5,2),r1=min(n/3+5,n-4);
int l2=max(n/3-5,2),r2=min(n/3+5,n-4);
for( int i=max(n/3-5,2);i<=min(n/3+5,n-4);i++ )
{
for( int j=max(n/3-5,2);i+j<=n-2 && j<=min(n/3+5,n-4);j++ )
{
int d=n-i-j;
if( __gcd(i,j)==1 && __gcd(i,d)==1 && __gcd(j,d)==1 )
{
int c1=max(i,max(d,j));
int c2=min(i,min(d,j));
ans=min(ans,abs(c2-c1));
}
}
}
if( ans==1e9 ) ans=-1;
printf("Case #%d: %d\n",cas++,ans);
}
}
}
}
}
/*
1
8275722
*/ Lottery
参考博客
https://blog.csdn.net/weixin_44216117/article/details/109545197
本题计算方法肯定类似二进制。如果有k个位置可以填1那么不同的数字就是 个.
然后考虑给定的若干个 ,2个
可以变成一个
,3个
可以组合成1个
和1个
。并且如果对于位置k只有2个
并且高一位
的个数为0，把当前这一位组合成
或者就保留成2个
对答案的贡献都是乘2，所以我们只有当个数大于2的时候才进行进位组合。
然后我们从小到大枚举位数，累加每位的个数，按上述规则进位，可以得到一段一段连续的非零数字串。例如：1,2,1,1,2.为一段连续的二进制每位的个数。首先可以表示 种数字，然后根据规律（将连续非零位置的数字减去1的获得的二进制数就是组合可以多出这个二进制表示的个数），获得
,那么答案计算为：
。这个是这一段能表示的数的答案，将每一个这样的段结果乘起来就是最终答案。(
规律我还不会证明
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
const int mod=1e9+7;
struct node{
ll a,x;
bool operator<(const node A) const {
return a < A.a;//按次方排序
}
}p[maxn];
// 对于每个二进制数
int main()
{
int t,cas=1;
scanf("%d",&t);
while( t-- )
{
int n;scanf("%d",&n);
for( int i=0;i<n;i++ )
{
scanf("%d%d",&p[i].a,&p[i].x);
}
sort(p,p+n);
ll sum=1,now=0,res=1,idx=0,tmp=0,add=0;
while( true )
{
if( p[idx] .a==now ) tmp+=p[idx++].x;
if( idx!=n && tmp==0 )
{
sum=(sum+add)%mod;
res=res*sum%mod;
sum=1,add=0;
tmp=p[idx].x;
now=p[idx++].a;
}
if( idx==n && tmp==0 )
{
sum=(sum+add)%mod;
res=res*sum%mod;
break;
}
if( tmp )
{
if( tmp%2==0 ) add=(add+sum)%mod;
sum=sum*2%mod;
now++;
tmp=(tmp-1)>>1;
}
}
printf("Case #%d: %lld\n",cas++,res);
}
}
京公网安备 11010502036488号