杂题整理

摘要

水题泛做

ZROI

ZROI332 摆花

对于一个整数序列和 m 个区间,定义序列的某一区间 的价值为 (即 sg 函数的 mex). 而这个序列的价值定义为这 m 个区间价值的最小值。

现在给定 m 个区间和序列长度,求构造一个序列使得价值最大。

显然,整个序列价值的上界为最短区间的长度

那么构造 即可。其中 len 为最短区间的长度

ZROI333 打饭

给定 k 和 n 个整数 ,要求安排 的顺序,最小化

输出这个最小值。

.

可以发现,只有在模 k 的剩余系里相邻的数会产生代价。那么我们将整个序列按照模 k 的剩余系分组为 k 个序列,称作模 k 的剩余序列。可以证明,对于一个最优的安排方案,分组后其每个模 k 的剩余序列内的数一定是单调的(非严格)。如果不是单调的,就可以交换剩余序列里两个数的位置来使答案更优:

p1

因此,我们可以将原序列排序。

考虑两个剩余序列中元素的相对关系。对于模 k 余 a 的剩余序列和模 k 余 b 的剩余序列,分别记做 . 那么对于 而言,这四个数的代价是 。显然,当 或者 的时候这四个数的代价最小。否则可以交换它们的位置使得答案更优:

p2

由此推出,每个剩余序列的元素在原序列里是连续的一段。问题转化为把序列分为 段,使得同一段内两相邻数的差的总和最小。不过这 段有长度的限制:有 段的长度为 ,有 段的长度为 . 因此设计 DP 状态 表示前面 段里有 段的长度为 ,然后就可以转移了

答案即为

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=300005,K=5003;
int n,k,ans;
int a[N],f[K][K];

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    a[0]=a[1];
    // 对于 n 个数,有分 k 组,每组 n/k 个数(有 n%k 个是 n/k+1 个)
    int len=n/k,cnt=n%k;
    //f[i,j] 表示考虑前 i 组,其中有 j 个是大小为 (n/k+1) 的,能放入间隔的最大的数的和
    // 当前的下标 i*len+j
    // 可从 f[i-1,j] 和 f[i-1,j-1] 转移(取最大值)
    for(int i=1;i<=k;i++){
        int pos=i*len-len;
        f[i][0]=f[i-1][0]+a[pos+1]-a[pos];
        for(int j=1;j<=cnt&&j<=i;j++){
            if(i==j)f[i][j]=f[i-1][j-1]+a[pos+j]-a[pos-1+j];
            else f[i][j]=max(f[i-1][j-1]+a[pos+j]-a[pos-1+j],
                f[i-1][j]+a[pos+1+j]-a[pos+j]
            );
        }
    }
    printf("%d",a[n]-a[1]-f[k][cnt]);
    return 0;
}

ZROI198 你

给出一个 n 个数的序列,为 ,循环移动 位之后,这个序列就变成了 。一种优秀的循环移动是,对于任意的前 项和都满足不小于零。请给出这个序列优秀循环移动的个数。

.

表示第 个前缀和中的 表示第 个前缀和中的

则当把前 k 个数循环移动后的最低前缀和为

由此判断正负即可。

#include<iostream>
#define min(s1,s2) ((s1)<(s2)?(s1):(s2))
using namespace std;
int n,tot,a[1000001],pre[1000001];
int mnp[1000001],mns[1000001];
int main(){
    cin>>n;
    mnp[0]=mns[n+1]=99999999;
    for(int i=1;i<=n;i++){
        cin>>pre[i];
        pre[i]+=pre[i-1];
    }
    for(int i=1;i<=n;i++)mnp[i]=min(pre[i],mnp[i-1]);
    for(int i=n;i>=1;i--)mns[i]=min(pre[i],mns[i+1]);
    for(int i=1;i<=n;i++){
        if(mnp[i]+pre[n]-pre[i]>=0&&mns[i+1]-pre[i]>=0)tot++;
    }
    cout<<tot;
    return 0;
}

ZROI224 移动杠铃

