CF1270X Good Bye 2019

---

今天下午兴致勃勃地跟wyq和xks一起打了这场挺水的ACM的vp，AK了

过题数是3(they)+9(me)=12

可能是我做的比较水吧

这里放出我过的几题的题解，也许之后会放上他们的题解？

题面在这

---

A. Who Is The Winner?

---

B. Rock-Paper-Scissors

---

C. Street Lamps

---

D. Alternating Strings

题意：

给你一个01串和k，让你将串分成最小的段数，使得每一段都不是01正好交替串，且各自长度小于等于k，其中单独一个数不属于交替

题解：

设f[i]表示强制第i个数分段的最小段数

转移枚举距离i k以内的位置j，如果i与j之间的串不是01交替的就可以转移

$f[i]=\min\{ f[j] \}+1$

答案是f[n]-1，因为最后一段不用分

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int N=1e3+5;
int n,m,a[N],f[N];

void doit(){
    read(n);read(m);
    for(int i=1;i<=n;i++) scanf("%1d",&a[i]);
    for(int i=1;i<=n;i++){
        f[i]=f[i-1]+1;
        for(int j=2,op=0;j<=m;j++){
            if(i-j<0) break;
            if(a[i-j+1]==a[i-j+2]) op=1;
            if(op) f[i]=min(f[i],f[i-j]+1);
        }
    }
    write(f[n]-1);puts("");
}

signed main(){
    int t;
    read(t);
    while(t--) doit();
}

---

E. Epic Professor

题意：

给出n个学生的成绩，大于等于50算及格

现在教授能给他们加上一样多的分数，但不能使任何一个人的分数超过100

问最多能使多少人及格

题解：

简单贪心，算出最多能加多少分，模拟即可

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int N=105;
int a[N];

void doit(){
    int n,ans=0,mi=0x3f3f3f3f;
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        mi=min(mi,100-a[i]);
    }
    for(int i=1;i<=n;i++) if(a[i]+mi>=50) ans++;
    write(ans);puts("");
}

signed main(){
    int t;
    read(t);
    while(t--) doit();
}

---

F. Travelling Salesman

题意：

给出一张无向图，图的边权是这条路耗油的量

在每个城市你可以加满油

问你的汽车油箱至少要多大，才可以在汽车不半路抛锚的前提下，从任意城市前往任意城市

题解：

简单最小生成树，跑遍kruskal即可

原理大概是要在保证图联通的基础上使得所有边权最小

那不就是最小生成树的性质吗（

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int N=1e5+5;
int f[N];

struct edge{
    int x,y,z;
    inline bool operator < (const edge &nt) const {
        return z<nt.z;
    }
}e[N];

int getf(int x){
    if(f[x]==x) return x;
    return f[x]=getf(f[x]);
}

void doit(){
    int n,m,ans=0;
    read(n);read(m);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1,x,y,z;i<=m;i++)
        e[i]=(edge){read(x),read(y),read(z)};
    sort(e+1,e+1+m);
    int num=0;
    for(int i=1;i<=m;i++){
        int x=getf(e[i].x),y=getf(e[i].y);
        if(x==y) continue;
        f[x]=y;
        ans=e[i].z;
        if(++num==n-1) break;
    }
    write(ans);puts("");
}

signed main(){
    int t;
    read(t);
    while(t--) doit();
}

---

G. Heavy Coins

题意：

给你一些数和k，让你从中选出最多的一些数

使他们满足加起来大于等于k且去掉其中的任何一个数都会使得这些数的和小于k

题解：

水题，转化一下题意后你会发现更是个大水题

毕竟n<=10，暴力枚举一下选那些数，模拟判定一下即可

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int N=15;
int n,s,a[N];

int check(int S){
    int sum=0,mi=1e9,m=0;
    for(int i=0;i<n;i++) if(S>>i&1) m++,sum+=a[i],mi=min(mi,a[i]);
    if(sum<s) return 0;
    if(sum-mi>=s) return 0;
    return m;
}

