集训队日常训练20180513-DIV2

A.2176

给一个字符串s，问距离为D的字母对是否存在相同。

模拟。

#include<bits/stdc++.h>

using namespace std;

int main()

{

    string s,b;

    while(cin>>s)

    {

        if(s[]=='*')break;

        int flag=;

        map<string,int>ma;

        for(int jump=;jump<s.size();jump++)

        {

            ma.clear();

            for(int L=;L+jump<s.size();L++)

            {

                b.clear();

                b+=s[L];

                b+=s[L+jump];

                if(ma[b]==)ma[b]=;

                else

                {

                    flag=;

                    break;

                }

            }

            if(flag==)break;

        }

        if(flag)cout<<s<<" is surprising.\n";

        else cout<<s<<" is NOT surprising.\n";

    }

    return ;

}

A.cpp

B.4694

给两堆糖果，每次从多的那堆拿gcd(a,b)个糖果，lemon先拿，问最后俩人糖果数。

模拟。

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int a,b;

    while(cin>>a>>b,a||b)

    {

        int le=,yu=,sum=;

        while(a||b)

        {

            if(sum%)le+=__gcd(a,b);

            else yu+=__gcd(a,b);

            if(a>b)a-=__gcd(a,b);

            else b-=__gcd(a,b);

            sum++;

            if(a==||b==)

            {

                if(sum%)le+=a+b;

                else yu+=a+b;

                break;

            }

        }

        cout<<le<<" "<<yu<<endl;

    }

    return ;

}

B.cpp

C.5259

给若干多项式和一个x，问多项式值最大和按值分组输出相同值最多的个数。

模拟。

#include <bits/stdc++.h>

#define ll long long

using namespace std;

ll mul(ll a, ll b,int x)

{

    if(b == ) return a;

    while(b--) a*= x;

    return a;

}

int main()

{

    int t; cin >> t;

    while(t--)

    {

        map<ll,int> mp;

        ll  n, x; cin >> n >> x;

        int maxx = -;

        while(n--)

        {

            ll k,sum = ; cin >> k;

            while(k--)

            {

                ll a, b; cin >> a >> b;

                sum += mul(a,b,x);

            }

            mp[sum]++;

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

        }

        map<ll,int>::reverse_iterator it=mp.rbegin();

        cout << it->first << " " << maxx << endl;

    }

    return ;

}

C.cpp

D.5265

给一个围棋谱，问黑棋还需要下在哪才能全围住白棋。

广搜。

#include<bits/stdc++.h>

using namespace std;

char a[][];

int dtx[]={,,,-};

int dty[]={,-,,};

int check(int i,int j)

{

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

    {

        int I=i+dtx[z],J=j+dty[z];

        if(I>=&&I<&&J>=&&J<)

        {

            if(a[I][J]=='W')

            return ;

        }

    }

    return ;

}

int main()

{

    while(gets(a[])!=NULL)

    {

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

            gets(a[i]);

        int sum=;

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

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

            {

                if(a[i][j]=='.')

                    if(check(i,j))

                        cout<<i+<<" "<<j+<<endl,sum++;

            }

        if(sum==)cout<<"YuYu Wins!\n";

    }

    return ;

}

D.cpp

E.5260

给一个1-n的序列，问全排列连接起来第x个数字是几。

模拟。

#include <bits/stdc++.h>

using namespace std;

int s[];

int main()

{

    int n,x,a[],b[],i,z,s1,flag,s2,k;

    while(~scanf("%d%d",&n,&x))

    {

        s1=n;flag=;s2=;k=;

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

        {

            scanf("%d",&z);

            a[i]=b[i]=z;

        }

        sort(a+,a+n+);

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

            s1*=i;

        sort(a,a+n);

        do

        {

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

            {

                if(a[i]!=b[i]) break;

            }

            if(i>n) flag=;

            if(!flag) s2++;

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

                s[k++]=a[i];

        }while(next_permutation(a+,a+n+));

        x+=s2*n;

        x%=s1;

        if(x!=) x--;

        printf("%d\n",s[x]);

    }

    return ;

}

