CodeForces 853(#433-Div1)解题报告

啊好久没写解题报告了,过来mark一下。

做法

A

我们考虑任意两个可以安排的航班,那么权值大的应该放在前面。所以用优先队列维护即可。

需要注意的是边扫描边加入以避免飞机过早被安排。

B

考虑排序,然后预处理前后缀,然后双指针扫一遍即可。

C

将询问区域四条边延长,整个矩形被划分为九宫格,容斥即可。

需要注意的是,这里的二维数点不需要树套树什么的,考虑每一列仅有一个黑点,利用主席树可持久化,复杂度变为一个log。

D

考虑到并不会花费太多优惠券,于是设置上限DP即可。

代码

A

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct node
{
int lb;
LL cost;
bool operator < (const struct node &p)const
{return cost<p.cost;}
}a[300005];
priority_queue<node> q;
int n,k,ans[300005];

int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
a[i].lb=i;
scanf("%lld",&a[i].cost);
}
for(int i=1;i<=k;i++)
if(i<=n)q.push(a[i]);
LL sum=0;
for(int i=k+1;i<=k+n;i++)
{
if(i<=n)q.push(a[i]);
node t=q.top();q.pop();
ans[t.lb]=i;
sum+=1ll*t.cost*(i-t.lb);
}
printf("%lld\n",sum);
for(int i=1;i<=n;i++)
{
if(i>1)printf(" ");
printf("%d",ans[i]);
}
return 0;
}

B

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
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long LL;
const int maxn=100005;
struct node
{
int d,to;
LL cost;
bool operator < (const struct node &p)const
{return d<p.d;}
};
vector<node> jin,chu;
int n,m,k,cnt;
LL pre[maxn],suf[maxn],now[maxn],sum;

int main()
{
scanf("%d%d%d",&n,&m,&k);
while(m--)
{
int d,x,y;LL co;
scanf("%d%d%d%lld",&d,&x,&y,&co);
if(x==0)chu.pb({d,y,co});else jin.pb({d,x,co});
}
sort(chu.begin(),chu.end());
sort(jin.begin(),jin.end());
cnt=0;
LL cs=1ll*(LL)n*(LL)(1e9);
sum=cs;
for(int i=1;i<=n;i++)now[i]=1e9;
for(int i=0;i<jin.size();i++)
{
node t=jin[i];
if(now[t.to]==1e9)cnt++;
if(now[t.to]>t.cost)
{
sum-=now[t.to];
sum+=t.cost;
now[t.to]=t.cost;
}
if(cnt<n)pre[i]=cs;else pre[i]=sum;
}
cnt=0;
for(int i=1;i<=n;i++)now[i]=1e9;
sum=cs;
int chus=chu.size();
for(int i=chus-1;i>=0;i--)
{
node t=chu[i];
if(now[t.to]==1e9)cnt++;
if(now[t.to]>t.cost)
{
sum-=now[t.to];
sum+=t.cost;
now[t.to]=t.cost;
}
if(cnt<n)suf[i]=cs;else suf[i]=sum;
}
LL ans=1e18;
int l=0,r=0;
while(l<(int)jin.size() && pre[l]>=cs)l++;
while(l<(int)jin.size())
{
while(r<(int)chu.size() && jin[l].d+k>=chu[r].d)r++;
if(r>=(int)chu.size())break;
if(pre[l]<cs && suf[r]<cs)ans=min(ans,pre[l]+suf[r]);
l++;
}
if(ans==1e18)printf("-1\n");else printf("%lld\n",ans);
return 0;
}

C

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
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200001
#define MAXBIT 20
typedef long long LL;
struct Tree{
int num, childL, childR;
}tree[MAXN * MAXBIT + 1];
int root[MAXN];
int cnt, maxValue;
void insert(int& i, int l, int r, int value)
{
tree[++cnt] = tree[i];
tree[i = cnt].num++;
int mid = (unsigned int)(l + r) >> 1;
if (l == mid)return;
if (value < mid)insert(tree[i].childL, l, mid, value);
else insert(tree[i].childR, mid, r, value);
}
int rnk(int i, int j, int value)
{
int ret = 0;
for (int t = maxValue >> 1; t; t >>= 1){
if (value & t){
ret += tree[tree[j].childL].num - tree[tree[i].childL].num;
i = tree[i].childR; j = tree[j].childR;
}
else{ i = tree[i].childL; j = tree[j].childL; }
}
return ret;
}
void build(int a[],int n)
{
root[0] = 0; cnt = 0;
for (maxValue = 1; maxValue <= n+1; maxValue <<= 1);
for (int i = 1; i <= n; i++){
root[i] = root[i - 1];
insert(root[i], 0, maxValue, a[i]);
}
}
int a[200001];
int n,q;
int query(int x,int y,int xx,int yy)
{
if(x>xx || y>yy || x>n || y>n || x<=0 || y<=0 || xx>n || yy>n || xx<=0 || yy<=0)return 0;
int ans=rnk(root[x-1],root[xx],yy+1)-rnk(root[x-1],root[xx],y);
return ans;
}

int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(a,n);
while(q--)
{
LL ans=0;
int u,d,l,r;
scanf("%d%d%d%d",&u,&l,&d,&r);
LL p=query(u,l,d,r);
LL q=n-p;
ans+=p*q;
ans+=1ll*p*(p-1)>>1;
LL sum=1ll*q*(q-1)>>1;
LL t=query(1,1,u-1,n);
sum-=1ll*t*(t-1)>>1;
t=query(d+1,1,n,n);
sum-=1ll*t*(t-1)>>1;
t=query(1,1,n,l-1);
sum-=1ll*t*(t-1)>>1;
t=query(1,r+1,n,n);
sum-=1ll*t*(t-1)>>1;
t=query(1,1,u-1,l-1);
sum+=1ll*t*(t-1)>>1;
t=query(d+1,1,n,l-1);
sum+=1ll*t*(t-1)>>1;
t=query(1,r+1,u-1,n);
sum+=1ll*t*(t-1)>>1;
t=query(d+1,r+1,n,n);
sum+=1ll*t*(t-1)>>1;
printf("%lld\n",ans+sum);
}
return 0;
}

D

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
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define MAXM 300005
int n;
LL a[MAXM], now[MAXM][50];
void mini(LL & x, LL y) {
x=min(x,y);
}
int main() {
cin>>n;
for(LL i = 0; i < n; i++) {
cin>>a[i];
}
for(LL i=0;i<=n;i++)
for(LL j=0;j<=34;j++)
now[i][j]=1e18;
now[0][0] = 0;
for(LL i = 0; i < n; i++) {
for(LL j = 0; j <= 30; j++) {
LL temp=min(j,a[i]/100ll);
mini(now[i + 1][j + a[i] / 1000ll], now[i][j] + a[i]);
mini(now[i + 1][j - temp], now[i][j] + a[i] - 100ll * temp);
}
}
LL ans = 1e18;
for(LL j = 0; j <= 30; j++) {
if(ans>now[n][j])ans=now[n][j];
}
cout<<ans<<endl;
return 0;
}