在线比赛选做

CF UR 51nod

---

Codeforces Round

可能500A以内的题目比较适合我

---

Codeforces Round #395 (Div. 1)

好激动啊，连击哥带我飞，Div. 2 Rank25，Rating飞涨278，抵消第一场fst两题的debuff。

763A[XJB hashing]

题意：一棵树上每个点有颜色，找一个点删除后，其他联通块同色
dfs一遍，把子树大小，子树颜色和、子树颜色积（替换成子树颜色平方和就少了一个log）、子树颜色xor和预处理出来。
接着枚举每个点，看它相邻子树是否符合要求。
防叉还把颜色重新random_shuffle了一波。写的时候觉得稳得一比，然后1A。

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 100010
#define maxm 200010
#define mod 1000000007
using namespace std;
#define G c=getchar()
typedef long long LL;
inline LL read()
{
    LL x=0,f=1;char G;
    while(c>57||c<48){if(c=='-')f=-1;G;}
    while(c>47&&c<58)x=x*10+c-48,G;
    return x*f;
}
int n;
#define AE(u,v) to[Si]=v,nxt[Si]=idx[u],idx[u]=Si++
int nxt[maxm],idx[maxn],to[maxm],cc[maxn],Si=1;
LL siz[maxn],xo[maxn],su[maxn],c[maxn],mu[maxn];
void dfs(int x,int f)
{
    siz[x]=1;xo[x]=c[x],su[x]=c[x];mu[x]=c[x];
    for(int i=idx[x];i;i=nxt[i])
        if(to[i]^f)
        {
            dfs(to[i],x);
            siz[x]+=siz[to[i]];
            xo[x]^=xo[to[i]];
            su[x]+=su[to[i]];
            (mu[x]*=mu[to[i]])%=mod;
        }
}
LL Pow(LL x,LL y,LL p=mod)
{
    LL r=1;
    for(;y;y>>=1,x=x*x%p)if(y&1)r=r*x%p;
    return r;
}
int main()
{
    srand(940012978);
    int n=read();
    for(int i=1;i<maxn;i++)
        cc[i]=i;
    random_shuffle(cc+1,cc+maxn);
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        AE(u,v),AE(v,u);
    }
    for(int i=1;i<=n;i++)
        c[i]=cc[read()];
    dfs(1,0);
    for(int i=1;i<=n;i++)
    {
        int flag=1;
        for(int j=idx[i];j;j=nxt[j])
        {
            int y=to[j];
            if(siz[i]>siz[y])//子树
            {
                LL F=c[y],Si=siz[y],Su=su[y],X=xo[y],M=mu[y];
                if(F*Si!=Su){flag=0;break;}
                if(F*(Si&1)!=X){flag=0;break;}
                if(Pow(F,Si)!=M){flag=0;break;}
            }
            else
            {
                LL F=c[y],Si=n-siz[i],Su=su[1]-su[i],X=xo[1]^xo[i],
                M=(mu[1]*Pow(mu[i],mod-2))%mod;
                if(F*Si!=Su){flag=0;break;}
                if(F*(Si&1)!=X){flag=0;break;}
                if(Pow(F,Si)!=M){flag=0;break;}
            }
        }
        if(flag)return printf("YES\n%d",i),0;
    }
    return puts("NO"),0;
    return 0;
}

763B[构造]

题意：对边长都是奇数的格点矩形4染色，使得相邻矩形颜色不同
边长是奇数。
只要按照左下角坐标奇偶性染色就好了。
原理：这样同色就不会相邻了

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 
using namespace std;
#define G c=getchar()
typedef long long LL;
inline LL read()
{
    LL x=0,f=1;char G;
    while(c>57||c<48){if(c=='-')f=-1;G;}
    while(c>47&&c<58)x=x*10+c-48,G;
    return x*f;
}
int n;
int main()
{
    puts("YES");
    n=read();
    for(int i=1;i<=n;i++)
    {
        int a=read(),b=read(),c=read(),d=read();
        printf("%d\n",1+(a&1)*2+(b&1));
    }
    return 0;
}

763C[数学]

题意：让你把数组重排，问能否得到模质数$m$意义下的等差数列
不慌，高二队长连击哥也没做出来
见题解，在下看不懂。

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 100010
using namespace std;
typedef long long LL;
#define G c=getchar()
inline LL read()
{
    LL x=0,f=1;char G;
    while(c>57||c<48){if(c=='-')f=-1;G;}
    while(c>47&&c<58)x=x*10+c-48,G;
    return x*f;
}
LL Pow(LL x,LL y,LL mod)
{
    LL r=1;
    for(;y;y>>=1,x=x*x%mod)if(y&1)r=r*x%mod;
    return r;
}
int n,m,a[maxn],b[maxn];
LL ans,ansd;
void solve(int a[],int n)
{
    LL g=a[1]-a[0],cnt=0;
    for(int i=0;i<n;i++)if(binary_search(a,a+n,(a[i]+g)%m))cnt++;
    LL k=n-cnt,d=Pow(k,m-2,m)*g%m;
    ans=-1;ansd=(m-d)%m;
    for(int i=0;i<n;i++)if(!binary_search(a,a+n,(a[i]+d)%m))
        if(ans==-1)ans=a[i];
        else{ans=-1;return;}
}
int main()
{
    m=read(),n=read();
    for(int i=0;i<n;i++)a[i]=read();
    if(n==1||n==m)return printf("%d 1\n",a[0]),0;
    sort(a,a+n);
    if(2*n<m)solve(a,n);
    else
    {
        int t=0;
        for(int i=0;i<m;i++)if(!binary_search(a,a+n,i))b[t++]=i;
        solve(b,t);
        if(ans!=-1)(ans+=ansd*t%m)%=m;
    }
    if(ans==-1)puts("-1");
    else printf("%lld %lld",ans,ansd);
    return 0;
}

763D[弃疗]

题意：找到一个根，使得不同构的子树最多

763E[LCT]

---

Educational Codeforces Round 17

762D[连通性DP]