E.cpp

F.4702

给币值为1，3，5，7，9，13的硬币的个数和糖果的价格g，问最少需要多少枚硬币组成g。

背包。

#include<iostream>

#include<stdio.h>

#include<math.h>

using namespace std;

int dp[];

const int LIM=1e9;

int main()

{

    int w[]={,,,,,};

    int v[];

    int t=,g;

    while(t!=)

    {

        int ans=;

        t=;

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

        {

            cin>>v[i];

            if(v[i]==)t++;

        }

        cin>>g;

        if(g==)

            if(t==)

                break;

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

            dp[i]=LIM;

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

            for(int j=;j<=v[i];j++)

                for(int k=g;k>=w[i];k--)

                    dp[k]=min(dp[k-w[i]]+,dp[k]);

        if(dp[g]==LIM)cout<<"impossible"<<endl;

        else cout<<dp[g]<<endl;

    }

    return ;

}

F.cpp

G.3331

给一个2n*2n的网格图，以中心为原点画一个直径为2n-1的圆，问圆周线穿过了多少个格子。

思维。

#include<bits/stdc++.h>

using namespace std;

int arr[];

int main()

{

    int n;

    arr[]=;

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

        arr[i]=arr[i-]+;

    }

    while(cin>>n&&n!=){

        cout << arr[n] <<endl;

    }

    return ;

}

G.cpp

H.4671

给n个数，求前M大并按小到大输出。

只需要记录前M个。

#include<bits/stdc++.h>

using namespace std;

int get() {

 int r=;

 char c;

 while(c=getchar(),!(c>=''&&c<=''));

 r = c-'';

 while(c=getchar(),c>=''&&c<='')

  r = (r*)+c-'';

 return r;

}

int main()

{

    int n,m,x,b[],len=;

    n=get();

    m=get();

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

    {

        x=get();

        if(len<m)b[len++]=x;

        else

            for(int j=;j<m;j++)

                if(b[j]<x)

                    swap(b[j],x);

    }

    sort(b,b+m);

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

    {

        if(i!=)printf(" ");

        printf("%d",b[i]);

    }

    putchar('\n');

    return ;

}

H.cpp

I.4959

给n个数，问能否选若干数使和=k。

深搜。

#include<bits/stdc++.h>

using namespace std;

int n,a[],i,k;

bool dfs(int i,int sum)

{

    if(i==n)

    {

        if(sum==k)return ;

        return ;

    }

    if(dfs(i+,sum))return ;

    if(dfs(i+,sum+a[i]))return ;

    return ;

}

int main()

{

    while(cin>>n>>k)

    {

        for(i=;i<n;i++)cin>>a[i];

        if(dfs(,))printf("Yes\n");

        else printf("No\n");

    }

    return ;

 }

I.cpp

J.4374

n个特工，密钥总量为k（编号为0到k-1），以及每个特工所带的m个密钥，求是否每3个特工的密钥都可以解密文件。

模拟。

#include<bits/stdc++.h>

using namespace std;

int n,m,k;

int check(int a[])

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

        if(a[i]==)

        return ;

        return ;

}

int main()

{

       while(cin>>n>>m>>k)

       {  vector<int> v[];

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

           { int x;

            for(int j=;j<k;j++)

              {cin>>x;

              v[i].push_back(x);}

            }

            int flag=;

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

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

                 {for(int z=j+;z<n;z++)

                   { int a[]={};

                     for(int t=;t<k;t++)

                        { a[v[i][t]]=;

                        a[v[j][t]]=;

                        a[v[z][t]]=;

                         }

                          if(!check(a))flag=;

                   }

                }

            }

            if(flag)cout<<"YES\n";

            else cout<<"NO\n";

       }

}

J.cpp

巴特西

集训队日常训练20180513-DIV2

最新文章

热门文章