The 13th Chinese Northeast Collegiate Programming Contest

文章目录

B. Balanced Diet
C. Line-line Intersection
E. Minimum Spanning Tree
D. Master of Data Structure
F. Mini-game Before Contest 坑
G. Radar Scanner
H. Skyscraper
J. Time Limit

B. Balanced Diet

贪心，假设最大天数为k，那么所有物品最大得k项都拿（再满足题意的情况下）

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 2e6 + 6;
const LL inf = 0x3f3f3f3f;
const int mod = 1e9+9;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
//LL __gcd(LL x,LL y){return y==0?x:__gcd(y,x%y);}
//head
int n,_,p[maxn],m,mx;
LL s[maxn];
VI G[maxn];
int main(){
    scanf("%d",&_);
    while(_--){
         scanf("%d%d",&n,&m);
         for(int i=1;i<=m;i++){
             scanf("%d",&p[i]);
             G[i].clear();
         }
         for(int i=1,x,y;i<=n;i++){
             scanf("%d%d",&x,&y);
             G[y].pb(x);
         }
         for(int i=1;i<=m;i++){
             sort(G[i].begin(),G[i].end());
             reverse(G[i].begin(),G[i].end());
         }
         for(int i=1;i<=m;i++){
             LL sum=0;
             for(int j=0;j<G[i].size();j++){
                s[max(j+1,p[i])]+=G[i][j];
                //printf("%llds",sum);
             }
         }
         LL zi=0,mu=1;
         for(int i=1;i<=n;i++) s[i]+=s[i-1];
         for(LL i=1;i<=n;i++){
             if(zi*i<s[i]*mu) zi=s[i],mu=i;
             //printf("%lld",s[i]);
             s[i]=0;
         }
         LL gcd=__gcd(zi,mu);
         printf("%lld/%lld\n",zi/gcd,mu/gcd);
    }
}

C. Line-line Intersection

两条直线有交点即斜率不同，用mp模拟就好（脑子抽抽，错了十几次😟）

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 1e5 + 6;
const LL inf = 0x3f3f3f3f;
const int mod = 1e9+9;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}

//head
pair<double,double> qq;
pair<PII,PII> q;
int _,n,cnt,a[maxn];
map<double,LL> mp;
map<double,LL> ::iterator it;
map<pair<double,double>,LL> mp1;
map<pair<double,double>,LL> ::iterator it1;
int main(){
    scanf("%d",&_);
    while(_--){
        scanf("%d",&n);mp.clear();mp1.clear();
        cnt=0;
        for(int i=1,x1,x2,y1,y2;i<=n;i++){
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            if(x1==x2){
                a[++cnt]=x1;continue;
            }
            double k=1.0*(y1-y2)/(x1-x2);
            double b=y1-1.0*x1*k;
            mp[k]++;
            mp1[make_pair(k,b)]++;
        }
        LL ans=0;
        for(it=mp.begin();it!=mp.end();it++){
            ans=ans+1ll*it->second*(n-it->second);
            //printf("%d,",it->se);
        }
        //printf("%lld*\n",ans);
        for(it1=mp1.begin();it1!=mp1.end();it1++){
            ans=ans+1ll*it1->second*(it1->second-1);
           // printf("%d,",it1->second);
        }
        sort(a+1,a+1+cnt);
        ans=ans+1ll*cnt*(n-cnt);
        for(int i=1;i<=cnt;){
            LL j=i+1;
            while(j<=cnt&&a[j]==a[i]) j++;
            ans=ans+1ll*(j-i)*(j-i-1);
            i=j;
        }
        printf("%lld\n",ans/2);
    }
}

E. Minimum Spanning Tree

贪心按层考虑，要想让当前节点u和儿子节点的边，与u的父亲的边联通。那么首先必须选出一条子节点的最小的边与fa相连，然后剩下的边和这些边最小的相连，dfs模拟就行，注意边界

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 2e6 + 6;
const LL inf = 0x3f3f3f3f;
const int mod = 1e9+9;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
//LL __gcd(LL x,LL y){return y==0?x:__gcd(y,x%y);}
//head
struct node{
    int to,next,w;
}edge[maxn];
int n,_,head[maxn],tot,p[maxn],m;
LL ans;
void add(int u,int v,int w){
    edge[++tot]={v,head[u],w};
    head[u]=tot;
}
int dfs(int u,int fa,int ww){
     int mi=ww,cnt=0;
     for(int i=head[u];i!=-1;i=edge[i].next){
         int v=edge[i].to,w=edge[i].w;
         if(v==fa) continue;
         dfs(v,u,w);
         ans+=w;
         mi=min(w,mi);
         cnt++;
     }
     if(fa!=-1&&cnt) ans+=1ll*ww;
     if(mi!=inf&&cnt) {
          ans+=1ll*mi*(cnt-1);
          if(fa==-1) ans-=mi;
     }
}
int main(){
    scanf("%d",&_);
    while(_--){
         scanf("%d",&n);
        for(int i=1;i<=n;i++) head[i]=-1;
        for(int i=1,u,v,w;i<n;i++){
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }
        ans=0;
        dfs(1,-1,inf);
        printf("%lld\n",ans);
    }
}

