Codeforces Round #402 (Div. 1) 题解（待续）

A String Game

#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
                        For(j,m-1) cout<<a[i][j]<<' ';\
                        cout<<a[i][m]<<endl; \
                        } 
#pragma
#define
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
    int x=0,f=1; char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
    return x*f;
} 
#define
char s[MAXN],t[MAXN];
int a[MAXN];
int n,l;
char s2[MAXN];
bool check(int m) {
    int cnt=0;
    For(i,n) if (a[i]>m) s2[cnt++]=s[i];
    int p=0;
    Rep(i,cnt) {
        if (s2[i]==t[p]) ++p;
        if (p==l) return 1;
    }return 0;
}
int main()
{
//  freopen("A.in","r",stdin);
//  freopen(".out","w",stdout);

    cin>>(s+1)>>t;
    n=strlen(s+1),l=strlen(t);
    For(i,n) {
        int p=read();
        a[p]=i;
    }
    int l=0,r=n,ans=0;
    while(l<=r) {
        int m=(l+r)/2;
        if (check(m)) ans=m,l=m+1;else r=m-1;
    }
    cout<<ans<<endl;
    return 0;
}

B Bitwise Formula

这不是NOI原题

#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
                        For(j,m-1) cout<<a[i][j]<<' ';\
                        cout<<a[i][m]<<endl; \
                        } 
#pragma
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
    int x=0,f=1; char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
    return x*f;
} 
int n,m;
#define
char s[5123];
map<string,string> h,h2;
stringstream ss;
string s0,s1;
bool b;
string get(string s) {
    if (s[0]=='0'||s[0]=='1') return s;
    if (s[0]=='?') {
        if (b==0) return s0;
        return s1; 

    }
    if (b==0) return h[s];
    return h2[s]; 
}
string get(string s,string op,string s2) {
    s=get(s),s2=get(s2);
    if (op=="XOR") {
        Rep(i,m) s[i]='0'+((s[i]-'0')^(s2[i]-'0'));
    }
    else if (op=="AND") {
        Rep(i,m) s[i]='0'+((s[i]-'0')&(s2[i]-'0'));
    }
    else {
        Rep(i,m) s[i]='0'+((s[i]-'0')|(s2[i]-'0'));
    }return s;
}
int f[MAXN][2]={};
int main()
{
//  freopen("B.in","r",stdin);
//  freopen(".out","w",stdout);

    cin>>n>>m;
    s0=string(m,'0');
    s1=string(m,'1');
//  cout<<s0<<endl;
    cin.getline(s,5120);
    For(i,n) {
        cin.getline(s,5120);
//      cout<<s<<endl;
        ss<<s;
        string s1,p,s2,s3,s4;
        bool fl=0;
        ss>>s1>>p>>s2;
        fl= (ss>>s3>>s4);
        b=0;
        if (!fl) {
            h[s1]=get(s2);
        } else {
            h[s1]=get(s2,s3,s4);
        }
        b=1;
        if (!fl) {
            h2[s1]=get(s2);
        } else {
            h2[s1]=get(s2,s3,s4);
        }

        ss.clear();
//      cout<<h[s1]<<endl;
//      cout<<h2[s1]<<endl;

        p=h[s1];
        Rep(i,m) if (p[i]=='1') ++f[i][0];
        p=h2[s1];
        Rep(i,m) if (p[i]=='1') ++f[i][1];

    }

    Rep(i,m) {
        if (f[i][0]<=f[i][1]) putchar('0');
        else putchar('1');      
    }
    cout<<endl;
    Rep(i,m) {
        if (f[i][0]>=f[i][1]) putchar('0');
        else putchar('1');      
    }
    cout<<endl;

    return 0;
}

C Peterson Polyglot

直接启发式合并字典树暴力计数（这怎么能是正解系列）

#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
                        For(j,m-1) cout<<a[i][j]<<' ';\
                        cout<<a[i][m]<<endl; \
                        } 
#pragma
#define
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
    int x=0,f=1; char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
    return x*f;
} 
#define
struct node {
    int ch[26];
}t[MAXN];
int n,cnt,c[MAXN]={};
int merge(int x,int y,int d) {
    if (!x||!y) return x+y;
    c[d]++;
    int p=++cnt;
    Rep(i,26) t[p].ch[i]=merge(t[x].ch[i],t[y].ch[i],d);
    return p;
} 
void dfs(int u,int d) {
    Rep(i,26) if (t[u].ch[i]) 
        dfs(t[u].ch[i],d+1);
    int rt = 0;
    Rep(i,26) rt=merge(rt,t[u].ch[i],d);
    if (rt) c[d]++;
}
int main()
{
//  freopen("C.in","r",stdin);
//  freopen(".out","w",stdout);
    n=read();
    For(i,n-1) {
        int u,v; char c;
        scanf("%d %d %c",&u,&v,&c);
        t[u].ch[c-'a']=v;
    } 
    cnt=n;
    dfs(1,1);
    cout<<n-*max_element(c,c+n)<<endl;
    cout<<(max_element(c,c+n)-c)<<endl;
    return 0;
}