The 2018 ACM-ICPC Asia Qingdao Regional Contest（青岛网络赛）

A Live Love

水

#include <algorithm>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;

const int maxn = 1e5 + ;

int main()

{

    int t;

    scanf("%d", &t);

    while(t--)

    {

        int n,m;

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

        if(m==){

            printf("0 0\n");

            continue;

        }

        if(n==m){

            printf("%d %d\n",n,m);

            continue;

        }

        if(n>=*m-){

            printf("%d %d\n",m,);

            continue;

        }

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

            if (n - m >= (m / i + (m % i != )) - ) {

                printf("%d %d\n", m, i);

                break;

            }

        }

    }

    return ;

}

B Red Black Tree

留坑

C Halting Problem

题意：自定义了一些程序，然后问程序会不会崩溃，也就是会不会有死循环出现

思路：队友写的，大致就是同一步不可以运行一摸一样的两次吧

#include <algorithm>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;

const int maxn = 1e5 + ;

struct com{

    char cm[];

    int v,k;

}prog[];

bool vstd[][];

int main()

{

    int n,t;

    scanf("%d", &t);

    while(t--) {

        scanf("%d",&n);

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

            scanf("%s%d",prog[i].cm,&prog[i].v);

            if(prog[i].cm[]!='a'){

                scanf("%d",&prog[i].k);

            }

        }

        int r=,ins=;

        int flag=;

        memset(vstd,,sizeof(vstd));

        while(true){

            if(ins>n){

                break;

            }

            if(vstd[r][ins]){

                flag=;

                break;

            }

            switch(prog[ins].cm[]){

                case 'd'://+

                    vstd[r][ins]=;

                    r+=prog[ins].v;

                    r%=;

                    ins++;

                    break;

                case 'e'://==

                    vstd[r][ins]=;

                    if(r==prog[ins].v){

                        ins=prog[ins].k;

                    }else{

                        ins++;

                    }

                    break;

                case 'n'://!=

                    vstd[r][ins]=;

                    if(r!=prog[ins].v){

                        ins=prog[ins].k;

                    }else{

                        ins++;

                    }

                    break;

                case 'l'://<

                    vstd[r][ins]=;

                    if(r<prog[ins].v){

                        ins=prog[ins].k;

                    }else{

                        ins++;

                    }

                    break;

                case 'g'://>

                    vstd[r][ins]=;

                    if(r>prog[ins].v){

                        ins=prog[ins].k;

                    }else{

                        ins++;

                    }

                    break;

                default:

                    vstd[r][ins]=;

                    ins++;

                    break;

            }

        }

        if(flag){

            puts("Yes");

        }else{

            puts("No");

        }

    }

    return ;

}

D Pixel Art

留坑

E Infinite Parenthesis Sequence

留坑

F Chaleur

留坑

G Couleur

留坑

H Traveling on the Axis

题意：模拟红绿灯，1过，0停，每一秒之后都会改变所有的灯的状态，1变0，0变1

思路：只需要特判第一步走的需不需要停就可以，之后走起来之后的状态都是重复进行的

#include <algorithm>

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

typedef long long ll;

char rd[];

ll len;

int main()

{

    int n,t;

    while(~scanf("%d",&t)) {

        while (t--) {

            scanf("%s", rd);

            len = strlen(rd);

            long long ans = ;

            long long tmp;

            for (ll i = ; i < len - ; i++) {

                tmp = (len - i - ) * (i + );

                if (rd[i] == rd[i + ])tmp *= ;

                ans += tmp;

            }

            //ll b=0;

            for (ll i = ; i < len; i++) {

                ans += rd[i] == '' ? (len - i) : (len - i) * ;

                //b+=rd[i]=='1'?(len-i):(len-i)*2;

            }

            cout << ans << endl;

        }

    }

    return ;

}

I Kuririn MIRACLE

留坑

J Press the Button

题意：按灯，当灯亮的时候按压可以加分，每一次按都会重置灯的熄灭时间。

思路：可以先找到两个数的最小公倍数，然后就可以按照这个周期进行一些剪枝，在每一次周期或者是最后一次的剩余时间里可以模拟，队友用了栈写之后超时了，后来另一位队友没有用栈就AC了

#include <algorithm>

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

typedef long long ll;

ll gcd(ll x, ll y)

{

    return x % y ==  ? y : gcd(y, x % y);

}

int main()

{

    int t;

    while(~scanf("%d",&t)) {

        while (t--) {

            ll a,b,c,d,v,t;

            scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&d,&v,&t);

            ll time=;

            ll tt=a*c/gcd(a,c);

            ll ta=a,tc=c;

            ll tans=;

            while(ta<=tt || tc<=tt){

                if(ta<=tc){

                    tans+=b;

                    if(ta-time>v){

                        tans--;

                    }

                    time=ta;

                    ta+=a;

                }else if(ta>tc){

                    tans+=d;

                    if(tc-time>v){

                        tans--;

                    }

                    time=tc;

                    tc+=c;

                }

            }

            ll sans=;ta=a,tc=c;

            time=;

            ll res=t%tt;

            while(ta<=res|| tc<=res){

                if(ta<=tc){

                    sans+=b;

                    if(ta-time>v){

                        sans--;

                    }

                    time=ta;

                    ta+=a;

                }else if(ta>tc){

                    sans+=d;

                    if(tc-time>v){

                        sans--;

                    }

                    time=tc;

                    tc+=c;

                }

            }sans+=b+d-;

            cout<<tans*(t/tt)+sans<<endl;

        }

    }

    return ;

}

K XOR Clique

题意：找一个最大的集合，使得这些任意两个异或后的值都比最小的那个小

思路：有个队友说可以用字典树，后来我想了想好像只需要计算每一个2，4，8，16，32，64，128，256，512，1024......这些区间的数字的个数就可以了，因为不同的这些2的次方它们异或之后显然最高位会是1，使得它们肯定会比最小的那个大，所以肯定是在同一个集合里面的，同一个集合里面的它们的第一位是相同的，所以异或之后肯定会比最小的那个数要小，所以统计区间个数就可以了，先打个表记录一下2的次方。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#include<map>

#include<ctime>

using namespace std;

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;

const int maxn = 1e5 + ;

int main()

{

    ll a[];

    int sum[];

    for(ll i=;i<=;i++)

    {

        a[i]=(ll)pow(*1.0,i);

      //  cout<<a[i]<<" ";

    }

    int t;

    while(~scanf("%d",&t))

    {

      while(t--)

      {

          int n;

          scanf("%d",&n);

          memset(sum,,sizeof sum);

          for(int i=;i<n;i++)

          {

              int x;

              scanf("%d",&x);

              for(int num=;num<=;num++)

              {

                  if(x<a[num])

                  {

                      sum[num]++;

                      break;

                  }else

                      continue;

              }

          }

          int maxx=-;

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

              maxx=max(maxx,sum[i]);

          printf("%d\n",maxx);

      }

    }

}

巴特西