写题月报2022Mar.

CF1635C Differential Sorting

link，R1200

题意

给定长度为$n$的序列$a$。对序列进行操作，每次操作可以选定一组$x,y,z$满足$1\le x<y<z\le n$，将$a_x$替换为$a_y-a_z$。

通过不超过$n$次操作将序列变为单调不减的，给出方案，或明确方案不存在。

$n\le 2\cdot10^5$

思路

显然若$a_{n-1}>a_n$则一定不存在方案，因为我们无法替换这两个元素。

根据操作对序列元素的影响，考虑以从后往前的顺序处理问题。

容易发现若$a_z\ge0$，我们可以使$a_x\le a_y$；进一步的，如果存在$a_i\ge0$，我们一定可以使$a_1\dots a_{i-2}$单调不减。

于是只需考察$a_n$是否为非负。
若$a_n\ge0$，则只需对$a_1\dots a_{n-2}$从从后往前依次执行一次$<x,y,z>=<i,i+1,n>$的操作即可。
否则，检查原始序列是否单调不减，是则不需要对序列进行操作，否则方案不存在。

假设$a_n<0,a_{x+1}\dots a_n$单调不减，而$a_x>a_{x+1}$。若要修改$a_x$，我们能够构造出的最小的$a_y-a_z=a_{x+1}-a_z>a_{x+1}$；若考虑修改$a_{x+1}$，则会使其大于$a_{x+2}$

复杂度$O(n)$

Code

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=(c=='-');c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

const int maxn=200000+100;
int T;
int n;
ll a[maxn];
int X[maxn],Y[maxn],Z[maxn];

void Work()
{
    read(n);
    for(int i=1;i<=n;++i)
    {
        read(a[i]);
    }
    if(a[n-1]>a[n])
    {
        puts("-1");
        return;
    }
    if(a[n]<0)
    {
        for(int i=1;i<n;++i)
        {
            if(a[i]>a[i+1])
            {
                puts("-1");
                return;
            }
        }
        puts("0");
        return;
    }
    else
    {
        printf("%d\n",n-2);
        for(int i=n-2;i;--i)
        {
            printf("%d %d %d\n",i,i+1,n);
        }
    }

}

int main()
{
    read(T);
    while(T--)
    {
        Work();
    }
    return 0;
}

CF1646C Factorials and Powers of Two

link,R1500

题意

将一个数$n$拆解为$k$个两两不同的$2$的幂或阶乘之和，最小化$k$或明确这样的$k$不存在

$n\le 10^{12}$

思路

一个数显然可以表示成若干个不同的$2$的幂之和，所以分解方案是一定存在的。

注意到阶乘$d!$随$d$的增长极快（事实上，$14!< 10^{12} < 15!$），我们只需要枚举有哪些阶乘出现在了$n$的分解结果中，然后计算剩余部分的二进制表示中有多少个$1$即可

复杂度$O(2^{14}\cdot \log n)$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=(c=='-');c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

ll fac[15];
int T;
ll n;
int ans;

void pre()
{
    fac[0]=1;
    for(ll i=1;i<=14;++i)
        fac[i]=fac[i-1]*i;
}

int Count(ll x)
{
    int re=0;
    while(x)
    {
        re+=(x&1);
        x>>=1;
    }
    return re;
}

void Search(int step,int use,ll rest)
{
    if(step==15)
    {
        ans=min(ans,use+Count(rest));
        return;
    }
    Search(step+1,use,rest);
    if(rest>=fac[step])
        Search(step+1,use+1,rest-fac[step]);
}

void Work()
{
    read(n);
    ans=0x7fffffff;
    Search(0,0,n);
    printf("%d\n",ans);
}

int main()
{
    pre();
    read(T);
    while(T--)
    {
        Work();
    }
    return 0;
}

CF1646D Weight the Tree

link,R2000

第一次在赛场上做出D祭上大分咯

题意

给定$n$个节点的无根树。如果树中某节点的权值为与其相邻的节点的权值之和，我们称这个节点是“好”的

找到一种节点权值分配方案，在最大化好节点的个数的前提下最小化节点权值之和，输出该个数、和以及分配方案。

$n\le 2\cdot 10^5$

思路

注意到当树节点数量为$2$时，两个节点都可以是好的。特判这种情况，输出

2 2
1 1

即可

当树的节点数量大于$2$时，显然任意两个好节点都不可能相邻；又注意到若一个节点不是好的，那么其权值可以为任意值，令其为$1$可使权值和尽可能小。

考虑树形dp，显然dp顺序对答案没有影响，定义状态$dp_{u,0/1}$表示节点$u$不是/是好节点的情况下，以节点$u$为根的子树中好节点的最大数量，转移方程：

$dp_{u,0}=\sum_{v\in son(u)}max\{dp_{v,0},dp_{v,1}\}$

