Codeforces #397 D 构造 E bfs，思维

题意：x是[1,m]时，g(h(x))=x; x是[1,n]时，h(g(x))=f(x)。给出[1,n]时的f(x)，求可能的m，h(x)，g(x)。

tags：好菜啊，大佬们都是xjb过，本菜鸡想了有2个小时都没想出来==

1、h(g(x))=f(x) -> h(g( h(x) ))=f(h(x))；又因为g(h(x))=x，代入则h(x)=f(h(x))，[1,m]。即有m种情况是y=f(y)，则h[i]=y，同时由h(g(x))=f(x)可求出相应的g[x]。这样可以先求出m个h[]和g[]。 2、由g(h(x))=x，将x用g(x)代掉有g(h( g(x) ))=g(x)；又因h(g(x))=f(x)，则g(f(x))=g(x)；如g(f(x))先在第1步没有求出来，则是不可能情况。这样可以求出剩下的g[]。

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define FF(i,a,b) for (int i=a;i<=b;i++)
#define F(i,b,a)  for (int i=b;i>=a;i--)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
typedef long long ll;
const int N = 1e6+10;

int n, m, f[N], h[N], g[N], vis[N];
int main()
{
    cin>>n;
    FF(i,1,n) {
        cin>>f[i];
        if(i==f[i]) h[++m]=i, g[i]=m, vis[i]=1;
    }
    if(m==0) return 0*puts("-1");
    FF(i,1,n) if(g[i]==0) {
        if(vis[f[i]]==0) return 0*puts("-1");
        else g[i]=g[f[i]];
    }
    cout<<m<<endl;
    FF(i,1,n) cout<<g[i]<<" "; puts("");
    FF(i,1,m) cout<<h[i]<<" "; puts("");

    return 0;
}

View Code

E. Tree Folding

题意：一棵树，有一个操作：如果两条链长度相同且有同一个端点，就可以删除掉其中一条链。问最后是否可以变成一条链，如可以，求这条链最短长度。

tags：从叶子节点开始往内bfs，走到分叉点的时候，用set保存当前的路径长度信息，最后只要check一下，看是不是所有的节点里面，只有最多一个节点的set的size是等于2的。然后求路径长度不断对折好了。注：这里用set来存size，很巧妙地利用set的去重性质。　　有点考思维，知道思路了都还写矬了几发。。

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define FF(i,a,b) for (int i=a;i<=b;i++)
#define F(i,b,a)  for (int i=b;i>=a;i--)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
typedef long long ll;
const int N = 2e5+10;

int n, vis[N], de[N], ans;
vector<int >G[N];
queue<int >Q;
set<int >S[N];
void bfs()
{
    FF(i,1,n) if(de[i]==1) Q.push(i), S[i].insert(0);
    while(!Q.empty()) {
        int u=Q.front();
        Q.pop();
        vis[u]=1;
        for(auto v : G[u])  if(vis[v]==0) {
            S[v].insert(*S[u].begin()+1);
            de[v]--;
            if(S[v].size()==1 && de[v]==1) Q.push(v);
        }
    }
}
int main()
{
    scanf("%d", &n);
    int u, v, cnt=0;
    FF(i,1,n-1) {
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
        de[u]++, de[v]++;
    }
    bfs();
    FF(i,1,n) {
        if(S[i].size()>2 || S[i].size()==0) return 0*puts("-1");
        else if(S[i].size()==2) cnt++, ans=max(ans, *S[i].begin()+*S[i].rbegin());
        else ans=max(ans, *S[i].begin());
    }
    if(cnt>1) return 0*puts("-1");
    while(ans%2==0)  ans=ans/2;
    printf("%d
", ans);

    return 0;
}

View Code