Codeforces 433 Div.2

发表于 | 分类于

Codeforces 433 Div.2

A. Fraction

问最大的分子分母和为$n\leq 1000$的最简假分数

题解：暴力枚举分子，然后计算就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int n,a,b;
int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}
int main()
{
	cin>>n;
	for(int i=1;n-i>i;i++)
	{
		if(gcd(i,n-i)!=1)
			continue;
		a=i,b=n-i;
	}
	cout<<a<<" "<<b;
}

B. Maxim Buys an Apartment

有$n$个房子，其中$k$个有人了，如果一个房子相邻的房子有人，则称为好的房子，问好的房子最少有多少，最多有多少。

题解：首先特判一下$n=k$和$k=0$的情况，剩下的最小肯定是$1$，最大是$min(n-k,k*2)$，因为一幢有人的房子周围两个都是最优的，只要让这个不重叠就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
using namespace std;
int n,k;
int main()
{
	cin>>n>>k;
	if(n==k||k==0)
		cout<<0<<" "<<0;
	else
		cout<<1<<" "<<min(n-k,k*2);
}

C. Planning

有$n$个航班本来起飞时间是$1,2,…n$，现在更改为起飞时间$k+1,k+2,…,n$，然后第$i$个航班的等待一分钟的代价是$c_i$，每个航班起飞时间不得早于之前的起飞时间，问最小代价。

题解：贪心。首先观察一下一个航班起飞时间为$t_i$，那么代价就是$(t_i-i)\times c_i$，展开后发现$-i\times c_i$是一个定值，那么只要最小化$t_i\times c_i$，那么如果没有限制就把$t_i,c_i$按$t_i$递减$c_i$递增就好了。但是考虑到限制，我们可以枚举当前时间然后用一个堆来维护，进行插入即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3e5+1e3+7;
typedef long long ll;
ll n,k,c[N],ans,t[N];
struct node{
	ll c,v;
}a[N];
bool operator <(node x,node y)
{
	return x.c<y.c;
}
priority_queue<node>q;
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		scanf("%I64d",&a[i].c),a[i].v=i;
		if(i<=k)
			q.push(a[i]);
	}
	for(int i=k+1;i<=k+n;i++)
	{
		if(i<=n)
			q.push(a[i]);
		node now=q.top();
		q.pop();
		t[now.v]=i;
		ans+=now.c*(i-now.v);
	}
	cout<<ans<<endl;
	for(int i=1;i<=n;i++)
		printf("%I64d ",t[i]);
}

D. Jury Meeting

对于所有$1…n$的城市的人需要到$0$城市开$k$天的会之后再回去，给定一些第$d$天出发（同日到达），从$f_i$到0或者从$0$到$t_i$，然后价值$c_i$的航班，问所有人进行开会包括回去的最小代价。

