本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-06 10:28:11

赛时没过真的遗憾。

大概错的原因是 dp 转移写挂了。

Sol

设 $dp_u$ 为以 $u$ 为根的子树的答案。

考虑当前为 $x$，那么如何合并 $x$ 的子树的答案。

显然先把所有子树答案加起来，然后，不同子树节点的 lca 一定是 $x$。

应该将 x 的所有子树划分成两个部分（注意不能分割子树)，使得两个部分的大小乘积最大。

树上背包就能解决。

Submission

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-06 16:47:06

读 CF 题解代码看到了这个神奇的方法。

开一个大小为 $n$ 的 bitset，$n$ 需要读入。

大概这么干：

template <int len = 1>
void subset_sum(int n) {
    if (n >= len) {
        subset_sum<std::min(len*2, maxn)>(n);
        return;
    }  
    else
    {
    	bitset<len> xxx;
      ...........
    }

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-05-10 14:26:25

就这还有时间整 OI，没想到。

• 省选算法完成进度

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-05-10 17:55:37

• 对于 $k = 2n - 2$
  $k$ 在 $2n$ 左右，提示每个栈安排两种颜色。
  由于中间的元素很难消掉，考虑维持每个栈大小不超过 $2$。
  这样只需要 $\frac{2n-2}{2}=n-1$ 个栈，还空出了一个栈作为备用。
  然后依次处理牌堆，设当前牌堆顶为 $x$： 若 $x$ 还没在任何一个栈出现过，那么将 $x$ 随便丢到一个大小不超过 $1$ 的栈。如果 $x$ 已经出现过，那么看 $x$ 的那个同类牌处于栈顶还是栈底，如果处于栈顶，那么将 $x$ 丢到同类牌所在的栈，直接相消，如果处于栈底，则将 $x$ 丢到备用栈，然后 2 操作将备用栈与 $x$ 同类牌所处的栈的底相消。

• 对于 $k = 2n-1$
  多出了一种颜色，得换换思路。
  可以考虑预知牌堆顶后面的牌，作出决策。
  从上到下依次枚举牌 $i$， 先尝试按照 $k=2n-2$ 的方法家加入牌 $i$，如果成功没问题，换下一个，如果失败了，那么使用新的策略。
  设当前牌堆顶为 $p$（显然 $p$ 就是 $i$）。
  向后枚举 $x$。
  若 $x$ 的同类牌在栈顶，那么直接将 $x$ 扔到对应栈顶就行。
  若 $x$ 等于 $p$，这 $x,p$ 随便消一下就行了，然后从 $x$ 的下一个牌重新开始。
  如果 $x$ 的同类牌在栈底，设 $x$ 的同类牌所在栈为 $s$，$s$ 栈顶为 $y$ 那么分类讨论以下：
  若 $y$ 在 $p$ 和 $x$ 之间出现了奇数次，那么 $y$ 必然被消掉，所以先把 $p$ 丢进备用栈，然后 $p$ 到 $x$ 之间的牌全丢进对应的栈，最后把 $x$ 丢进栈 $s$，这样栈 $s$ 就变成了空栈，也就是说备用栈换成了 $s$。
  若 $y$ 在 $sp$ 和 $x$ 之间出现了偶数次，那么把 $p$ 丢到 $s$ 上，把这偶数个 $y$ 丢到备用栈上全部消掉，然后把 $x$ 放到备用栈上，使用 $2$ 操作将备用栈与 $s$ 的栈底相消。
  执行完以上两种分类讨论任意一种之后，从 $x$ 下一张牌牌重新开始。

本题最后按照 $k=2n-1$ 的方案执行即可。

Code

const int maxn = 305;
const int maxk = maxn*2;
const int maxm = 2e6+5;
int T;
int n,m,k;
int a[maxm];
deque<int> stk[maxn];
int id[maxk];
vector<pii> ans;
int sp;
deque<int> empt;
void op1(int idx)
{
    ans.emplace_back(mkpr(idx,0));
}
void op2(int idx1,int idx2)
{
    ans.emplace_back(mkpr(idx1,idx2));
}
bool add(int x)
{
    int idx=id[x];
    if(!idx)
    {
        if(empt.empty())return false;
        id[x]=idx=empt.front();
        empt.pop_front();
        stk[idx].push_back(x);
        op1(idx);
    }
    else
    {
        id[x]=0;
        empt.push_back(idx);
        if(stk[idx].back()==x)
        {
            stk[idx].pop_back();
            op1(idx);
        }
        else
        {
            stk[idx].pop_front();
            op1(sp);
            op2(sp,idx);
        }
    }
    return true;
}
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        read(m);
        read(k);
        FOR(i,1,m)read(a[i]);
        sp=n;
        FOR(i,1,n-1)
        {
            empt.push_back(i);
            empt.push_back(i);
        }
        int i=1;
        while(i<=m)
        {
            if(!add(a[i]))
            {
                int r=i+1;
                int p=a[i];
                int x=a[r];
                while(1)
                {
                    if(r>m)break;
                    if(x==p)break;
                    if(stk[id[x]].back()!=x)break;
                    r++;
                    x=a[r];
                }
                if(x==p)
                {
                    op1(sp);
                    FOR(j,i+1,r-1)
                    {
                        add(a[j]);
                    }
                    op1(sp);
                }
                else
                {
                    int idx=id[x];
                    int stktop=stk[idx].back();
                    bool even=1;
                    FOR(j,i+1,r-1)
                    {
                        even^=(a[j]==stktop);
                    }
                    if(even)
                    {
                        op1(idx);
                        stk[idx].push_back(p);
                        FOR(j,i+1,r-1)
                        {
                            if(a[j]==stktop)
                            {
                                op1(sp);
                            }
                            else
                            {
                                add(a[j]);
                            }
                        }
                        op1(sp);
                        op2(sp,idx);
                        stk[idx].pop_front();
                        id[x]=0;
                        id[p]=idx;
                    }
                    else
                    {
                        op1(sp);
                        stk[sp].push_back(p);
                        FOR(j,i+1,r-1)
                        {
                            if(a[j]==stktop)
                            {
                                op1(idx);
                            }
                            else add(a[j]);
                        }
                        op1(idx);
                        stk[idx].clear();
                        id[x]=id[stktop]=0;
                        id[p]=sp;
                        empt.push_back(sp);
                        sp=idx;
                        
                    }
                }
                i=r+1;
            }
            else
                i++;
        }
        printf("%d\n",(int)ans.size());
        for(pii v:ans)
        {
            if(v.second)printf("%d %d %d\n",2,v.first,v.second);
            else printf("%d %d\n",1,v.first);
        }
        \/\/ clean
        empt.clear();
        ans.clear();
        FOR(i,1,n)
        {
            stk[i].clear();
        }
        FOR(i,1,k)
        {
            id[i]=0;
        }
    }
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-05-15 22:57:56

