The 13th Chinese Northeast Collegiate Programming Contest

B Balanced Diet

题目链接
题意:商店有n颗共m种类的糖,每种糖不买或买至少Li颗,每颗糖价值ai,种类是bi,求价值总和/买的最多种类的数量的最大值。
思路:枚举分母,前缀和处理分子,求最大值。

#include<iostream>  
#include<cstdio>
#include<cstring>
#include<map>
#include<vector> 
#include<set>
#include<queue>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#include<functional>
#include<bitset>
#define ll long long
#define maxn 100002
const int mod = 1e9 + 7;

using namespace std;
vector<ll> v[maxn];
ll limit[maxn], pre[maxn];
ll gcd(ll x,ll y){
    ll z = x % y;
    while(z){
        x = y;
        y = z;
        z = x % y;
    }
    return y;
}
int main(void){
    int a, b, t, n, m;
    ll g, fenmu, fenzi, temp, s, maxx, i, j;
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&m);
        for(i = 1;i <= m;i++){
            scanf("%I64d",&limit[i]);
            v[i].clear();
        }
        for(i = 0;i < n;i++){
            scanf("%d %d",&a,&b);
            v[b].push_back(a);
        }
        maxx = 0;
        for(i = 1;i <= m;i++){
            s = v[i].size();
            maxx = max(maxx,s);
            sort(v[i].begin(),v[i].end(),greater<ll>());
        }
        for(i = 0;i <= maxx;i++){
            pre[i] = 0;
        }
        for(i = 1;i <= m;i++){
            s = v[i].size();
            temp = 0;
            for(j = 0;j < s;j++){
                if(j + 1 > limit[i]){
                    pre[j + 1] += v[i][j];
                }
                else if(j + 1 == limit[i]){
                    pre[j + 1] += v[i][j] + temp;
                }
                else{
                    temp += v[i][j];
                }
            }
        }
        fenmu = 1;
        fenzi = 0;
        for(i = 1;i <= maxx;i++){
            pre[i] += pre[i - 1];
            if(fenzi * i < fenmu * pre[i]){
                fenzi = pre[i];
                fenmu = i;
            }
        }
        g = gcd(fenzi,fenmu);
        printf("%I64d/%I64d\n",fenzi / g,fenmu / g);
    }
    return 0;
}

C Line-line Intersection

题目链接
题意:n条线,求有多少对(i,j)满足线i和线j具有交点。
思路:容斥,将直线改成Ax+By+C=0。ans=总方案数-平行或重合的方案数+重合的方案数。直接GCD,压入tuple和pair中,再放入mp中即可。

    #include <bits/stdc++.h>

    typedef long long ll;
    using namespace std;

    map <pair<ll,ll>,ll>mp1;
    map <tuple<ll,ll,ll>,ll>mp2;
    ll gcd(ll a,ll b){
        return b==0?a:gcd(b,a%b);
    }
    void input(){
        int n;
        scanf("%d",&n);
        int x1,y1,x2,y2;
        mp1.clear();
        mp2.clear();
        for(int i=1;i<=n;i++){
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            ll A=y2-y1;
            ll B=x1-x2;
            ll C=1ll*y1*x2-1ll*x1*y2;

            ll gcd1=gcd(A,B);
            ll gcd2=gcd(gcd1,C);
            mp1[make_pair(A/gcd1,B/gcd1)]++;
            mp2[make_tuple(A/gcd2,B/gcd2,C/gcd2)]++;
        }

        ll res1=0,res2=0;
        for(auto it:mp1)
            res1+=it.second*(it.second-1)/2;
        for(auto it:mp2)
            res2+=it.second*(it.second-1)/2;

        printf("%lld\n",1ll*n*(n-1)/2-res1+res2);
    }

    int main(){
        int t;
        scanf("%d",&t);
        while(t--){
            input();
    //        solve();
        }
        return 0;
    } 

E Minimum Spanning Tree

题目链接
题意:给你一棵树,将原本的树上点变为边,边变为点,点权为原边两个端点的权值和。求最小生成树。
思路:因为题目是一棵树,所以图变为,链+环组成,对于一个环来说最优的就是最短的边和其他所有边相加的值。对于原树上每个点,贪心求即可

    #include <bits/stdc++.h>

    #define maxn 100005
    #define inf 0x3f3f3f3f
    typedef long long ll;
    using namespace std;

    vector <int>edge[maxn];
    int n;

    void input(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            edge[i].clear();
        for(int i=1,u,v,w;i<n;i++){
            scanf("%d%d%d",&u,&v,&w);
            edge[u].push_back(w);
            edge[v].push_back(w);
        }
    }

    void solve(){
        ll res=0;
        for(int i=1;i<=n;i++){
            if(edge[i].size()<=1)continue;
            ll ans=0,minn=inf;
            for(int j=0;j<edge[i].size();j++){
                ans+=edge[i][j];
                minn=min(minn,(ll)edge[i][j]);
            }
            res+=ans-minn+minn*(edge[i].size()-1);
        }
        printf("%lld\n",res);
    }

    int main(){
        int t;
        scanf("%d",&t);
        while(t--){
            input();
            solve();
        }
    } 

G Radar Scanner

