NOIP2020年赛前练习
本文最后更新于 54 天前,其中的信息可能已经有所发展或是发生改变。

P5290 [十二省联考2019] 春节十二响

题面不是人话,翻译一下。

给一棵树,每个点权值为 $w_i$,需要将节点分组。
分组要求:每个组内的点,两两不存在祖先——后代关系。
每个组的代价是组内的最大值,求最小的总代价。

考虑对于 $u$ 相连的所有子树,每棵子树内的点都只能与非该子树内的点在同一段内,也就是说,每棵子树内的组都必须与其他子树的组结合。

由于只与最大值有关,有一个贪心的想法:如果当前子树内某组结合后,不会改变原先的最大值,那么一定结合。

然而需要考虑,当前子树每个组只能与其他子树每个组一一结合,何况还有当前子树内出现最大组,要求其他子树合并的情况,因此需要妥当考虑。

可以发现,每次结合都会减少对应组代价的代价,因此:优先消去代价大的。

两类:当前子树,其他子树,分别取出最大值,比大小,然后小的并入大的中。

注意使用启发式合并,时间复杂度 $O(n\log n)$.

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cctype>
using namespace std;
const int bufSize = 1e6;
#define DEBUG
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize],*p1 = buf,*p2 = buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,bufSize,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
inline T read(T &r)
{
    static char c;
    r = 0;
    for(c=nc();!isdigit(c);c=nc());
    for(;isdigit(c);c=nc()) r=r*10+c-48;
    return r;
}
const int maxn = 2e5 + 100;
int n,fa[maxn],w[maxn];
struct node
{
    int to,next;
}E[maxn];
int head[maxn],tot;
inline void add(int x,int y){E[++tot].next = head[x],head[x] = tot,E[tot].to = y;}
priority_queue<int> S[maxn];
void dfs(int u)
{
    vector<int> more;
    for(int p = head[u];p;p=E[p].next)
    {
        int v = E[p].to;
        dfs(v);
        if(S[u].size() < S[v].size()) std::swap(S[u],S[v]);
        while(!S[v].empty())
            more.push_back(std::max(S[u].top(),S[v].top())),S[u].pop(),S[v].pop();
        for(vector<int>::iterator it = more.begin();it!=more.end();++it) S[u].push(*it);
        more.clear();
    }
    S[u].push(w[u]);
    vector<int>().swap(more);
}
int main()
{
    read(n);
    for(int i = 1;i<=n;++i) read(w[i]);
    for(int i = 2;i<=n;++i) read(fa[i]),add(fa[i],i);
    dfs(1);
    long long res = 0;
    while(!S[1].empty()) res += S[1].top(),S[1].pop();
    printf("%lld\n",res);
    return 0;
}

P4053 [JSOI2007]建筑抢修

一开始想动态规划,然而每个建筑修了没修是不可确定的。
可以考虑,按报废时间排序。当每个建筑马上报废时进行决策,如果能直接修它,那么修它。
如果不能直接修它,找到之前修的最耗时的,不修最耗时的而修它,节约时间。

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 3e5 + 100;
int n;
struct node
{
    int t1,t2;
}A[maxn];
bool cmp(const node &a,const node &b){return a.t2 < b.t2;}
priority_queue<int> q;
int main()
{
    scanf("%d",&n);
    for(int i = 1;i<=n;++i) scanf("%d %d",&A[i].t1,&A[i].t2);
    std::sort(A + 1,A + 1 + n,cmp);
    int now = 0,res = 0;
    for(int i = 1;i<=n;++i)
    {
        if(now + A[i].t1 <= A[i].t2) now += A[i].t1,q.push(A[i].t1),++res;
        else if(q.size() && A[i].t1 <= q.top()) now = now - q.top() + A[i].t1,q.pop(),q.push(A[i].t1);
    }
    printf("%d\n",res);
    return 0;
}

P5303 [GXOI/GZOI2019]逼死强迫症

一眼动态规划,然而数据范围奇大,转而想容斥……无果。
其实是矩阵快速幂
考虑把动态规划过程用矩阵加速。题解大部分用到了斐波那契数列,这里我写了一种纯动态规划的解法。
如何定义状态、转移?可以发现,一行只有单格砖是否出现这个状态,那么稍一思考我们认为有四种状态。

$f(i,0,0)$ 代表都没出现,$f(i,0,1)$ 与 $f(i,1,0)$ 分别代表上下出现,$f(i,1,1)$ 上下都出现。

考虑长度为二的,可以一根竖着,也可以两根横着,有:

$$f(i,0,0) = f(i-1,0,0) + f(i-2,0,0)$$

小方块纵向挨着的位置究竟放不放?我们人为定义,与小方块同横坐标为起点向右有一条长方块。

然后,可以发现,放完一个小格子,之后只能横着放长格子了。

$$f(i,1,0) = f(i-2,1,0) + f(i-1,0,0)$$
$$f(i,0,1) = f(i-2,0,1) + f(i-1,0,0)$$
最后就是合并的情况,可以发现,两个小格子都放完之后,与没放过小格子是一样的。
两个小格子可能在同一行,可能在不同行。因此这部分转移会比较恶心。
首先是自由放置长格子的方案:

$$f(i,1,1) += f(i-1,1,1) + f(i-2,1,1)$$

然后是同行转移的方案:

$$f(i,1,1) += f(i-3,1,0) + f(i-3,0,1)$$

然后是跨行转移的方案:

$$f(i,1,1) += f(i-2,1,0) + f(i-2,0,1)$$

真不错!每个状态都只跟前三项有关!接下来我们来汇总一下转移方程。

观察一下,$f(i,1,0) = f(i,0,1)$ 显然是恒成立的,所以可以进一步化简。重新定义 $f(i,0)$ 为无小格子,$f(i,1)$ 为一个小格子,$f(i,2)$ 为两个小格子。

$$f(i,0) = f(i-1,0) + f(i-2,0)$$
$$f(i,1) = f(i-2,1) + f(i-1,0)$$
$$f(i,2) = f(i-1,2) + f(i-2,2) + 2 \times f(i-3,1) + 2 \times f(i-2,1)$$
是不是混乱不堪?其实需要维护的,只有 $i-1$ 与 $i-2$ 与 $i-3$ 的位置的状态就够了!
一共 $9$ 个状态,再把转移矩阵写出即可。

$$\begin{vmatrix}f(i-3,0) & f(i-3,1) & f(i-3,2) & f(i-2,0) & f(i-2,1) & f(i-2,2) & f(i-1,0) & f(i-1,1) & f(i-1,2)\end{vmatrix} \times \begin{vmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 2 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \end{vmatrix} = \begin{vmatrix}f(i-2,0) & f(i-2,1) & f(i-2,2) & f(i-1,0) & f(i-1,1) & f(i-1,2) & f(i,0) & f(i,1) & f(i,2)\end{vmatrix}$$
虽然矩阵比较大,但不算太难写。
时间复杂度 $O(729 \times T \times \log n)$.

#include <cstdio>
#include <cstring>
using namespace std;
const int mod = 1000000007;
int T,n;
inline int add(int x,int y){int res = x + y;return res >= mod ? res - mod : res;}
inline int mul(int x,int y){return 1ll * x * y % mod;}
const int maxn = 10;
struct matrix
{
    int n,m,a[maxn][maxn];
    matrix(){memset(a,0,sizeof(a));}
    matrix operator*(const matrix &b)
    {
        matrix c;
        c.n = n,c.m = b.m;
        for(int i = 1;i<=n;++i) for(int j = 1;j<=m;++j) for(int k = 1;k<=b.m;++k) c.a[i][k] = add(c.a[i][k],mul(a[i][j],b.a[j][k]));
        return c;
    }
};
int f[4][3];
int main()
{
    scanf("%d",&T);
    f[1][0] = 1,f[1][1] = 1,f[2][0] = 2,f[2][1] = 1,f[3][0] = 3,f[3][1] = 3,f[3][2] = 2;
    while(T--)
    {
        scanf("%d",&n);
        if(n <= 3) {printf("%d\n",f[n][2]);continue;}
        matrix O;
        O.n = 1,O.m = 9;
        O.a[1][1] = f[1][0],O.a[1][2] = f[1][1],O.a[1][3] = f[1][2];
        O.a[1][4] = f[2][0],O.a[1][5] = f[2][1],O.a[1][6] = f[2][2];
        O.a[1][7] = f[3][0],O.a[1][8] = f[3][1],O.a[1][9] = f[3][2];
        matrix P;
        P.n = 9,P.m = 9;
        P.a[2][9] = 2,P.a[4][1] = 1,P.a[4][7] = 1,P.a[5][2] = 1,P.a[5][8] = 1,P.a[5][9] = 2,P.a[6][3] = 1,P.a[6][9] = 1;
        P.a[7][4] = P.a[7][7] = P.a[7][8] = 1,P.a[8][5] = 1,P.a[9][6] = P.a[9][9] = 1;
        n -= 3;
        while(n)
        {
            if(n & 1) O = O * P;
            P = P * P;
            n >>= 1;
        }
        printf("%d\n",O.a[1][9]);
    }
    return 0;
}

P5460 [BJOI2016]IP地址

首先有一个差分:$[l,r]$ 范围内的变化次数,可以转化为 $[1,r] – [1,l-1]$ 的次数。

转化为前缀和后,考虑按操作离线,此时只要求出 $[1,x]$ 中,在线询问的 ip 地址的变化次数即可。
对规则建字典树,维护 $cnt(x)$ 代表以 $x$ 结尾的串的变化次数。分别考虑增加、删除对 $cnt$ 的影响。
增加一条规则,会让它的子树内除了原本有匹配规则的节点外所有节点的 $cnt(x)$ 全部 $+1$,因为优先匹配更长的前缀。
删除一条规则,思考一下,也是一样的。
可以用一个懒标记维护一下。
还有题目的扯淡描述,询问的是 $[a + 1,b]$ 区间。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1e5 + 100;
int n,m;
int opt[maxn],ANS[maxn];
char opts[maxn][34], query[maxn][34];
vector<int> add[maxn],del[maxn];
int son[maxn * 33][2],cnt[maxn * 33],ed[maxn * 33],tag[maxn * 33],ind;
inline void pushdown(int x)
{
    if(!son[x][0]) son[x][0] = ++ind;
    if(!son[x][1]) son[x][1] = ++ind;
    if(!tag[x]) return;
    if(!ed[son[x][0]]) cnt[son[x][0]] += tag[x],tag[son[x][0]] += tag[x];
    if(!ed[son[x][1]]) cnt[son[x][1]] += tag[x],tag[son[x][1]] += tag[x];
    tag[x] = 0;
}
void modify(char *s,int val)
{
    int u = 0;
    for(;*s != '\0';++s) pushdown(u), u = son[u][*s - '0'];
    ed[u] += val,tag[u]++,cnt[u]++;
}
int ask(char *s)
{
    int u = 0;
    for(;*s != '\0';++s) pushdown(u),u = son[u][*s - '0'];
    return cnt[u];
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i = 1;i<=n;++i)
    {
        static char t[10];
        scanf("%s %s",t,opts[i] + 1);
        if(t[0] == 'A') opt[i] = 1; else opt[i] = -1;
    }
    for(int i = 1,a,b;i<=m;++i)
    {
        scanf("%s %d %d",query[i] + 1,&a,&b);
        del[a].push_back(i),add[b].push_back(i);
    }
    for(int i = 1;i<=n;++i)
    {
        modify(opts[i] + 1,opt[i]);
        for(vector<int>::iterator it = add[i].begin();it!=add[i].end();++it) ANS[*it] += ask(query[*it] + 1);
        for(vector<int>::iterator it = del[i].begin();it!=del[i].end();++it) ANS[*it] -= ask(query[*it] + 1);
    }
    for(int i = 1;i<=m;++i) printf("%d\n",ANS[i]);
    return 0;
}

P6623 [省选联考 2020 A 卷] 树

维护每个子树内,点的权值加点的深度的异或和?

可以发现,每次 $d(c_i,x)$ 都只会加一。
维护关于子树的信息,想到线段树合并。由于信息与位有关,考虑 01trie 这种类似线段树的东西,那么就可以考虑 01trie 合并。
考虑全局加一怎么处理,其实每次加一,定义根节点为二进制末尾,从根节点开始一路交换左右儿子,然后递归进入新的 $0$ 中,相当于加一之后一路进位。

当然,进位后还要继承一下原先的节点值。