对于 $n \le 16,m \le 25$ 和性质 A。

这 45 分是白送。

100pts

要保护的是割边，所以考虑边双缩点。

显然，缩点之后一定是一棵树，每个点（或者说是边双连通分量）内部的边不需要保护。

考虑树形 dp。
设 $dp_{i,1/0}$ 为以节点 $i$ 为根的子树建造军营和不建造军营的方案数。

但是发现对于 $i$ 不建造军营，子树建造军营的部分，无法确定 $i$ 到子树的边选不选，因为我们不知道 $i$ 为根的子树以外是否有军营。

只能增加限制。

具体地说，状态增加一条，强制 $i$ 子树内选的点能通过选的边和 $i$ 连通。

然后树形 dp 求出所有的 $dp_{i,1/0}$，这一部分比较容易。

大概写一下自认为比较难的部分的流水账：
统计答案，我们对于每个 $i$，假定所有的军营都在以 $i$ 为根的子树内，并且与 $i$ 相连，既然与 $i$ 相连，那么为了不让答案算重，就不能选 $father_i$ 到 $i$ 的边。

式子也就能推出来了。

结束。

#include <bits\/stdc++.h>
using namespace std;
const int maxn=5e5+5;
const int maxm=1e6+5;
typedef long long ll;
const ll MOD=1e9+7;
int n,m;
int head[maxn];
struct EDGE
{
    int to,nxt;
}edge[maxm<<1];
int cnt=1;
void add(int u,int to)
{
    edge[++cnt].to=to;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
}
vector<int> G[maxn];
int dfn[maxn],low[maxn],dfcnt;
bool ins[maxn];
bool cut[maxm<<1];
int bccnt;
int e[maxn],v[maxn];
int color[maxn];
void tarjan(int u,int _fa)
{
    dfn[u]=low[u]=++dfcnt;
    ins[u]=1;
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int to=edge[i].to;
        if(to==_fa)continue;
        if(!dfn[to])
        {
            tarjan(to,u);
            low[u]=min(low[u],low[to]);
        }
        else
        {
            low[u]=min(low[u],dfn[to]);
        }
        if(low[to]>dfn[u])cut[i]=cut[i^1]=1;
    }
    ins[u]=0;
}
bool visnode[maxn];
void dfs(int u)
{
    visnode[u]=1;
    v[bccnt]++;
    color[u]=bccnt;
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int to=edge[i].to;
        if(!visnode[to]&&!cut[i])
        {
            dfs(to);
        }
    }
}
int sub_edgecnt[maxn];
ll pw[maxn+maxm*2];
ll f[maxn][2];
ll ans=0;
void calcsub(int u,int _fa)
{
    sub_edgecnt[u]=e[u];
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int to=edge[i].to;
        if(to==_fa)continue;
        calcsub(to,u);
        sub_edgecnt[u]+=sub_edgecnt[to]+1;
    }
}
void dp(int u,int _fa)
{
    f[u][0]=pw[e[u]];
    f[u][1]=(pw[v[u]+e[u]]-pw[e[u]])%MOD+MOD;
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(v==_fa)continue;
        dp(v,u);
        f[u][1]=f[u][0]*f[v][1]%MOD+f[u][1]*(2ll*f[v][0]+f[v][1])%MOD;
        f[u][1]%=MOD;
        f[u][0]=f[u][0]*2ll*f[v][0]%MOD;
    }
    ans+=f[u][1]*pw[sub_edgecnt[1]-sub_edgecnt[u]-(u!=1)]%MOD;
    ans=(ans%MOD+MOD)%MOD;
}
int main()
{
    scanf("%d%d",&n,&m);
    pw[0]=1ll;
    for(int i=1;i<=n+m;i++)
    {
        pw[i]=pw[i-1]*2ll%MOD;
    }
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].emplace_back(v);
        G[v].emplace_back(u);
        add(u,v);
        add(v,u);
    }
    tarjan(1,0);
    for(int i=1;i<=n;i++)
    {
        if(!visnode[i])
        {
            ++bccnt;
            dfs(i);
        }
    }
    memset(head,0,sizeof head);
    cnt=0;
    for(int i=1;i<=n;i++)
    {
        for(int to:G[i])
        {
            if(color[i]!=color[to])
            {
                add(color[i],color[to]);
            }
            else
            {
                e[color[i]]++;
            }
        }
    }
    for(int i=1;i<=bccnt;i++)
    {
        e[i]\/=2;
    }
    calcsub(1,0);
    dp(1,0);
    printf("%lld",ans);
    return 0;
}  

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-05-22 16:17:20

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-05-27 20:19:11

