# Codeforces Round #615 (Div. 3) 题解

2019/04/10 10:10

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
ll max(ll a,ll b) {if(a>b) return a;return b;}
int main()
{
int t;
scanf("%d",&t);
while(t--){
int a[3],n;
scanf("%d%d%d%d",&a[0],&a[1],&a[2],&n);
sort(a,a+3);
int x=(a[2]-a[1])*2+a[1]-a[0];
if(x>n) cout<<"NO"<<endl;
else{
if((n-x)%3)    cout<<"NO"<<endl;
else    cout<<"YES"<<endl;
}
}
return 0;
}

B - Collecting Packages

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
ll max(ll a,ll b) {if(a>b) return a;return b;}
const int maxn=1005;
struct node{
int x,y;
}a[maxn];
int cmp(node a,node b)
{
if(a.x==b.x)  return a.y<b.y;
return a.x<b.x;
}
int main()
{
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=0;i<n;i++)    scanf("%d%d",&a[i].x,&a[i].y);
sort(a,a+n,cmp);
int flag=0;
for(int i=1;i<n;i++){
if(a[i].y<a[i-1].y){
cout<<"NO"<<endl;
flag=1;
break;
}
}
if(!flag){
cout<<"YES"<<endl;
for(int i=0;i<a[0].x;i++) cout<<"R";
for(int i=0;i<a[0].y;i++) cout<<"U";
for(int i=1;i<n;i++){
for(int j=a[i-1].x;j<a[i].x;j++) cout<<"R";
for(int j=a[i-1].y;j<a[i].y;j++) cout<<"U";
}
cout<<endl;
}
}
return 0;
}

C - Product of Three Numbers

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
vector<int> a;
typedef long long ll;
int main()
{
int n,t;
scanf("%d",&t);
while(t--){
int cnt=0;
a.clear();
scanf("%d",&n);
for(ll i=2;i*i<=n;i++){
if(n%i==0){
a.push_back(i);
cnt++;
n/=i;
}
if(cnt==3) break;
}
if(n!=1){
if(a.size()==3) a.back()*=n;
else    a.push_back(n);
}
if(a.size()<3) cout<<"NO"<<endl;
else{
if(a[0]==a[1]||a[1]==a[2]||a[0]==a[2])    cout<<"NO"<<endl;
else    cout<<"YES"<<endl,cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
}
}
return 0;
}

D - MEX maximizing

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=4e5+10;
int a[maxn];
int main()
{
int n,x,tem,t=0;
scanf("%d%d",&n,&x);
while(n--){
int tem;
scanf("%d",&tem);
a[tem%x]++;
while(a[t%x]){
a[t%x]--;
t++;
}
cout<<t<<endl;
}
return 0;
}

E. -  Obtain a Permutation

题意：

#include<iostream>
#include<algorithm>
#include<cstring>
#define inf 0x3f3f3f3f
#include<vector>
using namespace std;
typedef long long ll;
const int maxn1=2e4+10;
const int maxn=2e5+10;
int cnt[maxn],ans=0;
vector<int> a[maxn];
int main()
{
int n,m,x;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&x),a[i].push_back(--x);
for(int i=0;i<m;i++){
for(int j=0;j<n;j++) cnt[j]=n+j;
for(int j=0;j<n;j++){
if(a[j][i]%m==i&&a[j][i]/m<n){
int tmp=a[j][i]/m;
cnt[((j+n-tmp)%n)]--;
}
}
int num=inf;
for(int j=0;j<n;j++) num=min(num,cnt[j]);
ans+=num;
}
cout<<ans<<endl;
}

F - Three Paths on a Tree

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=2e5+10;
vector<int> a[maxn];
int n,vis[maxn],dis1[maxn],dis2[maxn],dis[maxn],pos;
void bfs(int x)
{
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
pos=x;
vis[x]=1,dis[x]=0;
queue<int> q;
q.push(x);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=0;i<a[u].size();i++){
if(!vis[a[u][i]]){
vis[a[u][i]]=1;
dis[a[u][i]]=dis[u]+1;
q.push(a[u][i]);
if(dis[a[u][i]]>dis[pos]) pos=a[u][i];
}
}
}
}
int main()
{
scanf("%d",&n);
int u,v;
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
a[u].push_back(v);
a[v].push_back(u);
}
int a,b,c;
bfs(1),a=pos;
bfs(pos),b=pos;
for(int i=1;i<=n;i++)    dis1[i]=dis[i];
bfs(pos);
for(int i=1;i<=n;i++)    dis2[i]=dis[i];
c=0;
for(int i=1;i<=n;i++)
if(dis1[i]+dis2[i]>dis1[c]+dis2[c]&&i!=a&&i!=b)    c=i;
int ans=(dis1[b]+dis1[c]+dis2[c])/2;
cout<<ans<<endl<<a<<" "<<b<<" "<<c;
return 0;
}

0
0 收藏

0 评论
0 收藏
0