#include <cstdio>
#include <algorithm>
const int maxn = 6e5 + 100;
int n,w[maxn];
int fa[maxn];
struct node
{
    int to,next;
}E[maxn];
int head[maxn],tot;
inline void add(int x,int y){E[++tot].to = y,E[tot].next = head[x],head[x] = tot;}
int sz[maxn],hson[maxn];
int root[maxn],son[maxn*4][2],cnt[maxn*4],cntsum[maxn*4],val[maxn*4],ind;
int s[maxn * 4],top;
inline int newnode(){return top > 0 ? s[top--] : ++ind;}
inline void del(int x){ if(x) son[x][0] = son[x][1] = cnt[x] = cntsum[x] = val[x] = 0,s[++top] = x; }
inline void pushup(int p)
{
    if(son[p][0] && son[p][1]) 
    {
        val[p] = ((val[son[p][0]] ^ val[son[p][1]]) << 1) ^ (cntsum[son[p][1]] & 1);
        cntsum[p] = cntsum[son[p][0]] + cntsum[son[p][1]] + cnt[p];
    }
    else if(son[p][0]) val[p] = val[son[p][0]] << 1,cntsum[p] = cnt[p] + cntsum[son[p][0]];
    else val[p] = (val[son[p][1]] << 1) ^ (cntsum[son[p][1]] & 1),cntsum[p] = cntsum[son[p][1]] + cnt[p];
}
void ins(int u,int t)
{
    if(!t) return (void)(cnt[u]++, cntsum[u]++);
    if(!son[u][t&1]) son[u][t&1] = newnode();
    ins(son[u][t&1],t>>1);
    pushup(u);
}
void addall(int u)
{
    std::swap(son[u][0],son[u][1]);
    if(son[u][0]) addall(son[u][0]);
    if(!son[u][1]) son[u][1] = newnode(); 
    cnt[son[u][1]] += cnt[u],cntsum[son[u][1]] += cnt[u],cnt[u] = 0;
    pushup(u);
}
void merge(int &x,int y)
{
    if(!x || !y) return (void)(x += y);
    merge(son[x][0],son[y][0]),merge(son[x][1],son[y][1]),cnt[x] += cnt[y],pushup(x),del(y);
}
int ANS[maxn];
void pre(int u)
{
    sz[u] = 1;
    for(int p = head[u];p;p=E[p].next)
    {
        int v = E[p].to;
        pre(v),sz[u] += sz[v],hson[u] = sz[v] > sz[hson[u]] ? v : hson[u];
    }
}
void dfs(int u)
{
    if(hson[u]) dfs(hson[u]),merge(root[u],root[hson[u]]);
    for(int p = head[u];p;p=E[p].next)
    {
        int v = E[p].to;
        if(v == hson[u]) continue;
        dfs(v);
        merge(root[u],root[v]);
    }
    addall(root[u]);
    if(w[u]) ins(root[u],w[u]); else 
    {
        if(!son[root[u]][0]) son[root[u]][0] = newnode();
        cnt[son[root[u]][0]]++,cntsum[son[root[u]][0]]++;
        pushup(root[u]);
    }

    ANS[u] = val[root[u]];
}
int main()
{
    scanf("%d",&n);
    for(int i = 1;i<=n;++i) scanf("%d",w + i);
    for(int i = 2;i<=n;++i) scanf("%d",fa + i),add(fa[i],i);
    for(int i = 1;i<=n;++i) root[i] = newnode();
    ind = n;
    pre(1),dfs(1);
    //for(int i = 1;i<=n;++i) printf("%d\n",ANS[i]);
    long long res = 0;
    for(int i = 1;i<=n;++i) res += ANS[i];
    printf("%lld\n",res);
    return 0;
}

P3201 [HNOI2009] 梦幻布丁

考虑对每一个颜色建立一棵动态开点线段树,上线段树合并即可。
如何处理当前一共有多少段颜色呢?考虑一次更改操作对答案的贡献。
可以用线段树维护分隔连续段的段数,每次合并前后更新即可。

维护左右端点是否有当前颜色。
似乎还可以用链表启发式合并来做,时间复杂度同样是 $O(n \log n)$,

#include <cstdio>
const int maxn = 1e5 + 100;
const int maxm = 1e6 + 100;
int n,m,a[maxn],vis[maxm],res;
int root[maxm],L[maxn * 20],R[maxn * 20],sum[maxn * 20],lval[maxn * 20],rval[maxn * 20],ind;
int s[maxn * 20],top;
inline int newnode(){return top > 0 ? s[top--] : ++ind;}
inline void del(int x){if(x) L[x] = R[x] = sum[x] = lval[x] = rval[x] = 0,s[++top] = x;}
inline void pushup(int p)
{
    sum[p] = sum[L[p]] + sum[R[p]],lval[p] = lval[L[p]],rval[p] = rval[R[p]];
    if(rval[L[p]] && lval[R[p]]) --sum[p];

}
void modify(int l,int r,int &p,int pos)
{
    if(!p) p = newnode();
    if(l == r) return (void)(lval[p] = rval[p] = sum[p] = 1);
    int mid = (l + r) >> 1;
    if(pos <= mid) modify(l,mid,L[p],pos); else modify(mid + 1,r,R[p],pos);
    pushup(p);
}
void merge(int &x,int y)
{
    if(!x || !y) return (void)(x += y);
    merge(L[x],L[y]),merge(R[x],R[y]),pushup(x),del(y);
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i = 1;i<=n;++i) scanf("%d",a + i),modify(1,n,root[a[i]],i);
    for(int i = 1;i<=n;++i) if(!vis[a[i]]) res += sum[root[a[i]]],vis[a[i]] = 1;
    for(int i = 1,opt,x,y;i<=m;++i)
    {
        scanf("%d",&opt);
        if(opt == 1)
        {
            scanf("%d %d",&x,&y);
            if(x == y) continue;
            res -= sum[root[x]] + sum[root[y]];
            merge(root[y],root[x]),root[x] = newnode();
            res += sum[root[y]];
        }
        else printf("%d\n",res);
    }
    return 0;
}

P5415 [YNOI2019]游戏

YnOI不考分块了

这似乎是一道货真价实的云南OI题?

初始时第 $k$ 个人最终获胜的概率,加上奇小的数据范围,感觉很是神奇。

考虑动态规划。既然有一个所谓的等待队列,那么考虑将这个东西定义到状态里。

定义 $f(i,j)$ 为初始时第 $k$ 个人在等待队列的第 $i$ 名,而当前的擂主连胜 $j$ 局的情况,此时初始第 $k$ 个人获胜的概率。

当这个人不参与游戏时,每轮游戏它可以稳定前进三名。而擂主可能输,可能赢。

那么有:

$$f(i,j) = \dfrac{1}{4} \times f(i-3,j+1) + \dfrac{3}{4} \times f(i-3,1)$$
考虑下边界条件,任意一个人连胜 $m$ 局后,游戏就结束了,只要知道这个人是不是他就可以了。

$$f(1,m) = 1$$

$$\forall 2 \le i \le n,f(i,m) = 0$$
接下来还有他参与游戏的情况。讨论输赢之后,还要讨论获胜的人在他前方还是后方。

如果他获胜,那么他成为擂主。如果原先的擂主获胜,按照编号插入尾部。如果非原先擂主获胜,那么原先擂主在尾部也要排在他的前面。

$$f(2,j) = \dfrac{1}{4} \times f(1,1) + \dfrac{1}{4} \times f(n-2,j + 1) + \dfrac{1}{2} \times f(n-1,1)$$
$$f(3,j) = \dfrac{1}{4} \times f(1,1) + \dfrac{1}{4} \times f(n-1,j + 1) + \dfrac{1}{4} \times f(n-1,1) + \dfrac{1}{4} \times f(n,1)$$
$$f(4,j) = \dfrac{1}{4} \times f(1,1) + \dfrac{1}{4} \times f(n,j + 1) + \dfrac{1}{2} \times f(n,1)$$
再讨论他是擂主的情况:

$$f(1,j) = \dfrac{1}{4} \times f(1,j + 1) + \dfrac{3}{4} \times f(n-2,1)$$
这下转移式就列完了,最后答案就是 $f(k,0)$,此时考虑怎么转移。

这一大团东西,看上去就成环了,考虑高斯消元。每个状态都有一个转移方程,那么解这个线性多元方程组即可。

一共 $n \times (m + 1)$ 个状态,时间复杂度 $O(n^3m^3)$.

还有一个鬼畜的小细节:需要使用 $+=$ 而非 $=$,因为可能有从相同状态转移。例如 $j=0$ 时。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 25;
int T,n,m,k;
int f[maxn][maxn],row,col;
long double a[maxn*maxn][maxn*maxn];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        col = row = 0;
        scanf("%d %d %d",&n,&m,&k);
        memset(a,0,sizeof(a));
        for(int i = 1;i<=n;++i) for(int j = 0;j<=m;++j) f[i][j] = ++col;
        ++col;//constant column.
        a[++row][f[1][m]] = 1.0,a[row][col] = 1.0;
        for(int i = 2;i<=n;++i) a[++row][f[i][m]] = 1.0,a[row][col] = 0.0;
        for(int i = 5;i<=n;++i)
            for(int j = 0;j<m;++j)
                a[++row][f[i][j]] = 1.0,a[row][f[i-3][j+1]] += -0.25,a[row][f[i-3][1]] += -0.75;//!!!
        for(int j = 0;j < m; ++j) 
        {
            a[++row][f[1][j]] = 1.0,a[row][f[1][j+1]] += -0.25,a[row][f[n-2][1]] += -0.75;
            a[++row][f[2][j]] = 1.0,a[row][f[1][1]] += -0.25,a[row][f[n-2][j+1]] += -0.25,a[row][f[n-1][1]] += -0.5;
            a[++row][f[3][j]] = 1.0,a[row][f[1][1]] += -0.25,a[row][f[n-1][j+1]] += -0.25,a[row][f[n-1][1]] += -0.25,a[row][f[n][1]] += -0.25;
            a[++row][f[4][j]] = 1.0,a[row][f[1][1]] += -0.25,a[row][f[n][j+1]] += -0.25,a[row][f[n][1]] += -0.5;
        }
        //for(int i = 1;i<=row;puts(""),++i) for(int j = 1;j<=col;++j) printf("%.2f ",a[i][j]);
        for(int i = 1;i<=row;++i)
        {
            int maxx = i;
            for(int j = i + 1;j<=row;++j) if(fabs(a[j][i]) > fabs(a[maxx][i])) maxx = j;
            if(maxx != i) for(int j = 1;j<=col;++j) std::swap(a[i][j],a[maxx][j]);
            for(int j = 1;j<=row;++j)
            {
                if(i == j) continue;
                double t = a[j][i] / a[i][i];
                for(int k = 1;k<=col;++k) a[j][k] -= t * a[i][k];
            }
            /*
            printf("gauss:%d\n",i);
            for(int i = 1;i<=row;puts(""),++i) for(int j = 1;j<=col;++j) printf("%.2f ",a[i][j]);
            puts("");
            */
        }
        printf("%.6Lf\n",a[f[k][0]][col] / a[f[k][0]][f[k][0]]);
    }
    return 0;
}

P6773 [NOI2020]命运

我会大暴力!对每条边枚举对应状态,预期得分16pts.

可以发现潜在的人生经历总是一条祖先到儿子的链,那么当若干个限制条件被施加,最严格的限制是上端点最深的那个限制。

可以定义状态:$f(u,i)$ 代表以 $u$ 为根的子树中,未被满足的最深的询问上端点的深度为 $i$ 时的方案数。

对于转移,其实就是要枚举对应边的 $0/1$ 状态。

首先有边界状态:$\forall i \ge dep(u),f(u,i) = 0$,因为再往上不可能满足这些询问的限制了。

再人为定义 $f(u,0)$ 为子树内限制完全在子树内满足,没有未满足的限制时的方案数。

$$f(u,i)’ = \sum \limits {j=0}^{i} f(v,j) \times f(u,i) + \sum \limits {j=0}^{i-1} f(u,j) \times f(v,i) + \sum \limits _{j=0}^{dep(u)} f(v,j) \times f(u,i)$$
分别对应:选择 $0$ 边且子树不影响当前限制、选择 $0$ 边且子树影响当前限制、选择 $1$ 边的情况。
注意第一二种情况的边界,当 $j=i$ 时只能统计一个。

这个东西看起来可以前缀和优化一下。

