省选前-我爱学习-解题报告-学习笔记

i207M · 2019-03-06 21:37:02 · 个人记录

CF235D

对基环树进行随机点分治，求期望复杂度。

我去，一眼看上去这道题好神仙啊...看了题解之后恍然大悟：考虑每对点的贡献。

具体来说，考虑Event(a,b)表示a作为“重心”时，b和a联通的概率。事实上，概率是1/dis(a,b)

原因：首先，如果重心不在ab的链上，对p没有影响。当重心在链上，只有a是重心是才为1，所以是1/dis(a,b)

扩展到基环树上，就是两个点之间联通的概率，容斥一下即可。

void dfs(int x,int d,int h)
{
    if(vis[x]) return;
    vis[x]=1;
    h+=(du[x]==2);
    if(h>=2) ans+=1.0/d+1.0/(d-h+2+sz-h)-1.0/(d+sz-h);
    else ans+=1.0/d;
    for(solid v:E[x]) dfs(v,d+1,h);
}

数轴上的概率题

小明在数轴原点，每次 p 概率向右走，1-p 概率向左走，求小明走到-1 位置的概率

设答案为q，则有

q=1-p+pq^2

解得q_1=1,q_2=1/p-1。应该是，若p\le 0.5，取前者；否则是后者。

CF325D

首先，为了解决环形的问题，我们可以将它复制一份接在旁边。然后呢？肯定是用并查集。因为并查集不能删边，所以我一直在想“时光倒流”之类的，但是不行。

看到题解之后恍然大悟：我们维护陆地八联通格子的连通性。如果(x,y)与(x,y+m)联通，那么不可行。证明好像比较显然。

注意：此时，我们倍长环的目的仅仅是为了检查是否有环绕一圈的路径，所以此时，倍长后的矩阵最左侧和最右侧依旧是相邻的。

Gym - 100551B Dynamic connectivity contest

好像这一场挺有意思的，看看。

GraphAero

动态加边，维护边双。

用两个并查集，一个维护连通性，一个维护边双（因为边双具有传递性）。

因为要求出LCA，所以离线建出完整的树（要强制在线的话\log^2）。

当然可以LCT在线维护。

Bridges in a Tree

给定一棵树，每次询问给出一个边集，问加入边集里的边之后，有多少割边。

两种做法：

1.每加入一个边，就树剖区间把边覆盖为1（表示不是割边了），最后查询全局和即可。

2.建出虚树，变成求链并。

检查矩阵

给你三个n*n矩阵A,B,C，验证是否满足

A*B = C

随机向量带进去。

codechef Connect

给你一个矩阵(含有-1,0以及一些正数)，希望选择一个连通块，使得连通块不含-1 ，且不同正数个数大于等于K。每选择一个格子都会有一定代价，求最小化代价。N, M ≤ 15, K ≤ 7

每次给每个整数随机一个1-7的编号，然后求斯坦纳树。则得到最优解当且仅当最优解的7个数在此次编号中互不相同。随机900次，正确概率为99%

先思考某个数据范围比较小时怎么做

CF241D

惊了...

codechef LECOINS

剩余系最短路好题。我们不仅要求出可行性，还要得到最多的颜色数量。看到颜色数比较小，我们可以建出分层图，具体的设dp[i][j][k]表示考虑前i个颜色，选了j个颜色，\mod M=k的最小和。

转移的话，因为比较卡常，所以不能无脑Dij或SPFA，而是要对剩余系下每个环分别考虑,O(n)DP出来（从每个同余gcd的环的最小值开始DP）。

CF266D

~~发现，如果我们确定了最终答案的点，那么最终答案很好求。于是我们对每条边三分最优解的位置即可。~~ PPT在骗我！这个函数根本不是单峰函数！

正解是这样：符合我一开始的直觉：答案要么是整数，要么是.5。我们枚举最终答案在哪个点取到，然后我们需要拼接一下，所以我们把所有点从大到小排序，然后维护一个r表示处理过的点到y的最大值，每次新处理一个点l，看l到x到y到r的路径的中点是否在这条边上，更新答案。

    for(ri e=1; e<=m; ++e)
    {
        int x=u[e],y=v[e],r=0;
        ve.clear();
        for(ri i=1; i<=n; ++i) ve.pb(mp(g[x][i],i));
        sort(ve.begin(),ve.end());
        for(ri i=n-1; i>=0; --i)
        {
            int l=ve[i].fi,mid=(l+r+w[e])/2;
            if(mid>=l&&mid<=l+w[e]) ckmin(ans,mid);
            ckmax(r,g[y][ve[i].se]);
        }
    }