在你的面前有两个数轴,摆放和移动杠铃的规则如下:

  • 数轴上每个整数坐标处都可以放一个杠铃,一个坐标上最多只能同时放下一个 杠铃。 初始时,两个数轴各自的 位置上都各放了一个杠铃。
  • 你可以将一个杠铃往左或往右移动一个单位,但需要满足移动到的位置在这之前是空的。这个操作可以对任意多个杠铃进行任意多次,且不耗费力气。
  • 你可以将一个杠铃移动到任意一排的任意一个此前为空的位置(整数坐标处)。这个操 作可以进行多次,每次耗费的力气等于移动的杠铃的质量。

刚开始架子上摆放着 对共 个杠铃,其中每对杠铃拥有相同且唯一的质量,即保证没有 两对杠铃的质量相等。你的目标是进行若干次操作,使得每一对的两个杠铃都被放在了同一排 架子的相邻两个位置上,不需要考虑不同对之间的位置关系。 你需要计算出,在达到目标的前提下,耗费的力气最大的操作最小可以是多少?

架子是无限长的

每个杠铃可进行两种操作:左右微调;跳行

  • 第一种操作:相对位置不变,并且保证每个杠铃的左右可以空出空位;不计消耗
  • 第二种操作:操作时将更新最大值的答案;不考虑移动次数,因为只要移动了一个,则比其价值小或相等的杠铃都可以移动。

利用第二个操作后,这一对杠铃都可以消失(移动到无限远的地方)

二分答案

对于每一个二分答案 mid,可令所有权值比它小的杠铃 “消失”,即删除。再考虑剩下的杠铃,是否能两两相邻配对,如果能,降低 mid,否则增加 mid。

线段树

考虑两个不在同一架子上的两个杠铃,必然会用到操作二,于是预处理,让它们消失

剩下的都是在同一直线上的杠铃。对于一对杠铃,若中间有其他杠铃间隔,则:要么对这一对杠铃执行操作二,要么对中间的所有杠铃做操作二,于是取两者的最小值,然后让所有做了操作二的杠铃消失。

以此用线段树维护,更新答案,解决问题。

ZROI226 串串

暂时封闭一段时间哦~

你认为一个字符串是好的当且仅当它由恰好 个不同的字符组成。例如当 时, 就是一个好的字符串, 就不是。

对 s 的每一个前缀,求它最少能划分成多少个连续的好串,对每个前缀输出段数

.

考虑 DP, 表示第 i 个前缀的最少段数

直接计算,复杂度 .

观察到字符串越长,不同字符数越多(单调性)因此合法的转移状态是连续的一段,并且随着 i 自增,这一个状态空间的上下界也是递增的(非严格)。

因此对于每个 i,我们维护合法的转移区间 ;当 i 增加时更新 . 我们维护每个 i 的各个字符的最后出现的位置,就可以在常数时间内更新 ,而由于单调性,因此单调队列即可

复杂度 .

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int m,f[N];
struct counter{
    int t[N],cnt;
    void add(int x){cnt+=t[x]==0,t[x]++;}
    void del(int x){t[x]--,cnt-=t[x]==0;}
};// 每个字符的出现次数,出现的不同字符数
counter cl,cr;// 当前最长好串和最短好串的计数器
char s[N];
int q[N],ql,qr;// 单调队列

int main(){
    scanf("%d%s",&m,s+1);
    int l=1,r=1;// 合法的转移状态区间,初始化为 1
    for(int i=1;s[i];i++){
        cl.add(s[i]),cr.add(s[i]);// 第 i 个字符累加次数
        f[i]=-1;// 先初始化为 -1
        if(cl.cnt<m)continue;// 最长的好串的出现次数都达不到,则继续添加字符
        while(cl.cnt>m)cl.del(s[l]),++l;// 直到大于 m 才删除
        while(cr.cnt>=m)cr.del(s[r]),++r;// 只要大于等于 m 就删除
        --r,cr.add(s[r]);// 最后补回来一个,构成最短好串
        //printf("\033[32mi:%d, [%d,%d] \n\033[0m",i,l,r);
        // 因此可转移的区间为 [l-1,r-1]
        while(ql<=qr&&q[ql]<l-1)++ql;// 排除队首过时的决策
        for(int j=q[qr]+1;j<r;j++){// 添加 {f[j]} 进单调队列
            if(f[j]==-1)continue;// 这个决策不可用
            //printf("[query]add(%d:%d)\n",j,f[j]);
            while(ql<=qr&&f[q[qr]]>=f[j])--qr;
            q[++qr]=j;
        }
        // 最后更新当前的值
        if(ql<=qr)f[i]=f[q[ql]]+1;
        //printf("\033[41mf[%d]:%d\n\033[0m",i,f[i]);
    }
    for(int i=1;s[i];i++)printf("%d\n",f[i]);
    return 0;
}