$$f(u,i)’ = sum(v,i) \times f(u,i) + sum(u,i-1) \times f(v,i) + sum(v,dep(u)) \times f(u,i)$$

合并一下:

$$f(u,i)’ = f(u,i) \times (sum(v,i) + sum(v,dep(u)) + f(v,i) \times sum(u,i-1)$$
这个 $sum(u,i-1)$ 看似有点鬼畜,但其实不复杂。因为转移到 $f(u,i)’$ 时一定知道 $f(u,i)$ 的值,那么这个就不难了。

这个东西怎么做?考虑维护一棵存放 $f(u,i)$ 的线段树,在树上跑线段树合并,在合并的过程中,用线段树二分的手法去维护前缀和。

还有一个 $sum(v,dep(u))$ 鹤立鸡群,直接查询出来。

在合并操作中,做区间加、区间乘,注意标记顺序即可。

还需要注意标记下放,可能会破坏线段树合并的复杂度,因为下放产生的新节点也会合并进去,随后不断产生复杂度代价把整棵树跑满。

由于是乘法标记,因此空节点可以直接不下放。

如果是通用标记,可以在合并过程中判断是空节点时,下放标记但不递归。

#include <algorithm>
#include <cctype>
#include <cstdio>
const int maxn = 1e6 + 100;
const int mod = 998244353;
inline int add(int x, int y) { int res = x + y; return res >= mod ? res - mod : res; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
const int bufSize = 1e6;
inline char nc()
{
#ifdef DEBUG
    return getchar();
#endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline T read(T& r)
{
    static char c;
    r = 0;
    for (c = nc(); !isdigit(c); c = nc());
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r;
}
struct node
{
    int to, next;
} E[maxn << 2];
int Eh[maxn], Gh[maxn], tot;
inline void addE(int x, int y) { E[++tot].next = Eh[x], Eh[x] = tot, E[tot].to = y; }
inline void addG(int x, int y) { E[++tot].next = Gh[x], Gh[x] = tot, E[tot].to = y; }
int n, m, dep[maxn], up[maxn], size[maxn], son[maxn], maxdep;
void dfs1(int u, int fa)
{
    dep[u] = dep[fa] + 1;
    for (int p = Gh[u]; p; p = E[p].next) up[u] = std::max(up[u], dep[E[p].to]);
    size[u] = 1;
    for (int p = Eh[u]; p; p = E[p].next)
    {
        int v = E[p].to;
        if (v == fa) continue;
        dfs1(v, u), size[u] += size[v];
        if (size[v] > size[son[u]]) son[u] = v;
    }
}
namespace seg
{
int root[maxn], L[maxn * 10], R[maxn * 10], sum[maxn * 10], multag[maxn * 10], s[maxn * 10], top, ind;
inline int newnode()
{
    int id = top > 0 ? s[top--] : ++ind;
    L[id] = R[id] = sum[id] = 0, multag[id] = 1;
    return id;
}
inline void delnode(int x) { if (x) s[++top] = x; }
inline void pushdown(int p)
{
    if (multag[p] != 1)
    {
        if (L[p])
        {
            sum[L[p]] = mul(sum[L[p]], multag[p]);
            multag[L[p]] = mul(multag[L[p]], multag[p]);
        }
        if (R[p])
        {
            sum[R[p]] = mul(sum[R[p]], multag[p]);
            multag[R[p]] = mul(multag[R[p]], multag[p]);
        }
        multag[p] = 1;
    }
}
inline void pushup(int p) { sum[p] = add(sum[L[p]], sum[R[p]]); }
void modify(int l, int r, int& p, int pos, int k)
{
    if (!p) p = newnode();
    if (l == r) return (void)(sum[p] += k);
    int mid = (l + r) >> 1;
    pushdown(p);
    if (pos <= mid) modify(l, mid, L[p], pos, k); else modify(mid + 1, r, R[p], pos, k);
    pushup(p);
}
int ask(int l, int r, int p, int ll, int rr)
{
    if (!p) return 0;
    if (l >= ll && r <= rr) return sum[p];
    int mid = (l + r) >> 1, res = 0;
    pushdown(p);
    if (ll <= mid) res = ask(l, mid, L[p], ll, rr);
    if (rr > mid) res = add(res, ask(mid + 1, r, R[p], ll, rr));
    return res;
}
int merge(int l, int r, int x, int y, int& xsum, int& ysum)  //ysum is originally depval
{
    if (!x && !y) return 0;
    if (!x || !y)
    {
        if (!x)
        {
            ysum = add(ysum, sum[y]);
            sum[y] = mul(sum[y], xsum), multag[y] = mul(multag[y], xsum);
            return y;
        }
        xsum = add(xsum, sum[x]);
        sum[x] = mul(sum[x], ysum), multag[x] = mul(multag[x], ysum);
        return x;
    }
    if (l == r)
    {
        ysum = add(ysum, sum[y]);
        int oldx = sum[x];
        sum[x] = add(mul(sum[y], xsum), mul(sum[x], ysum));
        xsum = add(xsum, oldx);
        delnode(y);
        return x;
    }
    int mid = (l + r) >> 1;
    pushdown(x), pushdown(y);
    L[x] = merge(l, mid, L[x], L[y], xsum, ysum);
    R[x] = merge(mid + 1, r, R[x], R[y], xsum, ysum);
    pushup(x), delnode(y);
    return x;
}
}  // namespace seg
void dfs2(int u, int fa)
{
    seg::modify(0, maxdep, seg::root[u], up[u], 1);
    if (son[u])
    {
        dfs2(son[u], u);
        int xsum = 0, ysum = seg::ask(0, maxdep, seg::root[son[u]], 0, dep[u]);
        seg::root[u] = seg::merge(0, maxdep, seg::root[u], seg::root[son[u]], xsum, ysum);
    }
    for (int p = Eh[u]; p; p = E[p].next)
    {
        int v = E[p].to;
        if (v == fa || v == son[u]) continue;
        dfs2(v, u);
        int xsum = 0, ysum = seg::ask(0, maxdep, seg::root[v], 0, dep[u]);
        seg::root[u] = seg::merge(0, maxdep, seg::root[u], seg::root[v], xsum, ysum);
    }
}
signed main()
{
    read(n);
    for (int i = 1, a, b; i < n; ++i) read(a), read(b), addE(a, b), addE(b, a);
    read(m);
    for (int i = 1, a, b; i <= m; ++i) read(a), read(b), addG(a, b), addG(b, a);
    dfs1(1, 0);
    for (int i = 1; i <= n; ++i) maxdep = std::max(maxdep, dep[i]);
    dfs2(1, 0);
    printf("%d\n", seg::ask(0, maxdep, seg::root[1], 0, 0));
    return 0;
}

P3750 [六省联考2017]分手是祝愿

神仙题。完全没有思路。抄题解。

一个数的约数是 $\log n$ 级别的,那么对一个数的操作可以直接上暴力模拟。

直接埃氏筛预处理约数,调和级数复杂度。

然后引出神秘结论:

每个开关的效果都是独一无二的。不存在开关组合,使得该组合执行后能得到某开关的效果。

从大到小,遇到亮的就消除,这个贪心就能获取最少步数。因为:如果它不是此时消除,就只能用更大的数消除,而原本是亮的更大的数已经消去,将灭的更大的数点亮后,大数又无法消除。而每个开关,最多操作一次,因为两次相当于没操作。

那么模拟一遍,就知道最少按几个键了。

知道最少按几个键之后,定义 $f(i)$ 为还需要按 $i$ 个键的期望步数。初始,有 $f(num) = 0$.

$$f(i) = \dfrac{i}{n} \times (f(i-1) + 1) + \dfrac{n-i}{n} \times (f(i+1) + 1)$$

我会高斯消元!显然高斯消元是无法通过这么大的范围的。

那么按照套路,换一种方法,定义 $f(i)$ 为按掉第 $i$ 个需要的键的期望步数,即从剩余 $i$ 个键状态转移到剩余 $i-1$ 个键状态的期望步数。初始时有 $f(n) = 1$.

$$f(i) = \dfrac{i}{n} + \dfrac{n-i}{n} \times (f(i) + f(i+1) + 1)$$

这个东西就是可做的了,化简一下有:

$$f(i) = \dfrac{n-i}{i} \times f(i+1) + \dfrac{n}{i}$$

最后统计答案,判断一下 $num$ 与 $k$ 的关系,然后累加即可。最后再莫名其妙地乘一个阶乘。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1e5 + 100;
const int mod = 100003;
inline int add(int x,int y){int res = x + y;return res >= mod ? res - mod : res;}
inline int mul(int x,int y){return 1ll * x * y % mod;}
vector<int> frac[maxn];
int n,k,a[maxn],f[maxn],inv[maxn];
int main()
{
    scanf("%d %d",&n,&k);
    for(int i = 1;i<=n;++i) scanf("%d",a + i);
    for(int j = 1;j<=n;++j) for(int i = 1;i<=n;i+=j) frac[i].push_back(j);
    int num = 0;
    for(int i = n;i;--i) if(a[i]) 
    {
        for(vector<int>::iterator it = frac[i].begin();it!=frac[i].end();++it) a[*it] ^= 1;
        ++num;
    }
    if(k >= num) 
    {
        for(int i = 1;i<=n;++i) num = mul(num,i);
        printf("%d\n",num);
    }
    else
    {
        inv[1] = 1;
        for(int i = 2;i<=n;++i) inv[i] = mul(mod - mod / i,inv[mod % i]);
        f[n] = 1;
        for(int i = n - 1;i;--i) f[i] = add(mul(mul(n-i,inv[i]),f[i+1]),mul(n,inv[i]));
        for(int i = 1;i<=n;++i) printf("%d %d\n",i,f[i]);
        int res = k;
        for(int i = num;i > k;--i) res = add(res,f[i]);
        for(int i = 1;i<=n;++i) res = mul(res,i);
        printf("%d\n",res);
    }
    return 0;
}

P3749 [六省联考2017]寿司餐厅

最大权闭合子图。

考虑将 $d(i,j)$ 的收益抽象成带权点,可以发现,选择 $d(i,j)$ 则一定选择 $d(i+1,j)$ 与 $d(i,j-1)$,可以依据此连边。

此外,代价的贡献可以拆成选择某种类型的物品一次性支付一定代价,随后每选择一个该种物品付出一定代价。
将物品种类抽象成带权点,选择 $d(i,i)$ 则一定选择对应的物品种类。至于单个物品代价,可以直接对 $d(i,i)$ 做减法。

使用最小割求解。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 110;
const int maxm = 1e6;
struct node
{
    int to,next,cap;
}E[maxm];
int head[maxm],tot = 1;
inline void add(int x,int y,int cap)
{
    E[++tot].next = head[x],head[x] = tot,E[tot].to = y,E[tot].cap = cap;
    E[++tot].next = head[y],head[y] = tot,E[tot].to = x,E[tot].cap = 0;
}
int n,m,a[maxn],d[maxn][maxn],id[maxn][maxn],type[maxn*10],S,T,cnt,maxtype;
const int inf = 1 << 28;
int dep[maxm],cur[maxm];
bool bfs()
{
    static int q[maxm],qh,qt;
    for(int i = 1;i<=cnt;++i) dep[i] = 0;
    qh = 1,q[qt = 1] = S,dep[S] = 1,cur[S] = head[S];
    while(qt >= qh)
    {
        int u = q[qh++];
        if(u == T) return 1;
        for(int p = head[u],v;p;p=E[p].next) 
            if(E[p].cap && !dep[v = E[p].to]) dep[v] = dep[u] + 1,q[++qt] = v,cur[v] = head[v];
    }
    return 0;
}
long long dfs(int u,long long flow)
{
    if(!flow || u == T) return flow;
    long long vflow = 0,sumflow = 0;
    for(int &p = cur[u];p;p=E[p].next)
    {
        int v = E[p].to;
        if(E[p].cap && dep[v] == dep[u] + 1 && (vflow = dfs(v,std::min(flow,1ll * E[p].cap))))
        {
            flow -= vflow,sumflow += vflow,E[p].cap -= vflow,E[p^1].cap += vflow;
            if(flow == 0) break;
        }
    }
    return sumflow;
}
int main()
{
    scanf("%d %d",&n,&m);
    S = ++cnt,T = ++cnt;
    for(int i = 1;i<=n;++i) scanf("%d",a + i),maxtype = std::max(maxtype,a[i]);
    for(int i = 1;i<=n;++i) for(int j = i;j<=n;++j) scanf("%d",d[i] + j),id[i][j] = ++cnt;
    for(int i = 1;i<=maxtype;++i) type[i] = ++cnt;
    long long sum = 0;
    for(int i = 1;i<=maxtype;++i) add(type[i],T,m * i * i);
    for(int i = 1;i<=n;++i) add(id[i][i],type[a[i]],inf);
    for(int i = 1;i<=n;++i) d[i][i] -= a[i];
    for(int i = 1;i<=n;++i) 
    {
        for(int j = i;j<=n;++j) 
        {
            if(d[i][j] > 0)  add(S,id[i][j],d[i][j]),sum += d[i][j];
            else add(id[i][j],T,-d[i][j]);
            if(id[i][j-1] > 0) add(id[i][j],id[i][j-1],inf);
            if(id[i+1][j] > 0) add(id[i][j],id[i+1][j],inf);
        }
    }
    long long sumflow = 0;
    while(bfs()) sumflow += dfs(S,1ll << 60);
    printf("%lld\n",sum - sumflow);
    return 0;
}

P4159 [SCOI2009] 迷路

定义 $f(u,i)$ 为在时刻 $i$ 位于位置 $t$ 的方案数。

$$f(v,i+1) = \prod f(u,i)$$

然后使用美食家的套路,拆点来做边权 $w > 1$ 的情况。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 110;
const int mod = 2009;
inline int add(int x,int y){int res = x + y;return res >= mod ? res - mod : res;}
inline int mul(int x,int y){return 1ll * x * y % mod;}
struct matrix
{
    int n,m;
    int a[maxn][maxn];
    matrix() {memset(a,0,sizeof(a));}
    matrix operator*(const matrix b)
    {
        matrix c;
        c.n = n,c.m = b.m;
        for(int i = 1;i<=n;++i) for(int j = 1;j<=m;++j) for(int k = 1;k<=b.m;++k) 
            c.a[i][k] = add(c.a[i][k],mul(a[i][j],b.a[j][k]));
        return c;
    }
};
int n,t,cnt,id[maxn][maxn];
matrix A,B;
char s[maxn];
int main()
{
    scanf("%d %d",&n,&t);
    for(int i = 1;i<=n;++i) for(int j = 1;j<=9;++j) id[i][j] = ++cnt;
    for(int i = 1;i<=n;++i) for(int j = 2;j<=9;++j) B.a[id[i][j]][id[i][j-1]] = 1;
    for(int i = 1;i<=n;++i)
    {
        scanf("%s",s + 1);
        for(int j = 1;j<=n;++j) 
            if(s[j] != '0')
            {
                int d = s[j] - '0';
                B.a[id[i][1]][id[j][d]] = 1;
            }
    }

    A.n = 1,A.m = cnt,B.n = B.m = cnt;
    A.a[1][id[1][1]] = 1;
    for(;t;t >>= 1)
    {
        if(t & 1) A = A * B;
        B = B * B;
    }
    printf("%d\n",A.a[1][id[n][1]]);
    return 0;
}

P3597 [POI2015]WYC

走 $k$ 步的总路径数是可以用矩阵计算出来的,那么有一个想法:倍增处理出 $2^k$ 步的转移矩阵,然后用状态矩阵去类似倍增那样找出步数。

然后同样拆点处理边权即可。

有一个鬼畜的坑点:连接相同两点的两条边,也看作不同,因此需要 $+1$ 而不能直接赋值。

注意一下不要溢出,可以用极大值标记的方法。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 200;
long long k;
inline long long add(long long x,long long y)
{
    if(x == -1 || y == -1) return -1;
    long long res = x + y;
    return res > k ? -1 : res;
}
inline long long mul(long long x,long long y)
{
    if(x == 0 || y == 0) return 0;
    if(x == -1 || y == -1) return -1;
    long long res = x * y;
    return res > k ? -1 : res;
}
struct matrix
{
    int n,m;
    long long a[maxn][maxn];
    matrix(){memset(a,0,sizeof(a));}
    matrix operator*(const matrix &b)
    {
        matrix c;
        c.n = n,c.m = b.m;
        for(int i = 1;i<=n;++i) for(int j = 1;j<=m;++j) for(int k = 1;k<=b.m;++k)
            c.a[i][k] = add(c.a[i][k],mul(a[i][j],b.a[j][k]));
        return c;
    }
    void output()
    {
        puts("");
        for(int i = 1;i<=n;puts(""),++i) for(int j = 1;j<=m;++j) printf("%lld ",a[i][j]);
        puts("");
    }
}A[100];
int n,m,id[maxn][4],ind;
int main()
{
    scanf("%d %d %lld",&n,&m,&k);
    for(int i = 1;i<=n;++i) for(int j = 1;j<=3;++j) id[i][j] = ++ind;
    ++ind;//sum point
    A[0].n = ind,A[0].m = ind;
    for(int i = 1;i<=n;++i) for(int j = 2;j<=3;++j) A[0].a[id[i][j]][id[i][j-1]] = 1;
    for(int i = 1;i<=n;++i) A[0].a[id[i][1]][ind] = 1;
    A[0].a[ind][ind] = 1;
    for(int i = 1,a,b,c;i<=m;++i)
    {
        scanf("%d %d %d",&a,&b,&c);
        A[0].a[id[a][1]][id[b][c]] += 1;
    }
    int maxlog = 1;
    matrix S;
    S.n = 1,S.m = ind;
    for(int i = 1;i<=n;++i) S.a[1][id[i][1]] = 1;
    S.a[1][ind] = -n;
    for(;;++maxlog)
    {
        A[maxlog] = A[maxlog-1] * A[maxlog-1];
        matrix T = S * A[maxlog];
        long long sum = T.a[1][ind];
        if(sum == -1) break;
        for(int j = 1;j<=n;++j) sum = add(sum,T.a[1][id[j][1]]);
        if(sum == -1) break;
        if(maxlog > 70){puts("-1");return 0;}
    }
    //A[0].output(),A[1].output();
    long long res = 0;
    for(int i = maxlog;i >= 0;--i)
    {
        matrix T = S * A[i];
        long long sum = T.a[1][ind];
        if(sum == -1) continue;
        for(int j = 1;j<=n;++j) sum = add(sum,T.a[1][id[j][1]]);
        if(sum == -1) continue;
        if(sum < k) res |= 1ll << i,S = T;
        //printf("%d %lld\n",i,sum);
        //if(sum == -1) continue;

    }
    //S.output();
    printf("%lld\n",res + 1);
    return 0;
}

P3582 [POI2015]KIN

题意:$m$ 种物品,每种权值为 $w_i$ ,给一个长为 $n$ 的序列,第 $i$ 个位置是第 $a_i$ 种物品。选择一个区间 $[l,r]$,随后可以获取区间内仅出现一次的物品的权值和。

最大化权值和。

考虑常规套路,移动一个端点,用数据结构维护选择另一个端点的答案,看起来就很线段树。

考虑左端点向左单调,当加入一个点时,它到它上次出现位置的答案会增加它的权值,而它的上次出现到它的上两次出现会减少它的权值。

所以就可以动态维护了,总感觉这个东西被出烂了。

区间加、全局最大值即可。

第一次写忘记下推标记了,我也太蠢了。

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize],*p1 = buf,*p2 = buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,bufSize,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
inline T read(T &r)
{
    static char c;
    r = 0;
    for(c=nc();!isdigit(c);c=nc());
    for(;isdigit(c);c=nc()) r=r*10+c-48;
    return r;
}
const int maxn = 1e6 + 100;
int n,m,a[maxn],w[maxn],last[maxn],vis[maxn];
long long maxx[maxn << 2],tag[maxn << 2];
#define ls p << 1
#define rs p << 1 | 1
inline void pushup(int p){maxx[p] = max(maxx[ls],maxx[rs]);}
inline void pushdown(int p)
{
    if(!tag[p]) return;
    maxx[ls] += tag[p],maxx[rs] += tag[p],tag[ls] += tag[p],tag[rs] += tag[p],tag[p] = 0;
}
void modify(int l,int r,int p,int ll,int rr,int k)
{
    if(l >= ll && r <= rr) return (void)(maxx[p] += k,tag[p] += k);
    int mid = (l + r) >> 1;
    pushdown(p);
    if(ll <= mid) modify(l,mid,ls,ll,rr,k); 
    if(rr > mid) modify(mid + 1,r,rs,ll,rr,k);
    pushup(p);
}
signed main()
{
    read(n),read(m);
    for(int i = 1;i<=n;++i) read(a[i]);
    for(int i = 1;i<=m;++i) read(w[i]);
    for(int i = n;i;--i) 
    {
        if(!vis[a[i]]) last[i] = n + 1;
        else last[i] = vis[a[i]];
        vis[a[i]] = i;
    }
    long long res = 0;
    for(int l = n;l;--l)
    {
        modify(1,n,1,l,last[l] - 1,w[a[l]]);
        if(last[l] <= n) modify(1,n,1,last[l],last[last[l]] - 1,-w[a[l]]);
        res = std::max(res,maxx[1]);
    }
    printf("%lld\n",res);
    return 0;
}

CF1327F AND Segments

首先每位是独立的,拆位后,计算每位的方案数用乘法原理。

对于一个限制,拆位后,对应位要么是零要么是一。如果是零,则要求 $[L,R]$ 中至少有一个零。如果是一,则要求 $[L,R]$ 中全部是一。

可以考虑动态规划?定义 $f(i,j)$ 为考虑前 $i$ 位,最后一个零在第 $j$ 位的方案数。

可以发现,零限制的 $L$ 越大,限制越严格,只需要用到最严的限制即可。

而一限制可以转化为对单点限制,即限制 $[L,R]$ 间的点强制选择一。

记最严格的零限制的左端点为 $lim(i)$,且保证 $lim(i) \le i$:

$$\forall j < lim(i), f(i,j) = 0$$

$$\forall lim(i) \le j < i, f(i,j) = f(i-1,j)$$

如果 $i$ 点强制选一,那么 $f(i,i) = 0$,否则有:$f(i,i) = \sum \limits _{k=lim(i-1)}^{i-1} f(i-1,j)$

第一反应拿数据结构硬上,然而拆位后复杂度必须是线性,否则无法通过。

有 $lim(i)$ 单调递增,可以用一个指针来维护。指针移动的同时还可以维护 $f(i,i) = \sum \limits _{k=lim(i-1)}^{i-1} f(i-1,j)$,那么一切都好起来了。

#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize],*p1 = buf,*p2 = buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,bufSize,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
inline T read(T &r)
{
    static char c;
    r = 0;
    for(c=nc();!isdigit(c);c=nc());
    for(;isdigit(c);c=nc()) r=r*10+c-48;
    return r;
}
const int maxn = 5e5 + 100;
const int mod = 998244353;
inline int add(int x,int y){int res = x + y;return res >= mod ? res - mod : res;}
inline int mul(int x,int y)
{
    long long res = 1ll * x * y;
    return res >= mod ? res % mod : res;
}
struct node
{
    int l,r,x;
}A[maxn];
int n,m,k,lim[maxn],f[maxn],d[maxn];
int main()
{
    read(n),read(k),read(m);
    for(int i = 1;i<=m;++i) read(A[i].l),read(A[i].r),read(A[i].x);
    int res = 1;
    for(int bit = 0;bit < k;++bit)
    {
        for(int i = 1;i<=n + 1;++i) d[i] = lim[i] = f[i] = 0;
        for(int i = 1;i<=m;++i) 
            if((A[i].x >> bit) & 1) d[A[i].l]++,d[A[i].r+1]--;
            else lim[A[i].r] = max(lim[A[i].r],A[i].l);
        for(int i = 2;i<=n + 1;++i) d[i] += d[i-1], lim[i] = max(lim[i],lim[i-1]);
        f[0] = 1;
        int p = 0,sum = f[0];
        for(int i = 1;i<=n + 1;++i)
        {
            if(!d[i]) f[i] = sum,sum = add(sum,f[i]);
            while(p < lim[i]) sum = add(sum,mod - f[p++]);
        }
        //printf("%d %d\n",bit,f[n+1]);
        res = mul(res,f[n+1]);
    }
    printf("%d\n",res);
    return 0;
}

CF1039D You Are Given a Tree

给一棵 $n$ 个节点的树,询问对于 $k \in [1,n]$,这棵树划分为若干条不相交的长度为 $k$ 的简单路径,能得到的最大路径数。

首先明确对于固定的 $k$ 如何求出答案。

对于一个以 $u$ 为根的子树,要么最长链与次长链拼接为答案做出贡献,要么让最长链向上延伸。

如果拼接可以 $>k$,那么直接拼接。因为向上延伸后也最多只能做出一次贡献,并且潜力更小。

那么可以 $O(nk)$ 地暴力求解,没有感觉到什么优化方法……

不过有一个直观感受,当 $k$ 上升时,路径数一定快速减小,并且有长段的平台。

可以发现,路径数的值域是 $[0,n]$,如果对每个值,二分出一个对应的 $k$ 的取值区间,就可以解决问题。

然而会发现,对于一个值,需要 $O(n \log n)$ 的代价才能求出对应的区间,这甚至大于暴力求解的 $O(n)$,如果值域这么大反而会跑得更慢。

那么一个 $k$ 的值域形式是什么?$\dfrac{n}{k}$,在 $k$ 较小时,随着 $k$ 增加,值域迅速缩小,因此可以考虑根号分治

设阙值为 $B$,对于 $k \in [1,B]$ 直接暴力,否则二分,时间复杂度 $O(nB + \dfrac{n}{B} \times n \log n)$,在 $B = \sqrt{n \log n}$ 时最优。

这样可以得到一个 $O(n\sqrt{n \log n})$ 的优秀做法,虽然常数巨大,但调调块长应该能过。

单次二分代价大,能不能整体二分

可以发现,随着 $k$ 单调递增,路径数单调递减,可以利用这个性质划分值域。

这样可能会退化到 $O(n^2)$,然而实际上复杂度是 $O(n \sqrt{n})$ 的,因为:

不同路径数的取值最多有 $2 \times \sqrt{n}$ 种。对于 $k \in [1,\sqrt{n}]$,每个 $k$ 可以对应一种取值,而对于 $k > \sqrt{n}$,$\dfrac{n}{k} \in [1,\sqrt{n}]$,因此也最多有 $\sqrt{n}$ 种取值。

也就是说,这个整体二分的递归树,最多只有 $\sqrt{n}$ 级别的叶子数量。每个叶子深度最多是 $\log n$,那么最多存在 $\sqrt{n} \times \log n$ 次有效递归,时间复杂度上界是 $O(n\sqrt{n} \log {n})$ 的,看起来很大,但考虑到有许多公共路径不会重复计算,因此常数很小。

然而这个做法应该是严格劣于根号分治的。

#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;
const int bufSize = 1e6;
#define DEBUG
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize],*p1 = buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,bufSize,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
inline T read(T &r)
{
    static char c;
    r = 0;
    for(c=nc();!isdigit(c);c=nc());
    for(;isdigit(c);c=nc()) r = r*10+c-48;
    return r;
}
const int maxn = 1e5 + 100;
struct node
{
    int to,next;
}E[maxn << 1];
int head[maxn],tot;
inline void add(int x,int y){E[++tot].next = head[x],head[x] = tot,E[tot].to = y;}
int n;
int nowk,num,f[maxn];
void dfs(int u,int fa)
{
    int maxx = 0,secx = 0;
    for(int p = head[u];p;p=E[p].next)
    {
        int v = E[p].to;
        if(v == fa) continue;
        dfs(v,u);
        if(f[v] > maxx) secx = maxx,maxx = f[v];
        else if(f[v] > secx) secx = f[v];
    }
    if(maxx + secx + 1 >= nowk) ++num,f[u] = 0;
    else f[u] = maxx + 1;
}
inline int get(int x)
{
    num = 0,nowk = x,dfs(1,0);
    return num;
}
int ANS[maxn];
void solve(int l,int r,int L,int R)
{
    if(l > r || L > R) return;
    if(l == r)
    {
        for(int i = L;i<=R;++i) ANS[i] = l;
        return;
    }
    if(L == R) return (void)(ANS[L] = get(L));
    /*
    int mid = (L + R) >> 1,lres = get(L),rres = get(R);
    ANS[L] = lres,ANS[R] = rres;
    if(lres == rres)
    {
        for(int i = L + 1;i<R;++i) ANS[i] = lres;
        return;
    }
    */
    int mid = (L + R) >> 1,res = get(mid);
    ANS[mid] = res;
    solve(res,r,L,mid - 1),solve(l,res,mid + 1,R);
    //solve(res,lres,L + 1,mid - 1),solve(rres,res,mid + 1,R - 1);
}
int main()
{
    read(n);
    for(int i = 1,a,b;i<n;++i) read(a),read(b),add(a,b),add(b,a);
    solve(0,n,1,n);
    for(int i = 1;i<=n;++i) printf("%d\n",ANS[i]);
    return 0;
}

P3616 富金森林公园

维护 $a_i \ge k$ 的连续段数,是可以用线段树维护的。

然后乱搞一个树套树,但是做不了。因为无法合并 $\log$ 棵树的答案。

维护 $f(i)$ 代表海拔为 $i$ 时的答案。

联通块个数等于点数减去边数。

考虑一个点,在 $h \le a_i$ 时都会存在,考虑一条边,在 $h \le \min(a_i,a_{i+1})$ 时都会存在。

这个动态维护即可。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 4e5 + 100;
struct node
{
    int opt,pos,val;
}A[maxn];
int n,m,a[maxn],H[maxn],cnt;
int sum[maxn];
inline void add(int x,int k) { for(++x;x <= cnt + 10;x+=x&-x) sum[x] += k;}
inline void addrange(int l,int r,int k){add(l,k),add(r+1,-k);}
inline int ask(int x){int res = 0;for(++x;x>0;x-=x&-x) res += sum[x];return res;}
inline void update(int x,int k)
{
    int minn = min(a[x],a[x+1]);
    addrange(1,minn,-k);
}
int main()
{
    scanf("%d %d",&n,&m);
    H[++cnt] = 1 << 30;
    for(int i = 1;i<=n;++i) scanf("%d",a + i),H[++cnt] = a[i];
    for(int i = 1;i<=m;++i)
    {
        scanf("%d",&A[i].opt);
        if(A[i].opt == 1) scanf("%d",&A[i].val),H[++cnt] = A[i].val;
        else scanf("%d %d",&A[i].pos,&A[i].val),H[++cnt] = A[i].val;
    }
    std::sort(H + 1,H + 1 + cnt),cnt = std::unique(H + 1,H + 1 + cnt) - H - 1;
    for(int i = 1;i<=n;++i) a[i] = lower_bound(H + 1,H + 1 + cnt,a[i]) - H;
    for(int i = 1;i<=m;++i) A[i].val = lower_bound(H + 1,H + 1 + cnt,A[i].val) - H;
    for(int i = 1;i<=n;++i) addrange(1,a[i],1);
    for(int i = 1;i<n;++i) update(i,1);
    for(int i = 1;i<=m;++i)
    {
        if(A[i].opt == 1) printf("%d\n",ask(A[i].val));
        else
        {
            int p = A[i].pos,v = A[i].val;
            add(a[p] + 1,1),add(v + 1,-1);
            update(p - 1,-1),update(p,-1);
            a[p] = v;
            update(p-1,1),update(p,1);
        }
    }
    return 0;
}

P4643 [国家集训队]阿狸和桃子的游戏

可以考虑模拟选点过程?然而因为有边权的存在,选点具有后效性。
查看题解。

把边权均摊到两个点上,即每个点都加上 $\dfrac{c}{2}$,然后贪心选择最大即可。

为什么是正确的?当同一个人选择两个点时,这条边权被正确累计。当两个点分别属于两个人时,要求最大化的答案 $X + \dfrac{c}{2} – (Y + \dfrac{c}{2})$,也正确累计。

这说明选择的点集的转化权值和的差等价于原来的权值和的差。

然后贪心一下就好了。感觉被恶评了?原题似乎是动态DP,改题号的时候没清空难度……

不过这个 trick 还是很有趣的。如果要构造出真实的得分,可以记录选择方案,最后计算一遍。

#include <cstdio>
#include <algorithm>
int n,m,w[11000],res;
int main()
{
    scanf("%d %d",&n,&m);
    for(int i = 1;i<=n;++i) scanf("%d",w + i),w[i] <<= 1;
    for(int i = 1,a,b,c;i<=m;++i) scanf("%d %d %d",&a,&b,&c),w[a] += c,w[b] += c;
    std::sort(w + 1,w + 1 + n);
    for(int i = n;i;--i) res += ((i & 1) ? -1 : 1) * w[i];
    return printf("%d\n",res >> 1),0;
}

P4317 花神的数论

首先发现 $sum(i)$ 的值域范围很小,可以考虑统计每个 $sum(i)$ 的值出现了多少次。

如何统计?定义 $f(i,j)$ 为剩余 $i$ 位待定,当前 $sum = j$ 的次数,然后数位 DP 的套路即可。

其实没必要钦定 $sum = j$,可以直接返回乘积。这样可以做到 $O(\log^2 n)$ 的复杂度。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod = 10000007;
long long f[70][70][2];
long long n;
long long dfs(int pos,int limit,int sum)
{
    if(pos == -1) return max(1,sum);
    if(f[pos][sum][limit] != -1) return f[pos][sum][limit];
    int up = limit ? (n >> pos) & 1 : 1;
    long long now = 1;
    for(int i = 0;i<=up;++i) now = now * dfs(pos - 1,limit && i == up,sum + i) % mod;
    return f[pos][sum][limit] = now;
}
int main()
{

    scanf("%lld",&n);
    int up = 0;
    while((1ll << up) < n) ++up;
    memset(f,-1,sizeof(f));
    printf("%lld\n",dfs(up,1,0));
    return 0;
}

P6198 [EER1]单调栈

可以发现 $S_i =1$ 是一个边界情况,这代表单调栈弹空,当前点是前缀最小值。

那么从后往前,第一个 $1$ 最小,第二个 $1$ 次小,依次类推。这样可以使字典序最小。

为什么一定是这样?因为正数第一个 $1$ 一定是当时的最小值,然后一旦出现更小的,势必会将栈弹空而得到 $1$。

对于两个 $S = 1$ 中间的元素,一定都有:$p_i > p_L$,因此可以发现,$p_L$ 始终在栈中,直到遇到 $p_R$,而这段中倒数第一个 $S = 2$ 是最小……出现了,递归!

那么对于确定的序列 $S$,我们已经可以解出 $P$ 了,然而有不确定元素。

可以发现,对于不确定元素,$S_i = S_{i-1} + 1$,这样可以让大的数尽量在后面,保证字典序最小。

然后打了个奇怪的 $O(n^2)$ 的垃圾实现,结果过了。。。。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cctype>
using namespace std;
const int bufSize = 1e6;
inline char nc()
{
    return getchar();
    static char buf[bufSize],*p1 = buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,bufSize,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    r = 0,flag = 1;
    for(c=nc();!isdigit(c);c=nc()) if(c == '-') flag = -1;
    for(;isdigit(c);c=nc()) r=r*10+c-48;
    return r*=flag;
}
const int maxn = 1e6 + 100;
int n,S[maxn],a[maxn],minval;
void solve(int l,int r)
{
    if(l > r) return;
    vector<int> V;
    V.push_back(r + 1);
    for(int i = r;i>=l;--i) if(S[i] == 1) V.push_back(i),a[i] = ++minval;
    V.push_back(l - 1);
    for(int i = l;i<=r;++i) --S[i];
    for(int i = V.size() - 1;i>0;--i) if(V[i] + 1 <= V[i-1] - 1) solve(V[i] + 1,V[i-1] - 1);
}
int main()
{
    read(n);
    for(int i = 1;i<=n;++i) read(S[i]);
    for(int i = 1;i<=n;++i) if(S[i] == -1) S[i] = S[i-1] + 1;
    solve(1,n);
    for(int i = 1;i<=n;++i) printf("%d ",a[i]);
    return 0;
}

要改成真的,其实也不难,记录递归层数,用桶排序去找当前为 $1$ 的点即可。

然而这个货真价实的稳定 $O(n)$ 跑得还没能被卡到 $O(n^2)$ 的乱搞快。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cctype>
using namespace std;
const int bufSize = 1e6;
inline char nc()
{
    return getchar();
    static char buf[bufSize],*p1 = buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,bufSize,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    r = 0,flag = 1;
    for(c=nc();!isdigit(c);c=nc()) if(c == '-') flag = -1;
    for(;isdigit(c);c=nc()) r=r*10+c-48;
    return r*=flag;
}
const int maxn = 1e6 + 100;
int n,S[maxn],a[maxn],head[maxn],minval;
vector<int> V[maxn];
void solve(int l,int r,int dep)
{
    if(l > r) return;
    int tail = head[dep];
    while(V[dep][tail + 1] <= r) ++tail;
    for(int i = tail;i>=head[dep];--i) a[V[dep][i]] = ++minval;
    if(l <= V[dep][head[dep]] - 1) solve(l,V[dep][head[dep]] - 1,dep + 1);
    for(int i = head[dep] + 1;i<=tail;++i) 
        if(V[dep][i-1] + 1 <= V[dep][i] - 1) 
            solve(V[dep][i-1] + 1,V[dep][i] - 1,dep + 1);
    if(V[dep][tail] + 1 <= r) solve(V[dep][tail] + 1,r,dep + 1);
    head[dep] = tail + 1;
}
int main()
{
    read(n);
    for(int i = 1;i<=n;++i) read(S[i]);
    for(int i = 1;i<=n;++i) if(S[i] == -1) S[i] = S[i-1] + 1;
    for(int i = 1;i<=n;++i) V[i].push_back(0),head[i] = 1;
    for(int i = 1;i<=n;++i) V[S[i]].push_back(i);
    for(int i = 1;i<=n;++i) V[i].push_back(n + 1);
    solve(1,n,1);
    for(int i = 1;i<=n;++i) printf("%d ",a[i]);
    return 0;
}

P2605 [ZJOI2010]基站选址

看起来很动态规划的题库。

每个基站会影响前后的费用,可以先不考虑对后方的影响,有状态定义: $f(j,i)$ 为建立了 $j$ 个基站,且最后一个基站在 $i$ 点的当前最小费用。

$$f(j,i) = f(j-1,k) + C_i + cost(k + 1,i – 1)$$

其中 $cost(k + 1,i – 1)$ 代表区间 $[k+1,i-1]$ 在当前覆盖情况下的补偿费用。

这个东西怎么计算?朴素计算方法就是大力遍历,$O(n)$ 查看。那么就能得到一个优秀的 $O(n^3k)$ 做法。

如果在枚举过程中计算,就可以得到 $O(n^2k)$ 的优秀做法。

考虑一个点 $i$ 会在什么时候产生补偿费用,可以二分出 $[L_i,R_i]$,代表如果有基站建造在 $[L_i,R_i]$ 中就不产生费用。反过来,$[1,L_i – 1]$ 与 $[R_i + 1,n]$ 就会产生费用。

考虑建立一棵下标线段树,每个点代表 $f(j-1,k) + cost(k + 1,i – 1)$,每次动态更新 $cost(k+1,i-1)$,可以发现是个区间加法。

然而这样会出现问题:未考虑到当前基站 $i$ 可以减少的费用。 因此我们需要妥善考虑何时将一个点加入费用线段树中。

加入的点需要满足:在之前未被记费用、接下来会被记费用,可以发现,满足条件的是 $R_j = i$ 的点,因此可以把这些点对应存放,遍历时加入。

维护一棵区间加、单点改、维护最小值的线段树。

统计答案是个问题,考虑建立虚点,免费在本点建立基站,但距离要无穷大。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <ctype.h>
const int bufSize = 1e6;
using namespace std;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline T read(T& r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 21000;
const long long inf = 1ll << 60;
int n, k, dis[maxn], cost[maxn], range[maxn], L[maxn], R[maxn], w[maxn];
long long sum[maxn], minn[maxn << 2], tag[maxn << 2];
#define ls p << 1
#define rs p << 1 | 1
inline void pushdown(int p)
{
    if (!tag[p]) return;
    minn[ls] += tag[p], minn[rs] += tag[p], tag[ls] += tag[p], tag[rs] += tag[p], tag[p] = 0;
}
inline void pushup(int p) { minn[p] = min(minn[ls], minn[rs]); }
void modify(int l,int r,int p,int pos,long long k)
{
    if (l == r) return (void)(minn[p] = k);
    int mid = (l + r) >> 1;
    pushdown(p);
    if (pos <= mid) modify(l, mid, ls, pos, k); else modify(mid + 1, r, rs, pos, k);
    pushup(p);
}
void modify(int l, int r, int p, int ll, int rr, long long k)
{
    if (l >= ll && r <= rr) return (void)(minn[p] += k, tag[p] += k);
    int mid = (l + r) >> 1;
    pushdown(p);
    if (ll <= mid) modify(l, mid, ls, ll, rr, k);
    if (rr > mid) modify(mid + 1, r, rs, ll, rr, k);
    pushup(p);
}
void build(int l, int r, int p)
{
    tag[p] = 0, minn[p] = 1 << 30;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(l, mid, ls), build(mid + 1, r, rs);
}
vector<int> V[maxn];
long long f[2][maxn];
int main()
{
    read(n), read(k);
    for (int i = 2; i <= n; ++i) read(dis[i]);
    for (int i = 1; i <= n; ++i) read(cost[i]);
    for (int i = 1; i <= n; ++i) read(range[i]);
    for (int i = 1; i <= n; ++i) read(w[i]), sum[i] = sum[i - 1] + w[i];
    for (int i = 1; i <= n; ++i)
    {
        int l = 1, r = i, mid, ans = i;
        while (l <= r)
        {
            mid = (l + r) >> 1;
            if (dis[mid] >= dis[i] - range[i]) ans = mid, r = mid - 1; else l = mid + 1;
        }
        L[i] = ans;
        l = i, r = n, ans = i;
        while (l <= r)
        {
            mid = (l + r) >> 1;
            if (dis[mid] <= dis[i] + range[i]) ans = mid, l = mid + 1; else r = mid - 1;
        }
        R[i] = ans;
    }
    ++n, L[n] = R[n] = n, cost[n] = 0, w[n] = 1 << 30;
    for (int i = 1; i <= n; ++i) V[R[i]].push_back(i);
    long long res = inf;
    int now = 1, last = 0;
    {
        long long tmp = 0;
        for (int i = 1; i <= n; ++i)
        {
            f[last][i] = tmp + cost[i];
            for (vector<int>::iterator it = V[i].begin(); it != V[i].end(); ++it) tmp += w[*it];
        }
        res = f[last][n];
    }
   for (int t = 2; t <= k + 1; ++t)
    {
        build(1, n, 1);
        for (int i = 1; i <= n; ++i)
        {
            f[now][i] = minn[1] + cost[i];
            for (vector<int>::iterator it = V[i].begin(); it != V[i].end(); ++it)
                if (L[*it] > 1) modify(1, n, 1, 1, L[*it] - 1, w[*it]);
            modify(1, n, 1, i, f[last][i]);
        }
        res = min(res, f[now][n]);
        now ^= 1, last ^= 1;
    }
    printf("%lld\n", res);
    return 0;
}

P2120 [ZJOI2007]仓库建设

动态规划,定义 $f(i)$ 为最后一个仓库建立在 $i$ 点,只考虑前 $i$ 个工厂的最小费用。

枚举上一个仓库进行转移。

$$f(i) = c_i + f(j) + \sum \limits _{k=j+1}^{i-1} p_k \times (x_i – x_k)$$

稍微整理一下式子。

$$f(i) = c_i + f(j) + x_i \times (\sum \limits {k=j+1}^{i-1} p_k) – \sum \limits {k=j+1}^{i-1} (p_k \times x_k)$$

预处理前缀和 $S(i) = \sum \limits {j=1}^i p_j$,$T(i) = \sum \limits {j=1}^i p_j \times x_j$,就可以做到 $O(n^2)$ 转移:

$$f(i) = c_i + f(j) + x_i \times (S(i-1) – S(j)) – (T(i-1) – T(j))$$

只有一项与 $i$,$j$ 同时有关,并且以乘积形式出现,考虑斜率优化。

$$x_i \times S(j) + f(i) – c_i – x_i \times S(i-1) + T(i-1) = f(j) + T(j)$$

令纵坐标$y = f(j) + T(j)$,横坐标 $x = S(j)$,截距 $f(i) – x_i \times S(i-1) + T(i-1) – c_i$,斜率 $k = x_i$,要求最小化截距。

维护斜率递增的下凸包即可。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 1e6 + 100;
int n, dis[maxn], num[maxn], cost[maxn];
int q[maxn], qt, qh;
long long S[maxn], T[maxn], f[maxn];
inline long long getx(int x) { return S[x]; }
inline long long gety(int x) { return f[x] + T[x]; }
inline bool cmp(int a, int b, int c) { return (gety(b) - gety(a)) * (getx(c) - getx(b)) >= (gety(c) - gety(b)) * (getx(b) - getx(a)); }
inline bool cmp2(int a, int b, long long k)
{
    return gety(b) - gety(a) <= k * (getx(b) - getx(a));
}
int main()
{
    read(n);
    for (int i = 1; i <= n; ++i) read(dis[i]),read(num[i]),read(cost[i]);
    for (int i = 1; i <= n; ++i) S[i] = num[i] + S[i - 1], T[i] = 1ll * num[i] * dis[i] + T[i - 1];
    q[++qt] = 0;
    for (int i = 1; i <= n; ++i)
    {
        while(qt > qh && cmp2(q[qh],q[qh + 1],dis[i])) ++qh;
        f[i] = cost[i] + f[q[qh]] + dis[i] * (S[i - 1] - S[q[qh]]) - (T[i - 1] - T[q[qh]]);
        while (qt > qh && cmp(q[qt - 1], q[qt], i)) --qt;
        q[++qt] = i;
    }
//    for(int i = 1;i<=n;++i) printf("%d %lld\n",i,f[i]);
    printf("%lld\n", f[n]);
    return 0;
}

Codeforces Round #683 (Div. 2, by Meet IT)

板刷该场比赛

A

一开始有很多个元素,可以选择 $m$ 次操作,第 $i$ 次操作给除了你选一个元素外其他元素都加 $i$,其实就相当于给你选择的元素减去 $i$,构造一个方案让所有元素相等。

然后发现初始时第 $i$ 个元素大小刚好是 $i$,于是只要顺次操作即可。

#include <cstdio>
int T,n;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        printf("%d\n",n);
        for(int i = 1;i<=n;++i) printf("%d ",i);
        puts("");
    }
    return 0;
}

