2021 BUAA Winter Training 4

题意

给你一个的棋盘，要求用的矩形覆盖这个棋盘，不能越出边界，不能有重叠，问最多能用多少个矩形。

解法

沙茶题秒出答案即可。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
    return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
int main(){
    int n,m;
    n=read();m=read();
    printf("%d\n",n*m/2);
    return 0;
}

题意

有一栋层的大楼，有个人要乘电梯，一直每个人在时刻开始等电梯，从层坐到层，问每个人最终到达的时间。

解法

一开始我以为是个扫描线+单调队列+主席树（OI打久了什么奇怪的想法都有。。。）

然而码着码着发现这是个结论题啊。。。

每次电梯从下到上要过层，从上到下亦然，所以我们只要根据推电梯已经运行了多少个来回，再根据上行或下行的层数得出答案即可。

手玩几个样例即可，具体可以看代码。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 100010
using namespace std;
int n,m;
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
    return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
void solve(){
    n=read();m=read();
    m=2*m-2;//注意这句话！
    for(int i=1,s,f,t;i<=n;i++){
        s=read();f=read();t=read();
        if(s<f)printf("%d\n",(t+m-s)/m*m+f-1);
        else if(s>f)printf("%d\n",(t+m-(m+2-s))/m*m+(m+2-f)-1);
        else printf("%d\n",t);
    }
}
int main(){
    solve();
    return 0;
}

题意

给出一串下标从到的数列，可以反转一个区间，求在偶数位上最大数字和是多少。

解法

没有那个反转那就是最大子段和的类似版本对吧。

那个反转也是要偶数长度才有效对吧。

因为奇数长度的的区间反转之后偶数位没有变化，那还做个毛线。。。

于是我们考虑区间反转的影响。

假设为偶数，原来的取值是，那么反转之后，取值的变化（注意是变化！）就是。

对于同理。

所以我们一开始就直接选取所有偶数位，然后逐个比较反转之后是否有更大价值。

至于连续区间，我们类比最大子段和，当变化是负值时，直接舍弃前面的反转，再从0开始。

复杂度显然，跑的飞起。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 200010
using namespace std;
int n;
long long ans,sum1,sum2,maxn,val[MAXN];
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
    return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
inline long long max(const long long &x,const long long &y){return x>y?x:y;}
void work(){
    for(int i=2;i<=n;i+=2){
        sum1=max(0,val[i]-val[i-1]+sum1);
        maxn=max(maxn,sum1);
    }
    for(int i=3;i<=n;i+=2){
        sum2=max(0,val[i-1]-val[i]+sum2);
        maxn=max(maxn,sum2);
    }
    printf("%lld\n",ans+maxn);
}
void init(){
    ans=sum1=sum2=maxn=0;
    n=read();
    for(int i=1;i<=n;i++){
        val[i]=read();
        if(i&1)ans+=val[i];
    }
}
int main(){
    int t=read();
    while(t--){
        init();
        work();
    }
    return 0;
}

题意

这个题面怎么这么长。。。

给一个长度为的空串，和个位置下标，之后是一行给定的模式字符串，最后是个下标。

问能否在这个位置都插入模式串并保证模式串能完整匹配而不被覆盖掉。

求其余未填充字符的位置能任意填字母的情况下，有多少种填充方案。

解法

不被覆盖掉的意思就是如果相邻两个插入的模式串有重叠部分，那么两模式串重叠部分相同。

再简略一点就是：模式串前后缀有部分相同。

这个用和都可以对吧。（当然你要用后缀数组我也拦不住。。。）

填充完了，求出剩余的空白位置，答案就是。

我这里用的是，一开始用单还了两次，于是怒改双终于过了。。。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 1000010
#define MOD 1000000007LL
using namespace std;
int n,m,len,ans,pos[MAXN];
unsigned long long base_one[MAXN],base_two[MAXN],hash_one[MAXN],hash_two[MAXN];
char str[MAXN];
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
inline int max(const int &x,const int &y){return x>y?x:y;}
long long mexp(long long a,long long b,long long c){
    long long s=1;
    while(b){
        if(b&1)s=s*a%c;
        a=a*a%c;
        b>>=1;
    }
    return s;
}
inline unsigned long long get_hash_one(int l,int r){
    return hash_one[r]-hash_one[l-1]*base_one[r-l+1];
}
inline unsigned long long get_hash_two(int l,int r){
    return hash_two[r]-hash_two[l-1]*base_two[r-l+1];
}
void make(){
    base_one[0]=base_two[0]=1;
    for(int i=1;i<=n;i++){
        base_one[i]=base_one[i-1]*131;
        hash_one[i]=hash_one[i-1]*131+str[i];
        base_two[i]=base_two[i-1]*4589632;
        hash_two[i]=hash_two[i-1]*4589632+str[i];
    }
}
bool check(int x,int y){
    if(pos[x]+len-1<pos[y])return true;
    int u=pos[x]+len-pos[y];
    if(get_hash_one(len-u+1,len)==get_hash_one(1,u)&&get_hash_two(len-u+1,len)==get_hash_two(1,u))return true;
    return false;
}
void work(){
    int maxr=pos[1]+len-1;
    ans=pos[1]-1;
    for(int i=2;i<=m;i++){
        if(pos[i]>maxr)ans+=pos[i]-maxr-1;
        maxr=max(maxr,pos[i]+len-1);
    }
    ans+=n-maxr;
    printf("%lld\n",mexp(26,ans,MOD));
}
void init(){
    n=read();m=read();
    if(m==0){
        printf("%lld\n",mexp(26,n,MOD));
        return;
    }
    scanf("%s",str+1);
    len=strlen(str+1);
    make();
    for(int i=1;i<=m;i++)pos[i]=read();
    sort(pos+1,pos+m+1);
    for(int i=2;i<=m;i++)if(!check(i-1,i)){
        printf("0\n");
        return;
    }
    work();
}
int main(){
    init();
    return 0;
}

