codeforces 732套题题解
Codeforces Round #377 (Div. 2)
这是原来的比赛：打CF打得多了之后，发现CF上分的秘诀有三个：
手速+暴力+模拟
DIV2场的AB基本送分题，C和D一般都是用简单的STL来维护几个数学值，然后用数学结论或者公式什么的搞一搞
然后E题呢，给足够的时间推推过程，其实是有可能做的
这场的6个题在补题之后写了5个
A. Buy a Shovel
这个题有个小小的坑点：注意多了一个单位价值为c的硬币：所以还有可能价值对10取余为c（当然这个坑点在样例中已经有了）
while(scanf("%d%d",&a,&b)!=EOF){
for(int ans=1;ans<=10;ans++){
int sum=a*ans;
if (sum%10==0||sum%10==b){
printf("%d\n",ans);
break;
}
}
}因为最多买10个（这样肯定可以被10整除了，余数为0）暴力就好
B. Cormen — The Best Friend Of a Man
要求连续两个数的和不小于K 那么：添加数的方案很简单：如果连续两个数的和小于K了，那么在后面那个数上补足（因为这个可以影响到第三个数）
代码：
while(scanf("%d%d",&n,&k)!=EOF){
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
tot=0;
for(int i=2;i<=n;i++)
if (a[i]+a[i-1]>=k) continue;
else{
add=k-a[i]-a[i-1];
tot+=add;
a[i]+=add;
}
printf("%d\n",tot);
for(int i=1;i<=n;i++)
printf("%d%c",a[i],i==n?'\n':' ');
} C. Sanatorium
这个题是个很好的题：怎么去理解这个题的意思
早上出发晚上吃饭吃完后回来……等等，这样可以列出七种情况，枚举一下就好
#include<bits/stdc++.h>
using namespace std;
#define LL __int64
LL a,b,c;
const LL INF=1e19;
LL calc(LL x,LL y,LL z){
LL Max=max(x,max(y,z));
return 3*Max-(x+y+z);
}
int main(){
while(scanf("%I64d%I64d%I64d",&a,&b,&c)!=EOF){
LL ans=INF;
ans=min(ans,calc(a,b,c));
ans=min(ans,calc(a+1,b,c));
ans=min(ans,calc(a,b+1,c));
ans=min(ans,calc(a,b,c+1));
if (a>0)
ans=min(ans,calc(a-1,b,c));
if (b>0)
ans=min(ans,calc(a,b-1,c));
if (c>0)
ans=min(ans,calc(a,b,c-1));
cout<<ans<<endl;
}
return 0;
}
D. Exams
经典的二分好题：判断连续K天是不是可行（这个复杂度是log（n））
因为第i科要在数组中的值为i的天数的时候考试，那么直接暴力一发即可（这个复杂度是O（n））
所以乘起来时间是够的
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+50;
int n,m;
int a[maxn];
int b[maxn];
struct node{
int Time;
int sub;
}c[maxn];
int cmp(node x,node y){
return x.Time<y.Time;
}
bool calc(int x){
int lefttime=0;
memset(c,0,sizeof(c));
for(int i=1;i<=x;i++)
if (a[i]){
c[a[i]].sub=a[i];
c[a[i]].Time=i;
}
for(int i=1;i<=m;i++)
if (!c[i].Time) return false;
sort(c+1,c+m+1,cmp);
//for(int i=1;i<=m;i++)
// printf("%d %d%c",c[i].sub,c[i].Time,i==m?'\n':' ');
for(int i=1;i<=m;i++){
lefttime+=c[i].Time-c[i-1].Time-1;
if (lefttime<b[c[i].sub]) return false;
lefttime-=b[c[i].sub];
}
return true;
}
int main(){
//freopen("input.txt","r",stdin);
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++) scanf("%d",&b[i]);
int L,R,mid,ans=-1;
if (!calc(n)){
printf("%d\n",ans);
continue;
}
L=1;R=n-1;ans=n;
while(L<=R){
mid=(L+R)>>1;
if (calc(mid)){
ans=mid;
R=mid-1;
}
else L=mid+1;
}
printf("%d\n",ans);
}
return 0;
}
E. Sockets
读题读完之后就是个暴力题，但是怎么暴力：有技巧
把每个火箭的值放进去查询，如果有，那么匹配，如果没有，就不断的（+1）/2，直到匹配或者到1为止
所以要用到STL的multiset来搞
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+50;
int a[maxn],b[maxn];
int n,m;
multiset<pair<int,int> > p;
multiset<pair<int,int> > s;
multiset<pair<int,int> >::iterator it;
multiset<pair<int,int> >::iterator iter;
int main(){
cin>>n>>m;
int x;
for(int i=1;i<=n;i++){
cin>>x;
p.insert(make_pair(x,i));
}
for(int i=1;i<=m;i++){
cin>>x;
s.insert(make_pair(x,i));
}
for(it=s.begin();it!=s.end();++it){
int value=it->first;
int index=it->second;
int tmp=0;
while(1){
iter=p.lower_bound(make_pair(value,-1));
if (iter!=p.end()&&(iter->first)==value){
a[index]=tmp;
b[iter->second]=index;
p.erase(iter);
break;
}
if (value==1) break;
value=(value+1)/2;
tmp++;
}
}
int ans=0;
for(int i=1;i<=n;i++)
if (b[i]) ans++;
cout<<ans<<" ";
ans=0;
for(int i=1;i<=m;i++)
ans+=a[i];
cout<<ans<<endl;
for(int i=1;i<=m;i++)
printf("%d%c",a[i],i==m?'\n':' ');
for(int i=1;i<=n;i++)
printf("%d%c",b[i],i==n?'\n':' ');
return 0;
}
