Codeforces Round #403 (Div. 2, based on Technocup 2017 Finals)

我会带着你远行 2022-03-30 09:57 234阅读 0赞

# [Codeforces Round \#403 (Div. 2, based on Technocup 2017 Finals)][Codeforces Round _403 _Div. 2_ based on Technocup 2017 Finals] #

--------------------

说一点东西：

昨天晚上$9:05$开始太不好了，我在学校学校$9:40$放学我呆到十点然后还要跑回家耽误时间....要不然$D$题就写完了

周末一些成绩好的同学单独在艺术楼上课然后晚上下第一节晚自习和他们在回廊里玩开灯之后再关上一片漆黑真好玩

--------------------

A.[Andryusha and Socks][]

日常煞笔提.....我竟然$WA$了一次忘了$n<<1$

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

--------------------

B.[The Meeting Place Cannot Be Changed][]

题意：数轴上$n$个点告诉你每个点坐标和移动速度，找一个点使得所有点都到那个点时间最短，求最短时间

各种加权平均没搞过去，最后急了我这是信息学竞赛不是数学竞赛不是物理竞赛，二分答案水过去...

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    typedef long long ll;
    const int N=6e4+5;
    inline int read(){
        char c=getchar();int x=0,f=1;
        while(c<'0'||c>'9'){
         if(c=='-')f=-1;c=getchar();}
        while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
        return x*f;
    }
    int n;
    double x[N],v[N];
    bool check(double g){
        double l=0,r=1e9;
        for(int i=1;i<=n;i++) l=max(l,x[i]-g*v[i]),r=min(r,x[i]+g*v[i]);
        return l<=r;
    }
    int main(){
        //freopen("in","r",stdin);
        n=read();
        for(int i=1;i<=n;i++) x[i]=read();
        for(int i=1;i<=n;i++) v[i]=read();
        double l=0,r=1e9;
        double eps=1e-7;
        while(r-l>eps){
            double mid=(l+r)/2;
            if(check(mid)) r=mid;
            else l=mid;
        }
        printf("%lf",l);
    }

--------------------

C.[Andryusha and Colored Balloons][]

题意：一棵树，$a--b--c$这样的三个点不能是相同颜色，求染色最少用几种颜色，并输出一个方案

一眼看出与同一个点相连的颜色不同，最大度数$+1$就行了

然后被构造方案卡住了.....

想记录每个点的相邻点的颜色集合感觉会被菊花图卡(为什么别人都几百ms我77ms)

**于是发现对于一个点除了父亲和自己颜色不是从小到大其他都可以从小到大分配，记录一下一个点分配到哪里遇到自己和父亲跳过就行了**

MD想了好长时间

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    typedef long long ll;
    const int N=2e5+5;
    inline int read(){
        char c=getchar();int x=0,f=1;
        while(c<'0'||c>'9'){
         if(c=='-')f=-1;c=getchar();}
        while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
        return x*f;
    }
    int n,de[N],u,v;
    struct edge{
        int v,ne;
    }e[N<<1];
    int h[N],cnt;
    inline void ins(int u,int v){
        cnt++;
        e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;
        cnt++;
        e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt;
    }
    int ans,col[N],fa[N],now[N];
    void dfs(int u){
        for(int i=h[u];i;i=e[i].ne){
            int v=e[i].v;
            if(v==fa[u]) continue;
            fa[v]=u;
            now[u]++;
            while(now[u]==col[u]||now[u]==col[fa[u]]) now[u]++;
            col[v]=now[u];
            dfs(v);
        }
    }
    int main(){
        //freopen("in","r",stdin);
        n=read();
        for(int i=1;i<n;i++) u=read(),v=read(),de[u]++,de[v]++,ins(u,v);
        for(int i=1;i<=n;i++) ans=max(ans,de[i]+1);
        printf("%d\n",ans);
        fa[1]=0;col[1]=1;
        dfs(1);
        for(int i=1;i<=n;i++) printf("%d ",col[i]);
    }

--------------------

D.[Innokenty and a Football League][]

题意：

队伍$i$有两种候选名字$a\_i\\ b\_i$，选了$b\_i$的话不能有其他队伍$j$选了$a\_j\\:a\_i==a\_j$

每个队伍名字不能相同，求一个方案

