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();
}
}
京公网安备 11010502036488号