8.16 test

· · 个人记录

T1

判断特殊情况的时候少打了个感叹号痛失第一（），首先我们要拿到九十分的暴力分只需要老老实实暴力模拟两个字符串就行，而我们可以看到，暴力拿不到的1e5的数据范围有特殊性质，翻译一下就是绝对不存在的意思，所以我们在n超过1e3的数据范围的时候直接输出No Answer!就可以

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin>>n;
    if(n>1000) {
        cout<<"No Answer!";
        return 0;
    }
    string s1,s2,t;
    cin>>s1>>s2>>t;
    int cnt1=0,f1=0;
    for(int i=0; i<n; i++) {
        string ans="";
        if(s1!=t) {
            s1+=s1[0];
            for(int i=1; i<=n; i++) {
                ans=ans+s1[i];
            }
            s1=ans;
            cnt1++;
        } else {
            f1=1;
            break;
        }
    }
    int cnt2=0,f2=0;
    for(int i=0; i<n; i++) {
        string ans="";
        if(s2!=t) {
            s2+=s2[0];
            for(int i=1; i<=n; i++) {
                ans=ans+s2[i];
            }
            s2=ans;
            cnt2++;
        } else {
            f2=1;
            break;
        }
    }
    if(f1==1&&f2==1) {
        if(cnt1<=cnt2) {
            cout<<"XIAO LAI AK IOI!";
        } else {
            cout<<"XIAO MENG AK IOI!";
        }
    } else if(f1==1&&f2!=1) {
        cout<<"XIAO MENG AK IOI!";
    } else if(f1!=1&&f2==1) {
        cout<<"XIAO LAI AK IOI!";
    } else {
        cout<<"No Answer!";
    }
    return 0;
}

T2

可以注意到为了B删减后会在A有一部分前缀和后缀
于是我们枚举这两段，在合法情况下在A中找这两段，然后为了定位精确，创立一个l数组前缀b在a中有多少个位置

#include<bits/stdc++.h>
using namespace std;
long long l[200005],r[200005];
long long ans=0;
int main() {
    long long n,m;
    cin>>n>>m;
    string a,b;
    cin>>a>>b;
    a='#'+a,b='#'+b;
    for(int i=1;i<=n;i++) {
        l[i]=l[i-1]+(a[i]==b[l[i-1]+1]);
    }
    for(int i=n;i>=1;i--) {
        r[i]=r[i+1]+(a[i]==b[m-r[i+1]]);
    }
    for(int i=0;i<=n;i++) {
        ans=max(ans,l[i]+r[i+1]);
    }
    cout<<min(ans,m);
    return 0;
}

T3

首先要满足两张图同构那么点的数量一定是相同的，所以可以先判断两张图的点数是否相同
由于一组映射就可以确定一组边的排列情况，于是可以全排列映射的情况来确定
需要注意的是，可能不相同的映射保留的边是相同的，所以我们用二进制的方法，存储每条边的保存情况

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10;
map<long long,int>mp;
int u1[maxn][maxn];
int u2[maxn][maxn];
int n,m1,m2,n1,n2;
int f[maxn];
int main() {
    cin>>n1>>n2;
    if(n1!=n2) {
        cout<<0;
        return 0;
    }
    n=n1;
    cin>>m1>>m2;
    for(int i=1;i<=m1;i++) {
        int a,b;
        cin>>a>>b;
        u1[a][b]=u2[b][a]=1;
    }
    for(int i=1;i<=m2;i++) {
        int a,b;
        cin>>a>>b;
        u2[a][b]=u2[b][a]=i;
    }
    for(int i=1;i<=n;i++) {
        f[i]=i;
    }
    int res=0;
    do {
        int flag=1;
        long long to=0;
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                if(u1[i][j]) {
                    if(u2[f[i]][f[j]]==0) {
                        flag=0;
                    }
                    to|=1ll<<u2[f[i]][f[j]];
                }
            }
        }
        if(flag&&mp[to]==0) {
            res++;
            mp[to]=1;
        }
    }
    while(next_permutation(f+1,f+1+n));
    cout<<res<<"\n";
    return 0;
}