头像

RingweEH

$Ringw\ddot{e}ElrondHarma.$




离线:11小时前



更好的阅读体验

Statement

给定一个 $n$ 点 $m$ 边无向连通图,不存在重边和自环。从任意一点出发,每次可以走向一个没去过的点或者按第一次访问当前点的路径回退。求一个字典序最小的遍历序列。

$n\leq 5e3$ , $m=n$ 或 $m=n-1$ .

Thoughts & Solution

这道题的关键显然在于数据范围。$m=n$ 或 $m=n-1$ ,就相当于是 一棵树或者基环树

60pts 树

对于一棵树,显然只要选定了起点,然后每次遍历子树时从小到大遍历即可。由于字典序要小,所以从 1 开始,一次 DFS 就能解决。

时间复杂度 $\mathcal{O}(n\log n)$ .(因为要排序)

40pts 基环树

仔细想想就会发现,由于 不是后退就是新点 ,所以易知无论图长什么样,我们都只会遍历到 $n-1$ 条边。所以其实就算有 $n$ 条边也是有一条没用的。那不妨枚举删掉一条,然后就可以按照树的方法跑了。

复杂度是 $\mathcal{O}(n^2)$ (排序在初始化就可以做掉,没必要放进 DFS 里面去),大概是 $2e7$ 左右。如果觉得不稳可以加剪枝,如果当前已经比答案劣了直接退出。

注意:删边要保证连通性,只要判最后 vis 了几个点就好了,没必要再写个找环;写剪枝(和最优解比较)的时候,只要前面有一次比最优解优,那么后面都不用判了,这点要加个标记。

大常数选手写了太多STL,所以在 ACWing 上得吸氧……