ZROI227 天天

有 n 个长度为 m 的 01 串,定义两个 01 串的距离为他们相同位置上的不同字符数。求一个长度为 m 的 01 串使得它到这 n 个 01 串的距离的最大值最小。输出这个距离

.

把距离为 1 的字符串连边,将距离转化为路径。那么我们需要找到一个字符串,使得它到这 n 个字符串的最长的路径最短。那么建立一个虚点连接 n 个字符串,距离为 0,然后跑最短路即可。输出最长的 值,即为目标字符串。

建立虚点的作用是把最短路合并到一起算

ZROI228 摆棋子

你有一个 的棋盘。 你现在手上有若干个棋子,想要把它们放到棋盘里。不过,你需要保证任意一行任意一列最多只有三个棋子。 现在你想要知道有多少种本质不同的摆放棋子的方案。两种方案本质不同当且仅当一个方 案里某个位置有棋子而另一个方案里没有。

.

中国象棋的强化版,定义 表示前 行的棋盘,有 列 0 个棋子, 列 1 个棋子, 列 2 个棋子,剩下的 有 3 列棋子。

转移一下就会发现,命都没了

可以用小的 DFS 写转移,对当前行放 颗棋子的情况,找到三个数 使得 . 这个可以用 DFS 做。转移的时候要乘上系数,因为可以在同棋子数量的列中任选一列放。

ZROI325 自闭的游戏

有一个骰子,这个骰子有 个面,分别写着 ,并且投掷时每面朝上的概率相同。

现在,小 S 投了这个骰子 次,并且在过程中点数 至少出现了一次。现在给出一个正整数 ,表示猜测的这 次骰子的点数之和是多少。求这个猜测的正确率(即和为 的概率)

.

典型的概率 DP

概率 DP
定义 表示丢了 次,和为 是否出现的概率。
转移方程如下:

答案即为

DP 的时候注意上界, 的上界是 .

ZROI232 小 T 的矩阵

小 T 有一个 的方阵。 这个方阵的第 列从上往下第 个数是 。我们令第 列的 和是 。 现在你想要知道 . .

首先知道异或运算的简单性质

  1. .
  2. .

把矩阵横排看,第 排的模数都是 ,即按 循环;两个循环节的异或起来是 0. 剩下的用性质 2 组合异或即可

#include<bits/stdc++.h>
using namespace std;
int sum,s,n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){//the i-th row
        int p=n/i,q=n%i;
        if(p%2){//q+1~i-1
            int l=q+1,r=i-1;
            if(l%2)sum^=l,l++;
            if(r%2==0)sum^=r,r--;
            sum^=((r-l+1)/2)%2;
        }else {//1~q
            sum^=1;
            if(q%2==0)sum^=q,q--;
            sum^=((q-2+1)/2)%2;
        }
    }
    printf("%d",sum);
    return 0;
}

复杂度 .

ZROI233 小 T 的算术

.

.

平方的前缀和用公式处理,向下取整的部分用数论分块


2019.6.28 更新

LOJ6515 贪玩蓝月

一个双端队列(deque),m 个事件:

  1. 在前端插入 (w,v)
  2. 在后端插入 (w,v)
  3. 删除前端的二元组
  4. 删除后端的二元组
  5. 给定 l,r,在当前 deque 中选择一个子集 S 使得 ,且最大化 .

.

离线算法

每个二元组是有一段存活时间的,因此对时间建立线段树,每个二元组做 log 个存活标记。因此我们要做的就是对每个询问,求其到根节点的路径上的标记的一个最优子集。显然这个可以 DP 做。 表示选择集合 S 中的物品余数为 j 的最大价值。(其实实现的时侯是有序的,直接 f[i,j] 做)

一共有 个标记,因此这么做的话复杂度是 的。

在线算法

这是一个在线算法比离线算法快的神奇题目。而且还 TM 好写 emmm

