A
题意：给一个起始时间，一个终止时间，取一下中间时间
题解：直接转化为分钟，除二求解
#include <bits/stdc++.h>
using namespace std;
int main(){
int h1,m1,h2,m2;
scanf("%d:%d\n%d:%d",&h1,&m1,&h2,&m2);
int l=h1*60+m1,r=h2*60+m2;
int ans=(l+r)>>1;
int ansh=ans/60,ansm=ans%60;
printf("%02d:%02d\n",ansh,ansm);
// while(1)getchar();
return 0;
} B
题意：找和能被k整除的 数对 的最大数量
题解：先把每个数模k处理一下，余数为零可以直接跟余数为零的组成一对
余数不为零的可以跟 k-余数 组成一对
#include <bits/stdc++.h>
using namespace std;
#define maxn 200000+7
int a[maxn],vis[maxn];
int main(){
int n,k;
scanf("%d%d",&n,&k);
map<int,int>m;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
m[a[i]%k]++;
}
map<int,int>::iterator it=m.begin();
int ans=(m[0]/2)*2;
while(it!=m.end()){
//cout<<1<<endl;
int now=it->first;
if(now==0){
it++;
continue;
}
if(now==k-now){
if(m[now]>1){
m[now]-=2;
ans+=2;
continue;
}else {
it++;continue;
}
}
if(m[now]>0&&m[k-now]>0){
m[now]--,m[k-now]--;
ans+=2;
// cout<<233<<endl;
continue;
}
it++;
}
printf("%d",ans);
//while(1)getchar();
return 0;
} C
题意：找一个人数最多 而且能力最高与能力最低相差不超过5 的队伍
题解：直接暴力找，遍历 n²能过
#include <bits/stdc++.h>
using namespace std;
#define maxn 200000+7
int a[maxn],vis[maxn];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
sort(a,a+n);
int ans=0,j=0;
for(int i=0;i<n;i++){
while(a[j]-a[i]<=5&&j<n)j++;
ans=max(j-i,ans);
}
printf("%d",ans);
//while(1)getchar();
return 0;
}
D
题意：选一个数d，按照题意给的公式生成序列c ，求c序列0最多有多少个
题解：c=0那么d=-bi/ai 然后有两点需要注意，一个是精度 我开的longdouble 才能过
第二注意 有 ai bi 为0 的情况
#include <bits/stdc++.h>
using namespace std;
#define maxn 200000+7
typedef long long int ll;
#define eps 100000000
int a[maxn],b[maxn];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(int i=0;i<n;i++){
scanf("%d",&b[i]);
}
int ans=0,flag=0;
map<long double,int>m;
for(int i=0;i<n;i++){
if(a[i]==0&&b[i]==0){
flag++;continue;
}
if(a[i]==0)continue;
long double tmp=(-b[i]*1.0)/a[i];
m[tmp]++;
ans=max(m[tmp],ans);
}
printf("%d\n",ans+flag);
//while(1)getchar();
} F1
题意：找到任意一个 最大度数最大的生成树 然后输出
题解：按照点的度数 排序 直接用并查集 搞生成树
#include <bits/stdc++.h>
using namespace std;
#define maxn 200000+7
typedef long long int ll;
#define eps 100000000
int n,m;
int pre[maxn],d[maxn];
vector<int>G[maxn];
struct node {
int u,d;
};
int Find(int x) {
int r=x;
while(r!=pre[r])
r=pre[r];
int i=x,j;
while(pre[i]!=r){
j=pre[i];
pre[i]=r;
i=j;
}
return r;
}
void mix(int x,int y)
{
int fx=Find(x),fy=Find(y);
if(fx!=fy){
pre[fy]=fx;
}
}
bool cmp(node a,node b){
return a.d<b.d;
}
int ansu[maxn],ansv[maxn],flag=0;
int main(){
scanf("%d%d",&n,&m);
memset(d,0,sizeof(d));
for(int i=0;i<=n;i++)pre[i]=i;
vector<node>s;
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
d[u]++,d[v]++;
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1;i<=n;i++){
node tmp; tmp.u=i,tmp.d=d[i];
s.push_back(tmp);
}
sort(s.begin(),s.end(),cmp);
for(int i=n-1;i>=0;i--){
int u=s[i].u;
for(int j=0;j<G[u].size();j++){
int v=G[u][j];
if(Find(u)!=Find(v)){
ansu[flag]=u,ansv[flag++]=v;
mix(u,v);
}
}
}
for(int i=0;i<flag;i++){
printf("%d %d\n",ansu[i],ansv[i]);
}
//while(1)getchar();
} F2
题意：找一个 让一号顶点 度数为d的生成树
题解：这个题难度还是有的。。。，一开始完全想歪了，按照f1的度数排序，然后wa37直接gg
所以这个题 的解法就是 先把一号顶点去掉，找其他的连通分量
如果连通分量的>D 或者一号定的顶点的度数<D 都不行
按照其他连通分量的顶点数从小到大（据说不用排序也行？） 连边
如果连完不够D其他的可以随便连
最后其他的边连城生成树就行了（别忘了别再给一号点加边了）
#include <bits/stdc++.h>
using namespace std;
#define maxn 200000+7
typedef long long int ll;
#define eps 100000000
int n,m,D;
int pre[maxn],d[maxn];
vector<int>G[maxn];
struct node {
int u,d;
};
int Find(int x) {
int r=x;
while(r!=pre[r])
r=pre[r];
int i=x,j;
while(pre[i]!=r){
j=pre[i];
pre[i]=r;
i=j;
}
return r;
}
void mix(int x,int y)
{
int fx=Find(x),fy=Find(y);
if(fx!=fy){
pre[fy]=fx;
}
}
bool cmp(node a,node b){
return a.d<b.d;
}
int si=0,cnt=0;
int vis[maxn];
void dfs(int x){
if(x==1)return;
vis[x]=1;
for(int i=0;i<G[x].size();i++){
int v=G[x][i];
if(!vis[v]){
si++;
vis[v]=1;
dfs(v);
}
}
}
int ansu[maxn],ansv[maxn],flag=0;
int main(){
scanf("%d%d%d",&n,&m,&D);
memset(d,0,sizeof(d));
memset(vis,0,sizeof(vis));
for(int i=0;i<=n;i++)pre[i]=i;
vector<node>s;
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
d[u]++,d[v]++;
G[u].push_back(v);
G[v].push_back(u);
}
vis[1]=1;
for(int i=0;i<G[1].size();i++){
int u=G[1][i];
if(!vis[u]){
si=0;cnt++;
dfs(u);
node tmp; tmp.u=G[1][i],tmp.d=si;
s.push_back(tmp);
}
}
//cout<<cnt<<endl;
sort(s.begin(),s.end(),cmp);
if(d[1]<D||cnt>D){
printf("NO\n");
return 0;
}
/*for(int i=0;i<G[1].size();i++){
if(i>=D&&d[s[i].u]<=1){
printf("NO\n");
return 0;
}else if(i<D){
int u=1,v=s[i].u;
if(Find(u)!=Find(v)){
mix(u,v);
ansu[flag]=u;ansv[flag++]=v;
}
}
}*/
for(int i=0;i<s.size();i++){
int u=1,v=s[i].u;
//cout<<v<<endl;
if(Find(u)!=Find(v)){
mix(u,v);
ansu[flag]=u;ansv[flag++]=v;
}
}
int ff=s.size();
for(int i=0;i<G[1].size();i++){
if(ff>=D)break;
int u=1,v=G[1][i];
if(Find(u)!=Find(v)){
mix(u,v);
ansu[flag]=u;ansv[flag++]=v;
ff++;
}
}
for(int i=2;i<=n;i++){
int u=i;
for(int j=0;j<G[i].size();j++){
int v=G[i][j];
if(v==1)continue;
if(Find(u)!=Find(v)){
mix(u,v);
mix(v,u);
ansu[flag]=u;ansv[flag++]=v;
}
}
}
for(int i=1;i<n;i++){
if(Find(i)!=Find(i+1)){
printf("NO\n");
//while(1)getchar();
return 0;
}
}
printf("YES\n");
for(int i=0;i<flag;i++){
printf("%d %d\n",ansu[i],ansv[i]);
}
//while(1)getchar();
}
京公网安备 11010502036488号