题意

有个点，条边的无向图，每条边的权值为或，每条边只能走一次，求从到的所有路径中，是否有路径能经过权值为的路。

解法

退役久了，一眼没看出来这个双连通分量。。。

双连通分量不会的自行出门左转百度。。。

双连通缩点之后，每个连通块内部只要有权值为的边，那么必定有一种路径能经过这条边，于是我们可以把缩完的点权值设为，否则为。

缩点连边不必多说。

然后本蒟蒻直接一发最大生成树+LCA完事。

不过网上一堆暴力解法，反正本蒟蒻是不会。。。

一开始敲错下标连六次，简直药丸。。。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 300010
using namespace std;
int n,m,s,t,num=0,c=1;
int head[MAXN],deep[MAXN],val[MAXN],path[MAXN];
struct Edge{
    int next,to,w;
}a[MAXN<<1];
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
    return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
namespace Kruskal{
    int d=0;
    int fa[MAXN],size[MAXN],son[MAXN],top[MAXN];
    struct Graph{
        int u,v,w;
        friend bool operator <(const Graph &u,const Graph &v){
            return u.w>v.w;
        }
    }graph[MAXN];
    inline void add(int u,int v,int w){
        d++;
        graph[d].u=u;graph[d].v=v;graph[d].w=w;
    }
    inline void add_edge(int u,int v,int w){
        a[c].to=v;a[c].w=w;a[c].next=head[u];head[u]=c++;
        a[c].to=u;a[c].w=w;a[c].next=head[v];head[v]=c++;
    }
    int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
    void uniun(int x,int y){x=find(x);y=find(y);if(x!=y)fa[y]=x;}
    bool check(int x,int y){x=find(x);y=find(y);return x==y;}
    void kruskal(){
        sort(graph+1,graph+d+1);
        for(int i=1;i<=num;i++)fa[i]=i;
        for(int i=1;i<=d;i++)if(!check(graph[i].u,graph[i].v)){
            add_edge(graph[i].u,graph[i].v,graph[i].w);
            uniun(graph[i].u,graph[i].v);
        }
        for(int i=1;i<=num;i++)fa[i]=0;
    }
    void dfs1(int rt){
        size[rt]=1;son[rt]=0;
        for(int i=head[rt];i;i=a[i].next){
            int will=a[i].to;
            if(!deep[will]){
                deep[will]=deep[rt]+1;
                fa[will]=rt;
                val[will]+=val[rt];
                path[will]=path[rt]+a[i].w;
                dfs1(will);
                size[rt]+=size[will];
                if(size[son[rt]]<size[will])son[rt]=will;
            }
        }
    }
    void dfs2(int rt,int f){
        top[rt]=f;
        if(son[rt])dfs2(son[rt],f);
        for(int i=head[rt];i;i=a[i].next){
            int will=a[i].to;
            if(will!=fa[rt]&&will!=son[rt])dfs2(will,will);
        }
    }
    int LCA(int x,int y){
        while(top[x]!=top[y]){
            if(deep[top[x]]<deep[top[y]])swap(x,y);
            x=fa[top[x]];
        }
        if(deep[x]>deep[y])swap(x,y);
        return x;
    }
    void solve(){
        int lca=LCA(s,t);
        if(path[s]+path[t]-2*path[lca]+val[s]+val[t]-val[lca]-val[fa[lca]]>=1)printf("YES\n");
        else printf("NO\n");
    }
    void work(){
        kruskal();
        deep[1]=1;
        dfs1(1);
        dfs2(1,1);
        solve();
    }
}
namespace Tarjan{
    int d=1;
    int low[MAXN],colour[MAXN];
    int top=0,stack[MAXN];
    struct Graph{
        int u,v,w;
    }graph[MAXN];
    inline void add_edge(int u,int v,int w){
        a[c].to=v;a[c].w=w;a[c].next=head[u];head[u]=c++;
        a[c].to=u;a[c].w=w;a[c].next=head[v];head[v]=c++;
    }
    void tarjan(int x,int fa){
        deep[x]=low[x]=d++;
        stack[++top]=x;
        for(int i=head[x];i;i=a[i].next){
            int v=a[i].to;
            if(v==fa)continue;
            if(!deep[v]){
                tarjan(v,x);
                low[x]=min(low[x],low[v]);
            }
            else{
                low[x]=min(low[x],deep[v]);
            }
        }
        if(low[x]==deep[x]){
            num++;
            do{
                colour[stack[top]]=num;
            }while(stack[top--]!=x);
        }
    }
    void build_new_graph(){
        c=1;
        memset(head,0,sizeof(head));
        memset(val,0,sizeof(val));
        memset(path,0,sizeof(path));
        memset(deep,0,sizeof(deep));
        memset(a,0,sizeof(a));
        s=colour[s];t=colour[t];
        for(int i=1;i<=m;i++){
            if(colour[graph[i].u]!=colour[graph[i].v])Kruskal::add(colour[graph[i].u],colour[graph[i].v],graph[i].w);
            else val[colour[graph[i].u]]|=graph[i].w;
        }
    }
    void work(){
        n=read();m=read();
        for(int i=1;i<=m;i++){
            graph[i].u=read();graph[i].v=read();graph[i].w=read();
            add_edge(graph[i].u,graph[i].v,graph[i].w);
        }
        s=read();t=read();
        for(int i=1;i<=n;i++)if(!deep[i])tarjan(i,0);
        build_new_graph();
    }
}
int main(){
    Tarjan::work();
    Kruskal::work();
    return 0;
}