Codeforces Round #425 (Div. 2))—

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=;

 using namespace std;

 typedef long long LL;

 int main() {

     ios::sync_with_stdio(false);cin.tie();

     LL n,k;

     LL ct;

     cin>>n>>k;

     if(n%k==){

         ct=n/k;

     }

     else ct=n/k;

     if(ct%){cout<<"YES"<<endl;}

     else cout<<"NO"<<endl;

     return ;

 }

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+;

 using namespace std;

 char a[N],b[N];

 int la,lb,lc,lm;

 int check[]={};

 typedef long long LL;

 int main() {

     ios::sync_with_stdio(false);cin.tie();

     cin>>a>>b;

     la=strlen(a);lb=strlen(b);

     for(int i=;i<la;i++) check[a[i]-'a']=;

     int n;

     cin>>n;

     while(n--){

         char c[N];cin>>c;

         int  lc=strlen(c);

         lm=lb-lc;

         int flag=;

         if(lm>) {cout<<"NO"<<endl;continue;}

         else if(lm==){

             int h=;

             for(int i=;i<lb;i++) if(b[i]=='*') {h=;break;}

             if(h){

                 for(int i=,j=;j<lc;i++){

                     if(b[i]=='*') {continue;}

                     else if(b[i]=='?'){

                         if(check[c[j]-'a']==) {flag=;break;}

                     }

                     else if(b[i]!=c[j]){

                         flag=; break;

                     }

                     j++;

                 }

             }

             else flag=;

         }

         else if(lm==){

             for(int i=;i<lb;i++){

                 if(b[i]=='*'||b[i]=='?'){

                     if(b[i]=='*'){

                         if(check[c[i]-'a']){flag=;break;}

                     }

                     else{

                         if(check[c[i]-'a']==){flag=;break;}

                     }

                 }

                 else if(b[i]!=c[i]){flag=;break;}

             }

         }

         else if(lm<){

             char mb[N];

             lm=-lm+;

             //cout<<lm<<endl;

             int ct=;

             for(int i=,j=;i<lb;i++){

                 if(b[i]=='*'){

                     for(int k=;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=;

             else{

                for(int i=;i<lc;i++){

                     if(mb[i]!=c[i]){

                         flag=;break;

                     }

                }

             }

         }

         if(flag) cout<<"YES"<<endl;

         else cout<<"NO"<<endl;

     }

     return ;

 }

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=+;

 using namespace std;

 typedef long long LL;

 typedef int II;

 vector<int>p[N];

 II n,q;

 II fr[*N],de[*N],pos[*N],tot=;

 II d[N][];

 void RMQ_init(){

     for(II i=;i<=tot;i++) d[i][]=fr[i];

     for(II j=;(<<j)<=tot;j++)

         for(II i=;i+(<<j)-<=tot;i++){

             II x=d[i][j-];

             II y=d[i+(<<(j-))][j-];

             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+))/log(2.0);

     II t1=d[L][k];

     II t2=d[R-(<<k)+][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=;i<p[u].size();i++){

         II v=p[u][i];

         if(v==pre) continue;

         dfs(v,u,dep+);

         fr[++tot]=u;

     }

 }

 II dist(II x,II y){

     II qe=RMQ(x,y);

     int len=de[x]+de[y]-*de[qe];

     return len;

 }

 int main(){

     ios::sync_with_stdio(false);cin.tie();

     cin>>n>>q;

     for(II i=;i<=n;i++){

         II x;

         cin>>x;

         p[i].push_back(x);p[x].push_back(i);

     }

     dfs(,-,);

     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)/+;//y为终点

         ans=max(t,ans);

         t=(lxy+lxz-lyz)/+;//x为终点

         ans=max(t,ans);

         t=(lxz+lyz-lxy)/+;//z为终点

         ans=max(t,ans);

         cout<<ans<<endl;

     }

     return ;

 }

巴特西

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

A. Sasha and Sticks

B. Petya and Exam

D. Misha, Grisha and Underground

最新文章

热门文章