2016-2017 ACM Central Region of Russia Quarterfinal Programming Contest

A. Fried Fish

题意：有N条鱼，有一个同时可以煎k条鱼的锅，鱼两个面都要煎；

分析：k*2个面要煎，是否有一种方式可以让锅没有空闲，当时我举了几个例子，确实可以找到，没有证明，注意n<k的情况

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int main()

{

    freopen("INPUT.TXT","r",stdin);

    freopen("OUTPUT.TXT","w",stdout);

    int x,y;

    while(scanf("%d%d",&x,&y)!= EOF)

    {

        if(2*x<=y)

        printf("2\n");

        else

        {

            if((2*x)%y==0)

            printf("%d\n",(2*x)/y);

            else

            printf("%d\n",(2*x)/y+1);

        }

    }

    return 0;

}

B. Hanoi tower

题意：用给出的汉诺塔算法，求出第一次相同时的步数；

分析：

网上有一个公式：先求出n层从A到B的步数：d(n)=d(n-1)*2+1

然后：ans(n)= d(n/3*2-1)+d(n/3-1)+1

勉强这个方案可以看懂，的确要比ans(n)=d(n/32)+d(n/3)或者 2d(n/3) 要小，

但是，最后有一个特判，不是很懂；

回到原题，直接根据给出的算法，打表求解，前几项分别是:

2 9 38 135 542 2079

直接给出公式把：强烈推荐python 写大整数

a = [0]*105

#print a

a[1] = 2

a[2] = 9

deta = 97

for i in range(3,103):

    if i%2==1:

        a[i] = a[i-1]*4+2

    else:

        a[i] = a[i-1]+deta

        deta = 16*deta - 15

cin = open("input.txt","r")

cout = open("output.txt","w")

n = int(int(cin.read())/3)

cout.write(str(a[n]))

打表程序：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <iostream>

#include <vector>

#include <queue>

#include <set>

using namespace std;

typedef long long ll;

int k;

int ans;

int num[3];

void hanoi(char x,char y,char z,int n) {

    if(n>0) {

        hanoi(x,z,y,n-1);

        printf("------->%d: %d%d%d\n",k++,--num[x-'a'],++num[y-'a'],num[z-'a']);

        //k++;

        //num[x-'a']--;

        //num[y-'a']++;

        //if(num[x-'a']==num[y-'a']&&num[y-'a']==num[z-'a']) {

          //  ans = k;

            //return ;

        //}

        hanoi(z,y,x,n-1);

    }

}

int main()

{

    freopen("output.txt","w",stdout);

    int n;

    scanf("%d",&n);

    k = 1;

    num[0] = n;

    hanoi('a','b','c',n);

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

    return 0;

}

D. Weather Station

题意：有8个方向，给出一个字符串，求这个字符串可能是几种方案合成的

分析：乘法原理，d(i) 是前 i 项字符的方案数，当i+1 个字符串可能模棱两可，那么这里就有两种可能，于是：d(i+1)= d(i)*2

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100000 + 5;

char str[maxn];

const int MOD = 1000000000+7;

int main()

{

    freopen("input.txt","r",stdin);

    freopen("output.txt","w",stdout);

    scanf("%s",str);

    int len = strlen(str);

    int ans = 1;

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

    {

        if(str[i]=='N'&&str[i+1]=='E')

            ans = ans*2%MOD;

        else if(str[i]=='S'&&str[i+1]=='W')

            ans = ans*2%MOD;

        else if(str[i]=='S'&&str[i+1]=='E')

            ans = ans*2%MOD;

        else if(str[i]=='N'&&str[i+1]=='W')

            ans = ans*2%MOD;

    }

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

    return 0;

}

E. Cupcakes

题意：有n个学生，来排队吃蛋糕k个，领完后又到队列后面可以继续吃，每个学生最多能吃a_i个，有一个大胃王，每次都吃完a_i，现在大家想让他吃的时候恰好没有蛋糕了，求是不是可能；

分析：贪心极端情况，当轮到大胃王吃的时候，如果，前面的人最少，最多能吃[l,r]个，k在个区间，于是就可以做到；

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100000+5;

long long a[maxn];

int main()

{

    freopen("input.txt","r",stdin);

    freopen("output.txt","w",stdout);

    int n;

    long long k;

    scanf("%d%lld",&n,&k);

    long long x = 0;

    int flag = -1;

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

        scanf("%lld",&a[i]);

        if(a[i]>x) {

            flag = i;

            x = max(x,a[i]);

        }

    }

    long long l = 0,r=0;

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

        l ++;

        r +=a[i];

    }

    if(l<=k&&r>=k) {

        puts("YES");

        return 0;

    }

    while(l<=r) {

        l+=x;

        r+=x;

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

        {

            l++;

            r = r + a[i];

        }

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

            l++;

            r = r + a[i];

        }

        if(l<=k&&r>=k) {

            puts("YES");

            return 0;

        }

        else if(l>k)

            break;

    }

    puts("KEK");

    return 0;

}