题解：分开计算，贪心。计算过去的时候，按时间枚举然后考虑当前航班的加入对答案的影响，然后计算一下就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+1e3+7;
typedef long long ll;
const ll INF=1e16;
struct node{
	ll d,f,t,c;
}a[N],b[N];
ll n,m,k,x,y,to[N],bc[N],nowa,nowb,ans1[N*13+N],ans2[N*13+N],ans=INF,flag1,flag2,via[N],vib[N],ta,tb;
bool cmp(node a,node b)
{
	return a.d<b.d;
}
int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		ll dd,ff,tt,cc;
		scanf("%I64d%I64d%I64d%I64d",&dd,&ff,&tt,&cc);
		if(tt==0)
			a[++x].d=dd,a[x].f=ff,a[x].t=tt,a[x].c=cc;
		else
			b[++y].d=dd,b[y].f=ff,b[y].t=tt,b[y].c=cc;
	}
	sort(a+1,a+x+1,cmp);
	sort(b+1,b+y+1,cmp);
	nowa=1,nowb=y;
	for(int i=1;i<=n;i++)
		to[i]=bc[i]=INF;
	for(ll i=0;i<=(ll)(1e6)+(ll)(2e5)+1;i++)
		ans1[i]=ans2[i]=INF;
	for(ll i=1;i<=(ll)(1e6)+(ll)(2e5);i++)
	{
		ans1[i]=ans1[i-1];
		while(a[nowa].d<=i&&nowa<=x)
		{
			if(to[a[nowa].f]>a[nowa].c)
			{
				if(flag1)
					ans1[i]-=to[a[nowa].f]-a[nowa].c;
				to[a[nowa].f]=a[nowa].c;
			}
			if(!via[a[nowa].f])
				via[a[nowa].f]=true,ta++;
			if(!flag1&&ta==n)
			{
				ans1[i]=0;
				for(int j=1;j<=n;j++)
					ans1[i]+=to[j],flag1=true;
			}
			nowa++;
		}
	}
	for(ll i=(ll)(1e6)+(ll)(2e5);i>=1;i--)
	{
		ans2[i]=ans2[i+1];
		while(b[nowb].d>=i+k&&nowb>=1)
		{
			if(bc[b[nowb].t]>b[nowb].c)
			{
				if(flag2)
					ans2[i]-=bc[b[nowb].t]-b[nowb].c;
				bc[b[nowb].t]=b[nowb].c;
			}
			if(!vib[b[nowb].t])
				vib[b[nowb].t]=true,tb++;
			if(!flag2&&tb==n)
			{
				ans2[i]=0;
				for(int j=1;j<=n;j++)
					ans2[i]+=bc[j],flag2=true;
			}	
			nowb--;
		}
	} 
	for(int i=1;i<=(int)(1e6);i++)
	if(ans1[i]!=INF&&ans2[i]!=INF)
		ans=min(ans,ans1[i]+ans2[i+1]);
	cout<<(ans==INF?-1:ans);
}

E. Boredom

给定一个矩形，定义好的矩形是又恰好两个角被标记了，每次给定一个矩形，问与这个矩形至少有一点重叠的好的矩形有多少。

题解：主席树。
考虑好的不好算，可以算不好的，$n$个标记点会有$n\times (n-1)/2$个好的，那么只要考虑把所有的不好的都求出来用这个算一下就好了。

考虑优化，询问二维区间个数二维线段树可能会T,考虑用主席树来查询，运用前缀性质可以优化到log。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+1e3+7;
typedef long long ll;
int n,m,tot,root[N];
ll p,ans;
struct node{
    int ls,rs;
	ll sum;
}t[N*30];
void insert(int x,int &y,int l,int r,int v)
{
	y=++tot;
    t[y]=t[x];
    t[y].sum++;
    if(l==r) 
		return;
    int mid=(l+r)>>1;
    if(v<=mid) 
		insert(t[x].ls,t[y].ls,l,mid,v);
    else 
		insert(t[x].rs,t[y].rs,mid+1,r,v);
}
ll query(int l,int r,int x,int y,int L,int R)
{
    if(L>R||l>r||L>r||R<l) 
		return 0;
    if(l>=L&&r<=R) 
		return t[y].sum-t[x].sum;
    int mid=(l+r)>>1;
    return query(l,mid,t[x].ls,t[y].ls,L,R)+query(mid+1,r,t[x].rs,t[y].rs,L,R);
}
ll cal(ll x)
{
	return x*(x-1)/2;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) 
	{
        int x;
        scanf("%d",&x);
        insert(root[i-1],root[i],1,n,x);
    }
    while(m--) 
	{
        int l,r,u,v;
        scanf("%d%d%d%d",&l,&r,&u,&v);
        ans=(ll)n*(ll)(n-1)/2;
        p=query(1,n,root[0],root[n],1,r-1);
        ans-=cal(p);
        p=query(1,n,root[0],root[n],v+1,n);
        ans-=cal(p);
        p=query(1,n,root[0],root[l-1],1,n);
        ans-=cal(p);
        p=query(1,n,root[u],root[n],1,n);
        ans-=cal(p);
        p=query(1,n,root[0],root[l-1],1,r-1);
        ans+=cal(p);
        p=query(1,n,root[0],root[l-1],v+1,n);
        ans+=cal(p);
        p=query(1,n,root[u],root[n],1,r-1);
        ans+=cal(p);
        p=query(1,n,root[u],root[n],v+1,n);
        ans+=cal(p);
        printf("%I64d\n",ans);
    }
}