B

给一个矩阵,可以选择给相邻的两个元素同时取反。最大化所有元素和。

每个元素可以被取反多次。

感觉只要有两个负数,那么两个负数就可以被同时取反。利用中间值一步步传递过去。

那么最后最多剩下一个负数,取绝对值最小的。

#include <cstdio>
#include <algorithm>
const int maxn = 20;
int T,n,m,a[maxn][maxn];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&n,&m);
        for(int i = 1;i<=n;++i) for(int j = 1;j<=m;++j) scanf("%d",a[i] + j);
        int num = 0,minn = 1 << 30;
        for(int i = 1;i<=n;++i) for(int j = 1;j<=m;++j) num += (a[i][j] < 0),minn = std::min(minn,std::abs(a[i][j]));
        int sum = 0;
        for(int i = 1;i<=n;++i) for(int j = 1;j<=m;++j) sum += std::abs(a[i][j]);
        if(num & 1) printf("%d\n",sum - 2 * minn);
        else printf("%d\n",sum);
    }
    return 0;
}

C

好 ad-hocs 的题啊……

首先,如果有任何一个 $w_i \ge \lceil \dfrac{W}{2} \rceil$,直接选择。扔掉所有比背包容量大的编号。

剩下情况,$\forall w_i < \lceil \dfrac{W}{2}\rceil$.