G. Sphenic numbers

题意：一个数是否是三个素数的乘积

分析：直接质因数分解

#include<bits/stdc++.h>

using namespace std;

const int maxn = 10467397 + 105;

vector<int> primes;

bool bo[maxn+5];

int prime_table() {

    int i,j,cnt=0;

    bo[0]=bo[1]=true;

    for(i=2; i<=sqrt(maxn*1.0); i++)

        if(!bo[i]) {

            j=i*i;

            for(; j<=maxn; j+=i)

                bo[j]=true;

        }

    for(i=0; i<=maxn; i++)

        if(!bo[i])

            primes.push_back(i);

    return primes.size();

}

bool add_int(int n){

    int e = 0;

    for(int i = 0; i < primes.size(); i++){

        bool f = true;

        while(n % primes[i] == 0){

            n /= primes[i];

            if(f){

                f = false;

                e++;

            }

        }

        if(n == 1)

            return e == 3;

    }

}

int main() {

//    freopen("in.txt", "r", stdin);

    freopen("input.txt", "r", stdin);

    freopen("output.txt", "w", stdout);

    int n;

    prime_table();

    scanf("%d", &n);

    puts(add_int(n) ? "YES" : "NO");

    return 0;

}

H. Non-random numbers

题意：生成一个n位的随机数，有多少种数，有三条规则：

没有前导零
第 i 位不是 i
n 位

分析：第一位8种，后面9种，再后面10种，不用写大整数.

#include <bits/stdc++.h>

using namespace std;

int main()

{

    freopen("input.txt","r",stdin);

    freopen("output.txt","w",stdout);

    int n;

    scanf("%d",&n);

    unsigned long long ans = 1;

    if(n<=9) {

        n--;

        ans = 8;

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

            ans = ans *9;

        cout<<ans<<endl;

    }

    else {

        ans = 8;

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

            ans = ans*9;

        cout<<ans;

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

            printf("%d",0);

        puts("");

    }

    return 0;

}

J. Architect of Your Own Fortune

题意：有两种票，可以折叠起来拼成一种超级幸运票，求最多能匹配多少张？

分析：最大匹配

#include <bits/stdc++.h>

using namespace std;

const int maxn = 500+5;

struct BPM

{

    int n,m;

    vector<int> G[maxn];

    int left[maxn];

    bool T[maxn];

    int right[maxn];

    bool S[maxn];

    void init(int n,int m)

    {

        this->n = n;

        this->m = m;

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

            G[i].clear();

    }

    void AddEdge(int u,int v)

    {

        G[u].push_back(v);

    }

    bool match(int u)

    {

        S[u] = true;

        for(int i=0; i<G[u].size(); i++)

        {

            int v = G[u][i];

            if(!T[v])

            {

                T[v] = true;

                if(left[v]==-1||match(left[v]))

                {

                    left[v] = u;

                    right[u] = v;

                    return true;

                }

            }

        }

        return false;

    }

    int solve()

    {

        memset(left,-1,sizeof(left));

        memset(right,-1,sizeof(right));

        int ans = 0;

        for(int u=0; u<n; u++)

        {

            memset(S,0,sizeof(S));

            memset(T,0,sizeof(T));

            if(match(u))

                ans++;

        }

        return ans;

    }

} sol;

char a[maxn][10];

char b[maxn][10];

int main()

{

    freopen("input.txt","r",stdin);

    freopen("output.txt","w",stdout);

    int n,m;

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

    sol.init(n,m);

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

        scanf("%s",a[i]);

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

        scanf("%s",b[i]);

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

    {

        int aa = a[i][0]-'0' + a[i][1] -'0' + a[i][2]-'0';

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

        {

            int bb = b[j][3]-'0'+b[j][4]-'0'+b[j][5]-'0';

            if(aa==bb)

                sol.AddEdge(i,j);

        }

    }

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

    {

        int aa = a[i][3]-'0' + a[i][4] -'0' + a[i][5]-'0';

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

        {

            int bb = b[j][0]-'0' + b[j][1] -'0' + b[j][2]-'0';

            if(aa==bb)

                sol.AddEdge(i,j);

        }

    }

    printf("%d\n",sol.solve());

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

        if(sol.right[i]!=-1) {

            int j = sol.right[i];

            int aa = a[i][0]-'0' + a[i][1] -'0' + a[i][2]-'0';

            int bb = b[j][3]-'0'+b[j][4]-'0'+b[j][5]-'0';

            if(aa==bb)

                printf("AT %s %s\n",a[i],b[j]);

            else printf("TA %s %s\n",b[j],a[i]);

        }

    }

    return 0;

}

巴特西

2016-2017 ACM Central Region of Russia Quarterfinal Programming Contest

最新文章

热门文章