题意：$3*n$的格子走一趟最大化收益
每个点考虑扭来扭去的6种情况和联通块情况，化简后每列应该只有15种情况（单点相连只能属于联通块1，两点扭回，三横有两种联通）。
然后就XJBDP辣！
不要问数组为啥离散。。

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 100010
using namespace std;
#define G c=getchar()
typedef long long LL;
inline LL read()
{
    LL x=0,f=1;char G;
    while(c>57||c<48){if(c=='-')f=-1;G;}
    while(c>47&&c<58)x=x*10+c-48,G;
    return x*f;
}
LL a[4][maxn],f[20],g[20];
LL max(LL a,LL b,LL c){return max(max(a,b),c);}
LL max(LL a,LL b,LL c,LL d){return max(max(a,b),max(c,d));}
LL max(LL a){return a;}
int main()
{
    int n=read();
    for(int j=1;j<=3;j++)
        for(int i=1;i<=n;i++)
            a[j][i]=read();
    memset(g,128,sizeof(g));
    g[1]=a[1][1],g[2]=g[1]+a[2][1],g[3]=g[11]=g[2]+a[3][1];
    for(int i=2;i<=n;i++)
    {
        memcpy(f,g,sizeof(f));
        g[1]=max(f[1],f[4],f[7],f[12])+a[1][i];
        g[2]=max(f[1],f[4],f[7],f[12])+a[1][i]+a[2][i];
        g[3]=max(f[1],f[4],f[7],f[12])+a[1][i]+a[2][i]+a[3][i];
        g[4]=max(f[2],f[5],f[8])+a[2][i]+a[1][i];
        g[5]=max(f[2],f[5],f[8])+a[2][i];
        g[6]=max(f[2],f[5],f[8])+a[2][i]+a[3][i];
        g[7]=max(f[3],f[6],f[9],f[13])+a[1][i]+a[2][i]+a[3][i];
        g[8]=max(f[3],f[6],f[9],f[13])+a[2][i]+a[3][i];
        g[9]=max(f[3],f[6],f[9],f[13])+a[3][i];
        g[11]=max(f[1],f[4],f[7],f[12])+a[1][i]+a[2][i]+a[3][i];
        g[12]=max(f[14],f[17])+a[1][i]+a[2][i]+a[3][i];
        g[13]=max(f[11],f[16])+a[1][i]+a[2][i]+a[3][i];
        g[14]=max(f[3],f[6],f[9],f[13])+a[1][i]+a[2][i]+a[3][i];
        g[16]=max(f[11])+a[1][i]+a[2][i]+a[3][i];
        g[17]=max(f[14])+a[1][i]+a[2][i]+a[3][i];
    }
    printf("%lld",max(g[3],g[6],g[9],g[13]));
    return 0;
}

8VC Venture Cup 2017 - Final Round

756C[数据结构]

题意：空的操作序列，每次把一个不存在的操作变成push或pop，求每次修改后按序操作完的栈顶
$10^5$有点想分块啊
然后就写了一棵线段树。居然TLE on test 21了QAQ
原因是标记合并是On的不T才怪
然后写了一棵用rope合并的线段树，居然TLE on test 17了QAQ
原因是常数太大，卡成$n^2$

学习了一下技巧，发现根本不用记录栈内情况，其实只需要还原到栈顶的位置就好了。
线段树内只需要记录和与左起最大连续子段和

查询XJB查

会了就不写了QAQ

756E[DP状态优化]

题意：第$k$种面值的硬币的面值是第$k-1$种面值硬币的$a_i$倍，有各种相同硬币$b_i$个，问支付$m$个第$1$种面值的硬币的方案数
范围：$n\leq 10,m\leq10^{10000}$

这题十分简单，就是普及组难度，只要用$dp[i][j]$表示用前$i$种金币支付$j$元的方案数就没了。
然后大家一定会出来把我批判一番【手动滑稽】

Scarlet：怎么优化啊，根本不会怎么办啊。
这题TM能$dp[i]$？

看了题解：$dp[i]$表示用前$i$种金币支付$x=kD+(m\%D),(k\in Z,k\leq \sum^i_{j=1}b_j)$，其中D是第$i$种面值硬币的面值。
日了苟……以天下之大，下而从六国破亡之故事！

然后枚举$k$转移，Tutorial证明了其复杂度不超过$2k\sum b_i$，前缀和维护一下就没事了。
（其实我只是没想到枚举$k$，淦TMD）

似乎有点像进制转换...？

这个前缀和优化，似乎又有点似曾相识，有点像敦敦敦的51nod某道背包。

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 300010
#define mod 1000000007
using namespace std;
#define G c=getchar()
typedef long long LL;
inline LL read()
{
    LL x=0,f=1;char G;
    while(c>57||c<48){if(c=='-')f=-1;G;}
    while(c>47&&c<58)x=x*10+c-48,G;
    return x*f;
}
char s[10010];
LL w[maxn];
int m,a[maxn],b[maxn],n;
vector<int>f[maxn];
int calc(int a)
{
    if(!m||a==1)return 0;
    int t;
    for(int i=m-1;i>=0;i--)
    {
        t=w[i]%a;w[i]/=a;
        if(i)w[i-1]+=t*1000000000ll;
    }
    while(m&&!w[m-1]) m--;
    return t;
}
int main()
{
    n=read();
    for(int i=2;i<=n;i++)a[i]=read();a[1]=1;a[n+1]=2000000000;
    for(int i=1;i<=n;i++)b[i]=read();
    scanf("%s",s);
    for(int i=strlen(s)-1;i>=0;i-=9,m++)
        for(int j=max(0,i-8);j<=i;w[m]=w[m]*10+s[j++]-'0');
    f[1].push_back(1);
    for(int i=1;i<=n;i++)
        for(int s=f[i].size(),delta=calc(a[i+1]),S=0,j=0;j<=s+b[i];j++)
        {
            if(j<s)(S+=f[i][j])%=mod;
            if(j>b[i])(S-=f[i][j-b[i]-1])%=mod;
            if(j%a[i+1]==delta)f[i+1].push_back(S);
        }
    printf("%d",m?0:f[n+1].size()==0?0:(f[n+1][0]+mod)%mod);
    return 0;
}

