单个罗马字母要不够用了……
# 题目
A. 贸易 business
一条直线上从左到右排着 $n$ 个仓库。第 $i$ 个仓库原本有 $p_i$ 的货物。
对于 $i,j(i<j)$ ，存在一条单向的从仓库 $i$ 到仓库 $j$ 的运输道路。且每条道路最多能运输 $c$ 个货物。
第 $i$ 个仓库最多可以出售 $s_i$ 的货物。
给出 $n,p_i,s_i$ 以及 $c$，求最多能出售多少货物。
数据规模：$1\le n\le10^4$；$0\le c,p_i,s_i\le10^9$
给出一个长度为 $n$ 的序列 $A$，对 $A$ 的每个区间 $[i,j]$ 求区间内元素的中位数 $b_{i,j}$，然后所有 $b_{i,j}$ 构成一个新的数组 $B$，求 $B$ 的中位数。
数据规模：$1\le n\le10^5$；$1\le a_i\le10^9$
C. 山楂 hawthorn
有 $n$ 个编号为 $1$ 到 $n$ 的山楂，山楂 $i$ 的酸度为 $a_i$。
连续吃若干个山楂获得的美味值为吃的山楂的 $a_i$ 的异或和。
进行 $m$ 次询问，每次询问给出 $l,r,x$，求只从 $[l,r]$ 这些山楂中选出一些吃掉，能否获得美味值恰好为 $x$。
数据规模：$1\le n,m\le5\times10^5$，$0<a_i,x<2^{30}$，$1\le l\le r\le n$。
# 解析
A. 贸易 business
根据题目意思，我们可以建立一个网络流模型，用流量表示货物数量：
- 每个仓库建点 i；
- 源点S向 i 连 $p_i$ 的边，表示初始货物；
- i 向汇点T 连 $s_i$ 的边，限制最大出售数量；
- $(i<j)$ i 向 j 连 $c$ 的边，限制转移数量。
正确性显然，只用跑最大流。
但是发现时间复杂度不行，考虑网络流图的特殊性，由于最大流本身很难用其他方法计算，但是最小割（在这道题里）可以用DP计算，所以不妨根据 最大流=最小割 先进行转换。
> Tab.
下面的 S部,T部 指最小割后，如果 i 在 源点S 的连通块内，就是属于 S部，反之属于 T部。
DP 其实就是要决策仓库 i 到底是在 S部 还是在 T部。定义状态 f[i][j] 表示考虑只有源点S汇点T、以及前 i 个仓库的子图，有 j 个点（不包括S,T）在 S 部的最小割。
从 f[i-1] 转移到 f[i]，只需把 i 这个点加入子图中：
- i属于S部：在这个子图中，i 只有
i->T 这一条与T部相连的边，只需要割掉这一条就好了，即 f[i-1][j-1]+s[i]
- i属于T部：当前子图中，i 本身有
S->i，还有之前 j 个属于S部的点与 i 有连边（即仓库之间的边，容量为 $c$），即 f[i-1][j]+p[i]+c*j。
于是这样转移就好了。
实际上是一个中位数的套路题：
判断一个数组 $\{a_i\}$ 的中位数是否比 $x$ 小，可以新建一个数组 $\{b_i\}$：
如果 $b_i$ 之和大于 $0$，则说明中位数一定小于 $x$，如果小于等于 $0$，说明中位数大于等于 $x$。
这样就可以二分了——二分题目中 $B$ 数组的中位数（也就是要求的答案），要计算的就是 $B$ 中比当前的 $mid$ 小的值有多少个。二分 check mid 的时候先按照套路处理出 $\{b_i\}$
把之前那个套路扩展到区间：
判断区间 $[l,r]$ 的中位数是否比 $x$ 小，就判断 $b_l+b_{l+1}+\dots+b_r$ 是否大于 $0$，如果是，则比 $x$ 小。
而连续一个区间的和可以直接前缀和优化：定义 $s_i$ 表示 $b_1+b_2+\dots+b_i$，那么就是要找有多少个数对 $(l,r)$ 满足 $l\le r$ 且 $s_r-s_{l-1}>0$。
考虑枚举 $r$，我们就要找满足 $l-1<r$，$s_{l-1}<s_r$ 的 $l-1$ 的个数——用树状数组维护就好了。
C. 山楂 hawthorn
单词拼错石锤了
判断一堆数能否选出一些数亦或和为指定值，显然线性基 awa 但是难点在区间的限制。
必须要 $O(n\log n)$ 才能过……$O(n\log^2n)$ 常数再小也过不了 QwQ
考虑先 $O(n\log n)$ 对每个 $r$ 处理出 $[1,r]$ 的线性基，具体方法：计算 $[1,r]$ 的线性基就是在 $[1,r-1]$ 的线性基里插入 $a_r$。
于是现在 $r$ 的限制满足了，就要让 $l$ 的限制也满足。我们发现，两个询问当 $r$ 一样时，$l$ 越大，条件限制就越“苛刻”，因为可以用的 $a_i$ 就越少。
于是贪心地想，需要让插入线性基里的元素位置尽可能靠后。如果 $a_i$ 和 $a_j$ $(i<j)$都可以作为线性基的第 $k$ 个元素，那么选 $a_j$ 就可以使更多的区间能够使用到这个元素。
于是在计算 $[1,r]$ 的线性基时，把 $a_r$ 插入 $[1,r-1]$ 的线性基就有几种情况：
- 如果线性基当前位置没有元素，而且 $a_r$ 可以作为这个元素，那么肯定就把 $a_r$ 插入到这个位置了；
- 如果 $a_r$ 可以充当这个元素，但是这个位置已经有元素了，就比较 $a_r$ 和原本元素的位置先后，如果 $a_r$ 靠后，就放 $a_r$，把原本元素替换出来，再看原本的元素能不能再往后插入到其他位置。
详见代码吧……口胡太难了
# 源代码
A. business.cpp
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
|
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e4;
const long long INF=(1ll<<60);
int n;
long long per;
int val[N+3],lim[N+3];
long long f[2][N+3];
int RI(){
int a=0,c=getchar();
while(c<'0' || '9'<c) c=getchar();
while('0'<=c && c<='9'){
a=(a<<1)+(a<<3)+c-'0';
c=getchar();
}
return a;
}
int main(){
freopen("business.in","r",stdin);
freopen("business.out","w",stdout);
n=RI();per=RI();
for(int i=1;i<=n;i++)
val[i]=RI();
for(int i=1;i<=n;i++)
lim[i]=RI();
fill(f[0],f[0]+n+1,INF);
f[0][0]=0;
for(int i=1;i<=n;i++){
int I=i&1;
fill(f[I],f[I]+n+1,INF);
for(int j=0;j<=i;j++){
f[I][j]=min(f[I][j],f[!I][j]+j*per+val[i]);
if(j)
f[I][j]=min(f[I][j],f[!I][j-1]+lim[i]);
}
}
long long ans=INF;
for(int j=0;j<=n;j++)
ans=min(ans,f[n&1][j]);
printf("%lld\n",ans);
return 0;
}
|
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<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5;
#define lowbit(x) ((x)&-(x))
int n;
long long ept;
int num[N+3],tre[N*2+10];
vector<int> uni;
void Modify(int pos){
while(pos<=2*n+1){
tre[pos]+=1;
pos+=lowbit(pos);
}
}
int Query(int pos){
int ret=0;
while(pos){
ret+=tre[pos];
pos-=lowbit(pos);
}
return ret;
}
int RI(){
int a=0,c=getchar();
while(c<'0' || '9'<c) c=getchar();
while('0'<=c && c<='9'){
a=(a<<1)+(a<<3)+c-'0';
c=getchar();
}
return a;
}
bool Check(int mid){
int sum=0;
long long cnt=0;
for(int i=1;i<=2*n+1;i++) tre[i]=0;
for(int i=1;i<=n;i++){
if(num[i]<mid) sum++;
else sum--;
cnt+=Query(sum-1+n+1);
Modify(sum+n+1);
}
return cnt>ept;
}
int main(){
freopen("median.in","r",stdin);
freopen("median.out","w",stdout);
n=RI();
ept=((n+1ll)*n/2)/2;
for(int i=1;i<=n;i++){
num[i]=RI();
uni.push_back(num[i]);
}
sort(uni.begin(),uni.end());
uni.erase(unique(uni.begin(),uni.end()),uni.end());
for(int i=1;i<=n;i++)
num[i]=lower_bound(uni.begin(),uni.end(),num[i])-uni.begin()+1;
int lef=0,rig=uni.size()+1;
while(lef+1<rig){
int mid=(lef+rig)>>1;
if(Check(mid)) rig=mid;
else lef=mid;
}
printf("%d\n",uni[lef-1]);
return 0;
}
|
C. hawthorn.cpp
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
|
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e5;
int n,m;
int val[N+3],qry[N+3][3];
struct DATA{
pair<int,int> dat[33];
void Insert(int val,int pos){
pair<int,int> cur=make_pair(val,pos);
for(int i=30;i>=0;i--)
if(cur.first>>i&1){
if(!dat[i].second) {dat[i]=cur;break;}
if(dat[i].second<cur.second) swap(dat[i],cur);
cur.first^=dat[i].first;
}
}
bool Check(int val,int lef){
for(int i=30;i>=0;i--)
if(val>>i&1)
if(dat[i].second>=lef)
val^=dat[i].first;
if(val) return false;
return true;
}
}Da[N+3];
int RI(){
int a=0,c=getchar();
while(c<'0' || '9'<c) c=getchar();
while('0'<=c && c<='9'){
a=(a<<1)+(a<<3)+c-'0';
c=getchar();
}
return a;
}
int main(){
freopen("hawthron.in","r",stdin);
freopen("hawthron.out","w",stdout);
n=RI();
for(int i=1;i<=n;i++)
val[i]=RI();
for(int i=1;i<=n;i++){
Da[i]=Da[i-1];
Da[i].Insert(val[i],i);
}
m=RI();
for(int i=1;i<=m;i++){
int lef=RI(),rig=RI(),key=RI();
printf("%s\n",Da[rig].Check(key,lef)? "Koyi":"Budexin");
}
return 0;
}
|
THE END
Thanks for reading!