Google Kick Start Round G 2019

Book Reading

暴力，没啥好说的

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e5+5;

int n,m,q,p[maxn],r[maxn];

int cnt[maxn];

int main()

{

	int T,Case=1;

	scanf("%d",&T);

	while(T--){

		scanf("%d %d %d",&n,&m,&q);

		for(int i=1;i<=n;i++)cnt[i]=0;

		for(int i=1;i<=m;i++){

			scanf("%d",&p[i]);

			int ub=sqrt(p[i]);

			for(int j=1;j<=ub;j++){

				if(p[i]%j==0){

					++cnt[j];

					if(j*j!=p[i])++cnt[p[i]/j];

				}

			}

		}

		ll ans=0;

		for(int i=1;i<=q;i++){

			scanf("%d",&r[i]);

			ans=ans+n/r[i]-cnt[r[i]];

		}

		printf("Case #%d: %lld\n",Case++,ans);

	}

    return 0;

}

The Equation

题意

给定数组A和整数M\((0 \leq A_i \leq 10^{15},0 \leq M \leq 10^{15})\)，求使得\(\sum_{i=1}^n(A_i xor k) \leq M\)成立的k的最大值。

解题思路

从k的二进制高位开始贪心，尽可能的选1，选1的条件是目前为止的高位和，加上之后低位和的最小值小于\(M\)。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=70;

int n,cnt[N];

ll m,sum[N],s;

ll a[1005];

int main()

{

	int T,Case=1;

	scanf("%d",&T);

	while(T--){

		for(int i=0;i<=62;i++)cnt[i]=0;

		s=0;

		scanf("%d %lld",&n,&m);

		for(int i=1;i<=n;i++)scanf("%lld",&a[i]),s+=a[i];

		for(int i=1;i<=n;i++)

			for(int j=0;j<=62;j++)

				if(a[i]&(1ll<<j))cnt[j]++;

		for(int i=0;i<=62;i++){

			if((1ll<<i)>2e15)break;

			sum[i]=(i-1>=0?sum[i-1]:0)+(1ll<<i)*min(cnt[i],n-cnt[i]);

		}

		ll k=0,cur=0;

		for(int i=62;i>=0;i--){

			if((1ll<<i)>2e15)continue;

			ll d=(n-cnt[i])*(1ll<<i);

			if(cur+(i-1>=0?sum[i-1]:0)+d<=m){

				k+=(1ll<<i);

				cur+=(n-cnt[i])*(1ll<<i);

			}

			else{

				cur+=cnt[i]*(1ll<<i);

			}

		}

		if(k==0)k=(s<=m?0:-1);

		printf("Case #%d: %lld\n",Case++,k);

	}

    return 0;

}

Shifts

题意

给定长度为\(n(n \leq 20)\)的数组A和B，对于每个下标\(i\)，至少选取\(A_i\)和\(B_i\)中的一个，问有多少种选法使得选中的\(A_i\)的和以及\(B_i\)的和都大于给定整数\(h\)。

解题思路

将n等分为两份，分别dfs求出所有可能得到的和，问题就转化为了二维偏序，离散化后树状数组即可求解。复杂度\(O(3^{10}log3^{10})\)

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e5+5;

const int maxl=1e5+5;

int n,n1,n2;

ll h,ans;

int a[30],b[30];

struct node{ll x,y;int t;};

bool cmp(node p,node q){

	if(p.x!=q.x)return p.x>q.x;

	if(p.y!=q.y)return p.y>q.y;

	return p.t<q.t;

}

node p[maxl<<1];

int cnt;

ll t[maxl<<2],m;

//BIT

	ll c[maxl<<2];

	ll lb(ll x){return x&(-x);}

	void add(ll x,ll d){for(;x<m;x+=lb(x))c[x]+=d;}

	ll getsum(ll x){ll r=0;for(;x;x-=lb(x))r+=c[x];return r;}	

void dfs1(int x,ll sa,ll sb){

	if(x==n1+1){

		p[++cnt]=(node){sa,sb,0};

		t[++m]=sa;t[++m]=sb;

		return;

	}

	dfs1(x+1,sa+a[x],sb);

	dfs1(x+1,sa,sb+b[x]);

	dfs1(x+1,sa+a[x],sb+b[x]);

}

void dfs2(int x,ll sa,ll sb){

	if(x==n+1){

		p[++cnt]=(node){h-sa,h-sb-1,1};

		t[++m]=h-sa;t[++m]=h-sb-1;

		return;

	}

	dfs2(x+1,sa+a[x],sb);

	dfs2(x+1,sa,sb+b[x]);

	dfs2(x+1,sa+a[x],sb+b[x]);

}

int main()

{

//#ifndef ONLINE_JUDGE

//	freopen("in.txt","r",stdin);

//#endif

	int T,Case=1;

	scanf("%d",&T);

	while(T--){

		cnt=0; m=0; ans=0;

		scanf("%d %lld",&n,&h);

		n1=n/2; n2=n-n1;

		for(int i=1;i<=n;++i)scanf("%d",&a[i]);

		for(int i=1;i<=n;++i)scanf("%d",&b[i]);

		dfs1(1,0,0);

		dfs2(n1+1,0,0);

		sort(t+1,t+1+m);

		m=unique(t+1,t+1+m)-(t+1);

		vector<int>op;

		ll count=0;

		sort(p+1,p+1+cnt,cmp);

		for(int i=1;i<=cnt;i++){

			if(p[i].t){

				int id=lower_bound(t+1,t+1+m,p[i].y)-t;

				ans+=(count-getsum(id));

			}

			else{

				int id=lower_bound(t+1,t+1+m,p[i].y)-t;

				add(id,1);

				op.push_back(id);

				count++;

			}

		}

		printf("Case #%d: %lld\n",Case++,ans);

		for(int id:op)add(id,-1);

	}

    return 0;

}

巴特西

Google Kick Start Round G 2019

Google Kick Start Round G 2019

Book Reading

The Equation

题意

解题思路

Shifts

题意

解题思路

最新文章

热门文章