---

8VC Venture Cup 2017 - Elimination Round

题目很短适合我这种弱智选手做。
可惜了没打。

---

755A[构造]

题意：给一个$n$，求一个$m$使得$nm+1$为合数

限制：$1\leq n,m\leq 1000$
一个比较显然的就是$n(n-2)+1=(n-1)^2$，那么$n=1,2$时特判就行了。

---

755B[模拟]

题意：给出两人单词表，不能说不会的和说过的，看谁赢

优先说对方会的单词，模拟即可

---

755C[搞笑]

题意：一座森林，给定每个点的最远点（的最小编号），求有几棵树

还以为要还原这棵树，TM吓死我了。
并查集数一数就好了

---

755D[螺杆]

题意：凸$n$边形，没有$3$对角线共点，将$x->x+k$连一圈以后求每次的划分块数

越过$1$点线$+1$，下一个再立刻$+2$
为什么正确呢，抱歉我是画图的我也不知道

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 1000010
using namespace std;
typedef long long LL;
#define G c=getchar()
inline LL read()
{
    LL x=0,f=1;char G;
    while(c>57||c<48){if(c=='-')f=-1;G;}
    while(c>47&&c<58)x=x*10+c-48,G;
    return x*f;
}
int main()
{
    LL n=read(),k=read(),ans=1,dt=1;
    k=min(k,n-k);LL x=k;
    for(;x;)
    {
        ans+=dt;
        printf("%lld ",ans);
        if(x<k)dt++;
        x+=k;if(x>=n)x-=n,dt++;
    }
    printf("%lld",n*k+1);
    return 0;
}

---

755E[构造]

题意：对完全图的边双染色，使得两种颜色的子图的最小值为$k$

假设大家知道了$2\leq k\leq 3$
那么$k=2$就依次连一条链
$k=3$就$1-2，2-(3..n-1)，(3..n-1)-n，(3..n-1)$内完全图，易证正确性。

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 1010
using namespace std;
typedef long long LL;
#define G c=getchar()
inline int read()
{
    int x=0,f=1;char G;
    while(c>57||c<48){if(c=='-')f=-1;G;}
    while(c>47&&c<58)x=x*10+c-48,G;
    return x*f;
}
int n,k;
int main()
{
    n=read(),k=read();
    if(k==1||k>3)return puts("-1"),0;
    if(k==2)
    {
        if(n<=4)return puts("-1"),0;
        printf("%d\n",n-1);
        for(int i=2;i<=n;i++)
            printf("%d %d\n",i-1,i);
    }
    else
    {
        if(n<=3)return puts("-1"),0;
        printf("%d\n",1+n-3+n-3+(n-3)*(n-4)/2);
        puts("1 2");
        for(int i=3;i<=n-1;i++)
            printf("%d %d\n",2,i),
            printf("%d %d\n",i,n);
        for(int i=3;i<=n-1;i++)
            for(int j=i+1;j<=n-1;j++)
                printf("%d %d\n",i,j);
    }
    return 0;
}

---

755F[模拟]

题意：一个没有不动点的置换表示$x$将会给$f(x)$送礼，一个人能收到礼物当且仅当他自己带了礼物并且给它礼物的人也带了礼物，若有$k$人忘带礼物，问至少、至多有多少人拿不到礼物

考虑一人不带礼物可能影响2、1、0人，那么最多应该尽量把不带礼物的人隔着放，奇偶环分开来考虑。最少应该尽量把人放在一起（同一个圈内）。
（大概是正确的）

---

755G【多项式+DP+FFT优化】

题意：$n$个数选出若干元素划分成$m$个集合，满足一个集合内只能有一个数或者两个相邻的数，求$1\leq m\leq k$的方案数
不会啊，放个$nk$就跑

for(int i=0;i<=n;i++)
    f[i][0]=1;
for(int i=1;i<=n;i++)
    for(int j=1;j<=k;j++)
        f[i][j]=f[i-1][j]+f[i-1][j-1]+f[i-2][j-1];

---

CR#391(combined)【5/7】

这套题ABCDE都是数学题，FG画风突变成数据结构大战。结果数学题还行，FG数据结构我都不会QAQ。

简单题：CD
好题：E（数论套DP）
难题：FG

757C[哈希+置换]

题意：每行每个数字在置换前后个数不变，问置换个数

什么JB题面。
只有出现情况完全相同的点才放在置换的同一个循环里的
vector记录一下每个数字出现的行，然后sort一下，相同的可以置换处理。
原来标签上的hashing是这个意思啊

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 1234567
#define mod 1000000007
using namespace std;
typedef long long LL;
#define G c=getchar()
inline int read()
{
    int x=0,f=1;char G;
    while(c>57||c<48){if(c=='-')f=-1;G;}
    while(c>47&&c<58)x=x*10+c-48,G;
    return x*f;
}
vector<int> a[maxn];
int main()
{
    int n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        int x=read();
        for(;x--;)
        {
            int k=read();
            a[k].push_back(i);
        }
    }
    sort(a+1,a+1+m);
    int ans=1,t=1;
    for(int i=2;i<=m;i++)
        if(a[i]==a[i-1])
            t++,ans=1ll*ans*t%mod;
        else t=1;
    printf("%d",ans);
    return 0;
}

---

757D[DP]

题意：一个01串，求切任意刀只形成了1-m的数字（舍去前后两段，不必一一对应）的方案数
规模：$n\leq 75$

