2020牛客暑期多校训练营（第一场）
in 牛客多校多校训练 with 1 comment
牛客 多校

2020牛客暑期多校训练营（第一场）

in 牛客多校多校训练 with 1 comment

牛客 多校

摘要

/ABCDEFGHIJK
场上 ✔ ✔ ✔
zyj ✔ ✔
wrf✔ ✔
lmj ✔ ✔ ✔✔ ✔

题目

A.B-Suffix Array

wrf (赛后)

题意

定义一个函数 $B:char[n] \rightarrow vector[n]$，其含义为：对于原串的第 $i$ 个字符，找到它之前与它相同的字符位置 $j$，结果的第 $i$ 个元素即为 $i-j$。如果不存在这样的字符，相应的结果为 $0$。

举例：
$B(aaa)=(0,1,1)$
$B(abaababb)=(0,1,2,1,3,2,2,1)$

题目要求对给出的，字符集仅为 $\{a,b\}$ 的串的所有后缀做函数 $B$，把结果按字典序排序，输出最后的顺序。
保证串长不超过 $10^5$。

题解

做法

对于字符串的第 $i$ 个字符，定义对偶函数 $b'(i)$，其含义为：对于原串的第 $i$ 个字符，找到它之后与它相同的字符位置 $j$，结果的第 $i$ 个元素即为 $j-i$。如果不存在这样的字符，相应的结果为 $\infty$。
就像题中的函数 $B$，一个字符串的函数 $B'$ 就是由每个位置的 $b'$组成。
定义 $B'$ 上的小于关系为字典序从大到小，并且前缀优先。

举例：
$B'(a)=(\infty)<B'(ab)=(\infty,\infty)<B'(aba)=(2,\infty,\infty)$

按照对偶函数的顺序构造后缀数组即可。

举例：
以串 abaabaaaabba 为例：

$rank[i]$$i$$s[i:n]$$B(s[i:n])$$LCP[i]$$B'(s[i:n])$$LCP[B'(i)]$
$1$$12$a$0$$-1$$\infty$$-1$
$2$$11$ba$0,0$$1$$\infty,\infty$$1$
$3$$5$baaaabba$0,0,1,1,1,5,1,3$$2$$5,1,1,1,3,1,\infty,\infty$$0$
$4$$9$abba$0,0,1,3$$3$$3,1,\infty,\infty$$0$
$5$$2$baabaaaabba$0,0,1,3,2,1,1,1,5,1,3$$4$$3,1,2,5,1,1,1,3,1,\infty,\infty$$2$
$6$$4$abaaaabba$0,0,2,1,1,1,5,1,3$$2$$2,5,1,1,1,3,1,\infty,\infty$$0$
$7$$1$abaabaaaabba$0,0,2,1,3,2,1,1,1,5,1,3$$4$$2,3,1,2,5,1,1,1,3,1,\infty,\infty$$1$
$8$$10$bba$0,1,0$$1$$1,\infty,\infty$$0$
$9$$8$aabba$0,1,0,1,3$$3$$1,3,1,\infty,\infty$$1$
$10$$3$aabaaaabba$0,1,0,2,1,1,1,5,1,3$$3$$1,2,5,1,1,1,3,1,\infty,\infty$$1$
$11$$7$aaabba$0,1,1,0,1,3$$2$$1,1,3,1,\infty,\infty$$1$
$12$$6$aaaabba$0,1,1,1,0,1,3$$3$$1,1,1,3,1,\infty,\infty$$2$

答案即为列 $i$。

证明

详细证明见论文 Parameterized Suffix Arrays for Binary Strings。以下大致描述该论文的思路。

我们只需证明，$B$ 与 $B'$ 存在对应的偏序关系。即

$$ \begin{aligned} B'(s[i:n])<B'(s[j:n]) \Rightarrow B(s[i:n])<B(s[j:n]) \\ B'(s[i:n])=B'(s[j:n]) \Rightarrow B(s[i:n])=B(s[j:n]) \end{aligned} $$

