E.Partial Sum

题意：

给出一个a序列，a1 a2 ... an，最多可以选择m个区间[L,R]，更新 区间和 - C,并且选过的[L,R]不能再被选择，问你最后的最大值

题解：

不用想那么复杂，直接前缀和排序，最大的减去最小的再减去C>=0，更新答案，否则跳出

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 100005;
ll pre[maxn],a[maxn];
int main()
{
    int n,m,c;
    while(~scanf("%d%d%d",&n,&m,&c))
    {
        pre[0] = 1ll*0;
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            pre[i] = pre[i-1] + a[i];
        }
        sort(pre,pre+1+n);
        ll ans = 0,l = 0,r = n,cnt = 0;
        while(cnt < m && pre[r]-pre[l]-c >=0){
            ans += (pre[r] - pre[l] - c);
            cnt++,r--,l++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

H.Highway

题意：

给出一颗树，有n个点和n-1条边，问你将这个树重新拆分成一颗边权最大的树，树的边权和是多少，每俩个点之间的距离是之前给出的树的距离

题解：

我们可以自己手画一下，先找出树的直径，直径对应俩个点，那么另外n-2个点的最大的边权肯定是连着树的直径对应的俩个点

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 100005;
vector< pair<int,ll> > v[maxn];
int flag[maxn];
int pos,n;
ll a[maxn],b[maxn],maxx = 0;
void init()
{
    for(int i=1;i<=n;i++){
        v[i].clear();
        flag[i] = 0;
        a[i] = 1ll*0;
        b[i] = 1ll*0;
    }
}
void dfs1(int x,ll len)
{
    a[x] = len;
    if(a[x] > maxx){
        maxx = a[x],pos = x;
    }
    for(int i=0;i<v[x].size();i++){
        if(!flag[v[x][i].first]){
            flag[v[x][i].first] = 1;
            dfs1(v[x][i].first , len + 1ll*v[x][i].second);
        }
    }
}
void dfs2(int x,ll len)
{
    a[x] = max(a[x],len);
    for(int i=0;i<v[x].size();i++){
        if(!flag[v[x][i].first]){
            flag[v[x][i].first] = 1;
            dfs1(v[x][i].first , len + 1ll*v[x][i].second);
        }
    }
}
void dfs3(int x,ll len)
{
    a[x] = len;
    for(int i=0;i<v[x].size();i++){
        if(!flag[v[x][i].first]){
            flag[v[x][i].first] = 1;
            dfs1(v[x][i].first , len + 1ll*v[x][i].second);
        }
    }
}
int main()
{
    ll x,y,l,ans;
    while(~scanf("%d",&n))
    {
        init();
        for(int i=1;i<n;i++){
            scanf("%d%d%lld",&x,&y,&l);
            v[x].push_back(make_pair(y,l));
            v[y].push_back(make_pair(x,l));
        }
        int now1,now2;
        maxx = 0,dfs1(1,0);
        memset(flag,0,sizeof(flag));
        now1 = pos,maxx = 0,dfs1(pos,0);
        now2 = pos;
        ll ans = maxx;
        //cout<<now1<<" "<<now2<<" "<<ans<<endl;
        memset(flag,0,sizeof(flag));
        dfs3(now1,0);
        for(int i=1;i<=n;i++){
            b[i] = a[i];
        }
        memset(flag,0,sizeof(flag));
        dfs2(now2,0);
        for(int i=1;i<=n;i++)
        {
            if(i == now1 || i == now2)
                continue ;
            ans += max(a[i],b[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

I：Strange Optimization

题意：

题目说的那么多，就是让你求2×n×m/gcd(n,m)

题解：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n , m;
    while(~scanf("%lld%lld",&n,&m))
    {
        ll gc = __gcd(n,m);
        printf("1/%lld\n",n*m*2/gc);
    }
    return 0;
}