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(); } }