Goodbye 2017

New Year and Original Order

数位DP

New Year and Entity Enumeration

好题，神仙题！

给定n个长为m的01串集合T，求出满足要求的S的个数，使T是S的子集，且S在&和~运算下封闭。

先不考虑T的限制，有这样一个事实：设f[x]表示包含第x位的最小的数（所有含x的数&起来），那么考虑x\neq y，要么f[x]=f[y]，要么f[x]\&f[y]=0。原因：此时!(f[x]&f[y])&f[x]含有第x位且更小。

因此，这就是m的集合划分数。

然后考虑T的限制，相当于我们强制一些数不在一个集合里。那么我们就把可以在一个集合里的数一起考虑，把每个分区的贝尔数乘起来即可。

New Year and Rainbow Roads

注意到我们只会连RB，GB，BB。对B形成的每一段分别考虑是否连BB即可。

New Year and Boolean Bridges

给定n\times n,n\le 47的矩阵，表示i,j能否在一个SCC中（必须/任意/必须不），你要求出符合条件的图的最小边数。

注意到对每个SCC我们肯定是连成一个环，那么答案就是n-1+环。于是我们要最小化环的数量。此时，大小为1的SCC无用，所以我们新图的总点数只有23个，可以状压。

现在问题转化为了，最少选择几个独立集（有边表示不能在一个SCC），我们可以设f[S]表示S内独立集的个数。那么我们可以枚举答案k，通过容斥求出从图中选k个独立集的方案数，如果可以，就得到了答案。

CF1129D

给定数列A，求划分A的方案数，使得每个区间内只出现一次的数的数量\le K

很明显要DP，我们运用扫描线的思想很容易将“后缀内只出现一次的数的数量”统计出来。然后看看我们需要支持什么操作：区间加，查询区间\le K的数的权值和。

貌似除了O(n\sqrt{n}\log n)之外没有好方法？

注意到区间加这个事情，其实我们每次只是前缀加，于是我们可以用更聪明的办法解决：差分。单点修改可以暴力重构解决。对于每块维护g[i]表示

\sum_j [sum[j+1,r]\le i]f[j]

于是就可以从后往前扫每个块，O(1)查询了。

WF2013 A

这道题的O(n^2)建图比较显然，考虑优化。发现只有26种本质不同的边，于是我们可以把26种关系看成点对，正方形看成边。

如何防止图形拼接时和自己相交？只要限制每次拼接必须换边即可。

int trans(const char s[])
{
    if(s[0]=='0') return -1;
    return (s[0]-'A')*2+(s[1]=='+');
}
int n;
int g[55][55];
signed main()
{
    in(n);
    for(ri i=1; i<=n; ++i)
    {
        static char s[10]; scanf("%s",s);
        static int a[5];
        for(ri j=0; j<4; ++j) a[j]=trans(s+j*2);
        for(ri j=0; j<4; ++j)
            if(a[j]!=-1) for(ri k=0; k<4; ++k)
                    if(j!=k&&a[k]!=-1) g[a[j]][a[k]^1]=1;
    }
    for(ri i=0; i<52; ++i)
        for(ri k=0; k<52; ++k)
            if(g[i][k]) for(ri j=0; j<52; ++j) g[i][j]|=g[k][j];
    for(ri i=0; i<52; ++i)
        for(ri j=0; j<52; ++j) if(g[i][j]&&g[j][i])
            {
                puts("unbounded");
                return 0;
            }
    puts("bounded");
    return 0;
}

CF241E

~~ri，写这道题写了好久，拓扑排序不知道为啥就是不对...~~

给定一张DAG，给每条边一个1或2的边权，使1-n的所有路径长度相同。

其实比较简单，每个点最终答案一定是一个，则需要满足：

L[v] \ge L[u]+1,R[v]\le R[u]+2

L[u]\ge L[v]-2,R[u]\le R[v]-1

于是跑一边SPFA即可。统计答案用L或R都可以。