链接：
https://codeforces.com/contestInvitation/e332faf6f5357c8baf3412c5d0e1bd80a23b0c6c

C 题。

status里面 vector_1 C 题最后一发 AC 提交。

我的做法：

每个人向自己买过彩票的天连一条容量为 1 的边，代表能对该天产生一个贡献。 因为每个人最多贡献一天，建立超级源点，向每个人连一条容量为 1 的边。 由于每天只能被贡献一次，每天向超级汇点连一条容量为 1 的边。 如果超级汇点最终得到的流量总和为 n，即每天都得到了贡献，那么有解。 否则一定无解。

我随机输入了几组数据都是对的，有没有大佬看看我有没有锅掉。

网络流没对拍。

我在 contest edit 里面开放了自由查看 WA 掉的测试数据和其他人代码。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-05-28 21:05:05

说一下我遇到的麻烦和解决方法。
好不容易摸索出来的解决方案。
polygon 真的比 luogu 方便多了，不加引号，自动生成数据，自动校验题目。

• 没地方上传 Generator
  在 Files 里面上传，你会发现找不到设置文件属性的地方（就是找不到告诉 polygon 你上传的这个文件是 generator 的地方）。

• 解决方案
  在 Tests 里面上传数据生成器脚本，CF 会默认你的脚本使用的那个文件为 Generator（在 polygon 启动脚本并且测试数据生成完毕后去 tests 里面看一下，能看到 CF 已经自动对该文件标记上 Generator）。

• Polygon 建完题，CF mushup 加题的时候说无法下载题目描述。

• 解决方案
  在 polygon 的题目编辑界面找到 Packages，看到里面有 Standard 和 Full 两个选项，随便选一个点一下，polygon 就会自动生成包。然后就可以在 CF mushup 里面添加了。生成 package 也方便备份。

• polygon 修改完，CF 对应却没有更新

• 解决方案
  在 CF对应的题目编辑界面（不是 polygon），什么也不用做，save change 点一下，然年就更新了。
  另外注意 polygon 修改完，一定要生成新的 package！！！！！

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-05-30 17:35:48

https://www.luogu.com.cn/blog/vectorlmn/

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-06-17 21:54:32

A-F 都是水题。

A-C

too simple.

D

dp。

E

multiset 模拟。

F

贡献拆开来算。
第一个部分，先不计算两个集合混合导致的排名变化，直接算。
第二个部分，考虑变化造成的影响，对于第 $A_{i,j}$，第 $i+1$ 到 $n$ 个集合中比它小的数的个数就是增加的贡献。

解决。

G

不会。

Ex

更不会。