Featured

My First Blog Post

Be yourself; Everyone else is already taken.
— Oscar Wilde.

This is the first post on my new blog. I’m just getting this new blog going, so stay tuned for more. Subscribe below to get notified when I post new updates.

写在前面的话

在Luogu-Blog上食用

网络流是什么？能干什么？

简而言之，网络流（network-flows） 是一种类比水流的算法，是用在图论上的。
它的应用遍布通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域，可不只能帮你打NOIP或ACM哟~~
它其实一点也不难。

Lead In

我们来看一个经典的问题。
这里有一张图：

有向图的边权表示流量，问：从A到D能流多少过去？

假设不存在水管爆了等特殊情况。

Method

可以发现，这里有一条Fantastic的路径

所以最大值为1？
很遗憾，最大值为2。

因为可以A-B-D + A-C-D = 2。

True Method

引入网络流Dinic算法。
有点类似BFS，但是在跑出一条合法路径时，需要做一件奇怪的事情。
建反向边。
What?
就是这样：

解释一下。
在跑出一条可行路后，反向建边。
同时给正边减掉最终流到终点的值，反边加上最终流到终点的值。
于是就有了上面那张图。

那有什么用呢？
哝↓

于是就有了另一条可以走的边

~~可以证明~~，这个算法是正确的。
So , How ?

Prove

其实在我们走B-C的反向边C-B时，相当于把这段流量退了回去。让B点的流量流向D。
这样做的前提是，发现了另一条可以到达C的路径也就是A-C。
可以这么理解，A-C最终接上了C-D，而A-B接上了B-D。

Attention

注意Dinic算法会选择包含弧最少的路径来流。

附录

优秀的Dinic代码：

bool Bfs()
{
    while(!q.empty()) q.pop();
    memset(vis,0,sizeof(vis));
    memset(incf,0x3f,sizeof(incf));
    q.push(S);
    vis[S]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=h[x];i;i=a[i].next)
        {
            if(vis[a[i].to]||!a[i].v) continue;
            incf[a[i].to]=min(incf[x],a[i].v);
            p[a[i].to]=i;
            q.push(a[i].to);
            vis[a[i].to]=1;
            if(a[i].to==T) return 1;
        }
    }
    return 0;
}
void Dfs()
{
    int x=T;
    while(x!=S)
    {
        int i=p[x];
        a[i].v-=incf[T];
        a[i^1].v+=incf[T];
        x=a[i^1].to;
    }
    maxflow+=incf[T];
}

使用：

while(Bfs()) Dfs();

Self-Introduction

Me, a Amorphophallus Konjac OIer studying in Bashu Secondary School. Started OI learning at the age of eleven, got fond of it and couldn’t stop.

Purpose of this Blog

This Blog is inuse because I’m disappointed about my old Blog and wanted to start a new one.

CopyRight Agreement (ZH-HANS)

遵循 CC 4.0 by-sa 版权协议，转载此博客任何一篇文章请附上原文出处链接。

CH5702 Count The Repetitions 题解

在Luogu-Blog上食用

重更Blog写道毒瘤题题解

题目地址

首先明确一个道理，即：
conn(conn(s2,n2),m)=conn(s2,n2*m)
[长得很像乘方运算]

所以可以求出一个最大的M，使得conn(s2,M)可以被conn(s1,n1)生成
然后⌊M/n2⌋即为答案

我们考虑将M拆分为：
M=2^k1+2^k2+2^k3+…+2^kn
于是效率就有了大幅的提升

再考虑使用DP。
定义状态f[i][j]
表示从s1[i]开始用多少个字符可以凑成conn(s2,2^j)
然后就是状态转移方程：

f[i][j]=f[i][j-1]+f[(f[i][j-1]+i)%s1.length()][j-1]

最后一步就是枚举s1起始位置，并统计最大的M值
这一步很简单，就不再赘述

下面讲细节问题：

1.<s1.length( ) <s2.length( )千万不要打错

2.当s1串中少了s2串中的一个字符时，特判输出0
然后千万不能return
因为是多组数据！

3.f数组的j那维要开到30
因为有10^6*100的数据，20不够！

好不容易听我耐心地讲完，该放代码了：

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
int n1,n2;
string s1,s2;
long long f[101][31];
int main()
{
    bool bj=0;
    St:
    while(cin>>s2>>n2>>s1>>n1)
    {
        for(int i=0;i<s1.length();i++)
        {
            f[i][0]=0;
            int t=i;
            for(int j=0;j<s2.length();j++)
            {
                int cnt=0;
                while(s1[t]!=s2[j])
                {
                    t=(t+1)%s1.length();
                    if(++cnt>=s1.length())
                    {
                        printf("0\n");
                        goto St;
                    }
                }
                t=(t+1)%s1.length();
                f[i][0]+=cnt+1;
            }
        }
        for(int j=1;j<=30;j++)
            for(int i=0;i<s1.length();i++)
                f[i][j]=f[i][j-1]+f[(i+f[i][j-1])%s1.length()][j-1];
        long long m=0;
        for(int i=0;i<s1.length();i++)
        {
            long long x=i,ans=0;
            for(int j=30;j>=0;j--)
                if(x+f[x%s1.length()][j]<=s1.length()*n1) x+=f[x%s1.length()][j],ans+=(1<<j);
            m=max(m,ans);
        }
        printf("%lld\n",m/n2);
    }
    return 0;
}

Introduce Yourself (Example Post)

This is an example post, originally published as part of Blogging University. Enroll in one of our ten programs, and start your blog right.

You’re going to publish a post today. Don’t worry about how your blog looks. Don’t worry if you haven’t given it a name yet, or you’re feeling overwhelmed. Just click the “New Post” button, and tell us why you’re here.

Why do this?

Because it gives new readers context. What are you about? Why should they read your blog?
Because it will help you focus you own ideas about your blog and what you’d like to do with it.

The post can be short or long, a personal intro to your life or a bloggy mission statement, a manifesto for the future or a simple outline of your the types of things you hope to publish.

To help you get started, here are a few questions:

Why are you blogging publicly, rather than keeping a personal journal?
What topics do you think you’ll write about?
Who would you love to connect with via your blog?
If you blog successfully throughout the next year, what would you hope to have accomplished?

You’re not locked into any of this; one of the wonderful things about blogs is how they constantly evolve as we learn, grow, and interact with one another — but it’s good to know where and why you started, and articulating your goals may just give you a few other post ideas.

Can’t think how to get started? Just write the first thing that pops into your head. Anne Lamott, author of a book on writing we love, says that you need to give yourself permission to write a “crappy first draft”. Anne makes a great point — just start writing, and worry about editing it later.

When you’re ready to publish, give your post three to five tags that describe your blog’s focus — writing, photography, fiction, parenting, food, cars, movies, sports, whatever. These tags will help others who care about your topics find you in the Reader. Make sure one of the tags is “zerotohero,” so other new bloggers can find you, too.