上述离线算法其实是略微小题大做的,因为如果把题目的 deque 改成直接维护一个集合的话(即随机删除集合内元素),那么离线算法同样适用。既然是 deque,不妨在数据结构上做点文章。

如果题目中维护的数据结构是一个栈呢?

直接 DP 即可。 表示前 i 个二元组,余数为 j 时的最大价值。

妥妥的背包啊

删除的时侯直接指针前移即可。这样做的复杂度是 的。

队列

如果题目中维护的数据结构是队列?

有一种操作叫双栈模拟队列。

其实在这之前笔者一直没有注意到这个简单的操作。我们使用两个栈 F,S 模拟一个队列,支持 push,pop 操作:

  1. Push:插入到栈 F 中
  2. Pop:如果 S 非空,弹栈顶;否则把 F 的元素倒过来圧到 S 中,然后再弹栈顶。

容易证明,每个元素只会进入 / 转移 / 弹出一次,均摊复杂度 .

那么队列也就转化为栈的维护了,复杂度仍是 .

双端队列

回到原题,那么 Deque 怎么做?

类比推理,我们尝试用栈模拟双端队列,于是似乎把维护队列的方法扩展一下就可以了。但如果每次是全部转移栈中的元素的话,单次操作复杂度很容易退化为 .

于是乎,神仙的想一想,我们可以丢一半过去啊

这样的复杂度其实均摊下来仍是常数级别。具体地说,丢一半指的是把一个栈靠近栈底的一半倒过来丢到另一个栈中。也就是说要手写栈以支持这样的操作。

丢一半的复杂度

似乎可以用势能分析法 证明。其实本蒟蒻有一个很仙的想法。我们考虑这个双栈结构的整体复杂度。m 个事件,我们希望尽可能增加这个结构的复杂度。

首先,如果全是插入操作的话显然是严格 的,因为插入的复杂度是 的。

“丢一半”操作是在什么时侯触发的?当某一个栈为空又要求删除元素的时侯。设另一个栈的元素个数是 ,那么丢一半的复杂度就是 的。因此我们要尽可能增加“丢一半”操作的次数。

为了增加丢一半的操作次数,必然需要不断删元素直到某一个栈为空。由于插入操作对增加复杂度是无意义的,因此我们不考虑插入操作。初始时有 m 个元素,假设全在一个栈中。则第一次丢一半的复杂度是 的。然后两个栈就各有 个元素。这时就需要 删除其中一个栈,然后就又可以触发一次复杂度为 的丢一半操作……

考虑这样做的总复杂度。

解得 .

于是,总复杂度仍是 .

询问操作

在询问的时侯,我们要处理的应该是“在两个栈中选若干个元素的最大价值”的问题。因此要对栈顶的 DP 值做查询,即两个 对于询问 [l,r] 的最大价值:

这个问题暴力做是 的,不过一个妥妥的单调队列可以做到 .

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
typedef long long lld;
typedef long double lf;
typedef unsigned long long uld;
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
/******************heading******************/
const int M=5e4+5,P=505;
int I,m,p;