题目链接
题意:给你若干个矩形,每个矩形可以上下左右移动,求移动多少步满足存在一个矩形与其余所有矩形存在交。
思路:二维分离,对于所有X坐标和Y坐标两维分开求中位数,计算矩形到中位数距离。

    #include <bits/stdc++.h>

    #define maxn 100005
    typedef long long ll;
    using namespace std;

    struct squ{
        int x1,y1,x2,y2;
    };
    int n;
    int x[maxn<<1];
    int y[maxn<<1];
    int x1[maxn],x2[maxn],y1[maxn],y2[maxn];

    void input(){
        scanf("%d",&n);
        memset(x,0,sizeof x);
        memset(y,0,sizeof y);
        for(int i=1;i<=n;i++){
            scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]);
            x[i]=x1[i];
            x[i+n]=x2[i];
            y[i]=y1[i];
            y[i+n]=y2[i];
        }

        sort(x+1,x+2*n+1);
        sort(y+1,y+2*n+1);

        int X=(x[n]+x[n+1])/2;
        int Y=(y[n]+y[n+1])/2;
        ll ans=0;
        for(int i=1;i<=n;i++){
            ans+=(abs(x1[i]-X)+abs(x2[i]-X)-abs(x1[i]-x2[i]))/2;
            ans+=(abs(y1[i]-Y)+abs(y2[i]-Y)-abs(y1[i]-y2[i]))/2;
        }
        printf("%lld\n",ans);
    }

    void solve(){

    }

    int main(){
        int t;
        scanf("%d",&t);
        while(t--){
            input();
            solve();
        }
    }

H Skyscraper

题目链接
题意:两种操作,对[l,r]区间所有a[i]+k,以及对于[l,r]区间的a[i]从0开始选择一个区间+1需要多少步
思路:得出差分就是第二种的询问答案,线段树维护差分数组,再维护一个不会置0的差分数组。

#include <bits/stdc++.h>

#define maxn 100005 
typedef long long ll;
using namespace std;

int t;
int n,m;
int a[maxn];
int b[maxn];

ll sum[maxn<<2];
ll sum2[maxn<<2];

void PushUp(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    sum2[rt]=sum2[rt<<1]+sum2[rt<<1|1];
}

void Build(int l,int r,int rt){
    if(l==r)
    {
        if(b[l]>0)
            sum[rt]=b[l];
        else
            sum[rt]=0;

        sum2[rt]=b[l];
        return;
    }

    int mid=(l+r)>>1;
    Build(l,mid,rt<<1);
    Build(mid+1,r,rt<<1|1);
    PushUp(rt);
}

void update(int index,int val,int val2,int l,int r,int rt){
    if(l==r){
        sum[rt]=1ll*val;
        sum2[rt]=1ll*val2;
        return;
    }

    int mid=(l+r)>>1;
    if(index<=mid) update(index,val,val2,l,mid,rt<<1);
    else update(index,val,val2,mid+1,r,rt<<1|1);

    PushUp(rt);
}

ll query(int L,int R,int l,int r,int rt){
    if(L<=l&&r<=R){
        return sum[rt]; 
    }

    int mid=(l+r)>>1;
    ll ans=0;
    if(L<=mid) ans+=query(L,R,l,mid,rt<<1);
    if(R>mid) ans+=query(L,R,mid+1,r,rt<<1|1);
    return ans;
}

ll query2(int L,int R,int l,int r,int rt){
    if(L<=l&&r<=R){
        return sum2[rt]; 
    }

    int mid=(l+r)>>1;
    ll ans=0;
    if(L<=mid) ans+=query2(L,R,l,mid,rt<<1);
    if(R>mid) ans+=query2(L,R,mid+1,r,rt<<1|1);
    return ans;
}

void input(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i]-a[i-1];
    }

    Build(1,n,1);
    for(int i=1,flag,l,r,k;i<=m;i++){
        scanf("%d",&flag);
        if(flag==2){
            scanf("%d%d",&l,&r);
            printf("%lld\n",query2(1,l,1,n,1)+query(l+1,r,1,n,1));
        }else{
            scanf("%d%d%d",&l,&r,&k);
            b[l]+=k;
            if(b[l]>0)
                update(l,b[l],b[l],1,n,1);
            else
                update(l,0,b[l],1,n,1);

            b[r+1]-=k;    
            if(r+1<=n){
                if(b[r+1]>0)
                    update(r+1,b[r+1],b[r+1],1,n,1);
                else
                    update(r+1,0,b[r+1],1,n,1);
            }
        }
    }
}

int main(){
    scanf("%d",&t);
    while(t--){
        input();
//        solve();
    }
}

J Time Limit

题目链接
按题意模拟即可。

    #include <bits/stdc++.h>

    #define maxn 20
    using namespace std;

    int n;
    int a[maxn];

    void input(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);

        int l=a[1]*3;
        for(int i=2;i<=n;i++)
        {
            if(l<a[i]+1){
                l=a[i]+1;
            }
        }
        if(l%2)
            l++;

        printf("%d\n",l);
    } 

    int main(){
        int t;
        scanf("%d",&t);
        while(t--){
            input();
    //        solve();
        }
    }