Codeforces Round #451 (Div. 2) 划水报告

本文主要是介绍Codeforces Round #451 (Div. 2) 划水报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A.Rounding
题意：给出一个数x,求出和x差值绝对值最小的,%10==0的数
贪心向上取整向下取整即可

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int A[200000+10];
int main(){//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int n;scanf("%d",&n);if(n%10==0)printf("%d\n",n);else if(n%10<=5)printf("%d\n",(n/10)*10);else printf("%d\n",(n/10+1)*10);
return 0;
}

B. Proper Nutrition
给出a,b,n
求 $a*x+b*y==n$ 的非负整数解
裸的扩展欧几里得

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int A[200000+10];
typedef long long ll;
inline void exgcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a;x=1;y=0;return ;}else {exgcd(b,a%b,d,y,x);y-=(a/b)*x;}
}
inline ll ab(ll x){return x<0?-x:x;
}
int main(){//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);ll n,a,b;scanf("%lld %lld %lld",&n,&a,&b);ll d,x,y;exgcd(a,b,d,x,y);//printf("%d\n",n%d);if(n%d!=0){puts("NO");return 0;}ll aa=a/d,bb=b/d;x*=(n/d),y*=(n/d);ll p=(x%bb+bb)%bb;ll tl=ab(x-p)/bb;if(x>p)y+=tl*aa;else y-=tl*aa;if(y>=0)printf("YES\n%lld %lld\n",p,y);else puts("NO");
return 0;
}

C. Phone Numbers
给出几段人名以及对应的几个字符串
将人名对应的字符串去重（若a为b的后缀a也算重复）输出
set判重，暴力判后缀

By Ostmbh, contest: Codeforces Round #451 (Div. 2), problem: (C) Phone Numbers, Accepted, ##include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
using namespace std;
map<string,int>m;
struct T{string nme;string B[310];int vis[310];int cnt;int tt;T(){cnt=0;memset(vis,0,sizeof(vis));}
}A[30];
int tot=0;
inline bool judge(int x,int y,int z){int ly=A[x].B[y].length(),lz=A[x].B[z].length();if(lz>ly)return false;int i=1;while(i<=lz&&A[x].B[y][ly-i]==A[x].B[z][lz-i])i++;if(i==lz+1)return true;return false;
}
int main(){//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int n;scanf("%d",&n);int x;string s;for(int i=1;i<=n;i++){cin>>s;if(!m[s])m[s]=++tot;int u=m[s];A[u].nme=s;scanf("%d",&x);for(int j=1;j<=x;j++)cin>>A[u].B[++A[u].cnt];}//printf("%d\n",tot);for(int i=1;i<=tot;i++){//printf("%d\n",A[i].cnt);for(int j=1;j<=A[i].cnt;j++)for(int k=1;k<=A[i].cnt;k++){if(j==k)continue;if(judge(i,j,k)&&A[i].B[j]!=A[i].B[k])A[i].vis[k]=1;else if(A[i].B[j]==A[i].B[k]){if(!A[i].vis[j]&&!A[i].vis[k])A[i].vis[k]=1;}}for(int j=1;j<=A[i].cnt;j++)if(!A[i].vis[j])A[i].tt++;}printf("%d\n",tot);for(int i=1;i<=tot;i++){cout<<A[i].nme<<' '<<A[i].tt<<' ';for(int j=1;j<=A[i].cnt;j++)if(!A[i].vis[j])cout<<A[i].B[j]<<' ';cout<<endl;}
return 0;
}

D. Alarm Clock
给出一串序列
问最少去除多少个数是的数轴上任意[x,x+m]区间内包括的序列中的数少于k个
排序+单调队列维护
在前面留数一定比在后面留优

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int A[200000+10];
queue<int>q;
int main(){//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int n,m,k;scanf("%d %d %d",&n,&m,&k);k--;if(k<=0){printf("%d\n",n);return 0;}for(int i=1;i<=n;i++)scanf("%d",&A[i]);sort(A+1,A+n+1);int now=2;q.push(1);int cnt=1;int ans=0;while(now<=n){int x=q.front();//printf("%d\n",x);while(now<=n){//printf("%d\n",A[now]);if(A[now]>=A[x]+m){q.push(now);cnt++;now++;break;}else {if(cnt<k){q.push(now);cnt++;}else ans++;now++;}}cnt--;q.pop();}printf("%d\n",ans);
return 0;
}

E. Squares and not squares
给出一个长度为偶数的序列
每次可以把一个数x改为x-1
求最少改多少次可以把这个序列变成一个恰好有一半是完全平方数
另一半不是
贪心先求一边完全平方数数量求出要补什么
然后把补得代价排序贪心取

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
typedef long long ll;
ll A[200000+10];
ll dl[200000+10];
ll bl[200000+10];
ll res[200000+10];
inline ll get_up(ll x){if(x==0)return 2;return 1;
}
inline ll get_sq(ll x){ll l=0,r=x;while(l+1<r){ll mid=(l+r)>>1;if(mid*mid>=x)r=mid;else l=mid;}if(r*r<=x)return r;return l;
}   
inline ll get_down(ll x){if(x==0)return dl[0];if(x==1)return dl[0];return 1;
}
int main(){freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int n;scanf("%d",&n);int nw=0;memset(bl,127,sizeof(bl));memset(dl,127,sizeof(dl));//printf("%lld\n",bl[0]);for(int i=1;i<=n;i++){scanf("%lld",&A[i]);ll td=get_sq(A[i]);if(td*td==A[i]){nw++;bl[i]=min(get_up(td),get_down(td));}else {dl[i]=min(A[i]-td*td,(td+1)*(td+1)-A[i]);//变成完全平方数的代}}int u=n-nw;if(u==nw){puts("0");return 0;}long long ans=0;if(u>nw){int res=(u-nw)/2;sort(dl+1,dl+n+1);for(int i=1;i<=res;i++)ans+=dl[i];}else {int res=(nw-u)/2;//printf("%d\n",res);sort(bl+1,bl+n+1);for(int i=1;i<=res;i++)ans+=bl[i];}cout<<ans<<endl;
return 0;
}