感觉自己切SB题速度挺慢的。怪不得打不动CF..
计算一下最多有20种不同的数，状压DP很舒服

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 78
#define maxm 1<<20
#define mod 1000000007
using namespace std;
int n,bin[22];
char s[maxn];
int f[maxn][maxm],g[maxn][maxn];
inline void add(int&x,const int&y)
{
    x+=y;
    x>=mod?x-=mod:0;
}
int main()
{
    bin[1]=1;
    for(int i=2;i<=21;i++)bin[i]=bin[i-1]<<1;
    int n;scanf("%d\n%s",&n,s+1);
    memset(g,63,sizeof(g));
    for(int i=1;i<=n;i++)
    {
        int S=0;
        for(int j=i;j<=n&&S<=20;j++)
        {
            S=(S<<1)+(s[j]=='1');
            g[i][j]=S;
        }
    }
    for(int i=0;i<=n;i++)f[i][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
            if(g[j+1][i]<=20&&g[j+1][i]>0)
                for(int S=0;S<(maxm);S++)
                    if(f[j][S])add(f[i][S|bin[g[j+1][i]]],f[j][S]);
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=20;j++)
            add(ans,f[i][(1<<j)-1]);
    printf("%d",ans);
    return 0;
}

---

757E[数论+DP]

题意：

$$f_0(n)=\sum_{pq=n}[gcd(p,q)=1]\\f_{r+1}(n)=\sum_{pq=n}\frac{f_r(p)+f_r(q)}{2}$$ 求$f_r(n)$，多组询问。
规模：$T,n,r\leq10^6$

