Menu
Article

【Fortuna OJ】10/29 Contest / 题解

Zepto

Zepto

• 9 min read

列队

题目描述

Sylvia 是一个热爱学习的女孩子。

在平时的练习中，他总是能考到 std 以上的成绩，前段时间，他参加了一场练习赛，又打爆了 std，感到十分无聊，便想要 hack 机房内同学的程序。众所周知，机房是一个 $n*n$ 的方阵。他会挑选一整行或一整列的同学进行 hack ( 而且每行每列只会 hack 一次 )，然而有些同学不是那么好惹，如果你 hack 了他两次，他会私下寻求解决,Sylvia 十分害怕，只会 hack 他们一次。假设 Sylvia 的水平十分高超，每次 hack 都能成功，求他最多能 hack 多少次？

思路

行列棋盘图为二分图经典模型，令行为左侧点，列为右侧点，有同学的格子就在对应行列之间连一条边，那么问题：一共最多取出多少行和列，就转化为二分图上最大点独立集问题。众所周知，最大独立集点数=总点数-最大匹配数，匈牙利算法即可。

代码

#include <bits/stdc++.h>
using namespace std;
int love[4010][4010],stall[4010],used[4010];
int n,m,k,p,ans; 
bool find(int x){
    for (int i=1;i<=m;i++){
        if (love[x][i]==true&&used[i]==false){
            used[i]=true;
            if (stall[i]==0||find(stall[i])){
                stall[i]=x;
                return true;
            }
        }
    }
    return false;
}
int main() {
    freopen("phalanx.in","r",stdin);
    freopen("phalanx.out","w",stdout); 
    scanf("%d%d",&m,&n);
    for (int i=1,a,b;i<=n;i++){
        scanf("%d%d",&a,&b);
        love[a][b]=1;
    }
    for (int i=1;i<=n;i++){
        memset(used,0,sizeof(used));
        find(i);
    }
    for (int i=1;i<=m;i++)
    if (stall[i]>0) ans++;
    printf("%d",m*(2*m-ans));
    return 0;
}

小凯学数学

题目描述

由于小凯上次在找零问题上的疑惑，给大家在考场上带来了很大的麻烦，他决心好好学习数学

本次他挑选了位运算专题进行研究 他发明了一种叫做“小凯运算”的运算符：

a$b =( (a&b) + (a|b) )>>1

他为了练习，写了n个数在黑板上(记为a[i]) 并对任意相邻两个数进行“小凯运算”，把两数擦去，把结果留下，这样操作n-1次之后就只剩了1个数，求这个数可能是什么？

将答案从小到大顺序输出。

思路

首先，这道题和位运算没什么关系，容易发现这个式子等价于 $\text {(a+b)/2}$。

然后，数据范围里，$a_i\leq 7, n\leq 150$。显然可以暴力区间 DP 解决这个问题。

设 $f_{i, j, k}$ 代表区间 $[i, j]$ 合并完成以后能不能产生 $k$。我们枚举 $p \in [i, j]$，合并 $[i, p]$ 和 $[p+1, j]$ 这两个区间，分别枚举这两个区间的 $k$ 即可。

时间复杂度 $\Theta (n^3k^2)$。

代码

