练习赛ABC-题解

A
题目描述
DK 想出一道超级没有素质的题
DK 给了你一个标准的时钟，初始时间在 12:00
每分钟分针会顺时针转动 6°，而时针会顺时针转动 0.5°
DK 想知道，t 分钟后，时针和分针的较小夹角的大小是多少
由于这题超级没有素质，所以你需要将答案四舍五入到整数
思路：简单模拟，找到t分钟后，时针和分针的位置，然后找到大的那个夹角，最后四舍五入即可。
代码：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
double a,b;

int main()
{
    int n;
    scanf("%d",&n);
    while(n--){
        int x;
        scanf("%d",&x);
        a=x*0.5,b=x*6.0;
        while(a>=360)a-=360;
        while(b>=360)b-=360;
        double ans=min(abs(a-b),360-abs(a-b));//cout<<ans;
        if(ans!=(int)ans)ans++;
        printf("%d\n",(int)ans);
    }
    return 0;
}

B:
题目描述
给你一个长度为 n 的序列，第 i 个数为 ai
将这个序列分割成 i 个不重合的子串，从每个子串中取出最大的 j 个数作为这个分割方法的价值，记价值最大的分割方法的价值为 val(i,j)
但是金发少女 DK 觉得这太好算了，于是她要你求下面的式子。
思路：通过划分，你总可以得到最大的数，所以直接排序然后求答案就行。
代码：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
long long a[100005];
bool cmp(long long c,long long d)
{
    return c>d;
}
long long sum=0;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%lld",&a[i]);
    sort(a,a+n,cmp);
    for(int i=1;i<n;i++)a[i]+=a[i-1];
    int x,y;
    scanf("%d%d",&x,&y);
    for(int i=1;i<=x;i++){
        for(int j=1;j<=y;j++)
            sum+=a[i*j-1];
    }
    printf("%lld\n",sum);
    return 0;
}

C:

思路：通过观察发现，总可以选到最大生成树上的边，而且每条边恰好选一次。
代码：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct Node{
    int u,v;
    long long w;
}a[500005];
int fa[500005],n,m;
void init()
{
    for(int i=0;i<=n;i++)fa[i]=i;
}
int findfa(int x)
{
    return x==fa[x]?x:fa[x]=findfa(fa[x]);
}
void con(int x,int y)
{
    fa[findfa(x)]=findfa(y);
}
bool cmp(Node c,Node d)
{
    return c.w>d.w;
}
bool vis[500005];
int ans[500005];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d%lld",&a[i].u,&a[i].v,&a[i].w);
    }
    init();
    sort(a,a+m,cmp);
    long long sum=0;
    for(int i=0;i<m;i++){
        if(findfa(a[i].u)!=findfa(a[i].v))con(a[i].u,a[i].v);
        else continue;
        sum+=a[i].w;
    }
    printf("%lld\n",sum);
    return 0;
}