#define N 1005
int n,m;
vector<int>E[N],fE[N];
int vis[N];
void dfs(int x)
{
    if(vis[x]) return;
    vis[x]=1;
    for(solid v:E[x]) dfs(v);
}
void efs(int x)
{
    if(vis[x]==1)
    {
        vis[x]=2;
        for(solid v:fE[x]) efs(v);
    }
}
int d[N];
bool work()
{
    bool res=0;
    for(ri x=1; x<=n; ++x)
        if(vis[x]==2) for(solid v:E[x])
            {
                if(vis[v]!=2) continue;
                res|=ckmax(d[v],d[x]+1);
                res|=ckmax(d[x],d[v]-2);
            }
    return res;
}
int ide[N][N];
int ans[N*5];
signed main()
{
    in(n,m);
    for(ri i=1,a,b; i<=m; ++i)
    {
        in(a,b);
        E[a].pb(b),fE[b].pb(a);
        ide[a][b]=i,ans[i]=1;
    }
    dfs(1); efs(n);
    while(work()&&d[1]==0);
    if(d[1]!=0)
    {
        puts("No");
        return 0;
    }
    for(ri x=1; x<=n; ++x)
        if(vis[x]==2) for(solid v:E[x])
            {
                if(vis[v]!=2) continue;
                ans[ide[x][v]]=d[v]-d[x];
            }
    puts("Yes");
    for(ri i=1; i<=m; ++i) out(ans[i]);
    return 0;
}

CF193D

扫描线。在扫描线的同时是可以维护[l,cur]的值域的区间个数的。

Middle

n 个点的树，边有权值。找出一条经过的边数在 l 到 r 之间的路径，使得路径上边权的中位数最大。

边分治，二分中位数，按深度枚举一边的点，另一边用单调队列维护。O(n\log ^2n)

Gym 10754E

两颗树，有根带标号，儿子有顺序。

你每次操作可以选择一颗树，然后执行二选一：

删除一个叶子。
将某个节点相邻两个儿子合并，前面那个节点的儿子排在前面，后面那个节点的儿子排在后面。

问至少操作多少次能使得两棵树同构。

发现，两棵树同构当且仅当它们的深度序相同（深度序为：dfs序，但是把每个点的编号换成深度）。发现这两个操作的实质就是在深度序上删一个点。但是我们并不是删任何一个点都可以，如果一个点只有一个儿子，那么那个儿子无法和其他儿子合并。但是注意到在最优策略中，我们不会删除某个点和单儿子的边的。于是求出两棵树深度序的LCS即可。

CF444D

可以证明，把出现的所有位置直接暴力归并排序的复杂度是对的。

BZOJ 3565 [SHOI2014]超能粒子炮

~~迄今为止还没有调出来求逆元的部分~~

注意到，大约每m/a次加法才会取模一次，所以形成了O(a)个等差数列，我们O(a^2)枚举，讨论一下，贡献答案。

void build()
{
    int tot=n,x=b;
    while(tot>0)
    {
        x=(x+a)%md;
        pt[++cnt].s=x;
        pt[cnt].l=(md-x+a-1)/a;
        if(pt[cnt].l>tot) pt[cnt].l=tot;
        pt[cnt].e=(x=(x+(LL)(pt[cnt].l-1)*a)%md);
        tot-=pt[cnt].l;
    }
}
void solve()
{
    build();
    for(ri i=1; i<=cnt; ++i)
        for(ri j=i+1; j<=cnt; ++j)
            calc(pt[i],pt[j]);
}

UOJ 284 快乐游戏鸡

这道题最重要的转化是注意到每次死亡的贡献是独立的，可以用线段树维护从i-1升到i的最小距离。然后线段树合并即可。

但是上面的做法写起来很麻烦，而且空间很紧。

更优秀的做法：长链剖分+单调队列。

单调队列从hd到tl，dep和w都递增。

这样对于一个询问，我们就可以在单调队列上二分，通过记录后缀和统计答案（原因是我们的单调队列每次在队头添加元素）。

考虑如何合并？每个队列的长度是O(子树最大深度)的，长链剖分。合并队列时，把x的队列中dep<mxd[v]的点也拿出来，然后和v的队列归并。

il void ins(int x,const Node &v)
{
    while(hd[x]<=tl[x]&&p[hd[x]].w<=v.w) ++hd[x];
    if(hd[x]>tl[x]||p[hd[x]].d>v.d)
    {
        sum[hd[x]-1]=(hd[x]<=tl[x]?(LL)p[hd[x]].d*(p[hd[x]].w-v.w)+sum[hd[x]]:0);
        p[--hd[x]]=v;
    }
}
void merge(int x,int y)
{
    static Node buk[N]; int tp=0;
    while(hd[x]<=tl[x]&&p[hd[x]].d<=p[tl[y]].d) buk[++tp]=p[hd[x]++];
    while(tp&&hd[y]<=tl[y])
        if(p[tl[y]].d>buk[tp].d) ins(x,p[tl[y]--]);
        else ins(x,buk[tp--]);
    while(tp) ins(x,buk[tp--]);
    while(hd[y]<=tl[y]) ins(x,p[tl[y]--]);
}