layout: post title: Codeforces Round 262 (Div. 2) author: "luowentaoaa" catalog: true tags: mathjax:
... .
layout: post
title: Codeforces Round 262 (Div. 2)
author: "luowentaoaa"
catalog: true
tags:
mathjax: true
- codeforces
- 暴力
- 二分
传送门
A - Vasya and Socks (签到)
题意
你有n个袜子每天必须穿一个，然后你妈每m天又给你买一个
问你几能连续几天有袜子穿
思路
直接模拟
#include<bits/stdc++.h>using namespace std;typedef long long ll;const ll mod=1e9+7;const int maxn=2e5+50;const ll inf=1e17;typedef unsigned long long ull;int main(){ int n,m; scanf("%d%d",&n,&m); int sum=n,k=0; while(n>=m){ n-=m; n++; sum++; } printf("%d/n",sum); return 0;} B - Little Dima and Equation (暴力)
题意
给你一个式子/(x=b*s(x)^a+c/) 其中/(s(x)/)代表x的每一位数的和
给你abc 让你找出所有的x
思路
因为x最多只有1e9所以s(x)最大只有81 所以直接枚举带入看是否正确
#include<bits/stdc++.h>using namespace std;typedef long long ll;const ll mod=1e9+7;const int maxn=2e5+50;const ll inf=1e17;typedef unsigned long long ull;vector<ll>ve;bool check(ll sum,ll i){ ll ans=0; while(sum){ ans+=sum%10; sum/=10; } return ans==i;}int main(){ ll a,b,c; scanf("%lld%lld%lld",&a,&b,&c); for(ll i=1;i<81;i++){ ll num=i; for(int j=1;j<a;j++)num*=i; ll sum=b*num+c; if(check(sum,i)&&sum>0&&sum<1e9)ve.push_back(sum); } printf("%d/n",ve.size()); for(int i=0;i<ve.size();i++)printf("%d ",ve[i]); return 0;} C - Present （二分+差分）
题意
你种了一排花每个花都有自己的高度，你每天可以给连续的w个花浇水让他们高度+1问你在m天内给花浇水 并且得到的花的最矮高度最大
思路
最大最小值就是二分。
枚举答案（高度）然后把低于这个高度的和他以后都浇水，然后判断天数是否足够。
区间加法可以用差分o(1)计算
#include<bits/stdc++.h>using namespace std;typedef long long ll;const ll mod=1e9+7;const int maxn=2e5+50;const ll inf=1e17;typedef unsigned long long ull;ll n,m,w;ll a[maxn];ll sum[maxn];bool check(ll mid){ memset(sum,sizeof(sum)); ll p=m; for(int i=1;i<=n;i++){ sum[i]+=sum[i-1]; if(sum[i]+a[i]<mid){ p-=mid-(sum[i]+a[i]);sum[i+w]-=mid-(sum[i]+a[i]); sum[i]+=mid-(sum[i]+a[i]); } } return p>=0;}int main(){ scanf("%lld%lld%lld",&m,&w); for(int i=1;i<=n;i++)scanf("%lld",&a[i]); ll l=0,r=1e15,ans=0; while(l<=r){ ll mid=(l+r)>>1; if(check(mid)){ ans=mid; l=mid+1; } else r=mid-1; } printf("%lld/n",ans); return 0;} D - Little Victor and Set (构造)
题意
输入/(l,r,k (1/leq l /leq r /leq10^{12};1/leq k /leq min(1e6,r-l+1))/)
从[l,r]选至多k个数使得选出的数的异或值最小，输出最小异或值和方案。
思路
分类讨论，首先如果r-l+1<=4，枚举集合解决之。
先面讨论r-l+1>=5的情况：
此时有至少5个数可以选择，故至少有连续的4个数满足2x,2x+1,2x+2,2x+3。
k=1时显然方案为{l}。k==2时，显然方案为{2x,2x+1}。k>=4时，显然方案为{2x,2x+3}。
k==3时再另外考虑：
首先，异或值至多为1（参考k==2）
我们现在来找异或值可否为0。先假设可以，则显然是选3个数。不妨设x>y>z。
111...1111
111...1110
000...0001
显然x,y,z前半部分必定是如上这样的，但由于我们要使得x,z尽量靠近，所以x,z前半部分必然是如下
11
10
01
之后，每添加一位，有可能是yi=zi=1,xi=0或xi=zi=1,yi=0或xi=yi=1,zi=0。
由于要x,z尽量靠近，所以显然采取yi=zi=1,zi=0。
所以x,z的二进制形式如下
110...0
101...1
011...1
#include<bits/stdc++.h>using namespace std;typedef long long ll;const ll mod=1e9+7;const int maxn=2e6+50;const ll inf=1e17;typedef unsigned long long ull;int cnt(int i){ int ans=0; while(i)i-=i&(-i),ans++; return ans;}int main(){ ll l,k; scanf("%lld%lld%lld",&l,&r,&k); if(r-l+1<5){ int n=r-l+1; ll ans=inf; vector<ll>val; for(int i=1;i<(1<<n);i++){ ll x=0; for(int j=0;j<n;j++) if(i&(1<<j))x^=(l+j); if(x<ans&&cnt(i)<=k){ ans=x; val.clear(); for(int j=0;j<n;j++)if(i&(1<<j))val.push_back(l+j); } } cout<<ans<<endl; cout<<val.size()<<endl; for(int i=0;i<val.size();i++)cout<<val[i]<<" "; } else{ if(k==1)cout<<l<<endl<<1<<endl<<l<<endl,exit(0); if(k==2){ if(l&1)l++; cout<<1<<endl<<2<<endl<<l<<" "<<l+1<<endl; exit(0); } if(k>=4){ if(l&1)l++; cout<<0<<endl<<4<<endl; for(int i=0;i<4;i++)cout<<l+i<<" "; } else{ ll x=-1,z; for(ll i=3;i<=r;i<<=1){ if((i^(i-1))>=l){ x=i; y=i-1; z=i^(i-1);break; } } if(x==-1){ if(l&1)l++; cout<<1<<endl<<2<<endl<<l<<" "<<l+1<<endl; exit(0); } else{ cout<<"0"<<endl; cout<<3<<endl; cout<<x<<" "<<y<<" "<<z<<endl; } } } return 0;} E - Roland and Rose (几何+暴力)
题意
让你在距离圆心/(r/)的距离中选n个整点 使得这/(n/)个点的两两欧几里得距离平方和最大
思路
直接枚举距离圆心最远的点然后暴力判断...不会证明。。
#include<bits/stdc++.h>using namespace std;typedef long long ll;const ll mod=1e9+7;const int maxn=2e6+50;const ll inf=1e17;typedef unsigned long long ull;struct Point{ int x,y;};int N,R,M,ans;vector<Point>vec;vector<int>anw,now;int dis(int x,int y){ return x*x+y*y;}bool cmp(Point a,Point b){ return dis(a.x,a.y)>dis(b.x,b.y);}void dfs(int cnt,int in,int value){ if(cnt==N){ if(value>ans){ ans=value; anw=now; } return; } for(int i=in;i<M;i++){ int res=0; for(int j=0;j<cnt;j++) res+=dis(vec[now[j]].x-vec[i].x,vec[now[j]].y-vec[i].y); now.push_back(i); dfs(cnt+1,i,value+res); now.pop_back(); }}int main(){ scanf("%d%d",&N,&R); for(int i=-R;i<=R;i++){ for(int j=-R;j<=R;j++){ if(i*i+j*j<=R*R) vec.push_back(Point{i,j}); } } ans=0; M=min((int)vec.size(),18); sort(vec.begin(),vec.end(),cmp); dfs(0,0); printf("%d/n",ans); for(int i=0;i<N;i++) printf("%d %d/n",vec[anw[i]].x,vec[anw[i]].y); return 0;} . .. ...