观察了一下，记$k(n)$表示整除$n$不同质因数的个数。
则$f_0(n)=2^{k(n)},f_{r+1}(n)=\sum_{d|n}f_r(d)$
轻易地发现$f_i$全是积性函数，分解一下质因数，$n=\prod p_i^{e_i}$然后我就不会了QAQ
看了TJ发现自己SB了，正因为是积性函数，$f_r(n)=\prod f_r(p_i^{e_i})$。
显然$f_r(p_i^{e_i})$的函数值只和$r$和$e_i$有关了，准确地说是一个这样的东西：$f_r(p_i^{e_i})=\sum_{a_r=0}^{e_i}\sum_{a_{r-1}=0}^{a_r}\cdots\sum_{a_1=0}^{a_2}2^{a_1+1}$，$e_i$不超过20，这个只要DP递推一下就好了吧。

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 1000010
#define mod 1000000007
using namespace std;
typedef long long LL;
#define G c=getchar()
inline int read()
{
    int x=0,f=1;char G;
    while(c>57||c<48){if(c=='-')f=-1;G;}
    while(c>47&&c<58)x=x*10+c-48,G;
    return x*f;
}
int dp[maxn][21];
inline void add(int&x,const int&y)
{
    x+=y;
    x>=mod?x-=mod:0;
}
int vis[maxn],pri[maxn],low[maxn],tot;
void getp(int N)
{
    for(int i=2;i<N;i++)
    {
        if(!vis[i])pri[tot++]=i,low[i]=i;
        for(int j=0;j<tot&&pri[j]*i<N;j++)
        {
            vis[pri[j]*i]=1;
            low[pri[j]*i]=pri[j];
            if(i%pri[j]==0)break;
        }
    }
}
int main()
{
    getp(maxn);
    for(int i=0;i<maxn;i++)
        dp[i][0]=1;
    for(int i=1;i<=20;i++)
        dp[0][i]=2;
    for(int i=1;i<maxn;i++)
        for(int j=1;j<=20;j++)
            add(dp[i][j],dp[i][j-1]+dp[i-1][j]);
    int T=read();
    for(;T--;)
    {
        int r=read(),n=read();LL ans=1;
        for(;n^1;)
        {
            int cnt=0,p=low[n];
            while(low[n]==p)n/=p,cnt++;
            ans=ans*dp[r][cnt]%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

出题人的函数表示技巧好酷炫啊，出题学到了。

---

757F【支配树】

题意：删除图上一个节点使得最短路改变的点数最多
规模：$n\leq 2*10^5$

支配树，也不知道什么时候学...

757G【Persistent Centroid Tree】

题意：给定一棵树和一个排列$a_1,a_2\dots a_n$，资辞两个操作：
1 l r v 询问$\sum_{i=l}^{r}dist(a_i,v)$
2 x 交换$a_x$和$a_{x+1}$
规模：$n,q\leq 2*10^5$

什么JB数据结构？？？

CR#390(Div. 2)(5/5)

TG组模拟赛+

简单题：D（高超的差分、扫描技巧）
好题：E（二进制位优化匹配）

---

754C[构造+DP]

题意：构造一个聊天记录，使得相邻消息不属于同一人而且自己的消息内不会提到自己的名字
没敢写，dp方程很好想，f[i][j]表示滋补资辞第j个人说第i句话，按照题意转移就行了。

---

754D[二分答案+高超扫描]

题意：选择$k$个区间使得区间交最大
规模：$k,n\leq3*10^5$

二分区间长度，然后...不会了
XJB思考了$20$分钟，发现就是个二维数点问题。
假装精神上用主席树已经AC了。
然后思考了一下$O(n)$check姿势，发现只要假装区间后半截被抛掉了一定长度，再看有没有$k$元交就好了。
我还是太菜QAQ

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 300010
#define INF 2000000010
using namespace std;
typedef long long LL;
#define G c=getchar()
inline LL read()
{
    LL x=0,f=1;char G;
    while(c>57||c<48){if(c=='-')f=-1;G;}
    while(c>47&&c<58)x=x*10+c-48,G;
    return x*f;
}
LL a[maxn],b[maxn],n,k,pos;
struct poi
{
    LL x,c;
}Q[maxn*2];
inline bool cmp(const poi &a,const poi &b){return a.x==b.x?a.c>b.c:a.x<b.x;}
bool check(LL x,bool w=0)
{
    if(x==0)return n;
    int top=0;
    for(int i=1;i<=n;i++)
        if(b[i]-x+1>=a[i])
            Q[top++]=(poi){a[i],1},
            Q[top++]=(poi){b[i]-x+1,-1};
    sort(Q,Q+top,cmp);
    LL cnt=0,mx=0,l=INF;
    for(int i=0;i<top;i++)
    {
        cnt+=Q[i].c;
        if(cnt>=k)return pos=Q[i].x+x-1,1;
    }
    return 0;
}
int main()
{
    n=read(),k=read();
    for(int i=1;i<=n;i++)
        a[i]=read(),b[i]=read();
    LL ans=0,L=0,R=2000000001;
    for(;L<=R;)
    {
        LL mid=L+R>>1;
        if(check(mid))ans=mid,L=mid+1;
        else R=mid-1;
    }
    printf("%lld\n",ans);
    if(ans==0)
    {
        for(int i=1;i<=k;i++)printf("%d ",i);
        return 0;
    }
    check(ans);
    for(int i=1,j=1;i<=n&&j<=k;i++)
        if(a[i]<=pos-ans+1&&pos<=b[i])printf("%d ",i),j++;
    return 0;
}

---

754E[bitset加速]

题意：矩阵内匹配（通配）矩阵

学习了毛子的高超（常数）技巧。
先确定照每个字符建$26$个bitset
然后枚举第二个矩阵的元素，去匹配前一个矩阵。
复杂度：$O(\frac{n\cdot m\cdot r\cdot c}{32})$
果然技术高超

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 404
using namespace std;
bitset<maxn>b[26][maxn];
bitset<maxn>ans[maxn];
char s[maxn];
bitset<maxn>Shift(const bitset<maxn>&b,int len,int shift){return (b>>shift)|(b<<(len-shift));}
int main()
{
    int n,m,r,c;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        scanf("%s",s);
        for(int j=0;j<m;j++)
            b[s[j]-'a'][i][j]=1;
    }
    scanf("%d%d",&r,&c);
    for(int i=0;i<n;i++)
        ans[i]=~ans[i];
    for(int i=0;i<r;i++)
    {
        scanf("%s",s);
        for(int j=0;j<c;j++)
        {
            if(s[j]=='?')continue;
            int c=s[j]-'a',X=(2333*n-i)%n,Y=(2333*m+j)%m;
            for(int x=0;x<n;x++)
            {
                int nx=x+X;
                if(nx>=n)nx-=n;
                ans[nx]&=Shift(b[c][x],m,Y);
            }
        }
    }
    for(int i=0;i<n;i++,puts(""))
        for(int j=0;j<m;j++)
            putchar(ans[i][j]?'1':'0');
    return 0;
}

Good Bye 2016(6/6)

简单题：CD
好题：E（矩阵优化DP）G（特技枚举+数位DP）H（对偶图上特技并查集暴力在线维护连通性）

---

750C[模拟不等式]

记录一位小哥连续几次CF记录（div1/2和Rating增长），求当前最大Rating

口胡：假设原Rating为$x$，那么可以得到若干条和$x$和div线的不等式，解一下就好了

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 200010
#define INF 233333333
using namespace std;
typedef long long LL;
#define G c=getchar()
inline int read()
{
    int x=0,f=1;char G;
    while(c>57||c<48){if(c=='-')f=-1;G;}
    while(c>47&&c<58)x=x*10+c-48,G;
    return x*f;
}
int L,R;
int main()
{
    int n=read(),s=0,L=-INF,R=INF;
    for(int i=1;i<=n;i++)
    {
        int ds=read(),d=read();
        if(d==1)R=min(R,s);//x+s>=1900
        else L=max(L,s);//x+s<=1899
        s+=ds;
    }
    if(1900-R>1899-L)puts("Impossible");
    else if(L==-INF)puts("Infinity");
    else printf("%d",1899-L+s);
    return 0;
}

750D[模拟]

题意：烟花在第$i$次飞出去$t_i$格，并转45°，求含有烟花的格子数

模拟吧，不想写，精神AC

750E【矩阵乘法优化DP】

题意：在一个数字串中去掉最少的数字使得存在子序列2017，不存在子序列2016，多组询问
规模：$n,q\leq2*10^5$

先要会做一组询问..
设计状态：$dp[i][0..4]$表示使前$i$位满足题意，删除最少的个数。其中$[0]$表示前$i$位与"$2016$"和"$2017$"无关，$[1]$表示有前缀"$2$"，$[2]$表示有前缀"$20$"，$[3]$表示有前缀"$201$"，$[4]$表示有前缀"$2017$"（实质上是一个AC自动机或者说是个KMP里的next）

那么就能转移了：一个$2$可以让$[0]$无代价转移到$[1]$，或是删除自身以$1$的代价转移回$[0]$。$0,1,7$同理。而单个$6$不仅可以让$[3]$以$1$的代价转移到$[3]$，还能让$[4]$以$1$的代价转移到$[4]$（比如情况$20176$，$6$不能出现在$2017$的后面，要删掉），这样就可以愉快地构造矩阵。

现在是多组询问了，可以知道这个矩阵乘法是具有结合律的，线段树XJB上就做完了。

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 200010
#define INF 1000000000
using namespace std;
#define G c=getchar()
inline int read()
{
    int x=0,f=1;char G;
    while(c>57||c<48){if(c=='-')f=-1;G;}
    while(c>47&&c<58)x=x*10+c-48,G;
    return x*f;
}
struct poi
{
    int a[5][5];
    void init()
    {
        for(int i=0;i<=4;i++)for(int j=0;j<=4;j++)a[i][j]=INF;
        for(int i=0;i<=4;i++)a[i][i]=0;
    }
    void init(int x)
    {
        init();
        if(x==2)a[0][0]=1,a[0][1]=0;
        else if(x==0)a[1][1]=1,a[1][2]=0;
        else if(x==1)a[2][2]=1,a[2][3]=0;
        else if(x==6)a[3][3]=1,a[4][4]=1;
        else if(x==7)a[3][4]=0;
    }
}T[maxn],ans;
poi operator +(poi x,poi y)
{
    poi c;
    for(int i=0;i<=4;i++)
        for(int j=0;j<=4;j++)
        {
            int &w=c.a[i][j];w=INF;
            for(int k=0;k<=4;k++)w=min(w,x.a[i][k]+y.a[k][j]);
        }
    return c;
}
char s[maxn];
void build(int x,int l,int r)
{
    if(l==r){T[x].init(s[l]-'0');return;}
    int mid=l+r>>1;
    build(x<<1,l,mid),build(x<<1|1,mid+1,r);
    T[x]=T[x<<1]+T[x<<1|1];
}
void qry(int x,int l,int r,int L,int R)
{
    if(L<=l&&r<=R){ans=ans+T[x];return;}
    int mid=l+r>>1;
    if(L<=mid)qry(x<<1,l,mid,L,R);
    if(mid<R)qry(x<<1|1,mid+1,r,L,R);
}
int main()
{
    int n=read(),m=read();
    scanf("%s",s+1);build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        ans.init();
        int l=read(),r=read();
        qry(1,1,n,l,r);
        printf("%d\n",ans.a[0][4]>n?-1:ans.a[0][4]);
    }
    return 0;
}

---

750F【交互】

题意：7层的满二叉树，每次可以获取一个点的邻居，试在16步内确定树根

不会做，题解强无敌。
思路：
当你找到两个叶子的时候，中间的点就是他们的LCA，然后你就获得了一个大致方向。
任选一点的两个方向遍历，可以保证找到2个叶子或者根。
假设$h=7$，并且假设你是非洲人，在遍历时只能找到叶子。
若叶子的LCA在第$2$层，那么你一定询问了$11$个点，可以确定LCA的另一个邻居是根，询问数$11$。
若叶子的LCA在第$3$层，那么你一定询问了$9$个点，你只要在LCA的父亲上BFS$1$层，询问数$9+2=11$
若叶子的LCA在第$4$层，那么你一定询问了$7$个点，你只要在LCA的父亲上BFS$2$层，询问数$7+6=13$
若叶子的LCA在第$5$层，那么你一定询问了$5$个点，你只要在LCA的父亲上DFS到另一个叶子，你就发现你以多$2$次询问的代价转移到了上面三种情况，代价不超过$15$
若叶子的LCA在第$6$层，那么你一定询问了$3$个点，你只要在LCA的父亲上DFS到另一个叶子，你就发现你以多1次询问的代价转移到了上面四种情况，询问次数不超过$16$
若你是非皇，那么你一定找到了$1$个叶子，你只要再找$1$个叶子就能以$0$代价转移到上面$5$种情况了
不想写

750G【特技DP】

题意：无限的满二叉树，求标号之和为$s$的链的条数
规模：$s\leq10^{15}$

一开始不会做，以为是枚举LCA，看了题解是枚举LCA的两侧的的长度，再计算LCA，稳得不行。

画图后发现可以通过一些平移（减法），问题就转化了以$1$为LCA的情况。

再考虑$1$到$a$的路径标号和为$2a-popcount(a)$。
问题变成计算$2a+2b-popcount(a)-popcount(b)=s$的解的组数，枚举$popcount(a)+popcount(b)$，数位DP即可。
$dp[i][j][0/1]$表示前i位用掉了$j$个$1$，此处是否进位。

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 
using namespace std;
typedef long long LL;
#define G c=getchar()
inline LL read()
{
    LL x=0,f=1;char G;
    while(c>57||c<48){if(c=='-')f=-1;G;}
    while(c>47&&c<58)x=x*10+c-48,G;
    return x*f;
}
LL s,ans,f[140][2],g[140][2];
LL solve(int o,int l0,int l1,LL tot)
{
    memset(f,0,sizeof(f));
    f[0][0]=1;
    for(int i=0;1LL<<i<=tot;i++)
    {
        memcpy(g,f,sizeof(f));
        memset(f,0,sizeof(f));
        for(int d0=0;d0<=1;d0++)if(d0==0||i<l0)
            for(int d1=0;d1<=1;d1++)if(d1==0||i<l1)
                for(int jw=0;jw<=1;jw++)
                {
                    int dig=d0+d1+jw;
                    if(dig%2!=((tot>>i)&1))continue;
                    for(int k=0;k+d0+d1<=o;k++)
                        f[k+d0+d1][dig/2]+=g[k][jw];
                }
    }
    return f[o][0];
}
int main()
{
    s=read();
    for(int a=0;a<=58;a++)
        for(int b=0;b<=58;b++)
        {
            LL mul=(1LL<<(a+1))-1+(1LL<<(b+1))-1-1;
            LL lca=s/mul;
            if(lca==0)continue;
            LL rem=s-lca*mul-(1LL<<b)+1;
            for(int o=0;o<=a+b;o++)
            {
                LL tot=rem+o;
                if(tot<0||(tot&1))continue;
                tot/=2;
                ans+=solve(o,max(a-1,0),max(b-1,0),tot);
            }
        }
    printf("%lld",ans);
    return 0;
}

证明一下为什么能已知两臂长计算lca。
其实只要证明对于确定两臂长，每个lca能导出的“值域”不相交就行了。
证明一样很简单，就是两个lca同侧的对应深度点有严格的大小关系，全部加起来以后不可能有交。

好神啊，他们是怎么想到枚举$2$个长度就能定lca的啊。

750H【对偶图+暴力+并查集】

给一张网格，每次临时删除网格上不超过$10$个点，询问左上到右下是否在同一个点双联通分量内，强制在线
规模：$h,w\leq1000,q\leq 10000$

官方暴力啊！
我们定义两个联通块“准联通”，当存在两个点分别属于两个联通块并且切比雪夫距离不超过$2$

把图对偶以后变成询问左下角S与左上角T所在联通块是否“准联通”

于是我们先在原图中的准联通块暴力连边，加入新点（雪块）后用并查集暴力维护新联通块的改变。

那么分成两种情况：

1.雪块沟通了几个联通块并且导致存在两个原图的准联通块在新图内分别和S、T联通

2.雪块造成了新的准联通块

按照两种情况分别维护就好了，可以证明每次关键点数在$9k（k\leq 10)$）右。询问时复杂度估计是$O(qk^2)$，且常数不超过$100$。

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 1010
using namespace std;
typedef long long LL;
#define G c=getchar()
#define pa pair<int,int>
#define fi first
#define se second
#define SS cc[3][0]
#define TT cc[0][3]
inline int read()
{
    int x=0,f=1;char G;
    while(c>57||c<48){if(c=='-')f=-1;G;}
    while(c>47&&c<58)x=x*10+c-48,G;
    return x*f;
}
int h,w;
char s[maxn];
bool a[maxn][maxn];
int cnt,cc[maxn][maxn];//dfs后的联通块着色
set<pa>E;//“准”联通块内连边
bool in(int r,int c){return 0<=r&&r<=h+1&&0<=c&&c<=w+1;}
namespace poi//（暴力并）查集，记录联通块之间是否相邻
{
    int g[maxn*maxn];//每个联通块所在关键点
    vector<int> inv[maxn*maxn];//关键点之间的边
    set<int>aff;//关键的联通块编号
    /*
    这里关键点包括：
    左下角起点SS所在联通块、右上角TT所在联通块
    每个临时雪块周围5*5的点所在的联通块
    */
    void init(int i)
    {
        if(aff.count(i))return;
        aff.insert(i);
        g[i]=i;
        inv[i].push_back(i);
    }
    void uni(int a,int b)//关键点暴力合并
    {
        init(a),init(b);
        a=g[a],b=g[b];
        if(a==b)return;
        for(int x:inv[a])
        {
            g[x]=b;
            inv[b].push_back(x);
        }
        inv[a].clear();
    }
    bool QC(int a,int b)//是否在同一个关键点内
    {
        init(a),init(b);
        return g[a]==g[b];
    }
    void clear()
    {
        for(int i:aff)
        {
            g[i]=0;
            inv[i].clear();
        }
        aff.clear();
    }
    bool QP()//是否存在某两个关键联通块分别与起终点处在相同关键点内并且“准”联通
    {
        init(SS),init(TT);
        for(int x:aff)if(QC(SS,x))
            for(int y:aff)if(QC(TT,y))
                if(E.count({x,y}))return 1;
        return 0;
    }
}
bool duality(vector<pa>snow)
{
    poi::clear();
    for(pa p:snow)
    {
        int r=p.fi,c=p.se;
        cc[r][c]=++cnt;
        for(int R=r-1;R<=r+1;R++)
            for(int C=c-1;C<=c+1;C++)
                if(cc[R][C])
                    poi::uni(cc[r][c],cc[R][C]);//雪块可能沟通不同的联通块，加入同一关键点
    }
    if(poi::QP())return 1;
    for(pa p:snow)//是否有雪块造成了新的“准”联通
    {
        int r=p.fi,c=p.se;
        for(int R=r-2;R<=r+2;R++)
            for(int C=c-2;C<=c+2;C++)
                if(in(R,C)&&cc[R][C])
                {
                    if(poi::QC(cc[r][c],SS)&&poi::QC(cc[R][C],TT))return 1;
                    if(poi::QC(cc[r][c],TT)&&poi::QC(cc[R][C],SS))return 1;
                }
    }
    return 0;                   
}
void dfs(int r,int c)//联通块着色
{
    for(int R=r-1;R<=r+1;R++)
        for(int C=c-1;C<=c+1;C++)
            if(in(R,C)&&a[R][C]&&!cc[R][C])
                cc[R][C]=cc[r][c],dfs(R,C);
}
int main()
{
    int q;
    h=read(),w=read(),q=read();
    for(int r=0;r<h;r++)
    {
        scanf("%s",s);
        for(int c=0;c<w;c++)
            a[r+1][c+1]=(s[c]=='#');
    }
    for(int r=3;r<=h+1;r++)a[r][0]=1;
    for(int c=1;c<=w-2;c++)a[h+1][c]=1;
    for(int c=3;c<=w+1;c++)a[0][c]=1;
    for(int r=1;r<=h-2;r++)a[r][w+1]=1;
    for(int r=0;r<=h+1;r++)
        for(int c=0;c<=w+1;c++)
            if(a[r][c]&&!cc[r][c])
                cc[r][c]=++cnt,dfs(r,c);
    for(int r=0;r<=h+1;r++)
        for(int c=0;c<=w+1;c++)
            if(cc[r][c])
                for(int R=r-2;R<=r+2;R++)
                    for(int C=c-2;C<=c+2;C++)
                        if(in(R,C)&&cc[R][C]&&cc[R][C]!=cc[r][c])E.insert({cc[r][c],cc[R][C]});//“准”联通块内连边
    for(;q--;)
    {
        int k=read();
        vector<pa>snow(k);
        for(pa &p:snow)
            p.fi=read(),p.se=read();
        puts(duality(snow)?"NO":"YES");
        fflush(stdout);
        for(pa &p:snow)
            cc[p.fi][p.se]=0;
        cnt-=snow.size();
    }
    return 0;
}