inline int _(int d){return (d+p)%p;}
namespace DQ{//双栈模拟双端队列
    pii fr[M],bc[M];//front,back; fi:w,se:v;
    int tf=0,tb=0;//top
    int ff[M][P],fb[M][P];
    void update(pii * s,int f[][P],int i){//update f[i] from f[i-1]
        FOR(j,0,p-1){
            f[i][j]=f[i-1][j];
            if(~f[i-1][_(j-s[i].fi)])
                f[i][j]=max(f[i][j],f[i-1][_(j-s[i].fi)]+s[i].se);
        }
    }
    void push_front(pii x){fr[++tf]=x,update(fr,ff,tf);}
    void push_back(pii x){bc[++tb]=x,update(bc,fb,tb);}
    void pop_front(){
        if(tf){--tf;return;}
        int mid=(tb+1)/2,top=tb;
        ROF(i,mid,1)push_front(bc[i]);
        tb=0;
        FOR(i,mid+1,top)push_back(bc[i]);
        --tf;
    }
    void pop_back(){
        if(tb){--tb;return;}
        int mid=(tf+1)/2,top=tf;
        ROF(i,mid,1)push_back(fr[i]);
        tf=0;
        FOR(i,mid+1,top)push_front(fr[i]);
        --tb;
    }
    int q[M],ql,qr;
    int query(int l,int r){
        const int * const f=ff[tf],* const g=fb[tb];
        int ans=-1;
        ql=1,qr=0;
        FOR(i,l-p+1,r-p+1){
            int x=g[_(i)];
            while(ql<=qr&&g[q[qr]]<=x)--qr;
            q[++qr]=_(i);
        }
        ROF(i,p-1,0){
            if(ql<=qr&&~f[i]&&~g[q[ql]])ans=max(ans,f[i]+g[q[ql]]);
            //删l-i,加r-i+1
            if(ql<=qr&&_(l-i)==q[ql])++ql;
            int x=g[_(r-i+1)];
            while(ql<=qr&&g[q[qr]]<=x)--qr;
            q[++qr]=_(r-i+1);
        }
        return ans;
    }
    void init(){FOR(i,1,P-1)ff[0][i]=fb[0][i]=-1;}
}
int main(){
    DQ::init();
    scanf("%d%d%d",&I,&m,&p);
    FOR(i,1,m){
        char op[5]; int x,y;
        scanf("%s%d%d",op,&x,&y);
        if(op[0]=='I'&&op[1]=='F') DQ::push_front(mk(_(x),y));
        else if(op[0]=='I'&&op[1]=='G') DQ::push_back(mk(_(x),y));
        else if(op[0]=='D'&&op[1]=='F') DQ::pop_front();
        else if(op[0]=='D'&&op[1]=='G') DQ::pop_back();
        else printf("%d\n",DQ::query(x,y));
    }
    return 0;
}
/*
 * BUG#1: DG::func.init. 写了一个init函数结果忘用了
 * BUG#2: DG::func.update. DP转移时没有判断是否为-1
 * BUG#3: DG::func.query. L75 求答案时没判断是否为-1
 */

LOJ6514 文明

整个游戏地图是 n 个结点的树,要在这个地图上进行 q 次游戏,每次有 k 个玩家,每个玩家的国家一开始的领土只有一个点 ,保证每个点两两不同。然后 号玩家轮流进行一个回合,每个回合可以对国家疆土上的每个节点进行距离为 1 的扩展,如果扩展到不属于任何其他国家的节点,则将这个点划入自己国家的疆土。如此往复,直到所有的节点都被某个国家占领。

黈 (tǒu) 力最近沉迷于《文明》无法自拔,他想问问你他的国家能占领多大的游戏地图。由于黈力是 STEAM 上的黄金会员,所以他每次都是 1 号玩家,即他每次都是第一个进行回合的。

.

文章之前先膜黈力和鏼爷 TQL

假设当前回合的游戏中,黈力在 R 结点,我们把 R 当作树根。哪些结点能被黈力占领?到达 R 结点距离小于等于到达其他任一结点距离的点。这个问题并不好做,我们可以反过来求哪些结点不能被黈力占领。因此我们枚举每个玩家结点 u,找到 u 到 R 路径的中点 mid。显然不能被占领的结点就是以 mid 为根的子树内的结点。

于是现在我们得到若干子树的根节点,我们需要求出结点数之和。考虑到子树可能有包含关系,那么就不能简单地累加子树大小和。怎么做呢?

如果这是一个序列上的问题,可以将其转化为区间覆盖和区间求和——线段树可以做到很优秀的复杂度。于是方法呼之欲出:树链剖分!剖分后,子树内的结点的 DFN 序是连续的,满足我们的要求。

接下来计算一下复杂度。

我们可以利用树剖快速计算路径的中点(树剖维护倍增,感觉不如直接树上倍增),单次复杂度 。给一棵子树的结点做标记,相当于一次线段树覆盖操作,复杂度 。最后线段树全集求和的复杂度是 ,因此总复杂度是 .

最后讲一下换根的事情,因为每个询问 R 结点不同,这意味着有些子树其实的“往上走”的,因此区间覆盖可能是一个补集,会分成两个操作完成。如果比较懒的话直接全集覆盖,然后把补集覆盖成 0 就行。

这道题还有虚树的做法,但本 JR 不会

BZOJ2410 Nim 游戏