#include <bits/stdc++.h>
#define maxn 200
using namespace std;
int n,a[maxn];
int f[maxn][maxn][8];
int main(){
    freopen("math.in","r",stdin);
    freopen("math.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
        scanf("%d",a+i);
    for (int i=1;i<=n;i++)
        f[i][i][a[i]]=1;
    for (int len=1;len<n;len++){
        for (int l=1;(l+len)<=n;l++){
            int r=l+len;
            for (int k=l;k<=r;k++){
                for (int p=0;p<8;p++){
                    if (f[l][k][p])
                    for (int q=0;q<8;q++){
                        if (f[k+1][r][q])
                        f[l][r][(p+q)/2]=1;
                    }
                }
            }
        }
    }
    for (int k=0;k<8;k++)
        if (f[1][n][k]) printf("%d ",k);
}

逛公园

题目描述

策策同学特别喜欢逛公园，公园可以看做有n个景点的序列，每个景点会给策策带来 $d_i$ 的愉悦度，策策初始有 $x_0$ 的愉悦度，然而愉悦度也是有上限的，他在每个景点的愉悦度上限为 $l_i$，策策想要从 $[l, r]$ 这一段景点中选择一段景点参观（从这一段的左端点逛到这一段的右端点），策策想知道他最终的愉悦度的最大值是多少，你能帮帮他吗？(区间可以为空，也就是说答案最小为 $x_0$。)

思路

首先，这道题提供了高达 $85pts$ 的 $\Theta (n^2)$ 暴力分值，代码非常简单，同时也是正解的基础之一：

#include <bits/stdc++.h>
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define maxn 400010
int n,q;
int d[maxn],p[maxn];
int main(){
    freopen("park.in","r",stdin);
    freopen("park.out","w",stdout);
    scanf("%d%d",&n,&q);
    for (register int i=1;i<=n;++i)
        scanf("%d",d+i);
    for (register int i=1;i<=n;++i)
        scanf("%d",p+i);
    for (register int i=1;i<=q;++i){
        int l,r;
        ll x;
        scanf("%d%d%lld",&l,&r,&x);
        ll cur=x,res=0;
        for (register int k=l;k<=r;++k){
            if (cur<x) cur=x;
            cur+=d[k];
            cur=min(cur,(ll)p[k]);
            res=max(res,cur);
        }
        printf("%lld\n",res);
    }
}

我们把对于一个固定左端点，不受限制所能到达的最右的右端点这两个点包含的区间称为极大子区间。显然，极大子区间的子区间不可能比它本身更优，这就是我们的暴力是 $\Theta (n^2)$ 而非 $\Theta (n^3)$ 的原因。

现在我们记 $Ans_{i, j, x_0}$ 表示以初始代价 $x_0$ 依次经过第 $i$ 景点到第 $j$ 景点后的答案。它有两个性质（思考一下便知）

  1. 对于 $a \geq b$，$Ans_{i,j,inf} \geq Ans_{i,j,inf}$；
  2. 记 $S_{i,j}$为 $Ans_{i,j,inf}$，（其中 $inf$ 是正无穷），$G_{i,j}$为 $i$ 到 $j$ 的 $D$ 值之和。
    则有 $Ans_{i,j,x_0}=\min( S_{i, j}, x_0+G_{i,j})$。

推论：对于询问的 $l,r$，如果两个子串都被包含在 $[l, r]$ 中，且有 $G_1\geq G_2$ 且 $S_1\geq S_2$，显然第二个子串是一定不会取到的（由性质二得到）。

于是可以考虑分块。

  • 块内贡献：每块大小根号 $n$，子串个数就是 $\Theta (n)$ 个。可以把每个子串的 $G$ 值和 $S$ 值都求出来，根据推论把没用的都扔掉，那么最后剩下的序列就是 $S$ 值不断减小 $G$ 值不断增大的序列 ，每次询问给出 $x_0$ ，最大的点一定中间某处，二分即可得出块内的答案。

  • 块间贡献：一共有 2 种

  1. 从当前块开始，到后面的某一块结束；
  2. 从之前的某一块开始到当前块结束。

参照 $85%$ 暴力的策略，那么我们就可以维护一个 $cur$ 值代表上一个块给这一个块带来的贡献，同时再维护前缀以及后缀的 $G, S$ 值。利用前缀和 $cur$ 值，我们可以采用和之前块内一样的二分来算出答案；利用后缀我们可以算出这一块给下一块的 $cur$ 值,也有三种情况：

  1. 从上个 $cur$ 走满整块到下个 $cur$；
  2. 从某个后缀开始；
  3. 直接取 $x_0$。

三者的最大值即为 $cur$。

总复杂度 $\Theta (n\sqrt n + q\sqrt n\log n)$

代码

#include <bits/stdc++.h>
#define pb push_back
#define inf INT_MAX
#define sc second
#define ft first
#define pii pair<int,int>
#define mid ((l+r)>>1)
#define mn(a,b) (a<b?a:b)
#define mx(a,b) (a>b?a:b)
#define maxn 50010
#define maxm 250
using namespace std;
int n,m,D[maxn],T[maxn],SD[maxn];
int cnt,L[maxn],R[maxn],belong[maxn];
void prepare(){
    int len=sqrt(n);
    L[1]=belong[1]=cnt=1;
    for (int u=1;u<=n;u++){
        belong[u]=cnt;
        if (u%len) continue;
        R[cnt]=u;
        cnt++;
        L[cnt]=u+1;
    }
    cnt=belong[n],R[cnt]=n;
}
int F[maxm][maxm][maxm],tcnt;
pii TM[maxn];
vector<pii> Vec[maxm],Pre[maxm],Suf[maxm];
int sta[maxn];
int S(int x,int y){return F[belong[x]][x-L[belong[x]]][y-L[belong[y]]];}
int G(int x,int y){return SD[y]-SD[x-1];}
void calc(vector<pii> &cur){
    sort(TM+1,TM+1+tcnt);
    int top=0;
    for (int i=1;i<=tcnt;++i){
        while(top&&TM[i].sc>=TM[sta[top]].sc) top--;
        sta[++top]=i;
    }
    for (int i=1;i<=top;++i)
        cur.pb(TM[sta[i]]);
}
void update(int x){
    for (int i=L[x];i<=R[x];++i){
        int tem=1<<30;
        for (int j=i;j<=R[x];++j)
            tem=mn(tem+D[j],T[j]),F[x][i-L[x]][j-L[x]]=tem;
    }
    tcnt=0;
    for (int i=L[x];i<=R[x];++i)
        for (int j=i;j<=R[x];++j)
            TM[++tcnt]=pii(S(i,j),G(i,j));
    calc(Vec[x]);
    tcnt=0;
    for (int i=L[x];i<=R[x];++i)
        TM[++tcnt]=pii(S(L[x],i),G(L[x],i));
    calc(Pre[x]);
    tcnt=0;
    for (int i=L[x];i<=R[x];++i)
        TM[++tcnt]=pii(S(i,R[x]),G(i,R[x]));
    calc(Suf[x]);
}
void init(){
    for (int i=1;i<=cnt;i++)
        update(i);
}
int find(vector<pii> cur,int tag){
    int l=0,r=cur.size()-1,res;
    while(l+1<r){
        if (cur[mid].ft>cur[mid].sc+tag) r=mid;
        else l=mid;
    }
    res=mn(cur[l].ft,cur[l].sc+tag);
    if (l+1<cur.size())
        res=mx(res,mn(cur[l+1].ft,cur[l+1].sc+tag));
    return res;
}
int solve(int l,int r,int x){
    int cur=x,ans=x,tem;
    if (belong[l]==belong[r]){
        for (int i=l;i<=r;++i)
            cur=mn(mx(cur,x)+D[i],T[i]),ans=mx(ans,cur);
        return ans;
    }
    for (int i=l;i<=R[belong[l]];++i)
        cur=mn(mx(cur,x)+D[i],T[i]),ans=mx(ans,cur);
    cur=mx(cur,x);
    for (int i=belong[l]+1;i<belong[r];i++){
        tem=find(Pre[i],cur);
        ans=mx(ans,tem);
        tem=find(Vec[i],x);
        ans=mx(ans,tem);
        cur=mn(S(L[i],R[i]),G(L[i],R[i])+cur);
        tem=find(Suf[i],x);
        cur=mx(cur,tem);cur=mx(cur,x);
    }
    for (int i=L[belong[r]];i<=r;++i)
        cur=mn(mx(cur,x)+D[i],T[i]),ans=mx(ans,cur);
    return ans;
}
int main(){
    freopen("park.in","r",stdin);
    freopen("park.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i)
        scanf("%d",D+i),
        SD[i]=SD[i-1]+D[i];
    for (int i=1;i<=n;++i)
        scanf("%d",T+i);
    prepare();
    init();
    while(m--){
        int l,r,x;
        scanf("%d%d%d",&l,&r,&x);
        printf("%d\n",solve(l,r,x));
    }
    return 0;
}
Share