codeforces #270题解

本文主要是介绍codeforces #270题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接:http://codeforces.com/contest/472

A:要求输入一个n,拆分成两个素数的和即可

//    >File Name: codeforces270A.cpp
//    > Author: Webwei#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;int judge(int x)
{int n=sqrt(x);for(int i=2;i<=n;i++){if(x%i==0)  return 0;}return 1;
}
int main()
{int n;cin>>n;for(int i=4; ;i++){int t=n-i;if(!judge(t)&&!judge(i)) {cout<<i<<" "<<t<<endl;return 0;}}
}

B:contains two integers n and k (1 ≤ n, k ≤ 2000) — the number of people and the maximal capacity of the elevator.

第一行给出人数和电梯的最大容纳数量

The next line contains n integers: f₁, f₂, ..., f_n (2 ≤ f_i ≤ 2000), where f_i denotes the target floor of the i-th person.

接下来就是地一个人要到第fi层楼,电梯每上一层一秒,问所有人到达自己想要到达的楼层最少需要几秒.最后电梯要返回第一层.

思路:就是电梯肯定要到达最高层,返回第一层,这样可以在电梯允许人数的范围内先送最高层,次高层稍带就上去了.接着依次模拟此过程

//    >File Name: codeforces270B.cpp
//    > Author: Webwei#include<iostream>
#include<algorithm>
using namespace std;int cmp(int a,int b)
{	return a>b;
}
int main()
{int n,k;cin>>n>>k;int a[2010];for(int i=1;i<=n;i++)  cin>>a[i],a[i]-=1;sort(a+1,a+1+n,cmp);cout<<endl;int sum=0;if(k>=n)  cout<<2*a[1]<<endl;else{for(int i=1;i<=n;i=i+k)	sum+=a[i]*2;cout<<sum<<endl;}return 0;
}

C:不确定因素.每一个人可以在两个名字中选择一个.问最后一次排下来是否可以按照字典序输出.贪心就好了.

//    >File Name: codeforces270C.cpp
//    > Author: Webwei#include<iostream>
#include<algorithm>
using namespace std;
struct node{string a;string b;
};node v[100010];
int a[100010];
int main()
{ios::sync_with_stdio(0);cin.tie(0);int n;cin>>n;for(int i=0;i<n;i++){cin>>v[i].a>>v[i].b;if(v[i].a>v[i].b){string s=v[i].a;v[i].a=v[i].b;v[i].b=s;}}for(int i=0;i<n;i++){cin>>a[i];a[i]-=1;}int flag=1;for(int i=1;i<n;i++){if(v[a[i]].a>v[a[i-1]].a||(v[a[i]].a>v[a[i-1]].b))v[a[i]].b=v[a[i]].a;else if(v[a[i]].b>v[a[i-1]].a||v[a[i]].b>v[a[i-1]].b)v[a[i]].a=v[a[i]].b;else {flag=0;break;}}if(flag==1)  cout<<"YES"<<"\n";else cout<<"NO"<<"\n";return 0;
}

D:这个题就是给出一个临接矩阵,已知两点之间的最小距离,问是否可以构成一棵树.

这个官方给的题解是最小生成数然后dfs搜索任意两点之间的距离看是否满足.这里有一个大神的思路和代码,受教了.

将1作为根，对于任意两点存在两种关系：

1.一个点位于另一个点的子树上。两点到1的距离之差绝对值等于两点距离。

2.两个点在某一个点的不同子树上。两点到1距离之和减去两点距离等于两倍某个点到1的距离。

这样不需要管父节点是哪一个，只要保证存在就行了。

判断这两种情况就可以了。

当然在开始的时候要注意一些特殊情况的判断，预处理一下。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
int n;
long long mp[2005][2005];
map <long long,int> m;
int main()
{int n;cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%I64d",&mp[i][j]);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if((i==j && mp[i][j]) || (i!=j && mp[i][j]==0) || mp[i][j]!=mp[j][i]){cout<<"NO"<<endl;return 0;}}for(int i=1;i<=n;i++)m[2*mp[1][i]]=1;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if((mp[i][j]==abs(mp[1][i]-mp[1][j])) || m[mp[1][j]+mp[1][i]-mp[i][j]])continue;cout<<"NO"<<endl;return 0;}}cout<<"YES"<<endl;return 0;
}

这篇关于codeforces #270题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---