Codeforces Round #109 (Div. 1) 题解 【ABC】

A - Hometask

题意：给你一个字符串，然后再给你k个禁止挨在一起的字符串，问你最少删除多少个字符串，使得不会有禁忌的字符串对挨在一起。题目保证每个字符最多出现在一个禁忌中。

题解：由于每个字符只会出现在一个禁忌里面，那么就说明每个询问是独立的。对于每个询问，我们贪心的去处理就好了，就连续的禁忌字符串，我们删除少的那个就好了。

#include<bits/stdc++.h>

using namespace std;

string s,s2;

int ans,a,b,m,c,d;

int main(){

    cin>>s;

    cin>>m;

    for(int i=0;i<m;i++){

        cin>>s2;

        a=0,b=0;

        for(int j=0;j<s.size();j++){

            if(s[j]==s2[0])

                a++;

            else if(s[j]==s2[1])

                b++;

            else

                ans+=min(a,b),a=0,b=0;

        }

        ans+=min(a,b);

    }

    cout<<ans<<endl;

}

B. Colliders

题意：你要实现两个功能，加x和减x。如果是加x的话，那么如果添加x的时候如果已经添加了和他不互质的数的话，那么就输出冲突。否则就加进去。

题解：我们对于每个数的因子都预处理处理啊，这个复杂度是nlogn，然后我们再用个set维护存在这个因子的数的开启个数，然后每次暴力的修改就可以了，这个复杂度是nlognlogn的。

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+7;

int v[maxn],n,m,num;

vector<int>p[maxn];

set<int> S[maxn];

string op;

void pre(){

    for(int i=2;i<maxn;i++){

        for(int j=i;j<maxn;j+=i){

            p[j].push_back(i);

        }

    }

}

void add(int x){

    if(v[x]==1){

        printf("Already on\n");

        return;

    }

    for(int i=0;i<p[x].size();i++){

        if(S[p[x][i]].size()){

            printf("Conflict with %d\n",*S[p[x][i]].begin());

            return;

        }

    }

    for(int i=0;i<p[x].size();i++){

        S[p[x][i]].insert(x);

    }

    printf("Success\n");

    v[x]=1;

}

void del(int x){

    if(v[x]==0){

        printf("Already off\n");

        return;

    }

    for(int i=0;i<p[x].size();i++){

        S[p[x][i]].erase(x);

    }

    printf("Success\n");

    v[x]=0;

}

int main(){

    pre();

    scanf("%d%d",&n,&m);

    for(int i=0;i<m;i++){

        cin>>op>>num;

        if(op[0]=='+')

            add(num);

        else

            del(num);

    }

}

C - Double Profiles

题意：给你一个1e6个点,1e6个边的无向图，然后问你有多少对点，满足这两个点的所连接的点都完全相同。

题解：分为两种情况，(i,j)相互连接的，这样就看边左右的两个点，加上自己这个点的hash值是否相同。不相互连接的，那么显然不加上自己这个点的边集hash是一样的，那么我们排序扫一遍统计即可。

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+7;

int n,m;

int g[2][maxn];

long long p[maxn],k[maxn];

int main(){

    scanf("%d%d",&n,&m);

    p[0]=1;

    for(int i=1;i<maxn;i++)

        p[i]=p[i-1]*31;

    for(int i=0;i<m;i++){

        scanf("%d%d",&g[0][i],&g[1][i]);

        g[0][i]--,g[1][i]--;

        k[g[0][i]]+=p[g[1][i]];

        k[g[1][i]]+=p[g[0][i]];

    }

    long long ans = 0;

    for(int i=0;i<m;i++){

        if(k[g[0][i]]+p[g[0][i]]==k[g[1][i]]+p[g[1][i]])

            ans++;

    }

    sort(k,k+n);

    int i=0,j=1;

    for(i=0;i<n;i=j){

        for(j=i;k[i]==k[j]&&j<n;j++);

        ans=ans+1ll*(j-i)*(j-i-1)/2;

    }

    cout<<ans<<endl;

}

Codeforces Round #109 (Div. 1) 题解 【ABC】的相关教程结束。