$dp_{u,1}=\sum_{v\in son(u)}dp_{v,0}+1$

同时，考虑到我们还需要最小化权值和，维护$sum_{u,0/1}$表示节点$u$不是/是好节点的情况下，以节点$u$为根的子树的权值和

转移方程：

$sum_{u,0}=\sum_{v\in son(u)}sum_{v,*}+1$（$*$取决于$dp_{v,0}$和$dp_{v,1}$中谁对$dp_{u,0}$有贡献）

$sum_{u,1}=\sum_{v\in son(u)}sum_{v,0}+\sum_{(u,v)\in G}1$

为方便分配权值，使用$n$个set维护若节点$u$不好，它的哪些儿子是好的

考察$u$不好的情况时，若$dp_{v,0}=dp_{v,1}$，那么$sum_{u,0}=min\{sum_{v,0},sum_{v,1}\}$；若仍相同，则认为此时$v$不是好的

Tutorial好像说这样一定能使$sum$最小化，但我不会证

答案即为$max\{dp_{1,0},dp_{1,1}\}$，二者相同时采取与上述过程相同的分配方案。

复杂度$O(n\log n)$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=(c=='-');c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

const int maxn=200000+100;
int n;
int dp[maxn][2];
ll sum[maxn][2];
ll ass[maxn];
set<int> goodson[maxn];

struct edge
{
    int u,v,nxt;
}g[maxn*2];

int head[maxn],ecnt;
void eADD(int u,int v)
{
    g[++ecnt].u=u;g[ecnt].v=v;g[ecnt].nxt=head[u];head[u]=ecnt;
}

void DFS(int u,int prt)
{
    for(int i=head[u];i;i=g[i].nxt)
    {
        int v=g[i].v;
        if(v==prt)
            continue;
        DFS(v,u);
        dp[u][0]+=max(dp[v][0],dp[v][1]);
        if(dp[v][1]>dp[v][0])
        {
            goodson[u].insert(v);
            sum[u][0]+=sum[v][1];
        }
        else if(dp[v][1]<dp[v][0])
            sum[u][0]+=sum[v][0];
        else
        {
            if(sum[v][0]>sum[v][1])
            {
                goodson[u].insert(v);
                sum[u][0]+=sum[v][1];
            }
            else
                sum[u][0]+=sum[v][0];
        }

        
        dp[u][1]+=dp[v][0];
        sum[u][1]+=sum[v][0]+1;
    }
    ++dp[u][1];
    if(prt)
        ++sum[u][1];
    ++sum[u][0];
}

void Assign(int u,int isgood,int prt)
{
    if(isgood)
    {
        for(int i=head[u];i;i=g[i].nxt)
        {
            ass[u]++;
        }
        for(int i=head[u];i;i=g[i].nxt)
        {
            int v=g[i].v;
            if(v==prt)
                continue;
            Assign(v,0,u);
        }
    }
    else
    {
        ass[u]=1;
        for(int i=head[u];i;i=g[i].nxt)
        {
            int v=g[i].v;
            if(v==prt)
                continue;
            if(goodson[u].find(v)!=goodson[u].end())
                Assign(v,1,u);
            else
                Assign(v,0,u);
        }
    }
}

int main()
{
    read(n);
    for(int i=1;i<n;++i)
    {
        int u,v;
        read(u),read(v);
        eADD(u,v),eADD(v,u);
    }
    if(n==2)
    {
        puts("2 2");
        puts("1 1");
        return 0;
    }
    DFS(1,0);
    int root;
    if(dp[1][0]==dp[1][1])
        root=(sum[1][0]>sum[1][1]);
    else
        root=(dp[1][0]<dp[1][1]);
    printf("%d %lld\n",dp[1][root],sum[1][root]);
    Assign(1,root,0);
    for(int i=1;i<=n;++i)
        printf("%lld ",ass[i]);
    return 0;
}

---

其实这场我感觉还蛮套路的，但是莫名其妙就上分了

$D$花的时间有点多（主要是考虑怎么做方案分配的部分），不然说不定还能搞一搞$E$

---

CF1651C Fault-tolerant Network

link

题意

给定两条长度均为$n$的链，点带权，第一条链上第$i$个点权为$a_i$，第二条链上第$i$个点权为$b_i$。连接两条边链上的两个点$a_i,b_j$的代价为$|a_i-b_j|$，问使得整个图成为点双的最小代价。

原题意为：使得图在去掉任意一个点的情况下仍然连通，该表述思路更自然

$n\le 2\cdot 10^5$

思路

考虑去掉的是一条链中间的某个点，要让这个点左边的点仍能到达右边的点，必须在其左边和右边均存在一个点连接到了另一条边。显然若完成连接后去掉任意一个点仍能使整个图连通，两条链的端点必须连接到另一条链上。

