Codeforces Round #270

A

题意:给出一个数n,求满足a+b=n,且a+b均为合数的a,b

方法一:可以直接枚举i,n-i,判断a,n-i是否为合数

 #include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<stack>
#include<vector>
#include<map>
#include<algorithm>
#define mod=1e9+7;
using namespace std; typedef long long LL;
bool isp[]; void isprime(){
isp[]=isp[]=true;
for(int i=;i<=;i++){
if(isp[i]==false)
for(int j=i*;j<=;j+=i)
isp[j]=true;
}
} int main()
{
int n;
cin>>n;
isprime();
for(int i=;i<=n;i++){
if(isp[i]&&isp[n-i]){
printf("%d %d\n",i,n-i);
break;
}
}
return ;
}

方法二:注意到n>=12,而4是最小的合数,

所以:当n为奇数的时候,那么n-9至少是为4的合数,输出9,n-9

当n为偶数的时候,那么n-8至少是为4的合数,输出8,n-8

 #include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<stack>
#include<vector>
#include<map>
#include<algorithm>
#define mod=1e9+7;
using namespace std; typedef long long LL; int main(){
int n;
cin>>n;
if(n%) printf("%d %d\n",,n-);
else printf("%d %d\n",,n-);
return ;
}

B

题意:给出一个电梯,给出n个人,n个人要上到的楼层a[i],以及电梯每次最多能装载的人数k,问把每个人都送到目标楼层,需要花费的最少时间

看的出题人的题解:先是第一组k个人和这k个人里面要去往的楼层最高的人乘同一次电梯,再是第二组k个人和这k个人里面要去往的楼层最高的人乘同一次电梯,

所以总时间为ans=2*((a[n]-1)+(a[n-k]-1)+a[n-2k]-1)----

所以先排序,再倒着取依次取第k个数,这样能够尽量减少下一次运送人的时间, 出题人的证明没有看明白= =

 #include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<stack>
#include<vector>
#include<map>
#include<algorithm>
#define mod=1e9+7;
using namespace std; typedef long long LL;
int a[]; int main(){
int n,k,i,j,ans=;
cin>>n>>k;
for(i=;i<=n;i++) cin>>a[i];
sort(a+,a+n+);
for(i=n;i>=;i=i-k){
ans+=(a[i]-)*;
}
printf("%d\n",ans);
return ;
}

C

题意:给出n个人的姓,和名,任意选择其中一个作为排序的关键字,问能否满足给出的序列。

按照给出的序列来遍历,先将a[i],b[i]排序成小的在前,大的在后,如果a[i]大于当前的cur,那么将a[i]赋值给cur,否则b[i]赋给cur,都不满足的话则是“NO” 就是尽量选择a[i],b[i]中更小的作为关键字

 #include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<stack>
#include<vector>
#include<map>
#include<algorithm>
#define mod=1e9+7;
using namespace std; typedef long long LL;
string a[],b[];
int p[];
string cur=""; int main()
{
int n,i,j;
cin>>n;
for(i=;i<n;i++) cin>>a[i]>>b[i];
for(i=;i<n;i++) {
cin>>p[i];
p[i]--;
} for(i=;i<n;i++){
int x=p[i];
if(a[x]>b[x]) swap(a[x],b[x]);
if(cur<a[x]) cur=a[x];
else if(cur<b[x]) cur=b[x];
else{
printf("NO\n");
return ;
}
}
printf("YES\n");
return ;
}

D

题意:给出一个矩阵,问这个矩阵是否能由一颗带权值的树构成

先用prim建树,再依次枚举每一个节点到其他节点的距离,看是否和给出的矩阵一样

还不懂写= =

上一篇:523 Continuous Subarray Sum 非负数组中找到和为K的倍数的连续子数组


下一篇:Codeforces gym 100685 F. Flood bfs