Codeforces Round #425 (Div. 2))——A题&&B题&&D题

A. Sasha and Sticks

题目链接：http://codeforces.com/contest/832/problem/A

题目意思：n个棍，双方每次取k个，取得多次数的人获胜，Sasha先取，问Sasha是否可以取胜。

代码：

//Author: xiaowuga
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <ctime>
#include <map>
#include <bitset>
#include <cctype>
#define maxx INT_MAX
#define minn INT_MIN
#define inf 0x3f3f3f3f
#define mem(s,ch) memset(s,ch,sizeof(s))
const long long N=100; 
using namespace std;
typedef long long LL;
int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    LL n,k;
    LL ct;
    cin>>n>>k;
    if(n%k==0){
        ct=n/k;
    }
    else ct=n/k;
    if(ct%2){cout<<"YES"<<endl;}
    else cout<<"NO"<<endl;
    return 0;
}

B. Petya and Exam

题目链接：http://codeforces.com/contest/832/problem/B

题目意思：一个xjb大模拟。第一行是好字符（26个），除此之外都是坏字符，第二行是B字符串，B中问号可以change为好字符，* 只能change为坏字符串（字符可以有可以0~MAX个），接下来n次询问，每次给出目标C字符串，问B可以change为C么？

思路：这个题真的wa了很多发啊…………，分四种情况:1.询问串长度大于模式串且差大于1；2.询问串长度大于模式串且差等于1，3.询问串长度等于模式串；4.询问串长度小于模式串。

其中在情况1的时候，还要判断是否出现过*，因为可能没有出现过*，整体的思路就是先把*代表东西补出来，然后安慰比较久可以了。

代码：

//Author: xiaowuga
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <ctime>
#include <map>
#include <bitset>
#include <cctype>
#define maxx INT_MAX
#define minn INT_MIN
#define inf 0x3f3f3f3f
#define mem(s,ch) memset(s,ch,sizeof(s))
const long long N=1e5+10;
using namespace std;
char a[N],b[N];
int la,lb,lc,lm;
int check[26]={0};
typedef long long LL;
int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>a>>b;
    la=strlen(a);lb=strlen(b);
    for(int i=0;i<la;i++) check[a[i]-'a']=1;
    int n;  
    cin>>n;
    while(n--){
        char c[N];cin>>c;
        int  lc=strlen(c);
        lm=lb-lc;
        int flag=1;
        if(lm>1) {cout<<"NO"<<endl;continue;}
        else if(lm==1){
            int h=0;
            for(int i=0;i<lb;i++) if(b[i]=='*') {h=1;break;}
            if(h){
                for(int i=0,j=0;j<lc;i++){
                    if(b[i]=='*') {continue;}
                    else if(b[i]=='?'){
                        if(check[c[j]-'a']==0) {flag=0;break;}  
                    }
                    else if(b[i]!=c[j]){
                        flag=0; break;
                    }
                    j++;
                }
            }
            else flag=0;
            
        }
        else if(lm==0){
            for(int i=0;i<lb;i++){
                if(b[i]=='*'||b[i]=='?'){
                    if(b[i]=='*'){
                        if(check[c[i]-'a']){flag=0;break;}
                    }
                    else{
                        if(check[c[i]-'a']==0){flag=0;break;}
                    }
                }
                else if(b[i]!=c[i]){flag=0;break;}
            }
        }
        else if(lm<0){
            char mb[N];
            lm=-lm+1;
            //cout<<lm<<endl;
            int ct=0;
            for(int i=0,j=0;i<lb;i++){
                if(b[i]=='*'){
                    for(int k=0;k<lm;k++){
                       if(check[c[j]-'a']){ mb[ct++]='?';}
                       else   mb[ct++]=c[j++];
                    }
                    continue;
                }
                else if(b[i]=='?'){
                    if(check[c[j]-'a']) mb[ct++]=c[j];
                    else mb[ct++]='?';
                }
                else if(b[i]!=c[j]) { mb[ct++]=b[i];}
                else mb[ct++]=c[j];
                j++;
            }
            if(ct<lc) flag=0;
            else{
               for(int i=0;i<lc;i++){
                    if(mb[i]!=c[i]){
                        flag=0;break;
                    }
               } 
            }
        }
        if(flag) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
        
    }
    return 0;
}

D. Misha, Grisha and Underground

题目链接：http://codeforces.com/contest/832/problem/D

题目意思：LCA模板题，可以数到标签的数量等于(dist（a,b）+dist（c,b）-dist（a,c）)/2+1。两点之间的距离可以用LCA算出。这里LCA用的是基于DFS序的RMQ算法。

代码：

//Author: xiaowuga
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <ctime>
#include <map>
#include <bitset>
#include <cctype>
#define maxx INT_MAX
#define minn INT_MIN
#define inf 0x3f3f3f3f
#define mem(s,ch) memset(s,ch,sizeof(s))
#define nc cout<<"nc"<<endl
const long long N=200000+1000;
using namespace std;
typedef long long LL;
typedef int II;
vector<int>p[N];
II n,q;
II fr[2*N],de[2*N],pos[2*N],tot=0;
II d[N][65];
void RMQ_init(){
    for(II i=1;i<=tot;i++) d[i][0]=fr[i];
    for(II j=1;(1<<j)<=tot;j++)
        for(II i=1;i+(1<<j)-1<=tot;i++){
            II x=d[i][j-1];
            II y=d[i+(1<<(j-1))][j-1];
            if(de[x]<de[y]) d[i][j]=x;
            else d[i][j]=y;
        }
}
II RMQ(II x,II y){
    II L=min(pos[x],pos[y]),R=max(pos[x],pos[y]);
    II k=log((double)(R-L+1))/log(2.0);
    II t1=d[L][k];
    II t2=d[R-(1<<k)+1][k];
    if(de[t1]<de[t2]) return t1;
    else return t2;
}

void dfs(II u,II pre,II dep){
    fr[++tot]=u;pos[u]=tot;de[u]=dep;
    for(II i=0;i<p[u].size();i++){
        II v=p[u][i];
        if(v==pre) continue;
        dfs(v,u,dep+1);
        fr[++tot]=u;
    }
}

II dist(II x,II y){
    II qe=RMQ(x,y); 
    int len=de[x]+de[y]-2*de[qe];
    return len; 
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>q;
    for(II i=2;i<=n;i++){
        II x;
        cin>>x;
        p[i].push_back(x);p[x].push_back(i);
    } 
    dfs(1,-1,1);
    RMQ_init();
    while(q--){
        II x,y,z;
        cin>>x>>y>>z;
        II t,ans=minn;
        II lxy=dist(x,y),lxz=dist(x,z),lyz=dist(y,z);
        t=(lxy+lyz-lxz)/2+1;//y为终点
        ans=max(t,ans);
        t=(lxy+lxz-lyz)/2+1;//x为终点
        ans=max(t,ans);
        t=(lxz+lyz-lxy)/2+1;//z为终点
        ans=max(t,ans);
        cout<<ans<<endl; 
    }
    return 0;
}