CF 396(2) C 简单dp D 并查集 E 二进制拆位+dfs统计

题意：给出a[26]数组，表示26个英文字母能够存在于长度不超过ai的字符串中。把长度为n的字符串分割，要使得分割后的各个字符串中的字母都满足条件。求有多少种方案，能分割出的最长子串的长度，和分割后子串数量的最小值。

题解：看了代码才发现，就是一个水dp。取dp[i]表示长度为i的字符串的分割方案数，然后往前推即可，答案就是dp[n]。但这样复杂度是O(n^2)，(n<1000)，官方题解说有O(n)的做法，不会。。

#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 = 1e3+10, mod = 1e9+7;

int n, a[26], cnt[N], maxn;
ll dp[N];
char s[N];
int main()
{
    cin>>n>>s+1;
    FF(i,0,25) cin>>a[i];
    mes(cnt, INF);
    dp[0]=1, cnt[0]=0;
    FF(i,1,n) {
        int m=a[s[i]-'a'];
        for(int j=i-1; i-j<=m&&j>=0; j--) {
            if(j>=1) m=min(m, a[s[j]-'a']);
            dp[i]=(dp[i]+dp[j])%mod;
            cnt[i]=min(cnt[i], cnt[j]+1);
            maxn=max(maxn, i-j);
        }
    }
    cout<<dp[n]<<endl<<maxn<<endl<<cnt[n]<<endl;

    return 0;
}

View Code

D. Mahmoud and a Dictionary

题意：n个单词，m个关系，每个关系表示两个单词是同义或是反义。q个询问，问两个单词是同义、反义还是没关联。

题解：大神都说是老题，但对我来说还是新题。。。如 i、j是同义，则2*i，2*j相同，2*i-1，2*j-1相同；如 i、j反义，则2*i，2*j-1相同，2*i-1，2*j相同。　　注：并查集变种

// CF396 C
#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 = 1e5+10;

int n, m, q, t, fa[N<<1], a, b;
string s1, s2;
map<string, int >M;
int Find(int c) {
    int p=c, i=c, j;
    while(fa[p]!=p) p=fa[p];
    while(fa[i]!=p) j=fa[i], fa[i]=p, i=j;
    return p;
}
void Unite(int u, int v) {
    int fau=Find(u), fav=Find(v);
    if(fau!=fav) fa[fav]=fau;
}
int main()
{
    cin>>n>>m>>q;
    FF(i,1,n<<1)  fa[i]=i;
    FF(i,1,n)  cin>>s1, M[s1]=i;
    FF(i,1,m) {
        cin>>t>>s1>>s2;
        a=M[s1], b=M[s2];
        if(t==1) {
            if(Find(2*a)==Find(2*b-1)) puts("NO");
            else { Unite(2*a, 2*b); Unite(2*a-1, 2*b-1); puts("YES"); }
        } else {
            if(Find(2*a)==Find(2*b)) puts("NO");
            else { Unite(2*a, 2*b-1); Unite(2*a-1, 2*b); puts("YES"); }
        }
    }
    FF(i,1,q) {
        cin>>s1>>s2;
        a=M[s1], b=M[s2];
        if(Find(2*a)==Find(2*b)) puts("1");
        else if(Find(2*a)==Find(2*b-1)) puts("2");
        else puts("3");
    }

    return 0;
}

View Code

E. Mahmoud and a xor trip

题意：给出一棵树，定义两点之间距离为链上点权的异或和，求所有点对的距离和。

题解：看了别人代码强行敲的，还是不太理解。。。这题首先要想到拆分成二进制每一位对答案的贡献，用ans[i]表示点对距离第i位为1的数量，最后答案就是ret+=(1<<(i-1))*ans[i]，(1<=i<=log2(n))。而如何统计出ans[]，不太懂。。看到有树dp的，也有树分治的。

#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 = 1e5+10, M = 20;

int n, f[N][2], a[N];
ll ans[M], ret;
vector<int >G[N];
void dfs(int u, int fa, int bit)
{
    int t=(a[u]>>bit)&1;
    f[u][0]=f[u][1]=0, f[u][t]=1;
    for(auto v:G[u]) if(v!=fa) {
        dfs(v,u,bit);
        ans[bit]+=1LL*f[v][0]*f[u][1]+1LL*f[v][1]*f[u][0];
        f[u][0]+=f[v][0^t],  f[u][1]+=f[v][1^t];
    }
}
int main()
{
    scanf("%d", &n);
    FF(i,1,n) scanf("%d", &a[i]), ret+=a[i];
    FF(i,1,n-1) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v), G[v].push_back(u);
    }
    FF(i,0,M-1) dfs(1,0,i), ret+=(1LL<<i)*ans[i];
    printf("%lld
", ret);

    return 0;
}

View Code