---

CR#388 (Div. 2)

---

749C[贪心+模拟]

题意：两派基佬按顺序围成一圈，依次指定一人退出游戏，当圈内只有某派人时胜出。问哪一派有必胜技巧

贪心模拟每派删除下一个有权讲话的敌人。

---

749D[STL]

题意：拍卖会，$a_i$的人拍出了$b_i$的价格，多次询问如果某$k$个人不存在，这件物品会以多少价格拍给了谁

先把每个人竞价存入各自vector，再把每个人的最大竞价放入一个有序数组，可以在最多$O(k)$的时间(别排序了，计数一下多轻松)内找到两个竞价最高的人，在竞价最高的人的数组中二分找第二大的人的最高竞价。
不是很想写代码，而且实现应该挺简单的。

---

749E[期望+树状数组]

题意：给出一个$n$的排列，任意取一个区间，将其中元素随机打乱，问整个序列的逆序对的期望

---

748E【弃坑】

看不懂

CR#387 (Div. 2)

747F[DP]

题意：问每种数字出现的次数不超过$t$的$16$进制数，第$k$小的是哪个

这个Dp有点DarkFantasy啊。。

CR#386 (Div. 2)

746F[双指针+数据结构]

题意：连续若干首歌，可以将$w$首时长换成$\lceil\frac{t_i}{2}\rceil$，加起来不超过$k$，求最大愉悦度