--------------------

发现有相同$a$的队伍只能选$b$，先处理这些

$a$唯一的队伍任意选，只要满足没有两只队伍选一样就行了，我建了个网络流.....

$s \\rightarrow team \\rightarrow name\_a,name\_b \\rightarrow t$

容量都为$1$

(好像只有$Candy?$这个沙茶用了这么$zz$的做法)

然后比赛结束好没写完，后来又发现好多细节问题：

$1.$先把$a$唯一的队伍中那些已经被不唯一的选过的名字处理掉不要建到图里去

$2.$一个名字只能往$t$连一条边，所以判断一下$builded$

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <string>
    using namespace std;
    typedef long long ll;
    const int N=3005,M=1e5+5,INF=1e9;
    inline int read(){
        char c=getchar();int x=0,f=1;
        while(c<'0'||c>'9'){
         if(c=='-')f=-1;c=getchar();}
        while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
        return x*f;
    }
    int n,a[N],b[N],m;
    char str[30];
    int has[M],c[M];
    
    int s,t;
    struct edge{
        int v,c,f,ne;
    }e[M<<1];
    int cnt,h[N];
    inline void ins(int u,int v,int c){
        cnt++;
        e[cnt].v=v;e[cnt].c=c;e[cnt].f=0;e[cnt].ne=h[u];h[u]=cnt;
        cnt++;
        e[cnt].v=u;e[cnt].c=0;e[cnt].f=0;e[cnt].ne=h[v];h[v]=cnt;
    }
    int cur[N],d[N],vis[N];
    int q[N],head,tail;
    bool bfs(){
        head=tail=1;
        memset(vis,0,sizeof(vis));
        d[s]=1;vis[s]=1;q[tail++]=s;
        while(head!=tail){
            int u=q[head++];
            for(int i=h[u];i;i=e[i].ne){
                int v=e[i].v;
                if(!vis[v]&&e[i].c>e[i].f){
                    vis[v]=1;d[v]=d[u]+1;
                    q[tail++]=v;
                    if(v==t) return true;
                }
            }
        }
        return false;
    }
    int dfs(int u,int a){
        if(u==t||a==0) return a;
        int flow=0,f;
        for(int &i=cur[u];i;i=e[i].ne){
            int v=e[i].v;
            if(d[v]==d[u]+1&&(f=dfs(v,min(e[i].c-e[i].f,a)))>0){
                flow+=f;
                e[i].f+=f;
                e[((i-1)^1)+1].f-=f;
                a-=f;
                if(a==0) break;
            }
        }
        if(a) d[u]=-1;
        return flow;
    }
    int dinic(){
        int flow=0;
        while(bfs()){
            for(int i=s;i<=t;i++) cur[i]=h[i];
            flow+=dfs(s,INF);
        }
        return flow;
    }
    
    int id[M],tot;
    string ss[M];
    int choose[N];
    int builded[N];
    int main(){
        //freopen("in","r",stdin);
        n=read();
        for(int i=1;i<=n;i++){
            scanf("%s",str);
            int x=str[0]-'A'+1,y=str[1]-'A'+1,z=str[2]-'A'+1;
            a[i]=x*27*27+y*27+z;
            has[a[i]]++;
            ss[a[i]]=string(str,3);
            
            scanf("%s",str);
            z=str[0]-'A'+1;
            b[i]=x*27*27+y*27+z;
            ss[b[i]]=ss[a[i]];ss[b[i]][2]=str[0];
            
            m=max(m,max(a[i],b[i]));
            //printf("hi %d %d ",a[i],b[i]);cout<<ss[a[i]]<<" "<<ss[b[i]]<<endl;
        }
        for(int i=1;i<=n;i++) if(has[a[i]]>1){
            c[b[i]]++,choose[i]=b[i];
            if(c[b[i]]>1) {puts("NO");return 0;}
        }
    
        tot=n;
        for(int i=1;i<=n;i++) if(has[a[i]]==1){
            if(!id[a[i]]&&c[a[i]]==0) id[a[i]]=++tot;
            if(!id[b[i]]&&c[b[i]]==0) id[b[i]]=++tot;
        }
        s=0;t=tot+1;
        int sum=0;
        for(int i=1;i<=n;i++) if(has[a[i]]==1){
            sum++;
            ins(s,i,1);
            if(id[a[i]]){
                int x=id[a[i]];
                ins(i,x,1);
                if(!builded[x]) ins(x,t,1),builded[x]=1;
            }
            if(id[b[i]]){
                int x=id[b[i]];
                ins(i,x,1);
                if(!builded[x]) ins(x,t,1),builded[x]=1;
            }
        }
        int flow=dinic();
        if(flow!=sum){puts("NO");return 0;}
    
        puts("YES");
        
        for(int u=1;u<=n;u++) if(has[a[u]]==1){
            for(int i=h[u];i;i=e[i].ne) if(e[i].f==1){
                if(e[i].v==id[a[u]]) choose[u]=a[u];
                if(e[i].v==id[b[u]]) choose[u]=b[u];
            }
        }
        
        //for(int i=1;i<=n;i++) printf("choose %d %d %d\n",i,choose[i],1);
        for(int i=1;i<=n;i++) cout<<ss[choose[i]]<<'\n';
    }

