Codeforces Round #396 (Div. 2) 题解

题目链接：http://codeforces.com/contest/766

A. Mahmoud and Longest Uncommon Subsequence

解法：水题，如果两个字符串不完全一样的话，最长不同子串肯定是其中最长的字符串。

#include <bits/stdc++.h>
using namespace std;

int main(){
    string a,b;
    cin>>a>>b;
    if(a==b) puts("-1");
    else cout<<max(a.size(),b.size())<<endl;
    return 0;
}

B. Mahmoud and a Triangle

题意：给你N条边，让你判断是否能够用其中三条边整出来一个三角形。

解法：直接将边按照从小到大排序。然后相邻的三条边进行判断即可。脑补理由。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
int n, a[maxn];

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1, a+n+1);
    int flag = 0;
    for(int i = 2; i <= n-1; i++){
        if(a[i]+a[i-1] > a[i+1]) flag = 1;
    }
    if(flag) puts("YES");
    else puts("NO");
}

C. Mahmoud and a Message

题意：给定一个小写字母组成的字符串和每个小写字母最多存在长度为a[i]的子串中，输出满足条件的分割方案数，并输出所有方案中最长子串的长度和最少的分割次数。

解法：设dp【i】表示前 i 个字母中有多少种合法的方案，则总方案数就是dp【n】。那么方案转移方程：dp【i】=dp【i】+dp【j】，注意转移方程的条件。

    #include<bits/stdc++.h>  
    using namespace std;  
    const int mod=1e9+7;  
    int a[35];  
    int dp[3][3000];  
    int main()  
    {  
        int n;  
        cin>>n;  
        string s;  
        cin>>s;  
        for(int i=0;i<26;i++) cin>>a[i];  
        dp[0][0]=1;  
        for(int i=1;i<=n;i++){  
            int len=mod;  
            dp[1][i]=-mod;  
            dp[2][i]=mod;  
            for(int j=i-1;j>=0;--j)  
            {  
                len=min(len,a[s[j]-'a']);  
                if(len>=i-j)  
                {  
                    //方案数  
                    dp[0][i]=(dp[0][i]+dp[0][j])%mod;  
                    //子串最大长度   
                    dp[1][i]=max(dp[1][i],max(i-j,dp[1][j]) );  
                    //最小子串数   
                    dp[2][i]=min(dp[2][i],dp[2][j]+1);   
                }         
            }  
        }  
        cout<<dp[0][n]<<endl<<dp[1][n]<<endl<<dp[2][n]<<endl;   
        return 0;  
    }

D. Mahmoud and a Dictionary

题意：给你n个串，然后给你m个关系，p个询问。每个关系告诉你两个单词是同义还是反义的，如果与之前的不矛盾的话，输出yes；如果矛盾，就忽略这次操作，输出no。对于每个询问，如果两个单词是同义输出1，反义输出2，不知道输出3.

解法：POJ食物链经典套路。我们用并查集去做，让2i表示这个词，2i-1表示这个词的反义。如果i和j同义，就说明2i和2j一样，2i-1和2j-1一样。如果反义，就说明2i-1和2j一样，2i和2j-1一样。然后check就好了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
int n, m, q;
map <string, int> mp;
string s[maxn];
namespace dsu{
    int fa[maxn];
    inline void init(){for(int i = 1; i <= 2*n; i++) fa[i] = i;}
    inline int find_set(int x){if(x == fa[x]) return x; else return fa[x] = find_set(fa[x]);}
    inline void union_set(int x, int y){int fx = find_set(x), fy = find_set(y); if(fx != fy) fa[fx] = fy;}
}
using namespace dsu;
int main()
{
    scanf("%d%d%d", &n, &m, &q);
    init();
    for(int i = 1; i <= n; i++) cin >> s[i], mp[s[i]] = i;
    for(int i = 1; i <= m; i++){
        int cmd; string a, b;
        cin >> cmd >> a >> b;
        int id1 = mp[a], id2 = mp[b];
        if(cmd == 1){//同意
            if(find_set(id1*2) == find_set(id2*2-1)){
                puts("NO");
                continue;
            }
            if(find_set(id1*2-1) == find_set(id2*2)){
                puts("NO");
                continue;
            }
            puts("YES");
            union_set(id1*2, id2*2);
            union_set(id1*2-1, id2*2-1);
        }
        else{//反义
            if(find_set(id1*2) == find_set(id2*2)){
                puts("NO");
                continue;
            }
            if(find_set(id1*2-1) == find_set(id2*2-1)){
                puts("NO");
                continue;
            }
            puts("YES");
            union_set(id1*2, id2*2-1);
            union_set(id1*2-1, id2*2);
        }
    }
    while(q--)
    {
        string a, b;
        cin >> a >> b;
        int id1 = mp[a], id2 = mp[b];
        if(find_set(2*id1) == find_set(2*id2)) puts("1");
        else if(find_set(2*id1-1) == find_set(2*id2-1)) puts("1");
        else if(find_set(2*id1-1) == find_set(2*id2)) puts("2");
        else if(find_set(2*id1) == find_set(2*id2 - 1)) puts("2");
        else puts("3");
    }
    return 0;
}

E. Mahmoud and a xor trip

题意：给定一颗n节点的树以及每个节点的权值，另dis(u,v)表示节点u到v路径上的异或和，求不大于i的节点与i组成的有序对的距离的和（1<=i<=n）。
解法：位运算的话大多可以想到按位拆分，统计每一位对答案的贡献，因为每一位的运算都是独立的。所以按位枚举，假设当前是第b位，则dp[x][0]表示以x为根节点的异或值为0的路径的数量，dp[x][1]也是如此定义。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
LL dp[maxn][2], a[maxn];
LL ans = 0;
int head[maxn], edgecnt;
struct edge{
    int to,next;
}E[maxn*2];
void init(){
    memset(head,-1,sizeof(head));
    edgecnt=0;
}
void add(int u,int v){
    E[edgecnt].to=v,E[edgecnt].next=head[u],head[u]=edgecnt++;
}
void dfs(int x, int fa, int bit){
    LL q = 0;
    LL b = (a[x] >> bit) & 1;
    dp[x][b] = 1;//init
    dp[x][b^1] = 0;
    for(int i=head[x]; ~i; i=E[i].next){
        int v = E[i].to;
        if(v == fa) continue;
        dfs(v, x, bit);
        q += dp[x][0] * dp[v][1] + dp[x][1] * dp[v][0];//统计子节点到x的路径上异或和，只需算1^0与0^1即可
        dp[x][b^0] += dp[v][0];//更新异或操作后的状态值。
        dp[x][b^1] += dp[v][1];
    }
    ans +=  (q << bit);
}
int main(){
    int n;
    init();
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%lld", &a[i]), ans += a[i];
    for(int i=1; i<n; i++){
        int u, v;
        scanf("%d %d", &u,&v);
        add(u, v);
        add(v, u);
    }
    for(int i=0; i<=20; i++) dfs(1, -1, i);
    printf("%lld\n", ans);
    return 0;
}