void doit(){
    int ans=0;
    read(n);read(s);
    for(int i=0;i<n;i++) read(a[i]);
    int lim=1<<n;
    for(int i=1;i<lim;i++) ans=max(ans,check(i));
    write(ans);puts("");
}

signed main(){
    int t;
    read(t);
    while(t--) doit();
}

---

H. Bridges

题意：

给你一张无向图，让你连上任意一条边，使得图中的割边最少

代码：

一眼题，挺无聊的，模板套模板

凭直觉，先对图进行边双缩点，于是我们就得到了一棵树

显然的，加一条边的贡献就是两端点之间树链的长度

贪心的，我们要选最长的，也就是树的直径

经典问题，两次dfs解决

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int N=1e5+5;
int en,h[N],st[N],lim,dfn[N],low[N],cnt,sn,scc[N],d[N],p,q,n,m;

struct edge{
    int n,u,v;
}e[N<<2];

void add(int x,int y){
    e[++en]=(edge){h[x],x,y};
    h[x]=en;
}

void tarjan(int x,int fa){
    dfn[x]=low[x]=++cnt;
    st[++lim]=x;
    for(int i=h[x];i;i=e[i].n){
        int y=e[i].v;
        if(y==fa) continue;
        if(!dfn[y]){
            tarjan(y,x);
            low[x]=min(low[x],low[y]);
        }
        else{
            if(!scc[y]) low[x]=min(low[x],dfn[y]);
        }
    }
    if(low[x]==dfn[x]){
        int top;
        sn++;
        for(;;){
            top=st[lim--];
            scc[top]=sn;
            if(top==x) break;
        }
    }
}

void dfs(int x,int fa){
    d[x]=d[fa]+1;
    if(d[x]>d[p]) p=x;
    for(int i=h[x];i;i=e[i].n){
        int y=e[i].v;
        if(y==fa) continue;
        dfs(y,x);
    } 
}

void getd(){
    p=0;
    dfs(1,0);
    q=p;
    dfs(q,0);
}

void init(){
    en=sn=cnt=0;
    memset(h,0,sizeof h);
    memset(scc,0,sizeof scc);
    memset(dfn,0,sizeof dfn);
    memset(low,0,sizeof low);
}

void doit(){
    read(n);read(m);
    init();
    for(int i=1,x,y;i<=m;i++){
        read(x);read(y);
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++) if(!scc[i]) tarjan(i,0);
    int enn=en;
    for(int i=1;i<=n;i++) h[i]=0;
    for(int i=1;i<=enn;i+=2){
        int x=e[i].u,y=e[i].v;
        if(scc[x]==scc[y]) continue;
        add(scc[x],scc[y]);
        add(scc[y],scc[x]);
    }
    getd();
    write(sn-d[p]);puts("");
}

signed main(){
    int t;
    read(t);
    while(t--) doit();
}

---

I. Bahosain and Digits

题意：

给出一个数字串

请你确定一个最大的常数k

使得存在方法可以对任意多组长度为k的串进行任意多次操作，使得串中的所有数相同

定义一次操作为将一条串中的每个数都+1(9会变0)

题解：

这题比较难，见这里)

---

J. Candy

题意：

给你一些人的年龄和一些袋装糖果每袋的数量

现让你分配糖果，一人一包，要求相同年龄的人糖果数量相同，年龄较大的人糖果更多

题解：

统计每个年龄的人数和每种糖果数的包数

从小到大搞遍双指针，如果糖果扫完了年龄还没扫完就是不合法的

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int N=55;
int a[N],b[N];