最少需要两件物品才行,可以考虑一路放过去,直到爆仓或者达到目标。

什么时候会爆仓?原本满足 $\sum w_i < \lceil \dfrac{W}{2}\rceil$,放一件之后爆仓,可以发现是不可能的!

所以只需要一路扫过去就可以了。

#include <cstdio>
#include <algorithm>
const int maxn = 2e5 + 100;
int T,n,a[maxn],s[maxn],top;
long long W,mid;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %lld",&n,&W);
        top = 0;
        for(int i = 1;i<=n;++i) scanf("%d",a + i);
        mid = (W + 1) / 2;
        long long now = 0;
        for(int i = 1;i<=n;++i) if(a[i] <= W && a[i] >= mid){printf("1\n%d\n",i);goto end;}
        for(int i = 1;i<=n;++i)
        {
            if(a[i] > W) continue;
            s[++top] = i, now += a[i];
            if(now >= mid)
            {
                printf("%d\n",top);
                while(top) printf("%d ",s[top--]);
                puts("");
                goto end;
            }
        }
        puts("-1");
        end:;
    }
    return 0;
}

D

这种鬼畜组合题?

首先回忆一下 最长公共子序列怎么求,定义 $f(i,j)$ 为 A 串匹配到前 $i$ 个字符,B 串匹配到前 $j$ 个字符时,最长公共子序列的长度。