双指针，当时长超过或不足k时向后挪动。
只要维护集合内前$w$大的数字之和，Treap is enough.
假装AC 【不行你多久没写平衡树了】
然后我就用线段树A掉了
线段树维护前$w$大数字和很不舒服，就可以转化成前$R-L-w$小

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 200010
using namespace std;
typedef long long LL;
#define G c=getchar()
inline int read()
{
    int x=0,f=1;char G;
    while(c>57||c<48){if(c=='-')f=-1;G;}
    while(c>47&&c<58)x=x*10+c-48,G;
    return x*f;
}
int sum[20010],siz[20010];
void update(int x)
{
    sum[x]=sum[x<<1]+sum[x<<1|1];
    siz[x]=siz[x<<1]+siz[x<<1|1];
}
int qry(int x,int l,int r,const int&w)
{
    if(l==r)return w*l;
    int mid=l+r>>1;
    if(siz[x<<1]>=w)return qry(x<<1,l,mid,w);
    else return sum[x<<1]+qry(x<<1|1,mid+1,r,w-siz[x<<1]);
}
void ins(int x,int l,int r,const int&w,const int&op)
{
    if(l==r){sum[x]+=w*op,siz[x]+=op;return;}
    int mid=l+r>>1;
    if(w<=mid)ins(x<<1,l,mid,w,op);
    else ins(x<<1|1,mid+1,r,w,op);
    update(x);
}
int a[maxn],t[maxn],n,w,k,sa,st,ans;
void ins(int x,int op)
{
    sa+=a[x]*op;st+=t[x]*op;
    ins(1,1,5000,t[x]>>1,op);
}
int main()
{
    n=read(),w=read(),k=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)t[i]=read();
    for(int L=0,R=0;R<=n;ins(++L,-1))
        for(;st-sum[1]+qry(1,1,5000,max(R-L-w,0))<=k&&R<=n;ins(++R,1))ans=max(sa,ans);
    printf("%d",ans);
    return 0;
}