然后从\_\_stdcall(我发现这个名字有毒卡latex)和[$zyf2000$][zyf2000]哪里看到$2SAT$做法

> 1、第一种相同，那么必须都选第二种 2、第二种相同，不能同时选第二种 3、第一种和第二种相同，不能同时选第一种和第二种

--------------------

E.[Underground Lab][]

题意：

$n$点$m$边找$k$条路径每个点至少覆盖一次，每条路径长度$\\le \\lceil \\frac\{2n\}\{k\}\\rceil$

--------------------

赛后补提...

直接搞一个既不是$dfs$序也不是欧拉序列的$dfs$序列，访问完一个孩子就把父亲加入序列，序列长度不会超过$2\*n$因为一个点最多给父亲贡献一次

然后第$7$个点貌似整除了$WA$了几次....又改了一个输出方式才过

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    typedef long long ll;
    const int N=4e5+5;
    inline int read(){
        char c=getchar();int x=0,f=1;
        while(c<'0'||c>'9'){
         if(c=='-')f=-1;c=getchar();}
        while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
        return x*f;
    }
    int n,m,k;
    struct edge{
        int v,ne;
    }e[N<<1];
    int h[N],cnt;
    inline void ins(int u,int v){
        cnt++;
        e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;
        cnt++;
        e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt;
    }
    int vis[N];
    int a[N<<1],p;
    void dfs(int u){
        vis[u]=1;
        a[++p]=u;
        for(int i=h[u];i;i=e[i].ne) 
            if(!vis[e[i].v]) dfs(e[i].v),a[++p]=u;
    }
    int main(){
        //freopen("in","r",stdin);
        n=read();m=read();k=read();
        for(int i=1;i<=m;i++) ins(read(),read());
        dfs(1);
        int c=ceil((double)2*n/k);
        int x=p/c,y=p%c,now=0;
        for(int i=1;i<=k;i++){
            if(i<=x){
                printf("%d ",c);
                for(int j=i;j<=i+c-1;j++) printf("%d ",a[++now]);
            }else if(i==x+1&&y!=0){
                printf("%d ",y);
                for(int j=1;j<=y;j++) printf("%d ",a[++now]);
            }else printf("1 1");
            puts("");
        }
        return 0;
    }

--------------------

[F.http://www.cnblogs.com/candy99/p/6511222.html][F.http_www.cnblogs.com_candy99_p_6511222.html]

[Codeforces Round _403 _Div. 2_ based on Technocup 2017 Finals]: http://codeforces.com/contest/782
[Andryusha and Socks]: http://codeforces.com/contest/782/problem/A
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220330/77642b908e554c69963a2d22b2710633.png
[The Meeting Place Cannot Be Changed]: http://codeforces.com/contest/782/problem/B
[Andryusha and Colored Balloons]: http://codeforces.com/contest/782/problem/C
[Innokenty and a Football League]: http://codeforces.com/contest/782/problem/D
[zyf2000]: http://blog.csdn.net/clove_unique/article/details/60570128
[Underground Lab]: http://codeforces.com/contest/782/problem/E
[F.http_www.cnblogs.com_candy99_p_6511222.html]: http://www.cnblogs.com/candy99/p/6511222.html