转移有:

$$f(i,j) = f(i-1,j-1) + 2, \text{ if } A_i = B_j$$

$$f(i,j) = \max(f(i-1,j),f(i,j-1)), \text{ otherwise}$$

在本题中,重新定义 $f(i,j)$ 为 A 串中选出的子串最后一个字符为 $i$,B 串中选出的子串最后一个字符为 $j$ 时,最大的贡献。

当 $A_i = B_j$ 时,可以发现有:

$$f(i,j) = f(i-1,j-1) + 2$$

如果前面已经有字符,那么这个转移方程就是正确的,因为子串必定连续。但有一个问题:可以从空串中转移。

手动加上:

$$f(i,j) = \max(f(i-1,j-1),0) + 2$$

这就是个完备的式子了。

其余情况:

$$f(i,j) = \max(f(i-1,j),f(i,j-1),0) – 1$$

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 5100;
char A[maxn],B[maxn];
int n,m,f[maxn][maxn];
int main()
{
    scanf("%d %d",&n,&m);
    scanf("%s\n%s",A + 1,B + 1);
    int res = 0;
    for(int i = 1;i<=n;++i) for(int j = 1;j<=m;++j)
    {
        if(A[i] == B[j]) f[i][j] = f[i-1][j-1] + 2;
        f[i][j] = max(f[i][j],max(0,max(f[i-1][j],f[i][j-1])) - 1);
        res = max(res,f[i][j]);
    }
    printf("%d\n",res);
    return 0;
}