一排 n 个格子,两人轮流用 k 种颜色给未染色的格子染色,要求每次染色后都不能有两个相邻的格子被染上了相同的颜色,你需要做的是判断一个已有部分格子被染色的初始局面是先手必胜还是后手必胜。

.

好的我们继续沿着 Memset’s Notebook 的路线口糊权限题题面可以看这里

这道题一看还是很吓人的,但是仔细分析一下

K>2

随便染色 emmm 显然每个空格一定可以被染色。于是判断空格个数奇偶性即可。

K=1

从这个基本一点的情况出发。这时可以将连续的一段空格看作一个游戏,这就是多个游戏的和。然后就打表。打表完发现是一个循环的东西。

K=2

相当于在 k=1 的版本上记录两边的状态。 表示长度为 i 的一段空格子,两端的状态为:

  1. 相同的颜色
  2. 不同颜色
  3. 一段染色一端边缘
  4. 两端边缘

时的 SG 值。然后大力打表发现

于是干完。

POI2000 病毒

给出若干 01 串,问能否找到一个无限长的 01 串使得不包含给出的 01 串。 .

考虑把这些串建一个 AC 自动机,那么标记为存在的结点就不合法。无限长的串,可以理解为一个循环串。因此问题转化为 AC 自动机上找环。那么就找环啊 emm

另外在建自动机的时侯,一个结点的 fail 不合法意味着这个结点也不合法,因此要注意标记的转移。普通的 AC 自动机并不考虑这一点。

#include<cstdio>
#include<cstdlib>
#include<queue>
using namespace std;
const int L=3e4+5;

int tot;
int tr[L][2],e[L],fail[L];
void insert(char *s){
    int u=0;
    for(int i=1;s[i];i++){
        if(!tr[u][s[i]-'0'])tr[u][s[i]-'0']=++tot;
        u=tr[u][s[i]-'0'];
    }
    e[u]=1;
}
queue<int>q;
void build(){
    for(int i=0;i<=1;i++)if(tr[0][i])q.push(tr[0][i]);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=0;i<=1;i++){
            int& v=tr[u][i];
            if(!v)v=tr[fail[u]][i];
            else fail[v]=tr[fail[u]][i], e[v]|=e[fail[v]], q.push(v);
        }
    }
}
bool vis[L],cur[L];
void dfs(int u){
    //printf("dfs(%d),tim:%d\n",u,vis[u]);
    if(cur[u])puts("TAK"),exit(0);
    if(vis[u]||e[u])return;
    vis[u]=cur[u]=1;
    dfs(tr[u][0]),dfs(tr[u][1]);
    cur[u]=0;
}

int n;
char s[2005];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        insert(s);
    }
    build();
    dfs(0);
    puts("NIE");
    return 0;
}
/*
 * BUG#1: 在 build 的时侯没有考虑匹配点状态的转移 L25
 */

BZOJ4179 B

给出若干 01 串,问能否找到一个长度大于 n 的 01 串使得不包含给出的 01 串。 .

这就是病毒的加强版。找环,如果没有环就说明是个 DAG,则求最长链即可。

BZOJ5403 marshland

用一个 的网格图来描述它,每一个格子代表着沼泽地的一小片区域。其中 (1, 1) 代表网格图的左上角,(n, n) 代表网格图的右下角。若用 X 表示行数,Y 表示列数,那么 X + Y 为奇数的格子有一个危险度 ,X + Y 为偶数的格子的危险度为 0。为了保障人们的安全,你有 m 个长相怪异的大石头,你可以选一些石头
放在网格图上的某些格子上,石头可以看成一个 ‘L’ 形的块,并且占三个格子,它通过旋转有四种方式供放置,仅会使得在拐角处的那个格子危险度减为 0。网格图中还有 k 个位置是 “禁止位置”,石头的任何部位都不能位于这些格子上,且这些位置的危险度一定为 0。现在你需要知道放置一些石头后最小的危险度之和是多少。(石头可以不放完)

.

考虑网络流。首先我们发现,我们只会在 X+Y 为奇数的地方“拐”一个石头。

那么就可以把 X+Y 为奇数的点拆点连一条费用为 V[X,Y] 的边。接下来考虑,我们相当于要在 X+Y 为偶数的点中选两个给它配。那么尝试将 X+Y 为偶数的点黑白染色,可以想到将 X,Y 都为奇数的点染黑,X,Y 都为偶数的点染白。由于 X+Y 为偶数的点也只能使用一次,因此也要拆点。

