【2016常州一中夏令营Day6】

小 W 算树
【问题描述】
山有苞棣,隰有树檖。未见君子,忧心如醉~
小 W 养了一棵有 N 个点的无根树，由于小 M 最喜欢二叉树了，为了讨小 M 欢喜，小 W想知道有多少个点作为根后，这棵树是一棵二叉树。注：二叉树，即每个节点最多有两个孩子的有根树。
【输入格式】
第一行一个整数 N，代表点数。
接下来 N-1 行，每行两个整数 X、Y，表示 X、Y 之间有一条连边。
【输出格式】
第一行一个整数 M，代表有 M 个点符合条件。
第二行 M 个用空格隔开的整数，为符合要求的点的编号，升序排列。
【输入输出样例】
root.in
4
1 2
1 3
1 4

root.out
3
2 3 4

【数据规模】
对于 20%的数据：N<=3
对于 40%的数据：N<=4
对于 60%的数据：N<=100
对于 80%的数据：N<=1000
对于 100%的数据：N<=100000

题解

如果树中某个点的度数大于3，则不存在可行解。

否则，如果树中某个点的度数小于3，即为可行解。

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int n;
bool flag;
int ind[100005],ans[100005];

int main()
{
    int i,j,x,y;
    freopen("root.in","r",stdin);
    freopen("root.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n-1;i++)
    {
        scanf("%d%d",&x,&y);
        ind[x]++;
        ind[y]++;
        if(!flag&&(ind[x]>3||ind[y]>3)) flag=true;
    }
    if(flag) goto hhh;
    for(i=1;i<=n;i++)
     if(ind[i]==1||ind[i]==2)
     {
         ans[0]++;
         ans[ans[0]]=i;
     }
     hhh:;
     printf("%d
",ans[0]);
     for(i=1;i<=ans[0];i++)
      printf("%d ",ans[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

小 W 算数
【问题描述】
投我以木桃，报之以琼瑶~
得到树的小 M 非常开心，回送小 W 一个名单，名单背后藏着甜蜜的秘密！名单里名字都很奇怪，并且很多捣乱的同学把自己等价名字写很多次。
现在小 M 告诉小 W 名字的等价方式：
1. 选择一个名字 S
2. 选择 S 的一个偶数长前缀 T
3. 把 T 反转，得到新的 S
例如：‘wrhmly’->‘rwhmly’->‘mhwrly’->‘hmwrly’
为了使秘密更容易浮现，等价可传递：A 和 B 等价，B 和 C 等价，那么 A 和 C 也等价。
小 W 需要每次取两个等价的名字，把它们去掉，求出最后剩下多少名字。
【输入格式】
第一行一个整数 N，代表名字个数。
第 2 到 N+1 行，每行一个字符串表示一个名字。
【输出格式】
一行一个整数，表示剩下名字个数。
【输入输出样例】
list.in
20
iprlzgukfggzg
bmhxvjbrtkbxy
khapjiabbny
nqlwgmcyvdikt
nxromtvtpug
leealcapovm
ushnxwjczczbmd
bwhykzupcux
xrlboyuwlnsp
bbjoketeheezfs
dxfztrldomjqkv
dkbktqdtgfujcut
zfybzyuxgpnt
ffmsldrdftode
vopuufksxd
pqhbsiujwda
yhwbkzupcux
hkbabnapjiy
zqsqefrrzehtxn
yovinyguyudmv

list.out
16

list.in
7
esprit
wrhmly
jitui
tujii
mhwrly
hmwrly
tirpse

list.out
1
【数据规模】
对于 20%的数据：N<=20，字符串长度<=8
对于 100%的数据：N<=50
字符串长度最多为 50

题解

易证，一个长度为偶数的字符串 $s$ 中，若每一对 $s_i,s_{i+1}(i&1)$ 在另一个字符串 $r$ 中的 $r_i,r_{i+1}(i&1)$ 都有出现过的话(顺序任意)，这两个字符串依题意认定为相同。

哈希后暴力枚举判断，记得判重。

长度为奇数的话最后一位一定相同，特判即可。

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

int n,ans;
int len[105],hash[105],f[105],fa[105];
bool flag,u[100005];
char str[105][105];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
bool work(int x,int y)
{
    int i,j,k,l;
    bool gg,b[105];
    l=len[x];
    for(i=1;i<=l;i++) b[i]=false;
    if(l&1&&str[x][l]!=str[y][l]) return false;
    if(l&1)l--;
    
    for(i=1;i<=l-1;i+=2)
    {
        gg=true;
        for(j=1;j<=l-1;j+=2)
         if(!b[j])
         {
             if((str[x][i]==str[y][j]&&str[x][i+1]==str[y][j+1])
             ||(str[x][i+1]==str[y][j]&&str[x][i]==str[y][j+1]))
             {
                 gg=false;
                 b[j]=true;
                 break;
             }
         }
        if(gg) return false;
    }
    return true;
}

int main()
{
    int i,j,fx,fy;
    for(i=2;i<=1000;i++)
    freopen("list.in","r",stdin);
    freopen("list.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("
%s",str[i]+1);
        len[i]=strlen(str[i]+1);
        for(j=1;j<=len[i];j++)
         hash[i]+=str[i][j];
    }
    for(i=1;i<=n;i++) f[i]=i;
    
    for(i=1;i<=n;i++)
     for(j=i+1;j<=n;j++)
     {
         if(len[i]!=len[j]||hash[i]!=hash[j]) continue;
         fx=find(i);
         fy=find(j);
         if(fx!=fy)
         {
             flag=work(i,j);
             if(flag)
            {
                 f[fx]=fy;
                 break;
            }
         }
     }
    for(i=1;i<=n;i++) fa[find(i)]++;
    for(i=1;i<=n;i++)
     if(fa[i])
       if(fa[i]&1) fa[i]=1;
       else fa[i]=0;
    for(i=1;i<=n;i++) ans+=fa[i];
    printf("%d",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

小 W 算术
【问题描述】
匪报也，永以为好也~
小 W 解开名单，一张地图浮现出来。图上有 N 个城市，M 条双向道路，每条道路都有长度 C。小 W 在城市 S，小 M 在城市 T。
地图上有 Q 个询问，给出 u、v，询问直接连接 u、v 城市的道路不通后小 W 离小 M 的最近距离。
为了小 W 尽快找到小 M，地图上两个城市之间最多只有一条道路。
【输入格式】
第一行两个整数 N,M，表示城市个数和道路数。
之后 M 行，每行三个整数 x，y，c，表示 x 和 y 城市之间有一条长度为 c 的道路。
之后一行两个整数 S,T，表示小 W 和小 M 的位置。
之后一行一个整数 Q，表示询问个数。
之后 Q 行，每行两个整数 u，v。
【输出格式】
对于每个询问，用一行输出最短长度，如果删除道路后不通则输出“Infinity”。
【输入输出样例】
dream.in
6 7
1 2 1
2 3 1
3 4 2
4 5 1
5 6 1
1 3 3
4 6 3
1 6
4
1 2
1 3
4 3
6 5

dream.out
7
6
Infinity
7
【数据规模】
对于 20%的数据：1<=N,M,Q<=1000
对于 100%的数据：1<=N,M,Q<=200000,1<=c<=10^9

题解

方法一：dijkstra+线段树

详情请见：http://tonyfang.is-programmer.com/posts/205232.html

方法二：

首先我们分别做两次最短路计算出 $disx[i]$ 以及 $disy[i]$ 分别表示 $s$ 到 $i$ 的最短路长度和 $t$ 到 $i$ 的最短路长度。
如果 $disx[u]=w(u,v)+disy[v]$ 则向图 $G'$ 中添加边 $(u,v)$
由于所有边权都为正整数，所以很容易看出 $G'$ 是一个有向无环图。
然后考虑 $G'$ 里所有这样的边 $(u,v)$ 即删除 $(u,v)$ 之后 $s$ 和 $t$ 不再连通，我们不妨称它们为关键边。容易当发现删除的边不是关键边时，答案始终为 $disx[t]$ 。所以我们只考虑删除关键边的询问。关键边即为割边。
我们求出关键边之后，可以发现这些关键边把整个图 $G'$ 分割成了若干个联通块，而且这些连通块可以排成一个序列。
然后我们从左到右处理所有的联通块，并用一个堆维护块与块之间的边。维护方式如下：
假设当前处理的联通块为 $T$ ，我们把所有起点在 $T$ 里，终点在 $T$ 之后的联通块里的边 $(u,v)$
添加进堆里，权值为 $disx[u]=w(u,v)+disy[v]$ 当我们处理一个关键边询问的时候，直接输出堆里的最小元素就行了。
当联通块 $T$ 处理完成后，我们把所有终点在 $T$ 里的边从堆里删除。也可以去堆顶是判断该边的终点是否在所在关键边之前。
每条边只会入堆一次出堆一次，保证时间复杂度。