E

可以发现,每个点向外连一条边,一共有 $n$ 条无向边,而树只有 $n-1$ 条边,因此一定出现重边或者环。

什么时候会出现重边?$a_x \oplus a_y$ 对 $a_x$ 与 $a_y$ 都是最小的时。

一棵树中,一定只会有一条重边。首先,一棵树一定只有一条边多余,现在证明这条边一定是重边:考虑 $\min a_x \oplus a_y$,在所有异或和中,该对最小,那么对 $a_x$ 与 $a_y$ 一定都最小,即出现重边。

原图被分割为若干个联通块,每个联通块都是带有重边的树。

要求选出一些点,使整个图联通,即只存在一条重边。

现在拆位考虑,从高到低,对于每位,按 $0/1$ 分类为集合 $S_0$,$S_1$,可以发现每个集合的点都只会向同集合内点连边。

那么只要保留两个集合内部连边,就一定让原图分裂成两个联通块。

因此需要将某个集合大小删到 $1$ 才能保证图联通。

递归求解。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 2e5 + 100;
int n,a[maxn];
int solve(vector<int> &v,int bit)
{
    if(v.size() <= 3) return 0;
    vector<int> S0,S1;
    for(vector<int>::iterator it = v.begin();it!=v.end();++it) if((*it >> bit) & 1) S1.push_back(*it); else S0.push_back(*it);
    vector<int>().swap(v);
    if(S0.size() <= 1) return solve(S1,bit - 1);
    if(S1.size() <= 1) return solve(S0,bit - 1);
    int s0 = (int)(S0.size()) - 1,s1 = (int)(S1.size()) - 1;
    return min(solve(S1,bit - 1) + s0,solve(S0,bit - 1) + s1);
}
int main()
{
    scanf("%d",&n);
    vector<int> v;
    for(int i = 1,x;i<=n;++i) scanf("%d",&x),v.push_back(x);
    printf("%d\n",solve(v,30));
    return 0;
}

F1

出现次数最多的元素有多个。

查看整个数组出现次数最多的元素,将它的出现次数减少到与次多的一致。

然而可能会在减少的过程中影响到次多的元素的个数。

由于值域较小,可以直接枚举次多的元素是哪个,然后遍历整个数组去检查。

做个只关于这两个元素的前缀和,令 $sum1(r) – sum1(l-1) = sum2(r) – sum2(l-1)$ 即可,调整下形式可以得到 $sum1(r) – sum2(r) = sum1(l – 1) – sum2(l – 1)$,开个桶记录。

那么可以得出相应的区间,使原本出现次数最多的元素与当前钦定的元素出现次数相等。但这有一个问题:它们可能不再是出现次数最多的元素了。

不过可以发现,如果有元素在对应区间出现次数更多,那么在枚举到那个元素时,能计算到的区间长度就更大,最后答案是正确的。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 100;
int n,a[maxn],cnt[110];
int vis[maxn * 2],last[maxn * 2],tim;
int main()
{
    scanf("%d",&n);
    for(int i = 1;i<=n;++i) scanf("%d",a + i),cnt[a[i]]++;
    int maxx = 1;
    for(int i = 1;i<=100;++i) if(cnt[i] > cnt[maxx]) maxx = i;
    int res = 0;
    for(int t = 1;t<=100;++t)
    {
        if(t == maxx) continue;
        int now = 0;
        ++tim;
        vis[now + 200000] = tim,last[now + 200000] = 0;
        for(int i = 1;i<=n;++i)
        {
            if(a[i] == maxx) ++now;
            else if(a[i] == t) --now;
            if(vis[now + 200000] == tim) res = max(res,i - last[now + 200000]);
            else vis[now + 200000] = tim,last[now + 200000] = i;
        }
    }
    printf("%d\n",res);
    return 0;
}

F2

值域变大了,上一题的枚举就做不了了。

考虑枚举左端点?也没法做。

看看题解,根号做法?

所有数的出现次数的和一定,那么出现次数大于 $\sqrt{n}$ 的数至多有 $\sqrt{n}$ 个。

这部分可以大力枚举解决。跟 F1 一样的做法。

然后考虑枚举出现次数。

出现次数只有 $\sqrt{n}$ 个,此时枚举的是答案的次数,满足条件需要:出现次数 $i$ 出现的次数 $\ge 2$,可以用类似莫队的技巧去维护。

双指针扫一遍。

时间复杂度 $O(n\sqrt{n})$.

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 100;
int n,a[maxn],times[maxn],B,s[maxn],top,vis[maxn * 2],tim,last[maxn * 2],res,cnt[maxn],tot[maxn];
inline void add(int x) { tot[cnt[a[x]]++]--,tot[cnt[a[x]]]++; }
inline void del(int x) { tot[cnt[a[x]]--]--,tot[cnt[a[x]]]++; }
int main()
{
    scanf("%d",&n);
    for(int i = 1;i<=n;++i) scanf("%d",a + i),times[a[i]]++;
    int maxx = 1;
    for(int i = 2;i<=n;++i) if(times[i] > times[maxx]) maxx = i;
    B = std::sqrt(n);
    for(int i = 1;i<=n;++i) if(i!=maxx && times[i] > B) s[++top] = i;
    for(int t = 1,now;t<=top;++t)
    {
        now = 0,vis[200000] = ++tim,last[200000] = 0;
        for(int i = 1;i<=n;++i) 
        {
            if(a[i] == maxx) ++now; else if(a[i] == s[t]) --now;
            if(vis[now + 200000] == tim) res = max(res,i - last[now + 200000]); else vis[now+200000] = tim,last[now + 200000] = i;
        }
    }
    for(int t = 1;t<=B;++t)
    {
        for(int i = 1;i<=n;++i) tot[i] = cnt[i] = 0;
        int l = 1,r = 0;
        while(r < n)
        {
            add(++r);
            while(cnt[a[r]] > t) del(l++);
            if(tot[t] >= 2) res = max(res,r - l + 1);
        }
    }
    printf("%d\n",res);
    return 0;
}

Codeforces Round #684 (Div. 2)

A

简单的贪心,要么原串要么全零,要么全一。

懒得讨论了,直接都算一遍取个最小值。

#include <cstdio>
#include <algorithm>
using namespace std;
int T,n,c0,c1,h;
char s[10000];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d %d %d %s",&n,&c0,&c1,&h,s + 1);
        int num0 = 0,num1 = 0;
        for(int i = 1;i<=n;++i) num0 += s[i] == '0',num1 += s[i] == '1';
        printf("%d\n",min(num0 * c0 + num1 * c1,min(num0 * h + n * c1,num1 * h + n * c0)));
    }
    return 0;
}

B

排序一遍,然后从后往前数数取一下就行了。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 100;
int T,n,k,a[maxn];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&n,&k);
        for(int i = 1;i<=n*k;++i) scanf("%d",a + i);
        sort(a + 1,a + 1 + n * k);
        int right = n - (n + 1) / 2;
        long long sum = 0;
        for(int i = 1;i<=k;++i) sum += a[n*k - (right+1) * (i-1) - right];
        printf("%lld\n",sum);
    }
    return 0;
}

C

在一个 $2 \times 2$ 方格中考虑。

如果有三个 $1$,那么一次操作解决。

如果有两个 $1$,那么可以一次操作转化为三个一,然后一次操作解决。

如果有一个 $1$,那么可以一次操作转化为两个 $1$.

如果有四个 $1$,那么可以一次操作转化为一个 $1$.

那么:三个需要一次操作,两个需要两次操作,一个需要三次操作,四个需要四次操作。

刚好卡到上界。

问题在于,可能不能正好分割为 $2 \times 2$ 的方格。

可以把所有的 $1$ 从上到下、从左到右压到最右下角的一个 $2 \times 2$ 的方格里。

具体地,对于平凡的点,如果为 $1$,那么将它的下方、右下方和它一起翻转。如果是最后一个,就将它的下方、左下方一起翻转。

直到两行,可以从左到右一路翻转。

这样每个点至多操作一次,最后在 $2 \times 2$ 的方格中乱搞一下即可。

#include <cstdio>
#include <algorithm>
int T,n,m,a[110][110];
int X[1000000],Y[1000000],cnt;
char s[110];
inline void add(int x,int y)
{
    X[++cnt] = x,Y[cnt] = y,a[x][y] ^= 1;
}
void solve(int n,int m)
{
    int num = a[n][m] + a[n-1][m] + a[n][m-1] + a[n-1][m-1];
        if(num == 4)
        {
            add(n,m),add(n-1,m),add(n,m-1);
            goto one;
        }
        else if(num == 3)
        {
            three:
            if(a[n][m]) add(n,m);
            if(a[n-1][m]) add(n-1,m);
            if(a[n][m-1]) add(n,m-1);
            if(a[n-1][m-1]) add(n-1,m-1);
        }
        else if(num == 2)
        {
            two:
            bool aa = 0,b = 0,c = 0,d = 0;
            if(!a[n][m]) add(n,m),aa = 1;
            if(!a[n-1][m]) add(n-1,m),b = 1;
            if(!a[n][m-1]) add(n,m-1),c = 1;
            if(!a[n-1][m-1]) add(n-1,m-1),d = 1;
            if(!aa && a[n][m]) add(n,m);
            else if(!b && a[n-1][m]) add(n-1,m);
            else if(!c && a[n][m-1]) add(n,m-1);
            else if(!d && a[n-1][m-1]) add(n-1,m-1);
            goto three;
        }
        else if(num == 1)
        {
            one:
            if(a[n][m]) add(n,m),add(n-1,m),add(n,m-1);
            else if(a[n-1][m]) add(n-1,m),add(n,m),add(n,m-1);
            else if(a[n][m-1]) add(n,m-1),add(n,m),add(n-1,m-1);
            else if(a[n-1][m-1]) add(n-1,m-1),add(n,m),add(n,m-1);
            goto two;
        }
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&n,&m);
        cnt = 0;
        for(int i = 1;i<=n;++i)
        {
            scanf("%s",s + 1);
            for(int j = 1;j<=m;++j) a[i][j] = s[j] - '0';
        }
        for(int i = 1;i<= n - 2;++i) for(int j = 1;j<=m;++j)
        {
            if(a[i][j]) 
            {
                add(i,j);
                add(i+1,j);
                if(j == m) add(i+1,j-1);
                else add(i+1,j+1);
            }
        }
        for(int j = 1;j<=m-2;++j) 
        {
            if(a[n-1][j] && a[n][j]) add(n-1,j),add(n,j),add(n-1,j + 1);
            else if(a[n-1][j]) add(n-1,j),add(n-1,j+1),add(n,j+1);
            else if(a[n][j]) add(n,j),add(n-1,j+1),add(n,j+1);
        }

        solve(n,m);
        printf("%d\n",cnt / 3);
        for(int i = 1;i<=cnt;++i) 
        {
            printf("%d %d ",X[i],Y[i]);
            if((i % 3) == 0) puts("");
        }
        //for(int i = 1;i<=n;puts(""),++i) for(int j = 1;j<=m;++j) printf("%d ",a[i][j]);
    }
    return 0;
}