那么 $B'(s[i:n])=B'(s[j:n])$ 时显然。下面考虑小于的情况。

证明：
反证。不妨设 $s_i[k]=s[i+k]=s[n],s_j[k]=s[j+k] \not = s[n]$
那么 $b'_i(k),b'_i(b'_i(k)),\dots$ 中必然有一个为 $n$，$b'_j(k),b'_j(b'_j(k)),\dots$ 中必然没有 $n$。
与 「$B'(s[i:n])$ 是 $B'(s[j:n])$ 的前缀」相矛盾。
另一侧的证明显然。

由此，显然对于任意的 $k$，要么 $b_i(k)=b_j(k)$，要么 $b_i(k)=0$。即 $B(s[i:n])$ 要么是 $B(s[j:n])$ 的前缀，要么存在 $b_i(k)=0<b'_j(k)$。

综上，原命题得证。

时间复杂度

视后缀数组的构造算法，$O(n \log n)$ 到 $O(n)$

实现细节

通过令 $\infty=n$，并且加入虚节点 $b'[n+1]>n$ 的方式，通过普通后缀数组模板实现排序。

代码

#include <bits/stdc++.h>

using namespace std;

const int N=3000020;

char ts[N];
int s[N];
int n,sa[N],rk[N],oldrk[N << 1],id[N],px[N],cnt[N];