746G[构造]

题意：给定每个深度点的个数和叶子数，构造原树

考虑第$i$层的叶子数区间是$[a_i-a_{i-1},a_i-1]$，而且取值独立，互不相关，这意味着只要任意找一个方程组的解就好了。
怎么会有这种傻逼G题

---

CR#385 (Div. 1)

---

744C[状压DP]

题意：每回合可以收集一张红色令牌和蓝色令牌，或者以$max(r_i-A,0)张红令牌，max(b_i-B,0)张蓝令牌$的代价购买第i张卡，其中A、B是现有红、蓝卡数，求所有卡买下的最少回合数

好明显的状压DP
先设计$f[S]$表示$S$时最小回合数，发现要记录剩余卡牌，但是$f[S][x][y]$显得特别傻逼，考虑到每次可以攒到刚刚好就去买卡，只需要$f[S][0/1][x]$。之后发现$x$可能其大无比。又发现对于$r_i\geq n$和$r_i=n$对于题目的影响是一样的，就可以把多余的先攒起来。
最终状态量是$f[2^{16}][0/1][16^2]$
加粗处挺神的..自己想的时候一直不知道怎么减少状态。
会了就不想写了

---

744D[计算几何]

题意：找一个最大的圆只含红点（边界上的任意）

二分半径，枚举每个点，使圆绕着点转，可以得到其他点在圆内出现的区间，就会判定答案了。

---

744E[弃坑]

网上没人翻译

---

CR#384 (Div. 2)

743E[二分答案+状压DP]

题意：给你一个长度为$N$的一个序列，需要我们找到一个最长的子序列，保证每个元素($1$~$8$)的个数之前的绝对值差小于等于$1$，而且对应选出来的序列中，需要保证相同的元素是连续的。

玛德暴力。
先二分一个答案，枚举$$1-8$是否多选，然后状压DP。
就没了= =

/*
    Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 1010
#define clr(a) memset(a,0,sizeof(a))
using namespace std;
#define G c=getchar()
typedef long long LL;
inline int read()
{
    int x=0,f=1;char G;
    while(c>57||c<48){if(c=='-')f=-1;G;}
    while(c>47&&c<58)x=x*10+c-48,G;
    return x*f;
}
int a[maxn],_[8],l[maxn];
int f[8][1<<8],g[1<<8],h[1<<8],n,m,bin[10];
#define rep(x) for(x=0;x<2;x++)
int check(int x)
{
    int X=x/8;
    rep(_[1])rep(_[2])rep(_[3])rep(_[4])rep(_[5])rep(_[6])rep(_[7])rep(_[0])
    {
        clr(f),clr(g),clr(h);
        int s=0;
        for(int i=0;i<8;i++)
            l[i]=X+_[i],s+=l[i];
        if(s!=x)continue;
        for(int i=0;i<256;i++)
        {
            int flag=1;
            for(int j=0;j<8;j++)
                if((i&bin[j])&&l[j]){flag=0;break;}
            if(flag)h[i]=1;
        }
        for(int i=1;i<=n;i++)
        {
            memcpy(g,h,sizeof(h));clr(h);
            for(int j=0;j<256;j++)
                if(g[j])
                {
                    h[j]=1;
                    f[a[i]][j]++;
                    if(f[a[i]][j]==l[a[i]])h[j|bin[a[i]]]=1;
                }
        }
        if(h[255])return 1;
    }
    return 0;
}
int main()
{
    bin[0]=1;for(int i=1;i<9;i++)bin[i]=bin[i-1]<<1;
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=read()-1;
    int L=0,R=n,mid,ans;
    for(;L<=R;)
        if(check(mid=L+R>>1))ans=mid,L=mid+1;
        else R=mid-1;
    printf("%d",ans);
    return 0;
}

---

UOJ Round

UTR#1

#9. vfk的字符串

字符串排序

#10. pyx的难题

看了一眼只会两个$\log$，题解说能拿90分。
不是很会做

#11. ydc的大树

看懂了题解，不是很会写

UER#1

#12. 猜数

数学题

#13. 跳蚤OS

#14. DZY Loves Graph

51nod