The 13th Chinese Northeast Collegiate Programming Contest

Northeast Collegiate Programming Contest"/>

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模拟就好（脑子抽抽，错了十几次