C++ 之父:STL常数大是你编译器不行(

//Author: RingweEH
const int N=5010;
int n,m,pos=0,cnt=0,better;
bool vis[N];
vector<int> g[N],path,ans;
pair<int,int> edge[N];

void dfs( int u )
{
    if ( (!better) && (u>ans[cnt]) ) return;
    if ( !better && u<ans[cnt] ) better=1;
    vis[u]=1; path.push_back( u ); cnt++;
    for ( int i=0; i<g[u].size(); i++ )
    {
        int v=g[u][i];
        if ( vis[v] ) continue;
        if ( (u==edge[pos].first) && (v==edge[pos].second ) ) continue;
        if ( (v==edge[pos].first) && (u==edge[pos].second ) ) continue;
        dfs( v );
    }
}

int main()
{
freopen( "travel.in","r",stdin ); freopen( "travel.out","w",stdout );

    n=read(); m=read();
    edge[0].first=edge[0].second=-1;
    for ( int i=1,u,v; i<=m; i++ )
    {
        u=read(),v=read(),g[u].push_back( v ),g[v].push_back( u );
        edge[i].first=u; edge[i].second=v;
    }

    for ( int i=1; i<=n; i++ )
        sort( g[i].begin(),g[i].end() );
    for ( int i=1; i<=n; i++ )
        ans.push_back( 60000 );
    if ( m==n )
    {
        for ( int i=1; i<=m; i++ )
        {
            memset( vis,0,sizeof(vis) ); path.clear();
            pos=i; cnt=better=0; dfs( 1 );
            if ( cnt==n ) ans=path;
        }
    }
    else
    {
        dfs( 1 );
        if ( cnt==n ) ans=path;
    }

    for ( int i=0; i<ans.size(); i++ )
        printf( "%d ",ans[i] );

fclose( stdin ); fclose( stdout );
    return 0;
}



Statement

一棵带边权的树,在树上选出 $m$ 条互不相交的链(点可以重合,但是边不能重合),使得 $m$ 条链中最短的链最长。

$2\leq n\leq 5e4,1\leq m\leq n-1$ .

Thoughts & Solution

看到“最短的链最长”就很容易想到二分。二分一个最短链长,然后看能否组成至少 $m$ 条互不相交的长度不小于 $mid$ 的链即可。

现在的问题就是如何判定了。我们定义“一条链对答案有贡献”表示,这条链的链长不小于当前枚举的最小值。

考虑一条链是如何被组成的。

对于一棵子树 $u$ ,显然通过根节点 $u$ 向上拼接的链最多只能有一条,因此让链尽可能在子树内贡献更多的答案而不是往上走显然是不会更劣的。

那么正解就来了。我们可以用 DP 处理出这个向上走的链长。令 $f[u]$ 为以 $u$ 为根的子树中,最优的不完整链长(就是通过根节点向上拼接的链)(完整的部分就是链长 $\ge mid$ 的,已经贡献到答案里面去了)。

暂时不考虑根节点 $u$ ,对于 $u$ 的所有儿子,如果能单独贡献就直接计入答案。否则,尝试两两合并这些子树中向上走的链(因为点是可以重合的,在根节点合并多少都没有关系),如果长度 $\ge mid$ 就一样计入答案。最后剩下的链中,取一条最长的(也就最容易产生贡献)走过根节点,计入 $f[u]$ 并往上走。

具体实现就可以直接对子树中所有的链长升序排序,然后倒序枚举,对于每一条链找一条 能匹配出 $\ge mid$ 的链中最短的一条链 进行拼接,计入答案即可。最后把剩下的链中的最大值转移给 $f[u]$ .

但是要注意一点,你贪心两两匹配子树中的链,最后得到的只是“能匹配的最大对数”,而不是“能匹配的最优方案”。所以要在得到这个最大对数之后,再来一次二分,找一个最大的 mid 使得 去掉这个mid之后,剩下的部分仍然能匹配出这个最大对数。那么最后得到的 mid 就是要计入 $f[u]$ 中的值。

//Author: RingweEH
const int N=5e4+10;
struct edge
{
    int to,nxt,val;
}e[N<<1];
int n,m,tot=0,head[N],res,f[N];
vector<int> son[N];

void add( int u,int v,int w )
{
    e[++tot].to=v; e[tot].nxt=head[u]; head[u]=tot; e[tot].val=w;
    e[++tot].to=u; e[tot].nxt=head[v]; head[v]=tot; e[tot].val=w;
}

int get_pair( int u,int pos,int num,int lim )       //在去掉pos这个数之后,所能匹配出的最大对数
{
    int now_res=0,l=0;
    for ( int r=num-1; r; r-- )
    {
        r-=(r==pos);
        while ( l<r && son[u][l]+son[u][r]<lim ) l++;
        l+=(l==pos);
        if ( l>=r ) break;
        now_res++; l++;
    }
    return now_res;
}

void dfs( int u,int fa,int lim )
{
    son[u].clear();
    for ( int i=head[u]; i; i=e[i].nxt )
    {
        int v=e[i].to; if ( v==fa ) continue;
        dfs( v,u,lim );  f[v]+=e[i].val;
        if ( f[v]>=lim ) res++;
        else son[u].push_back( f[v] );
    }
    //将所有子树上来的链拉到根节点,并判断是否可以独自产生贡献,如果不能那么放入配对序列
    int num=son[u].size(); sort( son[u].begin(),son[u].end() );
    int l=0,r=num-1,cnt=0;
    for ( ; r; r-- )
    {
        while ( l<r && son[u][l]+son[u][r]<lim ) l++;
        if ( l>=r ) break;
        cnt++; l++;  
    }
    //配对过程,cnt就是得到的最大对数。
    res+=cnt;
    if ( cnt*2==num ) { f[u]=0; return; }       //全配完了,不需要再往上转移
    l=0; r=num-1; int now_res=0;
    while ( l<=r )
    {
        int mid=(l+r)>>1,now=get_pair( u,mid,num,lim );
        if ( now==cnt ) now_res=mid,l=mid+1;
        else r=mid-1;
    }
    //二分转移上去的最大链长,使得剩下的链仍能满足最大匹配
    f[u]=son[u][now_res];
}

bool check( int mid )
{
    memset( f,0,sizeof(f) );
    res=0; dfs( 1,0,mid );
    return (res>=m) ? 1 : 0;
}

int main()
{
freopen( "track.in","r",stdin );  freopen( "track.out","w",stdout ); 

    n=read(); m=read(); int r=0;
    for ( int i=1,u,v,w; i<n; i++ )
        u=read(),v=read(),w=read(),add( u,v,w ),r+=w;

    int l=0,ans=0; r=r/m;
    while ( l<=r )
    {
        int mid=(l+r)>>1;
        if ( check(mid) ) ans=mid,l=mid+1;
        else r=mid-1;
    }

    printf( "%d\n",ans );

fclose( stdin ); fclose( stdout );
    return 0;
}



更好的阅读体验

感觉这道题重点不是 DP 是证明……很多高赞题解都是直接上结论的……

比如你考场的时候,想到了这个解法,如果用了怕结论是错的,得分还不如部分分;不用又怕错失正解,其实是很纠结的……所以我这里就写一写证明过程吧,其实也不难。

Statement

有 $n$ 种不同面值的货币,第 $i$ 种面值为 $a[i]$ ,每种无限张。

将一个有 $n$ 种货币、面值数组为 $a[1\dots n]$ 的货币系统记作 $(n,a)$ .称两个货币系统 $(n,a),(m,b)$ 等价,当且仅当对于任意 $x\in N$ ,要么均能被两个货币系统表示出来,要么不能被任何一个表示。

给定一个货币系统 $(n,a)$ ,找到一个最小的 $m$ 使得存在货币系统 $(m,b)$ 与 $(n,a)$ 等价。

$n\leq 100,a[i]\leq 25000$ .

Thoughts & Solution

有一个很显然的想法:答案中的系统方案一定是由原先的系统方案去掉若干种货币得到

事实上这就是正确的。

Proof

令给出的系统中的货币面值为 $A$ 集合,需要得到的货币面值为 $B$ 集合。

引理:$A$ 集合中不能被其他数组成的数一定会在 $B$ 集合中出现。

引理的证明:设有一个数 $x\in A$ 且不能被 $A$ 集合中其他数凑出来。 根据等价,如果 $x\notin B$ ,那么 $B$ 中的其他数一定能组成 $x$ .这就说明 $B$ 中至少存在一个不属于 $A$ 集合且不能被 $A$ 组合出来的数(不然 $A$ 集合就一定能合成 $x$ ),那么这个数本身不属于 $A$ 能组成的范畴,却属于 $B$ 能组成的范畴,就不符合题意了。所以 $x\in B$ ,引理正确性证毕。

那么现在我们需要证明:$B\subseteq A$ .

仍然采用反证法。设存在一个数 $x$ 满足 $x\in B$ 且 $x\notin A$ .

根据题意,显然 $x$ 能被 $A$ 中若干个 $a_1,a_2,\dots ,a_k$ 组成(假定这些数不能被拆分成 $A$ 中其他的数,如果能拆分就直接拿拆分方案替换即可)。根据引理,这些数都属于 $B$ ,也就是说,$B$ 完全可以通过这些数组成 $x$ ,那么 $B$ 中再存在一个 $x$ 显然就是多余的,和 $B$ 集合最小的要求不符。

Q.E.D.

接下来的事情就非常简单了。我们只需要考虑 $A$ 集合中哪些数是多余的就好了。

题目暗示:现在网友们打算 简化 一下货币系统。这说明就是在原基础上去掉某些数(

这个事情可以一次 DP 解决。观察到 $a[i]$ 的范围只有 $25000$ ,那么可以直接设 $f[i]$ 表示 $i$ 这个数能否被前面已经出现过的 $a[j]$ 组成。

  • 如果枚举到 $a[i]$ 时,$f[a[i]]=1$ ,那么直接计入答案并跳过即可;
  • 如果没有,那么枚举所有的 $j=a[i]\sim mx$ ,$f[j]|=f[j-a[i]]$ (就是用 $j-a[i]$ 和 $a[i]$ 组成 $j$ ,枚举范围中的 $mx$ 表示所有 $a[i]$ 中的最大值)

完结散花 (。・∀・)ノ゙

注意题目中给出的 $a$ 数组不一定有序,要记得排序。

//Author: RingweEH
const int N=110,M=25010;
int n,a[N],f[M];

int main()
{
    int T=read();
    while ( T-- )
    {
        n=read(); 
        for ( int i=1; i<=n; i++ )
            a[i]=read();

        sort( a+1,a+1+n ); int mx=a[n];
        memset( f,0,sizeof(f) ); f[0]=1; int ans=n;
        for ( int i=1; i<=n; i++ )
        {
            if ( f[a[i]] ) { ans--; continue; }
            for ( int j=a[i]; j<=mx; j++ )
                f[j]|=f[j-a[i]];
        }

        printf( "%d\n",ans );
    }
}



更好的阅读体验

Statement

给定一个长为 $n$ 的数组 $d$ ,每次可以选择一段连续区间 $[L,R]$ 并全部加一。问最少几次能将整个数组变成 $0$ .

$1\leq n\leq 1e5,0\leq d_i\leq 1e4$

Thoughts & Solution

一个很显然的想法是,如下图将所有的凹陷部分以尽可能连续的横向方块填充:(数据为样例)

(图中最上面一行为地面,黄色部分每一块就是一次填充)很显然这样就是最优方案。

实现也很简单:从右往左遍历,如果当前 $a[i]$$<$$a[i-1]$ ,就相当于结束掉了上一个横条,不用动;如果当前 $a[i]>a[i-1]$ ,说明又要新建 $a[i]-a[i-1]$ 个横条,计入答案即可。

复杂度 $\mathcal{O}(n)$ .

//Author: RingweEH
int n,las,ans;

int main()
{
    n=read(); las=ans=0;
    for ( int i=1,x; i<=n; i++ )
    {
        x=read();
        if ( x>las ) ans+=(x-las);
        las=x;
    }

    printf( "%d\n",ans );

    return 0;
}



仿照 一个月前的神wh 也来写真题了qwq

为了不再修一遍 LaTeX 阅读链接

ACWing题解链接:

Day1T1格雷码

Day1T2括号树

Day1T3树上的数

Day2T1Emiya家今天的饭

Day2T2划分

Day2T3树的重心

怎么说呢,一套题忘得差不多了,做下来也还是好题。

  • T1经过今年CSP-S T2的教训终于记得看题面了
  • T2 正好碰上模拟赛里有类似的题
  • 树上的数果然还是神题;但是现在看看也没那么不可做了。
  • T4 的减法取模直接 100->88 还在吃饭的时候自闭了半天;长记性了
  • T5 发现 ACWing 的神奇 RE(
  • T6 复习了二次扫描

总之:考前真题,yyds!

还有就是我发现我的常数非常大,划分的空间到 ACWing被卡成随机RE;6道题5道跑不进LOJ前十页,唯一一道因为交的人只有十页所以到了第三页




不是吧不是吧,这种真题居然还轮得到我这种一年之后的老年选手写题解(

更好的阅读体验

Statement

给定一棵 $n$ 点的树,求单独删去每条边之后,分裂出的两个子树的重心编号和之和。(重心定义和简单性质自行阅读题面)

$n\leq 299995$ .

Thoughts & Solution

55pts 有手就行

考场骗分小能手狂喜(

发现前面 40 分的部分分完全可以 $\mathcal{O}(n^2)$ 暴力碾过去,枚举删边,然后 $\mathcal{O}(n)$ DFS求一遍重心即可。

对于后面 15 分,有性质 $A$ 也就是链。对于链,重心显然是找个中点就好了。

75pts 完全二叉树

咳……这个要面向数据。

注意到题目里面对于这个部分分,钦定了 $n=262143$ ,算一算就会发现是个满二叉树……其实满二叉树的根节点就是重心……

那么可以得到如下推论:

  • 对于删掉的某一条边,儿子节点就是它这个子树的重心
  • 对于根节点,如果在左子树里面删了一条边,那么右儿子就是剩余部分的重心
  • 对于叶子节点,删掉之后根就是剩余部分的重心

然后直接 $\mathcal{O}(n)$ 枚举 $\mathcal{O}(1)$ 计算就好了。

正解

考虑重心的出现位置。有结论:

对于一个节点 $u$ ,如果 $n-siz[u]\leq \lfloor n/2\rfloor$ ,且 $u$ 本身并非重心,那么重心一定在 $u$ 的重儿子里面。

这个挺显然的的吧。

然后就有一些显然的推论:(此处的 $u$ 依然满足 $n-siz[u]\leq\lfloor n/2\rfloor$ )

  • 前置:显然 $u$ 只有一个重儿子。
  • 重心的可能位置只有两种,要么是 $u$ 要么在 $u$ 的重子树里面。
  • 如果 $u$ 是满足这个条件且 $dep[u]$ 最大的点,那么根据上面的结论, $u$ 就是重心,且 $fa[u]$ 也有可能是重心。

因此,重心一定在 root 向下的重链上,而且重链上自上往下,节点的 $siz$ 递减。再结合数据范围得到合理猜测:复杂度 $\mathcal{O}(n\log n)$ .

那么就可以考虑在重链上倍增。令 $f[i][x]$ 表示以 rt 为根,节点 $x$ 沿着重链往下走 $2^i$ 步达到的节点。这样,求重心的时候就类似 LCA 一样,逆序枚举 $i$ 往下跳就好了。

然后类似换根DP,二次扫描维护 $f$ 数组和重儿子即可。

时间复杂度是 $\mathcal{O}(n\log n)$ .

//Author: RingweEH
const int N=3e5+10,K=25;
struct edge
{
    int to,nxt;
}e[N<<1];
int head[N],tot=0,n,siz[N],f[N][K],son[N],fa[N];
ll ans;

void ST_init( int x )
{
    for ( int i=1; i<K; i++ )
        f[x][i]=f[f[x][i-1]][i-1];
}

void calc( int x )
{
    int u=x;
    for ( int i=K-2; i>=0; i-- )
        if ( f[u][i] && siz[f[u][i]]*2>=siz[x] ) u=f[u][i];
    if ( siz[u]*2==siz[x] ) ans+=fa[u];
    ans+=u;
}

void dfs( int u,int fat )
{
    fa[u]=fat; siz[u]=1; siz[0]=0; son[u]=0;
    for ( int i=head[u]; i; i=e[i].nxt )
    {
        int v=e[i].to;
        if ( v==fat ) continue;
        dfs( v,u ); siz[u]+=siz[v];
        if ( siz[v]>siz[son[u]] ) son[u]=v; //重儿子
    }
    f[u][0]=son[u]; ST_init( u );
}

void get_ans( int u,int fat )
{
    int mx1=0,mx2=0; siz[0]=0;
    for ( int i=head[u]; i; i=e[i].nxt )
    {
        int v=e[i].to;
        if ( siz[v]>=siz[mx1] ) mx2=mx1,mx1=v;
        else if ( siz[v]>=siz[mx2] ) mx2=v;
        //最大和次大的儿子
    }
    for ( int i=head[u]; i; i=e[i].nxt )
    {
        int v=e[i].to;
        if ( v==fat ) continue;
        calc( v ); f[u][0]=(v==mx1) ? mx2 : mx1; ST_init( u );
        siz[u]-=siz[v]; siz[v]+=siz[u];
        calc( u ); fa[u]=v; get_ans( v,u );
        siz[v]-=siz[u]; siz[u]+=siz[v];     //算完(u,v)之后撤销影响
    }
    f[u][0]=son[u]; ST_init( u ); fa[u]=fat;
}

void add( int u,int v )
{
    e[++tot].to=v; e[tot].nxt=head[u]; head[u]=tot;
    e[++tot].to=u; e[tot].nxt=head[v]; head[v]=tot;
}

int main()
{
//freopen( "centroid.in","r",stdin ); freopen( "centroid.out","w",stdout );

    int T=read();
    while ( T-- )
    {
        memset( siz,0,sizeof(siz) ); memset( son,0,sizeof(son) );
        memset( f,0,sizeof(f) ); memset( fa,0,sizeof(fa) ); ans=0;
        memset( head,0,sizeof(head) ); tot=0;

        n=read();
        for ( int i=1,u,v; i<n; i++ )
            u=read(),v=read(),add( u,v );

        dfs( 1,0 ); get_ans( 1,0 );

        printf( "%lld\n",ans );
    }

//fclose( stdin ); fclose( stdout );
    return 0;
}


新鲜事 原文

NOIP2020 RP+=INF!
图片



更好的阅读体验

Statement

给定一个长为 $n$ 的序列 $a_i$ ,对于一组规模为 $u$ 的数据,代价为 $u^2$ .你需要找到一些分界点 $1\leq k_1<k_2<…<n$ ,使得:
$$
\sum_{i=1}^{k_1}a_i\leq \sum_{i=k_1+1}^{k_2} a_i\leq \dots\leq \sum_{i=k_p+1}^n a_i
$$
$p$ 可以为 $0$ 且此时 $k_0=0$ .然后要求最小化::
$$
(\sum_{i=1}^{k_1}a_i)^2+(\sum_{i=k_1+1}^{k_2}a_i)^2+\dots +(\sum_{i=k_p+1}^n a_i)^2
$$
求这个最小的值。

(数据生成方式见题面)

$n\leq 4e7,1\leq a_i\leq 1e9,1\leq m\leq 1e5,1\leq l_i\leq r_i\leq 1e9,0\leq x,y,z,b_1,b_2\leq 2^{30}$

Thoughts & Solution

难想好写的典型案例(其实也不难……)

一个显然的想法是DP分组。由于这道题跟组数没有关系,所以可以修改一下常规的式子。

设 $f[i][j]$ 为对前 $i$ 个进行分组,最后一组为 $[j+1,i]$ 的最小代价,$sum[i]$ 为序列前缀和。

有方程:
$$
f[i][j]=\min{f[k][j]+(\sum_{l=j+1}^ia_l)^2}=\min{f[k][j]+(sum[i]-sum[j])^2}
$$
复杂度为 $\mathcal{O}(n^3)$ .问题出在上一个断点要一个一个枚举 $k$ 得到。考虑如何加速这个过程。

注意到 “平方之和”一定比 “和的平方”要小。所以把最后一段拆成几段(在满足递增的情况下)答案一定不会变劣。

也就是说最优解的方案一定是合法的里面 最后一段最短 的一种。

那么这时候的 $k$ 就是确定的,数组就省掉了一维变成 $f[i]$ .记录一个 $las[i]$ 表示 $f[i]$ 的方案中上一段的末尾。

方程就是:
$$
f[i]=\min{f[j]+(s[i]-s[j])^2},\\
j 满足 sum[j]-sum[las[j]]\leq sum[i]-sum[j].
$$
复杂度 $\mathcal{O}(n^2)$ 。这样已经实现了36分到64分的巨大飞跃(

然而对于 $n\leq 4e7$ ,加上常数的话复杂度得是线性的……继续优化。:pensive:

注意上面的 $j$ 的条件式。
$$
sum[j]-sum[las[j]]\leq sum[i]-sum[j]=>sum[i]\ge 2\times sum[j]-sum[las[j]]
$$
是不是清新可人的样子 你会发现如果一个 $j$ 对于 $i$ 满足上式,由于前缀和递增,显然对 $i+1$ 也满足上式,因此可行决策点的范围一定是左端点为 $1$ 的一个区间,且随着 $i$ 的增大,这个区间的右端点递增(显然)。

我们用一个函数 $g(j)=2\times sum[j]-sum[las[j]]$ 来表示右式的值。根据题意,显然 $j$ 的位置越靠右越优。

那么,如果有 $j$$<$$j’$ 且 $g(j)>g(j’)$ ,$j’$ 一定比 $j$ 优,$j$ 就是没用的了。

到这里,优化方式已经呼之欲出——单调队列!朴素想法就是在这个 $j$ 单增 $g(j)$ 单增的队列里面进行二分。但是这样还有一个 $\log$ .

再考虑左式 $sum[i]$ 的单调递增性质, 发现如果有一个点 $j$ 对当前点 $i$ 已经合法,可以进行转移了,那么 $j$ 之前的点虽然能用,但是显然没有 $j$ 好用,就可以丢掉了。所以每次从队头弹出直到留下最后一个合法点即可。

每个点只会入队一次出队一次,均摊一下,转移复杂度就是 $\mathcal{O}(1)$ 的,总复杂度 $\mathcal{O}(n)$ . 数据范围诚不欺我

LOJ AC链接 给大家讲个笑话,这道题我同一份代码(去掉文件头了)在 ACWing 上重复提交四次能得到1次RE的好成绩(

卡空间就有点过分,不过考虑到 OJ 确实开不起这么大的空间也可以理解,就是出题人太恶心。(包括这个 __int128 的离谱操作)

所以希望大家这道题尽量一次写对,避免把评测机搞炸给 y 总添麻烦(

//Author: RingweEH
const int N=4e7+10,M=1e5+10;
int n,las[N],p[M],l[M],r[M],typ,que[N];
ll a[N];

ll g( int x )
{
    return a[x]*2-a[las[x]];
}

int main()
{
//freopen( "partition.in","r",stdin ); freopen( "partition.out","w",stdout );

    n=read(); typ=read();
    if ( typ==0 )
    {
        for ( int i=1; i<=n; i++ )
            scanf( "%lld",&a[i] );
    }
    else
    {
        ll x,y,z; scanf( "%lld%lld%lld",&x,&y,&z );
        int now=0,b[2],m; scanf( "%d%d%d",&b[0],&b[1],&m );
        for ( int i=1; i<=m; i++ )
            scanf( "%d%d%d",&p[i],&l[i],&r[i] );
        for ( int i=1; i<=n; i++ )
        {
            while ( p[now]<i ) now++;
            if ( i<=2 ) a[i]=b[i-1]%(r[now]-l[now]+1)+l[now];
            else
            {
                b[0]^=b[1]^=(b[0]=(y*b[0]+x*b[1]+z)%(1<<30))^=b[1];
                a[i]=b[1]%(r[now]-l[now]+1)+l[now];
            }
        }
    }

    for ( int i=1; i<=n; i++ )
        a[i]+=a[i-1];
    int l=0,r=0;
    for ( int i=1; i<=n; i++ )
    {
        while ( l<r && g(que[l+1])<=a[i] ) l++;
        las[i]=que[l];
        while ( l<r && g(que[r])>=g(i) ) r--;
        que[++r]=i; 
    }

    I128 ans=0;
    while ( n ) ans+=(I128)(a[n]-a[las[n]])*(a[n]-a[las[n]]),n=las[n];
    int cnt=0;
    do
    {
        que[++cnt]=ans%10; ans/=10;
    }while ( ans );
    do
    {
        printf( "%d",que[cnt] ); cnt--;
    }while ( cnt );

//fclose( stdin ); fclose( stdout );
//    return 0;
}



更好的阅读体验

Statement

有 $1\sim n$ 种烹饪方法和 $1\sim m$ 种食材,使用 $i$ 方法,食材为 $j$ 的一共有 $a_{i,j}$ 道菜。

对于一种包含 $k$ 道菜的方案而言:

  • $k\ge 1$
  • 每道菜的烹饪方法不同
  • 每种食材最多出现在 $\Big\lfloor \dfrac{k}{2}\Big\rfloor$ 道菜中

求有多少种不同的搭配方案,对 $998244353$ 取模。$1\leq n\leq 100,1\leq m\leq 2000$

Thoughts & Solution

对于方阵 $a$ ,题目要求就相当于是:

  • 要取 $k\ge 1$ 个数
  • 每行只能取一个
  • 每列只能取不超过 $k\div 2$ 个。

考虑容斥,那么就是:每行至多取一个的方案 - 取了 0/1 个的方案 - 存在一列取了超过半数的方案(显然这样的列至多有一个)

对于每行至多取一个的总方案,来一遍 DP ,令 $g[i][j]$ 表示到第 $i$ 行,取了 $j$ 个的方案数,$sum[i]=\sum a_{i,j}$ 那么有:
$$
g[i][j]=g[i-1][j-1]\times sum[i]+g[i-1][j](可以开滚动维护)
$$
发现 取了 1 个的方案 其实可以直接在 存在一列取了超过半数的方案 里面统计掉,因为一定是超过半数的。

没有取的方案直接不加上就好了。

然后就可以暴力枚举超过半数的材料是哪个,进行DP。

设 $f[i][j][k]$ 表示前 $i$ 行,取了 $j$ 个,其中超过半数的 $x$ 取了 $k$ 个( $\Big\lfloor \dfrac{j}{2}\Big\rfloor <k$),枚举到 $pos$ 这道菜取了超过半数。

转移挺好想的,就是三种情况:

  • 不取
  • 取了除 $pos$ 外的任意一个
  • 取了 $pos$

转移方程:
$$
f[i][j][k]=f[i-1][j][k]+f[i-1][j-1][k]\times (sum[i]-a[i][pos])+f[i-1][j-1][k-1]\times a[i][pos]
$$
对于每个 $pos$ ,对答案的贡献就是 $\sum_{i=0}^n\sum_{j=\lfloor i/2\rfloor+1}^i f[k][i][j]$ .

这样的复杂度是 $\mathcal{O}(n^3m)$ 的,能得到 84 分的好成绩( 在考场上已经相当可观了……

然后考虑优化。发现合法状态只有 $2\times k>j$ 的部分,也就是说你完全不需要知道 $j,k$ 的具体值,所以可以把状态搞成 $2k-j$ ,省掉一维的枚举时间和空间。

那么方程就是:
$$
f[i][j(2k-j)]=f[i-1][j]+f[i-1][j+1(2k-j+1)]\times (sum[i]-a[i][pos])+f[i-1][j-1(2k-j-1)]\times a[i][pos]
$$
(数组下标内的小括号表示根据原先的 $j,k$ 定义,这个下标的值)

(注意,这里的合法状态指的是最终对答案有贡献的部分,从转移方程易知 $2k\leq j$ 的部分还是有用的,可以通过若干次 $j-1$ 部分的转移贡献到合法状态里面去)

复杂度是 $\mathcal{O}(n^2m)$ .

实现的时候注意减法取模……因为这个挂成 88 了qaq

//Author: RingweEH
const int N=110,M=2010;
const ll Mod=998244353;
int n,m;
ll a[N][M],g[N],sum[N],f[N][N<<1];

void add( ll &t1,ll t2 )
{
    t1=(t1+t2);
    if ( t1>Mod ) t1-=Mod;
}

int main()
{
    n=read(); m=read();
    for ( int i=1; i<=n; i++ )
        for ( int j=1; j<=m; j++ )
            a[i][j]=read(),add( sum[i],a[i][j] );

    memset( g,0,sizeof(g) ); g[0]=1;
    for ( int i=1; i<=n; i++ )
        for ( int j=i; j>=1; j-- )
            add( g[j],g[j-1]*sum[i]%Mod );
    ll ans=0;
    for ( int i=1; i<=n; i++ )
        add( ans,g[i] );
    for ( int pos=1; pos<=m; pos++ )
    {
        memset( f,0,sizeof(f) ); f[0][n]=1;
        for ( int i=1; i<=n; i++ )
            for ( int j=1; j<=n+i; j++ )
            {
                f[i][j]=f[i-1][j];
                add( f[i][j],f[i-1][j+1]*(sum[i]+Mod-a[i][pos])%Mod );
                add( f[i][j],f[i-1][j-1]*a[i][pos]%Mod );
            }
        for ( int i=n+1; i<=n*2; i++ )
            add( ans,Mod-f[n][i]);
    }

    printf( "%lld\n",ans );
    return 0;
}


新鲜事 原文

满心欢喜地跑到LOJ上去测我 CSP-S2019 的常数 然后除了树上的数连前10页都没进去…… 大常数选手.jpg 我无了(
图片