由于限制了石头个数,于是设一个点 即可。模型如下:

  1. S 连 S’,容量 m 费用无
  2. S’连黑,容量 1 费用无
  3. 黑连 X+Y 为奇,容量 1 费用无
  4. X+Y 为奇拆点,容量 1 费用 V[X,Y]
  5. X+Y 为奇连连白容量 1 费用无
  6. X+Y 为偶拆点,容量 1 费用无
  7. 白连 T 容量 1 费用无。

跑最大费用最大流即可。在这问题中,我们只关心最大费用而不关心最大流,因此跑増广路算法,每次累加的费用递减,一旦为负数就退出。

BZOJ5405 Platform

题面太长

首先考虑,如何计算一个子串的字典序倒序的 Rank。对这个串做一个后缀数组。字典序让我们想到 height 数组。于是你发现 height 数组倒序遍历就是子串的 Rank。

a
17
a  n  a
x  x  x
a  n  a  n  a
15 14 13 12 11
b  a  n  a  n  a
10 9  8  7  6  5
n  a
4  3
n  a  n  a
x  x  2  1

数组表示以当前字母结尾的后缀的前缀(即子串)的 Rank。

但是重复的子串不能计数,所以第 i 行前 个前缀是不能用的。显然我们有一个 的算法,即对着 height 数组扫一遍即可。每一行我们边处理出前缀和,然后与该位对应的 Rank 做比较。

事实上,我们可以直接对整个串处理权值前缀和。这样可以 计算任意子串的权值。在处理 height 数组的每一行时,你发现权值和是单增的,而 Rank 是单减的,因此可以二分查询答案,显然这样的答案在每一行最多只有一个。那么总复杂度是 的。

数学专题

HDU5288 OO’s Sequence

f(l,r) represent the number of , that there’s no satisfy

.

对每个 ,求出一个最小的 l 和最大的 r 使得区间 [l,r] 中没有 的因子。那么它对答案的贡献就是

于是对每个 的贡献求和即可。预处理的复杂度是 的,相当于做一次倍数筛。总复杂度 .

POJ3904 Sky Code

.

乍一看,是不是想来一发莫比乌斯?

好的。这玩意儿后面一大坨就很难受了。

可以一个一个强行展开,那么估计就会变成和 有关的恶心式子。

更好的算法是容斥。我们考虑所有 的数。这个条件等价于 a,b,c,d两两之间都不互质,是一个交集。于是可以用补集做容斥,最后减全集得到。最后用 减掉这个再除以 24 得到答案。

HDU5728 PowMod

多组数据, 。保证 n 是 square-free。

一看就是一道很罓的题。先大力推一发式子。设 p 是 n 的一个质因子。

好的。这样就可以递归求 f 了。至于 ans,利用欧拉定理的扩展:

又可以递归处理了。(见《上帝与集合的正确用法》)

CF615D Multipliers

(本题目中, 可能重复)。给出 m 个

求 n 的所有约数积对 1e9+7 取模,即

首先统计相同 的个数,转化为 ,其中 互不相同。

考虑每个质因子在约数积中出现的次数。我们知道约束个数是 。于是 的出现次数为

于是对每个 都做快速幂即可。

POJ2917 Diophantus of Alexandria

给定 n,求

的解的个数。

这是一道沙雕题。设 。化简得到 .

GYM 101102J Divisible Numbers

题意:给出 n 个数,然后每次询问 l r s,表示在 [l,r] 区间内有多少个 x,使 x 能被集合 s 里的至少一个元素整除,s 表示一个{1~10}的子集,

有两种做法。

由于当 s 为奇数时必有 1,此时必定整除。因此排除,则剩下 512 种情况。则 表示前 i 个数中能整除集合 j 中某一数字的个数,暴力算一波,然后 O(1) 作答。

另一种比较合理的方法是容斥。先考虑 的所有子集的 LCM,去重后只有 47 个。于是 表示前 i 个数可以被第 j 个数整除的个数。 。对于询问,先把倍数元素筛掉(比如 2,4 同时出现就筛掉 4),这时发现最多能保留 5 个元素,于是容斥的复杂度就是