枚举四个端点连到另一条边的最小代价，计算答案，发现可能存在端点之间相互连接的情况。讨论各种端点相连的情况，与答案进行比较取最小值即为最终答案。

这些情况分别包括：所有端点均与端点相连（2种），仅1个端点未与端点相连（4种），2个端点未与端点相连（4种）。

复杂度$O(n)$

Code

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;

template<typename T>void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=(c=='-');c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

const int maxn=200000+100;
const int dx[]={-1,0,0,1},dy[]={0,-1,1,0};
int T;
int n;
pii p[maxn];
pii ans[maxn];
int vst[maxn];
map<pii,int> idx;

int dis(pii a,pii b)
{
    return abs(a.first-b.first)+abs(a.second-b.second);
}

void Work()
{
    read(n);
    for(int i=1;i<=n;++i)
    {
        read(p[i].first),read(p[i].second);
        idx.insert({p[i],i});
    }
    queue<int> q;
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<4;++j)
        {
            int X=p[i].first+dx[j],Y=p[i].second+dy[j];
            if(idx.find({X,Y})==idx.end())
            {
                ans[i]={X,Y};
                q.push(i);
                break;
            }
        }
    }
    while(!q.empty())
    {
        int uidx=q.front();
        pii u=p[uidx];
        q.pop();
        for(int i=0;i<4;i++)
        {
            int X=u.first+dx[i],Y=u.second+dy[i];
            if(idx.find({X,Y})!=idx.end())
            {
                int vidx=idx[{X,Y}];
                pii v=p[vidx];
                if(dis(ans[uidx],v)<dis(ans[vidx],v))
                {
                    ans[vidx]=ans[uidx];
                    q.push(vidx);
                }
            }
        }
    }
    for(int i=1;i<=n;++i)
        printf("%d %d\n",ans[i].first,ans[i].second);
}

int main()
{
//  read(T);
    T=1;
    while(T--)
    {
        Work();
    }
    return 0;
}

*CF1651D Nearest Excluded Points

link

题意

给定一个包含平面上的$n$个点的集合，对集合中的每个点，找到与其曼哈顿距离最近的不在集合中的点

$n\le 2\cdot 10^5$

思路

未在四个方向上均被包围的点（称其为边缘点），显然其答案与其相邻，容易求得。

对于非边缘点，显然其答案来自于与其曼哈顿距离最近的边缘点

考虑BFS，初始所有边缘点入队，对非边缘点进行更新，更新成功时入队即可。

Code

实际实现中使用了map，复杂度$O(n\log n)$

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;

template<typename T>void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=(c=='-');c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

const int maxn=200000+100;
const int dx[]={-1,0,0,1},dy[]={0,-1,1,0};
int T;
int n;
pii p[maxn];
pii ans[maxn];
int vst[maxn];
map<pii,int> idx;

int dis(pii a,pii b)
{
    return abs(a.first-b.first)+abs(a.second-b.second);
}

void Work()
{
    read(n);
    for(int i=1;i<=n;++i)
    {
        read(p[i].first),read(p[i].second);
        idx.insert({p[i],i});
    }
    queue<int> q;
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<4;++j)
        {
            int X=p[i].first+dx[j],Y=p[i].second+dy[j];
            if(idx.find({X,Y})==idx.end())
            {
                ans[i]={X,Y};
                q.push(i);
                break;
            }
        }
    }
    while(!q.empty())
    {
        int uidx=q.front();
        pii u=p[uidx];
        q.pop();
        for(int i=0;i<4;i++)
        {
            int X=u.first+dx[i],Y=u.second+dy[i];
            if(idx.find({X,Y})!=idx.end())
            {
                int vidx=idx[{X,Y}];
                pii v=p[vidx];
                if(dis(ans[uidx],v)<dis(ans[vidx],v))
                {
                    ans[vidx]=ans[uidx];
                    q.push(vidx);
                }
            }
        }
    }
    for(int i=1;i<=n;++i)
        printf("%d %d\n",ans[i].first,ans[i].second);
}

int main()
{
//  read(T);
    T=1;
    while(T--)
    {
        Work();
    }
    return 0;
}

---

这场的C花时间有点太多了，之前一直都很怕分情况讨论，这次就吃亏了

D这种纯属就是对算法的应用不熟悉。思维题写多了容易把算法抛之脑后，有必要加强一下才行

CF1647D Madoka and the Best School in Russia

link

这种抽丝剥茧的过程还挺过瘾的

题意

给定$x,d$

若一个数是$d$的倍数，我们称其为好的

若一个数是好的，又不能被表达成两个好的数的乘积，称其为美的

问是否存在两种将$x$分解成若干个美的数的乘积的方案

$x,d\le 10^9$

思路

事实上，一个数是美的当且仅当其存在恰好1个$d$因子。

