xrc的比赛
先看考试题，附加题最后再写
T1
首先看到是求逆序对为奇数的子串，发现只需要贪心
贪心发现求长度为2的逆序对最优，所以时间复杂度为
O
(
n
)
O(n)
O(n)的贪心就能过了
#include<bits/stdc++.h>
using namespace std;
int read() {
int x=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0') {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int N = 1e6 + 10;
int a[N];
int main() {
// freopen("ex_data1.in","r",stdin);
int n=read();
for (int i = 1; i <= n; i ++ ) a[i]=read();
int res = 0;
for (int i = 1; i < n ; i ++ ) {
if(a[i] > a[i + 1]) {
res++,i++;
}
}
printf("%d\n", res);
return 0;
}
T2
这道题是可以考虑
D
P
DP
DP 的，但与正解无关
然后考虑解法：
对于所有区间，可能会存在一个区间
[
l
,
r
]
[l,r]
[l,r]，同时它存在一个分界点
i
i
i 使得分别对
[
l
,
i
]
[ l , i ]
[l,i] 和
[
i
+
1
,
r
]
[ i + 1 , r ]
[i+1,r]排序比对
[
l
,
r
]
[ l , r ]
[l,r] 排序更优，代价省去
1
1
1 。考虑找到这样的区间，计算所有可以省去的代价。
对于
[
l
,
r
]
[ l , r ]
[l,r] 若它分成两次排序会更优，则一定有
[
l
,
i
]
[ l , i ]
[l,i] 中的最大值小于
[
i
+
1
,
r
]
[ i + 1 , r ]
[i+1,r] 中的最小值。考虑枚举前半段的最大值
x
x
x ，位置为
b
b
b 。找到
b
b
b 位置前一个比
x
x
x 大的数，位置为
a
a
a ；后一个比
x
x
x 大的数，位置为
c
c
c ；
c
c
c 后面第一个比
x
x
x 小的数，位置为
d
d
d 。
然后考虑如何实现；
我们开两个
s
e
t
set
set 一个维护比当前数大的数的位置，一个维护比当前数小的数的位置
通过
l
o
w
e
r
b
o
u
n
d
lower_bound
lowerbound和
u
p
p
e
r
b
o
u
n
d
upper_bound
upperbound 两个函数就能解决
需要一部分指针的知识
这个复杂度是
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)的
能力接受。
当然还可以用单调栈进行解答，这里不再赘述。原因是作者单调栈能力有限
//查点的位置
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
int ans;
const int N=2e6+10;
int num[N];
int id[N];
int a,b,c,d;
bool cmp(int x,int y){
return num[x]<num[y];
}
signed main(){
// freopen("ex_data1.in","r",stdin);
int n=read();
set<int> s1,s2;
for(int i=1;i<=n;i++){
num[i]=read();
s1.insert(i);
id[i]=i;
ans+=i*(n-i);
}
sort(id+1,id+1+n,cmp);
// for(int i=1;i<=n;i++){
// cout<<id[i]<<endl;
// }
// cout<<ans;
s1.insert(0),s1.insert(n+1);
s2.insert(0),s2.insert(n+1);
//两个分别是比当前数大的位置和比当前数小的位置
for(int i=1;i<=n;i++){
b=id[i];
a=*(--s1.lower_bound(b));
c=*(s1.upper_bound(b));
// cout<<"__"<<a<<"__"<<b<<endl;
if(c!=n+1){
d=*s2.lower_bound(c);
ans-=(d-c)*(b-a);
// cout<<ans<<endl;
}
s1.erase(b);
s2.insert(b);
}
printf("%lld",ans);
return 0;
}
T3
考虑特殊性质的分数：直接输出 B
考试的时候想到了，但是输出的 A，要看清题目要求，题目要求输出必胜，我输出的必败
痛失
5
p
t
s
5pts
5pts
然后考虑正解
正解我不会，别人讲也不是特别懂，索性写个部分分吧
然后考虑DP，我们可以从最后一个区间向前转移，看图：
大概就是这么转移，一直转移到第一个区间，然后判断就行了
然后用
s
e
t
set
set 维护一下位置就又能多过一些点
代码按原题写的
#include<bits/stdc++.h>
#define ll long long
#define pir pair<ll,ll>
#define mkp make_pair
#define fi first
#define se second
#define pb push_back
using namespace std;
const ll maxn=1e6+10;
ll n,m,l[maxn],r[maxn],pre[maxn],nxt[maxn],vis[maxn],pos[maxn],tag0,tag1,tot=2,hd,x[maxn],len,g;
set<pir>st0,st1;
int main() {
// freopen("p.in","r",stdin);
scanf("%lld",&n);
for(ll i=1; i<=n; i++) {
scanf("%lld%lld",l+i,r+i);
}
pre[2]=1, nxt[1]=2;
pos[1]=0, pos[2]=l[n];
hd=1;
g=0;
st0.insert(mkp(l[n],1));
for(ll i=n-1; i; i--) {
if(g==0) {
tag0+=l[i], tag1+=r[i];
while(!st1.empty()&&st1.begin()->fi+tag0-tag1<=0) {
pir t=*st1.begin();
st1.erase(st1.begin());
ll x=t.se, y=nxt[x];
if(!nxt[y]) {
nxt[x]=0;
continue;
}
if(!pre[x]) hd=nxt[y];
nxt[pre[x]]=nxt[y], pre[nxt[y]]=pre[x];
if(pre[x]) st0.erase(mkp(pos[x]-pos[pre[x]],pre[x]));
if(nxt[y]) st0.erase(mkp(pos[nxt[y]]-pos[y],y));
if(pre[x]&&nxt[y]) st0.insert(mkp(pos[nxt[y]]-pos[pre[x]],pre[x]));
}
++tot, pos[tot]=-tag1;
g^=1;
nxt[tot]=hd, pre[hd]=tot;
st1.insert(mkp(pos[hd]-pos[tot],tot)), hd=tot;
} else {
tag1+=l[i], tag0+=r[i];
while(!st0.empty()&&st0.begin()->fi+tag1-tag0<=0) {
pir t=*st0.begin();
st0.erase(st0.begin());
ll x=t.se, y=nxt[x];
if(!nxt[y]) {
nxt[x]=0;
continue;
}
if(!pre[x]) hd=nxt[y];
nxt[pre[x]]=nxt[y], pre[nxt[y]]=pre[x];
if(pre[x]) st1.erase(mkp(pos[x]-pos[pre[x]],pre[x]));
if(nxt[y]) st1.erase(mkp(pos[nxt[y]]-pos[y],y));
if(pre[x]&&nxt[y]) st1.insert(mkp(pos[nxt[y]]-pos[pre[x]],pre[x]));
}
++tot, pos[tot]=-tag0;
g^=1;
nxt[tot]=hd, pre[hd]=tot;
st0.insert(mkp(pos[hd]-pos[tot],tot)), hd=tot;
}
}
ll u=hd;
while(u) {
x[++len]=pos[u]+(g&1? tag1:tag0);
g^=1;
u=nxt[u];
}
scanf("%lld",&m);
while(m--) {
ll c;
scanf("%lld",&c);
ll tmp=upper_bound(x+1,x+1+len,c)-x-1;
if(tmp==len) puts("Draw");
else puts((tmp^1)&1? "Alice":"Bob");
}
return 0;
}
T4
这道题需要用到匈牙利算法或网络流，借此机会回忆一下这两个算法：
首先看匈牙利算法：
参考资料：匈牙利算法
匈牙利算法是在二分图中跑最大匹配，就是最大的配对数
好多概念在这篇博客上都有了，我就不再抄一遍了
这里要注意：
完美匹配一定是最大匹配，最大匹配不一定是完美匹配
然后最大匹配的代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int N=1e5+10;
int head[N],tot;
bool vis[N];
int mat[N];
struct node{
int to,nxt;
}e[N*2];
void add(int a,int b){
tot++;
e[tot].to=b;
e[tot].nxt=head[a];
head[a]=tot;
}
int n,m,q;
bool find(int x){
// cout<<"OPOPOO";
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;
if(!vis[y]){
vis[y]=true;
if(mat[y]==0||find(mat[y])){
mat[y]=x;
return true;
}
}
}
return false;
}
signed main(){
n=read(),m=read(),q=read();
for(int i=1;i<=q;i++){
int a=read(),b=read();
add(a,b);
// add(b,a);
}
int ans=0;
for(int i=1;i<=n;i++){
// cout<<"K";
memset(vis,false,sizeof vis);
if(find(i)) ans++;
}
printf("%lld",ans);
return 0;
}
匈牙利还可以解决最小点覆盖问题：
最小点覆盖就是选出最少的点使得删除这些点相连的边后就没有边了，其实最小点覆盖就是最大匹配
下面给出匈牙利的伪代码：
while(找到Xi的关联顶点Yj){
if(顶点Yj不在增广路径上){
将Yj加入增广路
if(Yj是未覆盖点或者Yj的原匹配点Xk能找到增广路径){ //扩充集合M
将Yj的匹配点改为Xi;
返回true
}
}
返回false
}
接下来看网络流，问了同只因房大犇，dinic使用场景更多，更适合我这个小蒟蒻
幸运的是打了一遍板子过了
d
i
n
i
c
dinic
dinic算法涉及的范围比较广泛，所以我这里就不都进行概述了，只说一下求最大流：
具体怎么求我也就不说了，就说一下注意事项
- 我们考虑几个优化：搜索顺序优化，当前弧优化，余量优化，残枝优化
- 然后就是因为考虑到反向边流量的计算，建边时 t o t tot tot要从2开始，即初始化为1
- 源点看作是无限的流量
- bfs 是对点分层，找增广路
- dfs是多路增广，就是不断找可行的流量
- 最后统计最大流
- 代码还是熟能生巧，所以还是要多练
还有部分注释写在代码中了
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int N=1e5+10;
int head[N],tot=1;
int d[N],now[N];
struct node{
int to,nxt,w;
}e[N*2];
void add(int a,int b,int c){
tot++;
e[tot].to=b;
e[tot].w=c;
e[tot].nxt=head[a];
head[a]=tot;
}
int s,t,n,m;
//对图进行分层
bool bfs(){
memset(d,0,sizeof d);
queue<int> q;
q.push(s);
d[s]=1;
while(q.size()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;
if(d[y]==0&&e[i].w){
d[y]=d[x]+1;
q.push(y);
if(y==t) return true;
}
}
}
return false;
}
int dfs(int x,int flow){
//flow等于剩余流量
if(x==t) return flow;
int sum=0;
for(int i=now[x];i;i=e[i].nxt){
now[x]=i;//当前弧优化
int y=e[i].to;
if(d[y]==d[x]+1&&e[i].w){
int f=dfs(y,min(flow,e[i].w));//一定是取min ,用脑子能想出来
e[i].w-=f;
e[i^1].w+=f;//更新残留网
sum+=f;//增加x的流出流量
flow-=f;//减少x的剩余流量
if(m<=0) break;//余量优化
}
}
if(sum==0) d[x]=0;//残枝优化
return sum;
}
int dinic(){
int maxflow=0;
while(bfs()){
memcpy(now,head,sizeof now);
//源点可以看作是无限的流量
maxflow+=dfs(s,1e9);
}
return maxflow;
}
signed main(){
n=read(),m=read(),s=read(),t=read();
for(int i=1;i<=m;i++){
int a=read(),b=read(),c=read();
add(a,b,c);
add(b,a,0);
}
printf("%lld",dinic());
return 0;
}
然后我们看这道题：
记位置 i 会对答案产生贡献当且仅当
a
i
−
1
≠
a
i
a_{i-1} \neq a_{i}
ai−1=ai , 问题可以转化成在
2
n
2 n
2n 个点中选最多的贡献给答案,现在考虑限制。对于两个区间
[
l
1
,
r
1
)
,
[
l
2
,
r
2
)
\left[l_{1}, r_{1}\right),\left[l_{2}, r_{2}\right)
[l1,r1),[l2,r2) , 我们分情况讨论:
- [ l 1 , r 1 ) ∈ [ l 2 , r 2 ) \left[l_{1}, r_{1}\right) \in\left[l_{2}, r_{2}\right) [l1,r1)∈[l2,r2) 。显然我们先执行 [ l 2 , r 2 ) \left[l_{2}, r_{2}\right) [l2,r2) 再执行 [ l 1 , r 1 ) \left[l_{1}, r_{1}\right) [l1,r1) 是好的。
- [ l 1 , r 1 ) ∩ [ l 2 , r 2 ) = ∅ \left[l_{1}, r_{1}\right) \cap\left[l_{2}, r_{2}\right)=\varnothing [l1,r1)∩[l2,r2)=∅ 。显然互不影响。
-
[
l
1
,
r
1
)
∩
[
l
2
,
r
2
)
≠
∅
\left[l_{1}, r_{1}\right) \cap\left[l_{2}, r_{2}\right) \neq \varnothing
[l1,r1)∩[l2,r2)=∅ 。 令
l
1
<
l
2
,
r
1
<
r
2
l_{1}<l_{2}, r_{1}<r_{2}
l1<l2,r1<r2 , 如果
[
l
1
,
r
1
)
\left[l_{1}, r_{1}\right)
[l1,r1) 在后面则
r
1
r_{1}
r1 会产生贡献, 否则
l
2
l_{2}
l2 会产生贡献。所以
r
1
r_{1}
r1 与
l
2
l_{2}
l2 不能同时选择，这就是一个建图后的独立集。
这里给出我画的草图：
发现题目保证
l
i
,
r
i
l_{i}, r_{i}
li,ri 互不相等, 故这是一个二分图,所以我们可以用到上面的芝士了。
然后题解有一个证明：为什么找到独立集后一定有对应解。
无解当且仅当对于区间执行顺序的先后限制构成环。考虑找到这个环上随便一个区间
[
l
1
,
r
1
)
\left[l_{1}, r_{1}\right)
[l1,r1) , 假设它取的是右端点
r
1
r_{1}
r1 产生贡献, 找到它下一个区间
[
l
2
,
r
2
)
\left[l_{2}, r_{2}\right)
[l2,r2) ,
l
1
<
l
2
,
r
1
<
r
2
l_{1}<l_{2}, r_{1}<r_{2}
l1<l2,r1<r2 , 此时只能是
r
2
r_{2}
r2 产生贡献。于是递归下去, 因为
r
i
r_{i}
ri 互不相同, 所以环上的区间的
r
r
r 单调递增, 故不会形成环。
最后得出结论：一定有解
最后跑最大流就行了，注意
b
i
t
s
e
t
bitset
bitset 优化
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
inline int read() {
int x=0,f=1;
char ch=getchar();
while (!isdigit(ch)) {
if (ch=='-') f=-1;
ch=getchar();
}
while (isdigit(ch)) {
x=x*10+ch-48;
ch=getchar();
}
return x*f;
}
int n,S,T,dep[10005];
bitset<10005>g[10005];
int bfs() {
for(int i=1; i<=T; i++)dep[i]=0;
dep[S]=1;
queue<int>q;
q.push(S);
while(!q.empty()) {
int u=q.front();
q.pop();
for(int v=g[u]._Find_first(); v<=T; v=max(v+1,(int)g[u]._Find_next(v))) {
if(g[u][v]==0)continue;
if(!dep[v])dep[v]=dep[u]+1,q.push(v);
}
}
return dep[T];
}
int dinic(int u,int flow) {
if(u==T)return flow;
int rest=0;
for(int v=g[u]._Find_first(); v<=T&&flow; v=max(v+1,(int)g[u]._Find_next(v))) {
if(g[u][v]==0)break;
if(dep[v]!=dep[u]+1)continue;
int k=dinic(v,min(flow,1));
if(!k)dep[v]=0;
rest+=k,flow-=k;
if(k)g[u][v]=0,g[v][u]=1;
}
return rest;
}
int l[5005],r[5005],pos[10005];
signed main() {
n=read(),S=2*n+1,T=2*n+2;
for(int i=1; i<=n; i++) {
l[i]=read(),r[i]=read();
pos[l[i]]=0,pos[r[i]]=1;
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(l[i]<l[j]&&l[j]<r[i]&&r[i]<r[j]) {
g[l[j]][r[i]]=1;
}
}
}
for(int i=1; i<=2*n; i++)if(pos[i]==0)g[S][i]=1;
for(int i=1; i<=2*n; i++)if(pos[i]==1)g[i][T]=1;
int ans=2*n;
while(bfs())ans-=dinic(S,inf);
printf("%d\n",ans);
return 0;
}
附加题有点难度
还涉及到了新知识，所以就不写了