Educational Codeforces Round 98 (Rated for Div. 2)

A

斜着走很优。然后就可以两步走一格。

#include <cstdio>
#include <algorithm>
int T,x,y;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&x,&y);
        int minn = std::min(x,y),res = minn * 2;
        x -= minn,y -= minn,x += y;
        if(x == 0) {printf("%d\n",res);continue;}
        printf("%d\n",res + 2 * x - 1);
    }
}

B

假定调整后的总和为 $sum$,平均后的元素就是 $\dfrac{sum}{n-1}$,要求最大元素不超过这个,即 $maxx \le \dfrac{sum}{n-1}$,反过来就是要求 $sum \ge maxx \times (n – 1)$。

找出原数组中最大元素,对应进行调整?

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 100;
int T,n,a[maxn];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        int maxx = 0;
        long long sum = 0,oldsum;
        for(int i = 1;i<=n;++i) scanf("%d",a + i),maxx = max(maxx,a[i]),sum += a[i];
        oldsum = sum;
        sum = (sum + n - 2) / (n - 1) * (n - 1);//round up
        sum = max(sum,1ll * maxx * (n - 1));
        printf("%lld\n",sum - oldsum);
    }
    return 0;
}

C

每次删除一个子序列,要求子序列是合法括号串。

要求最大化删除次数。

考虑每次只删一个括号,能删则删,两种括号并不互相影响。

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 2e5 + 100;
char s[maxn];
int T,n,num1,num2;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s + 1);
        n = strlen(s + 1);
        int res = 0;
        num1 = num2 = 0;
        for(int i = 1;i<=n;++i)
        {
            if(s[i] == '(') ++num1;
            else if(s[i] == ')')
            {
                if(num1) ++res,--num1;
            }
            else if(s[i] == '[') ++num2;
            else
            {
                if(num2) ++res,--num2;
            }
        }
        printf("%d\n",res);
    }
    return 0;
}

D

考虑第一个塔在哪里,覆盖范围是确定的,然后就分治成了一个子问题?

现在需要覆盖 $[L,R]$ 间的所有位置,枚举第一座塔 $i$,然后就分治成了覆盖 $[2 \times i – L,R]$.

然后发现右端点是永远不变的,因此可以倒着做一个动态规划。

$f(i)$ 代表覆盖 $[i,R]$ 间的概率。枚举第一座塔进行转移。

$$f(i) = \sum \limits _{k=0} ^{i + 2 \times k + 1 \le n} \dfrac{1}{2^{k+1}} \times f(i + 2 \times k + 1)$$

稍微改写一下:

$$f(i) = 2^i \times \sum \limits _{k=0} ^{i + 2 \times k + 1 \le n} \dfrac{1}{2^{i + k+1}} \times f(i + 2 \times k + 1)$$

分奇偶记录前缀和即可。

#include <cstdio>
#include <algorithm>
using namespace std;
const int mod = 998244353;
const int inv = 499122177;//inv(2)
inline int add(int x,int y){int res = x + y;return res >= mod ? res - mod : res;}
inline int mul(int x,int y)
{
    long long res = 1ll * x * y;
    return res >= mod ? res % mod : res;
}
const int maxn = 2e5 + 100;
int n,f[maxn],g[maxn][2],prod[maxn],prodinv[maxn];
int main()
{
    scanf("%d",&n);
    prod[0] = prodinv[0] = 1;
    for(int i = 1;i<=n + 1;++i) prod[i] = mul(prod[i-1],2),prodinv[i] = mul(prodinv[i-1],inv);
    f[n + 1] = 1,g[n + 1][(n + 1) & 1] = prodinv[n+1];
    for(int i = n;i;--i)
    {
        f[i] = mul(prod[i],g[i+1][(i+1) & 1]);
        g[i][0] = g[i+1][0],g[i][1] = g[i+1][1];
        g[i][i & 1] = add(g[i][i & 1],mul(prodinv[i],f[i]));
    }
    printf("%d\n",f[1]);
    return 0;
}

看了看题解,发现其实只要将 $[1,n]$ 划分为若干个奇数段即可。

设 $f(i)$ 为划分完 $[1,i]$ 的方案数,有:

$$f(i) = f(i-1) + f(i-2)$$

即考虑最后一位可以单独一段,也可以后两位接到最后一段上。

这个转移可以矩阵加速。

E

对于每个学生的区间 $[L,R]$,有中心点 $mid = \dfrac{L+R}{2}$,使讲师区间越靠近中心点,对学生吸引力越大。

按照 $mid$ 对学生排序,即可保证在某点处,前一部分学生都倾向一个讲师,后一部分学生都倾向另一个讲师。

可以考虑枚举这个分界点,那么只需要计算对于前一部分学生、后一部分学生,放置长度为 $k$ 的讲师区间能得到的最大贡献值。

$O(nm)$ 枚举学生,然后枚举对应位置即可预处理。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 2100;
int n,m,k,prefix[maxn],suffix[maxn],pos[maxn];
struct node
{
    int l,r;
}A[maxn];
bool cmp(const node &a,const node &b)
{
    return a.l + a.r < b.l + b.r;
}
int main()
{
    scanf("%d %d %d",&n,&m,&k);
    for(int i = 1;i<=m;++i) scanf("%d %d",&A[i].l,&A[i].r);
    if(m == 1) return printf("%d\n",min(k,A[1].r - A[1].l + 1)),0;
    sort(A + 1,A + 1 + m,cmp);
    for(int i = 1; i <= m; ++i)
    {
        for(int j = 1; j + k - 1 <= n; ++j)
        {
            int l = max(A[i].l,j),r = min(A[i].r,j + k - 1);
            if(l <= r) pos[j] += r - l + 1;
            prefix[i] = max(prefix[i],pos[j]);
        }
    }
    for(int i = 1;i<=n;++i) pos[i] = 0;
    for(int i = m;i;--i)
    {
        for(int j = 1;j + k - 1 <= n;++j)
        {
            int l = max(A[i].l,j),r = min(A[i].r,j + k - 1);
            if(l <= r) pos[j] += r - l + 1;
            suffix[i] = max(suffix[i],pos[j]);
        }
    }
    int res = 0;
    for(int i = 1;i<m;++i) res = max(res,prefix[i] + suffix[i + 1]);
    printf("%d\n",res);
    return 0;
}

Codeforces Round #687 (Div. 2, based on Technocup 2021 Elimination Round 2)

A

曼哈顿距离最大值?

四个角。

#include <cstdio>
#include <algorithm>
using namespace std;
int T,n,m,r,c;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d %d %d",&n,&m,&r,&c);
        printf("%d\n",max(r - 1 + c - 1,max(n - r + c - 1,max(r - 1 + m - c,n - r + m - c))));
    }
    return 0;
}

B

枚举一个最终颜色,从左到右遍历,遇到一个不同就刷,然后指针直接向后跳。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 100;
int T,n,k,a[maxn];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&n,&k);
        int maxx = 0;
        for(int i = 1;i<=n;++i) scanf("%d",a + i),maxx = max(maxx,a[i]);
        int res = 1 << 30;
        for(int c = 1;c<=maxx;++c)
        {
            int now = 0;
            for(int i = 1;i<=n;++i)
                if(a[i] != c) ++now,i += k - 1;
            res = min(res,now);
        }
        printf("%d\n",res);
    }
    return 0;
}

C

相对操作,在开头删除一个,相当于出发点向后移一位。

维护对于对应出发点的贡献即可,枚举出发点统计答案。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 100;
int T,n,p,k,cnt[maxn],x,y;
char a[maxn];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&p,&k);
        scanf("%s",a + 1);
        scanf("%d %d",&x,&y);
        for(int i = 0;i<k;++i) cnt[i] = 0;
        int res = 1 << 30;
        for(int i = n;i >= p;--i)
        {
            cnt[i % k] += (a[i] == '0') * x;
            res = min(res,y * (i - p) + cnt[i % k]);
        }
        printf("%d\n",res);
    }
    return 0;
}

D

如果所有数的最高位都不相同,那么肯定无解。因为异或之后最高位不变,那么相对大小永远不变。

如果有超过两个连续的最高位相同,那么一步就有解。

感觉这个多个连续最高位相同的可能性很大,因为如果都要求不同,最多只有三十种最高位,那么数组最多就有六十的长度。

这个数据范围考虑乱搞。

最终有一个 $a_i > a_{i+1}$,可以发现这两个东西一定是两端区间异或和的结果,所以可以考虑直接枚举分界点,然后枚举左右端点,即使 $O(n^3)$ 的复杂度也无所谓。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 100;
int n,a[maxn],hb[maxn],sum[maxn];
int main()
{
    scanf("%d",&n);
    for(int i = 1;i<=n;++i) scanf("%d",a + i);
    for(int i = 1;i<=n;++i) for(int j = 30;j>=0;--j) if((a[i] >> j) & 1) { hb[i] = j; break; }
    for(int i = 1;i+2<=n;++i) if(hb[i] == hb[i+1] && hb[i+1] == hb[i+2]) {puts("1");return 0;}
    for(int i = 1;i<=n;++i) sum[i] = sum[i-1] ^ a[i];
    int res = 1 << 30;
    for(int i = 1;i<n;++i)
        for(int l = i;l;--l)
            for(int r = i + 1;r<=n;++r)
                if((sum[i] ^ sum[l-1]) > (sum[r] ^ sum[i]))
                    res = min(res,i - l + r - i - 1);
    if(res > n) puts("-1");
    else printf("%d\n",res);
    return 0;
}

E

首先,一定不会在当前分数为正时清零。

然后,根据套路,先打贡献分数大的。

考虑什么时候清空。这个显然可以有 $O(nk)$ 的动态规划来做,只是时空双炸,不可接受。

口胡了一下没想到怎么优化,看了官方题解,写得不错。

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 5e5 + 100;
int n,k,a[maxn];
priority_queue<long long> q;
int main()
{
    scanf("%d %d",&n,&k);
    for(int i = 1;i<=n;++i) scanf("%d",a + i);
    sort(a + 1,a + 1 + n);
    for(int i = 1;i<=k + 1;++i) q.push(0ll);
    long long res = 0;
    for(int i = n;i;--i)
    {
        long long t = q.top();
        q.pop(),res += t,q.push(t + a[i]);
    }
    printf("%lld\n",res);
    return 0;
}

F

官方题解写得好。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 5100;
#define int long long
struct node
{
    int t,x;
}A[maxn];
inline bool cmp(const node &a,const node &b){return a.t < b.t;}
int n,f[maxn][maxn],minn[maxn];
inline int dis(int a,int b){return abs(A[a].x - A[b].x);}
signed main()
{
    scanf("%lld",&n);
    for(int i = 1;i<=n;++i) scanf("%lld %lld",&A[i].t,&A[i].x);
    sort(A + 1,A + 1 + n,cmp);
    for(int i = 1;i<=n;++i) minn[i] = 1 << 30;
    f[0][0] = 1;
    for(int i = 0;i<n;++i)
    {
        if(minn[i] <= A[i].t)
        {
            minn[i + 1] = min(minn[i + 1],max(A[i].t,minn[i] + dis(i,i+1)));
            for(int j = i + 2;j<=n;++j)//place a clone
                if(max(A[i].t, minn[i] + dis(i,j)) + dis(j,i+1) <= A[i+1].t) f[i+1][j] = 1;
        }
        if(i < n - 1 && f[i][i+1]) //go directly to i + 2 and leave the i + 1 to clone onw
        {
            minn[i+2] = min(minn[i+2],max(A[i+1].t,A[i].t + dis(i,i + 2)));
            for(int j = i + 3;j<=n;++j) if(max(A[i+1].t,A[i].t + dis(i,j)) + dis(j,i + 2) <= A[i+2].t)
                f[i+2][j] = 1;      
        }
        if(A[i].t + dis(i,i+1) <= A[i+1].t) for(int j = i + 2;j<=n;++j) f[i+1][j] |= f[i][j];
    }
    if(minn[n] <= A[n].t || f[n-1][n]) puts("YES"); else puts("NO");
    return 0;
} 
本文标题:NOIP2020年赛前练习
本文作者:Clouder
本文链接: https://www.codein.icu/noiptraining2020/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