D. Master of Data Structure

https://blog.csdn.net/qq_43914084/article/details/105688079

F. Mini-game Before Contest 坑

G. Radar Scanner

先假设那个点为{x,y}那么所有的快首先要将x覆盖，然后再将y覆盖，所以问题就可以从二维转化为一维（即从矩形 ->线段）。
然后可以发现每条线段到x的距离为 abs(r-x)+abs(l-x)+abs(r-l);
那么整体代价就为Σabs(Ri-x)+abs(Li-x)再加上线段总长度，从而问题又转化为一些点到x的距离之和，那么我们设x的左边又q个点，右边有p个点，那么当x+1时，答案加q-p当p>q时一直减小。
这样就会发现，k取所有点种中间的那个点时，答案最优，

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 2e5 + 6;
const LL inf = 0x3f3f3f3f;
const int mod = 1e9+9;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}

//head
int n,_,x[maxn],y[maxn];
LL ans;
int main(){
    scanf("%d",&_);
    while(_--){
         scanf("%d",&n);
         ans=0;
         for(int i=1,a,b,c,d;i<=n;i++){
             scanf("%d%d%d%d",&a,&b,&c,&d);
             ans=ans-1ll*(d-b+c-a);
             x[i]=a;x[i+n]=c;
             y[i]=b;y[i+n]=d;
         }
         sort(x+1,x+1+2*n);sort(y+1,y+1+2*n);
         int nx=x[n],ny=y[n];
         for(int i=1;i<=2*n;i++){
             ans+=abs(x[i]-nx)+abs(y[i]-ny);
         }
         printf("%lld\n",ans/2);   
    }
}

H. Skyscraper

先考虑不加询问怎么做，考虑每个数字的贡献，
发现当ai-1>=ai时，无贡献，
否则贡献为ai-ai-1;
然后对于区间【l,r】的答案就为al+(l+1~r的差分）
然后树状数组或线段树模拟差分数组和dp数组就行
assume：假设！

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 1e5 + 6;
const LL inf = 0x3f3f3f3f;
const int mod = 1e9+9;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
//LL __gcd(LL x,LL y){return y==0?x:__gcd(y,x%y);}
//head
int _,n,m,op,l,r;
LL a[maxn],b[maxn],x;
struct tree{
    LL c[maxn];
    void init(){memset(c,0,sizeof c);}
    void update(int x,LL val){
        for(;x<=n;x+=x&(-x)) c[x]+=val;
    }
    LL qu(int x){
        LL res=0;
        while(x>0) {
            res+=c[x];x-=x&(-x);
        }
        return res;
    }
    LL ask(int l,int r){
        return qu(r)-qu(l-1);
    }
}t1,t2;
int main(){
    scanf("%d",&_);
    while(_--){
        t1.init();t2.init();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            b[i]=a[i]-a[i-1];
        }
        //b[n+1]=-a[n];
        for(int i=1;i<=n;i++){
            t1.update(i,a[i]-a[i-1]);
            t2.update(i,max(a[i]-a[i-1],0ll));
        }
        while(m--){
            scanf("%d%d%d",&op,&l,&r);
            if(op==1){
                scanf("%lld",&x);
                t1.update(l,x);t1.update(r+1,-x);
                if(b[l]>0) t2.update(l,x);
                else if(b[l]+x>0) t2.update(l,b[l]+x);
                if(b[r+1]>0) t2.update(r+1,-min(b[r+1],x*1ll));
                b[l]+=x;b[r+1]-=x;
            }
            else {
                printf("%lld\n",t1.ask(1,l)+t2.ask(l+1,r));
            }
        }
        
    }
}

J. Time Limit

。。这题不用说了吧

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 1e5 + 6;
const LL inf = 0x3f3f3f3f;
const int mod = 1e9+9;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}

//head
pair<PII,PII> q;
int _,n;
map<long double,LL> mp;
map<long double,LL> ::iterator it;
map<pair<PII,PII>,LL>mp1;
map<pair<PII,PII>,LL>::iterator it1;
int main(){
    scanf("%d",&_);
    while(_--){
         scanf("%d",&n);
         int mx=0;
         for(int i=1,d;i<=n;i++){
             scanf("%d",&d);
             mx=max(mx,d+1);
             if(i==1) mx=max(mx,3*d);
         }
         printf("%d\n",mx&1?mx+1:mx);
    }
}