void doit(){
    int n,m;
    read(n);read(m);
    memset(a,0,sizeof a);
    memset(b,0,sizeof b);
    for(int i=1,x;i<=n;i++) a[read(x)]++;
    n=0;
    for(int i=1;i<=15;i++) if(a[i]) a[++n]=a[i];
    for(int i=1,x;i<=m;i++) b[read(x)]++;
    m=0;
    for(int i=1;i<=50;i++) if(b[i]) b[++m]=b[i];
    for(int i=1,j=1;i<=n;i++,j++){
        while(a[i]>b[j]&&j<=m) j++;
        if(j>m){
            puts("NO");
            return ;
        }
    }
    puts("YES");
}

signed main(){
    int t;
    read(t);
    while(t--) doit();
}

---

K. Runtime Error

题意：

给出n个数和常数k

让你在n个数中找出x和y，满足$x*y=k$，$x\leqy$且x最小

题解：

题如其名，注意除法时特判0，不然会RE。。。

直接扫一遍就可以了

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

#define int long long

const int N=1e5+5;
int a[N];

void doit(){
    int n,k,ans1=-1,ans2=0,zero=0;
    map<int,int> v;
    read(n);read(k);
    for(int i=1;i<=n;i++) read(a[i]),a[i]=!a[i]?1e9:a[i],zero|=a[i]==1e9;
    sort(a+1,a+1+n);
    if(k==0){
        if(zero){
            for(int i=1;i<=n;i++) if(a[i]!=1e9){
                ans1=a[i];
                break;
            }
            if(ans1!=-1){
                printf("0 ");write(ans1);puts("");
            }
            else{
                puts("-1");
            }
        }
        else{
            puts("-1");
        }
        return ;
    }
    for(int i=1;i<=n;i++) if(k%a[i]==0){
        if(v[k/a[i]]){
            ans1=k/a[i];
            ans2=a[i];
        }
        v[a[i]]=1;
    }
    if(ans1==-1) puts("-1");
    else write(ans1),putchar(' '),write(ans2),puts("");
}

signed main(){
    int t;
    read(t);
    while(t--) doit();
}

---

L. Alternating Strings II

题意：

D的加强版

题解：

显然的D中的朴素转移的j是连续的一段

于是我们可以$O(n)$预处理出每一位前面最长的01交替串的长度

拿线段树维护f[]的区间最小值

查询范围就是[原来的左边界,i-以i结尾的最长01交替串的长度-1]

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int N=1e5+5;
int n,m,a[N],f[N],g[N],mi[N<<2];

void pushup(int x){
    mi[x]=min(mi[x<<1],mi[x<<1|1]);
}

void up(int x,int l,int r,int p,int v){
    if(l==r){
        mi[x]=v;
        return ;
    }
    int mid=l+r>>1;
    if(p<=mid) up(x<<1,l,mid,p,v);
    else up(x<<1|1,mid+1,r,p,v);
    pushup(x);
}

int que(int x,int l,int r,int p,int q){
    if(p>q||q<1) return 0x3f3f3f3f;
    if(p<=l&&r<=q){
        return mi[x];
    }
    int mid=l+r>>1,res=0x3f3f3f3f;
    if(p<=mid) res=min(res,que(x<<1,l,mid,p,q));
    if(q>mid) res=min(res,que(x<<1|1,mid+1,r,p,q));
    return res;
}

void doit(){
    read(n);read(m);
    for(int i=1;i<=n;i++) scanf("%1d",&a[i]);
    memset(mi,0x3f,sizeof mi);
    g[1]=1;
    up(1,1,n,1,0);
    for(int i=2;i<=n;i++) g[i]=a[i]==a[i-1]?1:g[i-1]+1;
    for(int i=1;i<=n;i++){
        f[i]=f[i-1]+1;
        f[i]=min(f[i],que(1,1,n,1+max(0,i-m),1+i-g[i]-1)+1);
        if(i^n) up(1,1,n,i+1,f[i]);
    }
    write(f[n]-1);puts("");
}

signed main(){
    int t;
    read(t);
    while(t--) doit();
}