霍尔定理

hall 定理(Hall’s marriage theorem)是判定二分图是否存在完全匹配的定理。完全匹配:是指最大匹配数为 min(|X|,|Y|) 也就是 X 或 Y 集合其中一个集合所有点都被匹配了。

内容

设二分图 ,则 G 中存在从 的完美匹配当且仅当 中的任意 k 个结点都与 中至少 k 个结点相邻,即

BZOJ5404 Party

Treeland 国有 n 座城市,其中 1 号城市是首都。这些城市被一些 单向 高铁线路相连,对于城市 i 6= 1, 有一条线路从 i 到 pi(pi < i). 每一条线路都是一样长的,通行花费时间也是一样长的. 这个国家的每一个城市都有一种特产,整个国家有 m 种特产 (不同城市可能有相同的特产), 其中城市 i 的特产用 ai 表示. 小 C 和他的几位 A 队爷朋友 (总共 c 人,2 ≤ c ≤ 5) 正在 Treeland 国游玩,他们准备在一个城市进行 water party. 召开 party 的城市必须满足每个人
从各自城市出发能 尽快到齐. 注意 可能有人在同一个城市. 小 C 和他的朋友们准备各自带一些特产到 party. 这些特产必须满足以下条件:

  1. 每个人带的特产数量必须相同
  2. party 里不能够有任何两种相同的特产
  3. 每个人只能带他所经过的城市的特产

对于每个询问,计算出 party 中最多有多少种特产

首先肯定在 LCA 处汇合是最优的。那么我们可以处理出每个人可能拿到的特产集合,这样就要考虑分配特产的问题。我们假设每个人拿 x 个特产。相当于把每个人拆成 x 个点与特产集合连边,然后求一个完美匹配。根据 hall 定理,任意 k 个点都至少与 k 个特产有连边。显然,对于一个人的 x 个点是满足要求的(除非 x 比他能拿到的特产总数还多)。于是我们考虑对 c 个人的 种子集情况做一一判定。假设选了 p 个人,就有 px 个点,假设这 p 个人连向的特产集合为 S,那么就要求 。于是 。于是我们枚举 种情况的时侯取最小值即可。即

那么,如何处理出每个人能拿到的特产集合?树剖 + 线段树 +Bitset 可以高效完成。统计一下复杂度。预处理树剖的复杂度是 ,预处理线段树和 Bitset 的复杂度是 。查询一次路径上的特产集合是 ,我们要查询 c 次。然后枚举 种情况,用选中的 p 个集合做交集,复杂度 ,然后算大小 并更新答案。 种情况,每个集合出现了 次,于是复杂度就是 。因此做一次查询的复杂度是

总复杂度

好的。也许我算错了,总之好像大概能过?

SPOJ INS14H

2019.6.21

在一个 n 维无限空间中,一开始原点处有一个细胞。细胞每秒都会增殖,每个原有细胞都会消亡,在与它曼哈顿距离恰为 1 的所有位置都会新增一个细胞。求 T 秒后,原点处会有多少细胞,答案

Q 组询问。

问题等价于求,有多少长度为 T 的回到源点的路径。设 表示用了前 i 个维度,长度为 2j 的路径的条数。考虑 的贡献。相当于我们选 2k 条路走第 i+1 个维度。有 种选法。而在这 2k 条路中,要选 k 条向“正”方向走,剩下 k 条向反方向走。因此有 种选法。于是贡献即为 。于是我们预处理 DP 数组,可以常数时间回答询问。


  转载请注明: Sshwy's Blog 杂题整理

 上一篇
讲题 讲题
摘要 Day2T1 无向图对每种权值判断是否有边(没边就做完了),每次删边判连通 50 分直接计算,复杂度 . 从小到大枚举权值 动态图问题,要求支持加边,删边,问图是否连通 如果只有加边,可以用并查集判断是否连通 发现在
2019.03.07
下一篇 
网络流建模 网络流建模
摘要 网络流算法本身不难,但是很多情况下难以被想到。其原因就在于网络流模型过于抽象,与表面的题目关联性不强。本文就从常见的建模角度,浅谈网络流建模 最大流建模魔术球问题 有 n 根柱子,现要按下述规则在这 n 根柱子中依次放入编号为 1,
2019.03.02
  目录