bool cmp(int x,int y,int w) 
{
    return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

void solve()
{
    int l[2]={n+1,n+1};
    for(int i=n;i>0;i--)
    {
        s[i]=((l[ts[i]-'a']>n?n:l[ts[i]-'a']-i));
        l[ts[i]-'a']=i;
    }
    n++;
    s[n]=n;
    int i,m=n+3,p,w;

    for(int i=0;i<=n+5;i++)
    {
        sa[i]=rk[i]=oldrk[i]=oldrk[i+n+5]=id[i]=px[i]=cnt[i]=0;
    }

    for(i=1;i<=n;++i) ++cnt[rk[i]=s[i]];
    for(i=1;i<=m;++i) cnt[i]+=cnt[i-1];
    for(i=n;i>=1;--i) sa[cnt[rk[i]]--]=i;

    for(w=1;w<n;w<<=1,m=p) 
    { 
        for(p=0,i=n;i>n-w;--i) id[++p]=i;
        for(i=1;i<=n;++i) if(sa[i]>w) id[++p]=sa[i]-w;
        for(i=0;i<=n;++i) cnt[i]=0;
        for(i=1;i<=n;++i) ++cnt[px[i]=rk[id[i]]];
        for(i=1;i<=m;++i) cnt[i]+=cnt[i-1];
        for(i=n;i>=1;--i) sa[cnt[px[i]]--]=id[i];
        for(i=0;i<=min(N-1,2*n+5);++i) oldrk[i]=rk[i];
        
        for(p=0,i=1;i<=n;++i) rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
    }

    for(i=n-1;i>=1;--i) printf("%d ",sa[i]);
    printf("\n");
}

int main(void)
{
    while(~scanf("%d",&n))
    {
        scanf("%s",ts+1);
        solve();
    }

    return 0;
}

B.Infinite Tree

lmj (赛后)

题意

给定一张图，mindiv(n)为n的最小的除数，n与n/mindiv(n)之间有一条长度为1的边，求一个点u使得$\sum_1^mw_i*dis(u,i!)$最小

题解

可以认为u是$x_1*x_2*x_3*x_4……$，同时是递减的，即为从根1走到$x_1$后再走到$x_1*x_2$，那么考虑枚举质数和每种质数的个数，考虑走到某个地方能否使得答案是减少的，可以确定该答案是一个区间，在不断缩小后即可以得到答案

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
vector<int>v[N];
bool prime[N];
ll w[N];
ll sum[N];
void pre(int n)
{
    for(int i=2;i<=n;i++){
        if(!prime[i]){
            for(int j=i;j<=n;j+=i){
                if(i!=j)prime[j]=1;
                int tmp=j;
                while(tmp%i==0){
                    tmp/=i;
                    v[i].push_back(j);
                    sum[j]++;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        sum[i]+=sum[i-1];
    }
}
void work()
{
    pre(1e5);
    int n;
    while(~scanf("%d",&n)){
        ll cnt=0;
        for(int i=1;i<=n;i++){
            scanf("%lld",&w[i]);
            cnt-=w[i];
            w[i]+=w[i-1];
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            ans+=(w[i]-w[i-1])*sum[i];
        }
        int l=1,r=n;
        for(int i=n;i>=2;i--){
            if(!prime[i]){
                for(int j=0;j<v[i].size();j++){
                    int x=v[i][j];
                    if(x>n)break;
                    if(x>l){
                        ll tmp=(w[x-1]-w[l-1])*2;
                        if(cnt+tmp>=0){
                            if(r>=x){
                                cnt+=(w[r]-w[x-1])*2;
                                r=x-1;
                            }
                            break;
                        }
                        cnt+=tmp;
                        l=x;
                    }
                    //printf("%d\n",ans);
                    ans+=cnt;
                }
                if(cnt>=0)break;
            }
        }
        printf("%lld\n",ans);
    }
 
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

D.Quadratic Form

lmj (赛后)

题意

$x_1,x_2,……,x_n$属于$R$,要求$\sum_{i=1}^n\sum_{j=1}^na_{ij}x_ix_j \le 1$,并且$\sum_{i=1}^nb_ix_i$最大,求$(\sum_{i=1}^nb_ix_i)^2$的值模998244353

题解

考虑使用拉格朗日乘数法

$$ f\left(x_{1}, x_{2}, \cdots, x_{n}, \lambda\right)=\sum_{i=1}^{n}\left(b_ix_{i}\right)+\lambda\left(\sum_{i=1}^{n}\sum_{j=1}^{n} a_{ij} x_{i} x_{j}-t\right) \quad t \leqslant 1 $$

求偏导

$$ \left\{\begin{array}{l}b_{1}+2 \lambda\left(a_{11} x_{1}+a_{12} x_{2}+\cdots+a_{1n} x_{n}\right)=0 \\ b_{2}+2 \lambda\left(a_{21} x_{1}+a_{22} x_{2}+\cdots+a_{2 n} x_{n}\right)=0 \\ b_{n}+2 \lambda\left(a_{n 1} x_{1}+a_{n 2} x_{2}+\cdots++a_{n n} x_{n}\right)=0 \\ \sum_{i=1}^{n} \sum_{j=1}^{n}\left(a_{i j} x_{i} x_{j}\right)=t\end{array}\right. $$

可得

$$ \left\{\begin{array}{l}B+2 \lambda A x=0 \\ x^{\top} A x=t\end{array}\right. $$

$$ \begin{array}{l}\because B+2 \lambda A X=0 \Rightarrow 2 \lambda A X=-B \Rightarrow X=-\frac{A^{-1} B}{2 \lambda} \\ \because B^{T} x=-B^{T} \frac{A^{\top}}{2 \lambda} B=X^{T} B \Rightarrow x^{T}=-B \frac{T{A^{-1}}}{2 \lambda}\end{array} $$

代入运算可得

$$ \begin{aligned}-B \frac{T A^{-1}}{2 \lambda} \cdot A \cdot\left(-\frac{A^{-1} B}{2 \lambda}\right) &=t \\ \frac{B^{\top} A^{-1} B}{4 \lambda^{2}} &=t \end{aligned} $$

$$ \begin{aligned}\left(\sum_{i=1}^{n} b_{i} x_{i}\right)^{2}=\left(B^{\top} x\right)^{2} &=\left(-\frac{1}{2 x} \cdot B^{\top} \cdot A^{-1} \cdot B\right)^{2} \\ &=\frac{1}{4\lambda^{2}} \cdot\left(B^{\top} A^{-1} \cdot B\right)^{2} \\ &=t \cdot\left(B^{\top} \cdot A^{-1} \cdot B\right) \end{aligned} $$

$$ \begin{array}{l} \because t \leq 1 \\ \therefore t 取1时最大 \\ 最大值为 B^{T} \cdot A^{-1} \cdot B\end{array} $$

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const ll mod=998244353;
ll a[410][410];
ll b[410];
ll c[410];
int n,is[410],js[410];
void exgcd(int a,int b,int &x,int &y){
    if(!b)return x=1,y=0,void();
    exgcd(b,a%b,y,x);y-=x*(a/b);
}
int inv(int p){
    int x,y;exgcd(p,mod,x,y);
    return (x+mod)%mod;
}
void inv(){
    for(int k=1;k<=n;k++){
        for(int i=k;i<=n;i++) // 1
            for(int j=k;j<=n;j++)if(a[i][j]){
                is[k]=i,js[k]=j;break;
            }
        for(int i=1;i<=n;i++) // 2
            swap(a[k][i],a[is[k]][i]);
        for(int i=1;i<=n;i++)
            swap(a[i][k],a[i][js[k]]);
        if(!a[k][k]){
            puts("No Solution");
            exit(0);
        }
        a[k][k]=inv(a[k][k]); // 3
        for(int j=1;j<=n;j++)if(j!=k) // 4
            (a[k][j]*=a[k][k])%=mod;
        for(int i=1;i<=n;i++)if(i!=k) // 5
            for(int j=1;j<=n;j++)if(j!=k)
                (a[i][j]+=mod-a[i][k]*a[k][j]%mod)%=mod;
        for(int i=1;i<=n;i++)if(i!=k) // 就是这里不同
            a[i][k]=(mod-a[i][k]*a[k][k]%mod)%mod;
    }
    for(int k=n;k;k--){ // 6
        for(int i=1;i<=n;i++)
            swap(a[js[k]][i],a[k][i]);
        for(int i=1;i<=n;i++)
            swap(a[i][is[k]],a[i][k]);
    }
}
void work()
{
    while(~scanf("%d",&n)){
        memset(c,0,sizeof(c));
        memset(a,0,sizeof(a));
        memset(is,0,sizeof(is));
        memset(js,0,sizeof(js));
        memset(b,0,sizeof(b));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                scanf("%lld",&a[i][j]);
                a[i][j]=(a[i][j]%mod+mod)%mod;
            }
        }
        for(int i=1;i<=n;i++){
            scanf("%lld",&b[i]);
            b[i]=(b[i]%mod+mod)%mod;
        }
        inv();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                c[i]=(c[i]+a[j][i]*b[j]%mod)%mod;
            }
        }
        for(int i=1;i<=n;i++){
            c[i]=(c[i]*b[i])%mod;
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            ans=(ans+c[i])%mod;
        }
        printf("%lld\n",(ans+mod)%mod);
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

E.Counting Spanning Trees

zyj (赛后)

题意：

给定一张（n+m）个点的图，点为$ x_1,x_2,...,x_n $和$ y_1,y_2,...y_m $
节点$x_i$和$y_1,y_2,...,y_{a_i}$有边
给出n,m和$a_i$，问生成树数量

题解：

由论文可得，答案为：
$sort(deg(x_i))$
$\prod_{i < n} deg(x_i) * \prod_{i >= 2} deg(y_i)$

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
int n,m,mod;
ll a[maxn],c[maxn];
void solve(){
    rep(i,1,n) scanf("%lld",&a[i]);
    sort(a+1,a+1+n);
    rep(i,1,m+1) c[i]=0;
    rep(i,1,n) c[1]++,c[a[i]+1]--;
    rep(i,1,m+1) c[i]+=c[i-1];
    ll ans=1;
    rep(i,1,n-1) (ans*=a[i])%=mod;
    rep(i,2,m) (ans*=c[i])%=mod;
    printf("%lld\n",ans); 
}
int main(){
    while(~scanf("%d%d%d",&n,&m,&mod)) solve();    
}

F.Infinite String Comparision

wrf (00:28:15) +0

题意

给出两个无限循环串的循环节，比较两个串的大小。
两循环节长度均不超过 $10^5$

题解

做法

令两循环节分别为 $p,q$。模拟题意，比较两字符串直到第 $$|$p$|$+$|$q$|$-gcd($|$p$|$,$|$q$|$)$ 个字符为止。

证明

以下记号不区分串和串长

首先给出 Periodicity Lemma：

假设一个字符串 $S$ 有循环节（不需要是完整循环节） $p$ 和 $q$，并且满足 $p+q \leq S+\gcd(p,q)$，那么 $\gcd(p,q)$ 也是一个循环节。

证明见 张晴川知乎专栏
叉姐给出了一个数论证明

记由串 $k$ 无限循环得到的串为 $k^{\infty}$。记串 $S$ 到第 $i$ 位的前缀为 $pre_{S,i}$。令 $S_p=pre_{p^\infty,p+q-\gcd(p,q)}$，$S_q=pre_{q^\infty,p+q-\gcd(p,q)}$。
当 $S_p \not = S_q$ 时答案显然。下面证当 $S_p=S_q$ 时，必有 $p^\infty=q^\infty$：
令 $S=S_p=S_q$，由 Periodicity Lemma，$S$ 存在循环节 $\gcd(p,q)$，并且它显然是 $S$ 的一个完整循环节。
由此易得，$\gcd(p,q)$ 也是 $p,q,p^\infty,q^\infty$ 的完整循环节，并且已经验证了 $pre_{p^\infty,\gcd(p,q)}=pre_{q^\infty,\gcd(p,q)}$，所以 $p^\infty=q^\infty$。

时间复杂度

显然 $O(n)$

代码

#include <bits/stdc++.h>

using namespace std;

const int N=100020;

char c1[N],c2[N];

char solve()
{
    int n=strlen(c1);
    int m=strlen(c2);

    for(int i=0;i<2*max(n,m);i++) //懒惰，直接*2了
    {
        if(c1[i%n]<c2[i%m]) return '<';
        else if(c1[i%n]>c2[i%m]) return '>';
    }
    return '=';
}

int main(void)
{    
    while(~scanf("%s",c1))
    {
        scanf("%s",c2);
        printf("%c\n",solve());
    }
    
    return 0;
}

G.BaXianGuoHai, GeXianShenTong

lmj (赛后)

题意

给出一个三元组$(x_0,x_1,x_2)$，设定乘法运算为$(x_0,x_1,x_2)*(y_0,y_1,y_2)=(x_0*y_0+x_1*y_2+x_2*y_1,\\x_1*y_0+x_2*y_2+x_0*y_1,\\x_2*y_0+x_0*y_2+x_1*y_1)$
现在给定n个三元组，和q组n个的e，求$(x_{10},x_{11},x_{12})^{e_{11}}*(x_{20},x_{21},x_{12})^{e_{12}}*……*(x_{n0},x_{n1},x_{n2})^{e_{1n}}\\(x_{10},x_{11},x_{12})^{e_{21}}*(x_{20},x_{21},x_{12})^{e_{22}}*……*(x_{n0},x_{n1},x_{n2})^{e_{2n}}\\……\\(x_{10},x_{11},x_{12})^{e_{q1}}*(x_{20},x_{21},x_{12})^{e_{q2}}*……*(x_{n0},x_{n1},x_{n2})^{e_{qn}}$

题解

可以证明该三元组满足交换律和结合律，同时单位元为(1,0,0),满足快速幂，但是幂次可以达到$2^{300}$存不下，使用JAVA或者PYTHON大数也显然会T，然后选择将幂次对$p*p-1$进行取模（别问我为什么，我也不知道），然后就好做了。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=998244353;
ll e[25][N];
__int128 pre[405];
__int128 mo=1ll*p*p-1;
struct node
{
    ll x,y,z;
    node operator *(const node &a)const{
        return {(x*a.x+y*a.z+z*a.y)%p,(y*a.x+z*a.z+x*a.y)%p,(z*a.x+x*a.z+y*a.y)%p};
    }
}v[N];
node qpow(node a,ll n)
{
    node res;
    res.x=1;
    res.y=0;
    res.z=0;
    while(n){
        if(n&1)res=res*a;
        a=a*a;
        n>>=1;
    }
    return res;
}
void work()
{   
    pre[0]=1;
    for(int i=1;i<=400;i++){
        pre[i]=pre[i-1]*2%mo;
    }
    int n,m,q,z0,a,b;
    scanf("%d%d%d%d%d%d",&n,&m,&q,&z0,&a,&b);
    ll z=z0;
    for(int i=1;i<=n;i++){
        z=(z*a+b)%pre[32];
        v[i].x=z%p;
        z=(z*a+b)%pre[32];
        v[i].y=z%p;
        z=(z*a+b)%pre[32];
        v[i].z=z%p;
    }
    for(int k=1;k<=q;k++){
        for(int i=1;i<=n;i++){
            e[k][i]=0;
            for(int j=0;j<m;j++){
                z=(z*a+b)%pre[32];
                __int128 tmp=z;
                tmp=tmp*pre[32*j]%mo;
                e[k][i]=(e[k][i]+tmp)%mo;
            }
        }
    }
    for(int i=1;i<=q;i++){
        node res;
        res.x=1;
        res.y=0;
        res.z=0;
        for(int j=1;j<=n;j++){
            res=res*qpow(v[j],e[i][j]);
        }
        printf("%lld %lld %lld\n",res.x,res.y,res.z);
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){ 
        work();
    }
}

H.Minimum-cost Flow

lmj (01:35:09) +2

题意

给定网络的边和费用，每次询问给定所有边的容量u和要求的流量v，问最少所需要的费用，如果不能满流输出NaN

题解

由于所有边的容量相同，所以可以得到一个性质，$k*u$的流量在图中形成了k条1-n的路径，每多u的流量多形成一条路径（可能会导致原路径改变，但是只会在$k*u$到$k*u+1$时发生改变），这u的流量所用的花费是相同的，所以考虑u和v的倍数关系，预处理出u为1，v从1到100的花费，然后询问时直接求出对应的花费

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
struct ZKW_SPFA{
    #define maxn 201
    #define maxe 5005
    const ll INF=1e18;
    ll dis[maxn],vis[maxn],head[maxn],tot;
    ll n,Cost=0,Flow=0;
    struct Edge{ll v,cap,cost,nxt;}g[maxe<<1];
    void init(ll _n){tot=Cost=Flow=0;memset(head,-1,sizeof(head));n=_n;}
    void add(ll u,ll v,ll cap,ll cost){
        g[tot]={v,cap,cost,head[u]};head[u]=tot++;
    }
    void addedge(ll u,ll v,ll cap,ll cost){
        add(u,v,cap,cost);add(v,u,0,-cost);
    }
    bool spfa(ll S,ll T){
        for(ll i=0;i<=n;i++) vis[i]=0,dis[i]=INF;
        deque<ll>Q;Q.push_back(T);dis[T]=0;vis[T]=1;
        while(!Q.empty()){
            ll u=Q.front();Q.pop_front();
            for(ll i=head[u],v;~i;i=g[i].nxt)
                if(g[i^1].cap&&dis[v=g[i].v]>dis[u]+g[i^1].cost){
                    dis[v]=dis[u]+g[i^1].cost;
                    if(!vis[v]){
                        vis[v]=1;
                        if(!Q.empty()&&dis[v]<dis[Q.front()]) Q.push_front(v);
                        else Q.push_back(v);
                        //SLF???
                    }
                } vis[u]=0;
        } return dis[S]<INF;
    }
    ll dfs(ll S,ll T,ll flow){
        if(S==T){vis[T]=1;return flow;}
        ll used=0,res;vis[S]=1;
        for(ll i=head[S],v;~i;i=g[i].nxt)
            if(!vis[v=g[i].v]&&g[i].cap&&dis[S]-g[i].cost==dis[v]){
                res=dfs(v,T,min(g[i].cap,flow-used));
                if(res) Cost+=res*g[i].cost,g[i].cap-=res,g[i^1].cap+=res,used+=res;
                if(used==flow)break;
            }
        return used;
    }
    void solve(ll S,ll T){
        while(spfa(S,T)){
            vis[T]=1;
            while(vis[T]) memset(vis,0,sizeof vis),Flow+=dfs(S,T,INF);
        }
    }
    //?zkw.init(n),?zkw.addedge(),?zkw.solve(S,T)
    //????zkw.Flow??kw.Cost
}zkw;
ll ans[105];
ll x[105],y[105],z[105];
void work()
{
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        zkw.init(n+2);
        for(int i=1;i<=m;i++){
            scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
        }
        int limit=0;
        for(int i=1;i<=101;i++){
            zkw.init(n+2);
            zkw.addedge(n+1,1,i,0);
            for(int j=1;j<=m;j++){
                zkw.addedge(x[j],y[j],1,z[j]);
            }
            zkw.solve(n+1,n);
            ans[i]=zkw.Cost;
            if(zkw.Flow!=i){
                limit=i-1;break;
            }
        }
        int q;
        scanf("%d",&q);
        while(q--){
            ll u,v;
            scanf("%lld%lld",&u,&v);
            if(u*limit<v){
                printf("NaN\n");continue;
            }
            ll sum=ans[v/u]*u;
            ll tmp=v%u;
            sum+=(ans[v/u+1]-ans[v/u])*tmp;
            ll tmp1=__gcd(sum,v);
            sum/=tmp1;
            v/=tmp1;
            printf("%lld/%lld\n",sum,v);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

I.1 or 2

zyj (赛后)

题意

给出一张图和每个点的期望度数，要求你删掉一些边使得每个点的度数都等于期望度数，问是否可行。

题解

我们考虑匹配问题，每条边会关联两个点，那么肯定是点和边有关联；每个点需要减的度数是$deg(v_i) - d_i$，因此每个点拆成$deg(v_i) - d_i$个点，然后每条边拆成两个点$e_i$和$e_i '$，连完边之后这就是一个二分图，跑完图匹配之后必定还有某些边没有匹配上（因为每一个拆出来的点都会连$deg(v_i)$条边，最大的情况也不过是全部都匹配上）；
但是我们对于边拆出来的点也有限制，就是它只能被匹配0次或者2次（匹配一次说明一条边只关联了一个点，不符合现实）；
那么现在的问题就是如何判断边拆出来的点不会匹配1个点，那么我们把$e_i$和$e_i '$连一条边，这样的话如果有一条边没有被用到那么这条边会形成一个匹配，满足题意。

J.Easy Integration

lmj (00:11:02) +0

题意

求 $\int_0^1(x-x^2)^ndx$ 输出分数p/q为$p*q^{-1}$%998244353

题解

oeis的 并不会证 答案为 $(n!)^2/(2n+1)!$
补：欧拉积分 $\int_0^1x^n(1-x)^ndx=B(n+1,n+1)=\frac{n*n}{(2*n+1)(2*n)}*B(n,n)$，最后即可得到上式

本文由 Edwiv 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 1, 2020 at 11:47 am

← → ↓ ↑
2020杭电多校联合训练（第十场）
杭电多校多校训练
2020杭电多校联合训练（第九场）
杭电多校多校训练
2020杭电多校联合训练（第八场）
杭电多校多校训练
2020杭电多校联合训练（第七场）
杭电多校多校训练
2020牛客暑期多校训练营（第十场）
牛客多校多校训练
2020牛客暑期多校训练营（第九场）
牛客多校多校训练
Responses
  1. Edwiv

    太菜了，被学弟爆踩

    Reply