CF1257F Make Them Similar

$solution:$

折半搜索后考虑如何维护两个数组的和，可以将 $A$ 中每个数减 $A_1$ ，$B$ 中每个数被减 $B_1$ ，$map$ 维护一下即可。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<map>

#include<vector>

using namespace std;

inline int read(){

    int f=,ans=;char c=getchar();

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

const int MAXN=;

int lowbit(int x){return x&-x;}

int cont(int x){int c=;while(x) c++,x-=lowbit(x);return c;}

int N,A[MAXN];

vector<int> sta;

map<vector<int> ,int> M;

int main(){

    N=read();for(int i=;i<=N;i++) A[i]=read();

    for(int i=;i<(<<)-;i++){

        int cur=cont(i^((A[]>>)));sta.clear();

        for(int j=;j<=N;j++) sta.push_back(cont(i^(A[j]>>))-cur);

        M[sta]=i;

    }

    int all=((<<)-);

    for(int i=;i<(<<)-;i++){

        int cur=cont(i^((A[]&all)));sta.clear();

        for(int j=;j<=N;j++) sta.push_back(cur-cont(i^(A[j]&all)));

        if(M.count(sta)){

            printf("%d\n",(M[sta]<<)+i);

            return ;

        }

    }printf("-1\n");return ;

}

CF1257E The Contest

 $solution:$

设 $f_{i,j}$ 表示现在在 $i$ 个数，现在在第 $j$ 段。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

inline int read(){

    int f=,ans=;char c=getchar();

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

const int MAXN=;

int col[MAXN],f[MAXN][],k1,k2,k3,N;

int main(){

    k1=read(),k2=read(),k3=read();N=k1+k2+k3;

    for(int i=;i<=k1;i++) read();

    for(int i=;i<=k2;i++) col[read()]=;

    for(int i=;i<=k3;i++) col[read()]=;

    memset(f,/,sizeof(f));

    f[][]=;

    for(int i=;i<=N;i++){

        for(int j=;j<;j++){

            for(int k=;k<=j;k++) f[i][j]=min(f[i][j],f[i-][k]+(col[i]!=j));

        }

    }

    int Minn=min(f[N][],min(f[N][],f[N][]));

    printf("%d\n",Minn);return ;

}

CF1268C And Reachability

$solution:$

设 $f_{i,j}$ 表示从 $i$ 点走到离 $i$ 最近并且 $j$ 位上是一的，可以简单递推得到。

时间复杂度 $O(20^2\cdot n)$ 。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

inline int read(){

    int f=,ans=;char c=getchar();

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

const int MAXN=;

int f[MAXN][],g[],n,q,A[MAXN];

int main(){

    n=read(),q=read();

    for(int i=;i<=n;i++) A[i]=read();

    for(int i=;i<=n+;i++) for(int j=;j<=;j++) f[i][j]=g[j]=n+;

    for(int i=n;i>=;i--){

        for(int j=;j<=;j++){

            if(A[i]&(<<j)){

                for(int k=;k<=;k++) f[i][k]=min(f[i][k],f[g[j]][k]);

                f[i][j]=i;g[j]=i;

            }

        }

    }

    while(q--){

        int x=read(),y=read();bool ok=;

        for(int i=;i<=;i++) if(A[y]&(<<i)) ok|=(f[x][i]<=y);

        if(ok){printf("Shi\n");continue;}

        printf("Fou\n");

    }return ;

}/*

5 5

0 0 1 3 7

1 2

2 2

3 5

4 5

1 5

*/

CF1268B Good Triple

$solution:$

因为 $2k\leq 9$ ，所以直接 $r$ 单调性暴力处理就行。时间复杂度 $O(9n)$ 。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define int long long

using namespace std;

inline int read(){

    int f=,ans=;char c=getchar();

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

const int MAXN=;

int L[MAXN],N,A[MAXN];

char str[MAXN];

signed main(){

    scanf("%s",str+);N=strlen(str+);

    for(int i=;i<=N;i++) A[i]=str[i]-'';

    int ll=,Ans=;

    for(int r=;r<=N;r++){

        for(int i=;r-*i>=;i++){

            if(A[r]==A[r-i]&&A[r-i]==A[r-*i]){ll=max(ll,r-*i);break;}

        }

        Ans+=ll;

    }printf("%lld\n",Ans);

}

CSGRound2 逐梦者的初心

$solution:$

考虑将 $S$ 串翻转后1问题就变为了维护多项式系数。$bitset$ 优化即可。

时间复杂度 $O(\dfrac{m^2}{w})$

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<vector>

#include<bitset>

using namespace std;

inline int read(){

    int x=,f=; char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-;

    for(;isdigit(c);c=getchar()) x=x*+c-'';

    return x*f;

}

const int N=;

const int MAXN=;

int n,m,A[N],Ans[MAXN];

bitset<MAXN> Bit,ve[],e;

int main(){

    n=read(),m=read();

    for(int i=;i<=m;i++) A[i]=read();for(int i=;i<=n-m;i++) read();

    for(int i=;i<=m;i++) ve[A[i]][m-i+]=;

    n=m;

    for(int i=;i<=m;i++){

        int opt=read(),x=read();

        if(opt==) Bit|=(ve[x]<<i);

        else{Bit=(Bit<<);Bit|=(ve[x]<<);}

        e[m+i]=;printf("%d\n",(Bit.flip()&e).count());

        Bit.flip();

    }

    return ;

}/*

2 2

1 2

1 1

1 3

*/

CSGRound2 开拓者的卓识

$solution:$

考虑每一位 $a_i$ 对答案的贡献，根据插板原理可以得到。

$$S_{k,1,r}=\sum_{i=1}^r A_i\cdot \dbinom{i+k-2}{k-1}\cdot \dbinom{r-i+k-1}{k-1}\\=A_i\cdot\dfrac{(i+k-2)!}{(k-1)!\cdot(i-1)!}\cdot\dfrac{(r-i+k-1)!}{(k-1)!\cdot(r-i)!}\\=A_i\cdot\dfrac{(i+k-2)!\cdot (r-i+k-1)!}{(i-1)!\cdot(r-i)!}\cdot\dfrac{1}{(k-1)!^2}$$

$NTT$ 优化一下即可，而阶乘的预处理可以分段打表。

时间复杂度 $O(n\log n+n\times blo)$

CF1225E Rock Is Push

$solution:$

设 $f_{i,j,0/1}$ 表示从 $(1,1)$ 走到 $(i,j)$，其中最后一步的走向是右还是下。

则 $f_{i,j,0}=\sum_{e=k}^{j-1} f_{i,e,1}$ ，可以记录前缀和得到一段区间的 $dp$ 和。

而 $k$ 的得到可以因为实现不同，故时间复杂度为 $O(nm\log n)$ 或 $O(nm)$ 。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define int long long

#define mod 1000000007

using namespace std;

inline int read(){

    int f=,ans=;char c=getchar();

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

const int MAXN=;

int n,m,f[MAXN][MAXN][];

/*left 0   down 1*/

char str[MAXN];

int A[MAXN][MAXN],S1[MAXN][MAXN],S2[MAXN][MAXN];

int Qi(int id,int l,int r){/*col*/

    return S1[r][id]-S1[l-][id];

}

int Qj(int id,int l,int r){/*row*/

    return S2[id][r]-S2[id][l-];

}

int fS1[MAXN][MAXN],fS2[MAXN][MAXN];

int Mod(int x){return ((x%mod)+mod)%mod;}

signed main(){

//    freopen("maker.in","r",stdin);

    n=read(),m=read();

    for(int i=;i<=n;i++){

        scanf("%s",str+);

        for(int j=;j<=m;j++) A[i][j]=(str[j]=='R');

    }

    if(n==&&m==){printf("%lld\n",A[][]^);return ;}

    for(int i=;i<=n;i++) for(int j=;j<=m;j++) S1[i][j]=S1[i-][j]+A[i][j];

    for(int i=;i<=n;i++) for(int j=;j<=m;j++) S2[i][j]=S2[i][j-]+A[i][j];

    f[][][]=f[][][]=;fS1[][]=,fS2[][]=;

    for(int i=;i<=n;i++){

        for(int j=;j<=m;j++){

            if(i==&&j==) continue;

            int l=,r=i-,res=i;

            while(l<=r){

                int mid=l+r>>;

                if(Qi(j,mid+,n)<=(n-i)) res=mid,r=mid-;

                else l=mid+;

            }

            f[i][j][]=fS1[i-][j]-fS1[res-][j];f[i][j][]=Mod(f[i][j][]);

            l=,r=j-,res=j;

            while(l<=r){

                int mid=l+r>>;

                if(Qj(i,mid+,m)<=(m-j)) res=mid,r=mid-;

                else l=mid+;

            }

            f[i][j][]=fS2[i][j-]-fS2[i][res-];f[i][j][]=Mod(f[i][j][]);

            fS1[i][j]=fS1[i-][j]+f[i][j][];fS1[i][j]=Mod(fS1[i][j]);

            fS2[i][j]=fS2[i][j-]+f[i][j][];fS2[i][j]=Mod(fS2[i][j]);

        }

    }printf("%lld\n",(f[n][m][]+f[n][m][])%mod);return ;

}/*3 3

.RR

...

R..

*/

CF1239D Catowice City

$solution:$

考虑类似于 $2-SAT$ 将必须选择的关系连边，$tarjan$ 后让最开始遍历的强连通分量为 $1$ ，因为 $dfs$ 的顺序易知这是正确的。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<vector>

using namespace std;

inline int read(){

    int f=,ans=;char c=getchar();

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

const int MAXN=;

int n,m,T,col[MAXN],sta[MAXN],num,dfn[MAXN],low[MAXN],Ans0[MAXN],Ans1[MAXN];

vector<int> vec[MAXN];

void Init(){

    num=;Ans0[]=,Ans1[]=;

    for(int i=;i<=n;i++) vec[i].clear();

    for(int i=;i<=n;i++) col[i]=dfn[i]=low[i]=;

}

void tarjan(int u){

    dfn[u]=low[u]=++num;sta[++sta[]]=u;

    int siz=vec[u].size();

    for(int i=;i<siz;i++){

        int v=vec[u][i];

        if(!dfn[v]){

            tarjan(v);

            low[u]=min(low[u],low[v]);

        }else if(!col[v]) low[u]=min(low[u],low[v]);

    }

    if(dfn[u]==low[u]){

        col[u]=++col[];

        while(sta[sta[]]!=u){

            col[sta[sta[]]]=col[];

            sta[]--;

        }sta[]--;

    }return;

}

int main(){

//    freopen("8.in","r",stdin);

    T=read();

    while(T--){

        n=read(),m=read();

        Init();

        for(int i=;i<=m;i++){int u=read(),v=read();vec[u].push_back(v);}

        for(int i=;i<=n;i++) if(!dfn[i]) tarjan(i);

        if(col[]==){printf("No\n");continue;}

        for(int i=;i<=n;i++){

            if(col[i]==) Ans0[++Ans0[]]=i;

            else Ans1[++Ans1[]]=i;

        }

        printf("Yes\n%d %d\n",Ans0[],Ans1[]);

        for(int i=;i<=Ans0[];i++) printf("%d ",Ans0[i]);printf("\n");

        for(int i=;i<=Ans1[];i++) printf("%d ",Ans1[i]);printf("\n");

    }return ;

}

CF1244F Chips

$solution:$

考虑若对于 $i$ 来说在 $i-1,i+1$ 有颜色相同的话，那么无论经过多少次操作都可以为本身颜色。

否则，与其相邻的是 $01$ 段，模拟一下即可。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

inline int read(){

    int f=,ans=;char c=getchar();

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

const int MAXN=;

char str[MAXN];

int n,k,A[MAXN],B[MAXN],C[MAXN];

void print(int opt){opt?printf("W"):printf("B");}

int main(){

    n=read(),k=read();

    scanf("%s",str+);

    for(int i=;i<=n;i++) A[i]=(str[i]=='W');

    A[]=A[n],A[n+]=A[];

    for(int i=;i<=n;i++) B[i]=(A[i-]==A[i]||A[i]==A[i+]),B[i+n]=B[i];

    bool F=;for(int i=;i<=n;i++) F|=B[i];

    if(!F){for(int i=;i<=n;i++) print(A[i]^(k&));printf("\n");return ;}

    int ps=;for(int i=;i<=n;i++) if(B[i]) ps=i;

    for(int i=n+;i<=*n;i++){if(B[i]) ps=i;C[i-n]=i-ps;}

    for(int i=*n;i>n;i--) if(B[i]) ps=i;

    for(int i=n;i>=;i--){if(B[i]) ps=i;C[i]=min(C[i],ps-i);}

    for(int i=;i<=n;i++){

        if(B[i]) print(A[i]);

        else print(A[i]^(min(k,C[i])&));

    }printf("\n");return ;

}

CF1245F Daniel and Spring Cleaning

$solution:$

按维容斥后做简单数位 $dp$ 即可。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#define int long long

using namespace std;

inline int read(){

    int f=,ans=;char c=getchar();

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

const int MAXN=;

int T,a,b,A[MAXN],B[MAXN],len,f[MAXN][][];

int dfs(int ps,int lim1,int lim2){

    if(ps==-) return ;

    if(f[ps][lim1][lim2]!=-) return f[ps][lim1][lim2];

    int e1=(lim1==)?A[ps]:,e2=(lim2==)?B[ps]:,res=;

    for(int i=;i<=e1;i++)

        for(int j=;j<=e2;j++){

            if(i==&&j==) continue;

            res+=dfs(ps-,lim1&&(i==A[ps]),lim2&&(j==B[ps]));

    }

    return f[ps][lim1][lim2]=res;

}

int calc(int x,int y){

    if(x<||y<) return ;

    memset(f,-,sizeof(f));

    len=;

    for(int i=;i>=;i--) A[i]=(x&(<<i))?:;

    for(int i=;i>=;i--) B[i]=(y&(<<i))?:;

    return dfs(,,);

}

signed main(){

//    freopen("4.in","r",stdin);

    T=read();

    while(T--){

        int l=read(),r=read();

        printf("%lld\n",calc(r,r)+calc(l-,l-)-*calc(l-,r));

    }

    return ;

}

CF1245E Hyakugoku and Ladders

 $solution:$

设 $f_{i,j}$ 表示从 $(i,j)$ 走到 $(1,1)$ 的期望步数，按题意模拟的转移即可。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

inline int read(){

    int f=,ans=;char c=getchar();

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

const int N=;

int M[N][N],fro[N*N];

double f[N*N];

int main(){

    for(int i=;i<=;i++)

        for(int j=;j<=;j++){

            if(i&) M[i][j]=(i-)*+j;

            else M[i][j]=(i-)*+-j;

        }

    double sum=;

    f[]=;for(int i=;i<=;i++){

        f[i]=(sum+)/(i-);

        sum+=f[i];

    }

    for(int i=;i<=;i++){

        for(int j=;j<=;j++){int x=read();fro[M[i][j]]=M[i-x][j];}

    }

    for(int i=;i<=;i++){

        double s=;

        for(int j=;j<=;j++) s+=min(f[i-j],f[fro[i-j]]);

        f[i]=s/6.0+;

    }

    printf("%.10lf\n",f[]);return ;

}

CF1249F Maximum Weight Subset

$solution:$

设 $f_{i,j}$ 表示以 $i$ 号节点为根的子树下距离 $i$ 最近的点至少为 $j$ 的方案数，枚举哪个要选即可。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

inline int read(){

    int f=,ans=;char c=getchar();

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

const int N=;

int n,k,f[N][N],head[N],cnt,val[N],son[N];

struct node{

    int u,v,nex;

}x[N<<];

void add(int u,int v){

    x[cnt].u=u,x[cnt].v=v,x[cnt].nex=head[u],head[u]=cnt++;

}

void dfs(int u,int fath){

    for(int i=head[u];i!=-;i=x[i].nex){

        if(x[i].v==fath) continue;

        dfs(x[i].v,u);

    }

    son[]=;

    for(int i=head[u];i!=-;i=x[i].nex){

        if(x[i].v==fath) continue;

        son[++son[]]=x[i].v;

    }

    for(int i=;i<=k;i++){

        if(i==){

            f[u][]=val[u];

            for(int j=;j<=son[];j++) f[u][]+=f[son[j]][k];

            continue;

        }

        for(int j=;j<=son[];j++){

            int res=f[son[j]][i-];

            for(int p=;p<=son[];p++){

                if(j==p) continue;

                res+=f[son[p]][max(k-i,i-)];

            }

            f[u][i]=max(f[u][i],res);

        }

    }for(int i=k;i>=;i--) f[u][i]=max(f[u][i],f[u][i+]);

}

int main(){

    memset(head,-,sizeof(head));

    n=read(),k=read();

    for(int i=;i<=n;i++) val[i]=read();

    for(int i=;i<n;i++){

        int u=read(),v=read();

        add(u,v),add(v,u);

    }dfs(,);

    printf("%d\n",f[][]);return ;

}

最新文章

  1. 获取iPhone手机的UDID和设备名称.
  2. 机器学习实战笔记(Python实现)-05-支持向量机(SVM)
  3. socket通信
  4. AEAI Portal V3.5.4升级说明，门户集成平台
  5. 判断一个数num是否是2的幂（乐视题）
  6. Java基础-继承-编写一个Java应用程序，设计一个汽车类Vehicle，包含的属性有车轮个数 wheels和车重weight。小车类Car是Vehicle的子类，其中包含的属性有载人数 loader。卡车类Truck是Car类的子类，其中包含的属性有载重量payload。每个 类都有构造方法和输出相关数据的方法。最后，写一个测试类来测试这些类的功 能。
  7. QThread与QWidget使用
  8. PHP之文件目录基础操作
  9. JAVA日历
  10. js 数字，金额 用逗号 隔开。数字格式化
  11. [Quick-x]移动CCEditbox的父对象导致输入框位置偏移问题
  12. 解决Android AVD启动报错问题
  13. [转]easyui常用控件及样式收藏
  14. EF结合SqlBulkCopy
  15. System.Data.DbType和数据库映射关系
  16. ubuntu 安装 pythonenv
  17. ssh免秘钥配置
  18. 【转】Kafka 之 中级
  19. appium--每次启动会重新安装的问题(没试过)
  20. Ubuntu14.04下Pycharm3.4 字体渲染

热门文章

  1. mven 在个网址
  2. IDEA如何将git下来的是工程转为maven工程
  3. 浙大PAT CCCC L3-001 凑零钱 ( 0/1背包 &amp;&amp; 路径记录 )
  4. Spring Cloud云架构 - SSO单点登录之OAuth2.0 登出流程(3)
  5. 【错误记录】Python 负数取余问题
  6. maven 私服的setting.xml配置
  7. Codeforces Aim Tech Round4 (Div2) D
  8. html上传文件
  9. ES6 暂时性死区
  10. kaptcha Spring 整合