将$x$表示为$s\cdot d^r=\prod_{i=1}^k(a_i\cdot d)$的形式，如果$r=0$，那么显然方案不存在，否则$x$恰好是$k$个美的数的乘积。

一种分解方式显然是$(1\cdot d)(1\cdot d)\cdots (1\cdot d)(s\cdot d)$，考虑构造第二种分解方案，由此我们可以进一步发现$r=1$时找不到第二种方案。

考察$s$是否为质数，如果不是，则可以将$s$分解为$a\cdot b$，在上述方案中选择一个$1$改为$a$，将$s$改为$b$构造出第二种方案。

如果$s$是质数，那么我们必须要分解$d$。此时如果$d$是质数，那么第二种方案也是不存在的；
否则可以将$d$分解为$m\cdot n$，即$x=mns\cdot d^{r-1}$。在此情况下若$r\ge 4$（即$r-1\ge 3$），那么我们可以构造出第二种方案$(1\cdot d)\cdots(m\cdot d)(n\cdot d)(s\cdot d)$。

再来考虑$r=2$和$r=3$的情况。
显然$r=2$时我们无法构造出第二种方案（$x=(mns\cdot d^{r-1})=(s\cdot d^2)$）。
当$r=3$时，$x$可以分解成$(ms\cdot d)(n\cdot d)$或$(m\cdot d)(sn\cdot d)$。在此情况下，我们又必须要保证$ms\neq kd$或$sn\neq kd$。当$ms=k_1d,ns=k_2d\iff d=s^2$时，第二种方案也是不存在的，否则即可按照上述任意一种方案进行分解。

必要性显然，下证充分性。假设$d$的任意分解方案$d=mn,m<d,n<d$都会使得$ms=k_1d,ns=k_2d$，那么有$m=\frac{k_1d}{s},n=\frac{k_2d}{s}，mn=\frac{k_1k_2d^2}{s^2}=d,s^2=k_1k_2d$. 又$s$是质数，$k_1,k_2,d$中至少有一个是$1$，不妨$k_2=d$.若$k_1=d=s$，那么有$m=s=d$，产生矛盾，从而$k_1=k_2=1,d=s^2$

取$d$因子复杂度为$O(\log x)$，判断质数复杂度为$O(\sqrt{x})$，最终复杂度为$O(\log x+\sqrt{x}+\sqrt{d})$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=(c=='-');c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

int T;
int n,d;

void Work()
{
    read(n),read(d);
    int tms=0;
    while(n%d==0)
    {
        ++tms;
        n/=d;
    }
    if(tms<=1)
    {
        puts("NO");
        return;
    }
    int sqn=sqrt(n);
    bool isp=true;
    for(int i=2;i<=sqn && isp;++i)
        if(n%i==0)
            isp=false;
    if(!isp)
    {
        puts("YES");
        return;
    }
    if(tms<=2)
    {
        puts("NO");
        return;
    }
    sqn=sqrt(d);
    isp=true;
    for(int i=2;i<=sqn && isp;++i)
        if(d%i==0)
            isp=false;
    if(isp)
    {
        puts("NO");
        return;
    }
    if(tms>=4)
    {
        puts("YES");
        return;
    }
    if(d==n*n)
    {
        puts("NO");
        return;
    }
    puts("YES");
}

int main()
{
 read(T);
    while(T--)
    {
        Work();
    }
    return 0;
}

CF1657C Bracket Sequence Deletion

link

我真傻，真的

题意

给定括号串，每次从串中删去一个最短的满足以下任一条件的前缀

1. 是合法括号串
2. 是长度至少为2的回文串

求能够执行删除的次数和剩下的字符数量

$n\le 5\cdot 10^5$

思路

考察当前剩余字符串的第一个字符是什么。

如果是(，那么可以从串中直接删去一个长度为2的前缀，因为()是合法括号序列，((是回文串。

如果是)，那么前缀不可能是一个合法括号串，只需考察)后接上零或多个(再接上一个)构成的回文串即可。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=(c=='-');c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

const int maxn=500000+100;
int T;
int n;
char s[maxn];

void Work()
{
    read(n);
    scanf("%s",s);
    int cur=0;
    int times=0,rest=n;
    while(cur<n-1)
    {
        if(s[cur]=='(')
        {
            ++times;
            cur+=2;
            rest-=2;
        }
        else
        {
            int t=cur+1;
            while(t<n && s[t]!=')')
            {
                ++t;
            }
            if(t<n)
            {
                ++times;
                rest-=t-cur+1;
            }
            cur=t+1;
        }
    }
    printf("%d %d\n",times,rest);
}

int main()
{
  read(T);
    while(T--)
    {
        Work();
    }
    return 0;
}

目前来看写题思路还是不够灵活，这种题手玩一下样例说不定就能找到思路的。

而且我发现自己写题的时候喜欢企图一口吃成个胖子，或许也是经常入不了手的原因吧。