Codeforces Round #324 (Div. 2) A, B, C, D, E

A. Olesya and Rodion

题目链接：

　　codeforces 584A. Olesya and Rodion

题目描述：

　　给出n, t, 问是否存在一个n位数能被t整除，能的话输出这个数，否则输出-1.  题目太水，加上题目描述是为了确保此题是此题，此题非彼题(看的是同一个题目)

解题思路：

　　当n=1，t=10时输出-1，其他时候先输出一个t，然后其他剩余的位置用0填补。

题目代码：

#include <bits/stdc++.h>
using namespace std;

int main ()
{
    int n, t;
    while (scanf ("%d %d", &n, &t) != EOF)
    {
        if (n == 1 && t == 10)
            {
                printf ("-1
");
                continue;
            }
        if (t == 10)
            n --;
        printf ("%d", t);
        while (-- n)
            printf ("0");
        printf ("
");
    }
    return 0;
}

B. Kolya and Tanya

题目链接：

　　codeforces 584 B. Kolya and Tanya

题目描述：

　　有一个圆环，圆环上有3*n个点，三个点组成一个正三角形。每个点上可以放1, 2 or 3个金币，n个正三角形里的金币总数不能同时等于6。问有多少种摆放方案？

解题思路：

　　每个正三角形有3^3种摆放方式，其中7种方式不合法，那么当有n个正三角形的时候，方案数就为27^n - 7^n.

题目代码：

#include <bits/stdc++.h>
using namespace std;

typedef __int64 LL;
const LL mod = 1000000007;
int main ()
{
    LL n, a, b;
    scanf("%I64d", &n);
    a = 27; b = 7;
    while (-- n)
    {
        a = (a * 27) % mod;
        b = (b * 7) % mod;
    }
    printf ("%I64d
", (a - b + mod) % mod);
    return 0;
}

C. Marina and Vasya

题目链接：

　　codeforces 584 C. Marina and Vasya

题目描述：

　　给出长度都为n的字符串a, b, 输出一个新构造出的串s，存在s[i] == a[i] 的数目与 s[j] == b[j]的数目都等于k。不能构造出这样的新串s，输出-1.

解题思路：

　　怎么构造都可以，题目也是比较水的。扎扎的构造方式是：先把s串置成空，然后把a[i] == b[i]的位置选择前k位放置到s[i]里面。a[i] == b[i]的数目k'小于k的话，找前 k - k' 个 s[i] 为空的位置，使得a[i] == s[i], b字符串同理，然后把s串中当前还是空的位置，赋为!a也!b的字母。如果构造不成功就输出-1即可。

#include <bits/stdc++.h>
using namespace std;

typedef __int64 LL;
const LL maxn = 100010;

int main ()
{
    int n, t;
    char a1[maxn], a2[maxn], ans[maxn];

    while (scanf ("%d %d", &n, &t) != EOF)
    {
        scanf ("%s %s", a1, a2);
        memset (ans, 0, sizeof(ans));
        t = n - t;

        for (int i=0; i<n; i++)
        {
            if (!t)
                break;
            if (a1[i] == a2[i])
            {
                ans[i] = a1[i];
                t --;
            }
        }
        int resa1 = t;
        for (int i=0; i<n; i++)
        {
            if ( !resa1 )
                break;
            if (!ans[i])
            {
                ans[i] = a1[i];
                resa1 --;
            }
        }

        int resa2 = t;
        for (int i=0; i<n; i++)
        {
            if ( !resa2 )
                break;
            if (!ans[i])
            {
                ans[i] = a2[i];
                resa2 --;
            }
        }

        for (int i=0; i<n; i++)
            if ( !ans[i] )
            {
                if (a1[i]!='a' && a2[i]!='a')
                    ans[i] = 'a';
                else if (a1[i]!='b' && a2[i]!='b')
                    ans[i] ='b';
                else
                    ans[i] = 'c';
            }

        if (resa1 || resa2)
            printf("-1
");
        else
            puts (ans);

    }
    return 0;
}

D. Dima and Lisa

题目链接：

　　codeforces 584 D. Dima and Lisa

题目描述：

　　一个数，问是否可以由小于等于3个素数相加得出？可以输出素数的值，否则输出-1.

解题思路：

　　额！这个题目是我胡搞的，我先找出一个小于n但是距离n最近的素数x。由于n和x都是奇数，辣么n-x肯定是偶数咯，然后就拆分n-x，如果n-x可以拆成两个素数就输出这些素数，否则输出-1。写一发，测试实力过了，然后提交，心好虚！但是竟然过了，对的没错就是过了。事后听大家讨论题目好像有什么定理，然后找之。

　　哥德巴赫猜想:任何大于2的偶数都可以用两个素数和来表示。扩展：任何大于5的奇数都可以用三个素数的和来表示。(n-x肯定可以表示为两个素数的和或者是2咯)

题目代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 500;
int mark[maxn], isprime[maxn];

void init ()
{
    int i, j;
    mark[0] = mark[1] = 1;
    for (i=2; i<=maxn; i++)
            for (j=i+i; j<maxn; j+=i)
                mark[j] = 1;
}

int main ()
{
    int n;
    init();

    while (scanf ("%d", &n) != EOF)
    {
        int i, a, b, c, m;

        for (a=n; ; a--)
        {
            if (a == n - 1)
                continue;
            m = (int)sqrt (a);

            for (i=2; i<=m; i++)
                if (a%i == 0)
                    break;

            if (i > m)
                break;

        }
        if (a == n)
            printf ("%d
%d
", 1, n);
        else if (a == n - 2)
            printf ("%d
%d %d
", 2, 2, n-2);
        else
        {
            int m = n - a;
            for (i=2; i<=m-i; i++)
            {
                if (!mark[i] && !mark[m-i])
                {
                    c = i;
                    b = m - i;
                    break;
                }
            }

            printf("%d
%d %d %d
", 3, c, b, a);
        }
    }
    return 0;
}

E. Anton and Ira

题目链接：

　　codeforces 584 E. Anton and Ira

题目描述：

　　给出两个长度都为n的序列a, b。两个序列中的数字都是[1, n]。现在可以交换a中的任意两个元素(a[i], a[j])，交换价值为|i - j|，问最小的交换价值为多少？可以使得strcmp(a, b) == 0.

解题思路：

　　其实这个题目就是需要向前换与需要向后换的数互换，为了保证最优，交换(a[i], a[j])的时候posb[a[i]]<=j && posb[a[j]]>=i.

　　交换的次数还是很多的，结构体数组保存一直WA 14，最后突然醒悟，发现数组开小了........下次遇到不确定大小的数组保证开STL。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 2010;
int a[maxn], b[maxn], posb[maxn];
struct node
{
    int x, y;
    node (int a = 0, int b = 0):x(a),y(b) {}
} p[10000000];

int main ()
{
    int n;
    while (scanf ("%d", &n) != EOF)
    {
        for (int i=1; i<=n; i++)
            scanf ("%d", &a[i]);
        for (int i=1; i<=n; i++)
        {
            scanf ("%d", &b[i]);
            posb[b[i]] = i;
        }

        int res, nu;
        res = nu = 0;
        for (int i=1; i<=n; i++)
        {
            int x = i;
            for (int j=i-1; j>0; j--)
            {
                if (posb[a[j]]>=x && posb[a[x]]<=j)
                {
                    swap (a[x], a[j]);
                    res += abs (x - j);
                    p[nu ++] = node(x, j);
                    x = j;
                }
            }
        }

        printf ("%d
%d
", res, nu);
        for (int i=0; i<nu; i++)
                printf ("%d %d
", p[i].x, p[i].y);
    }
    return 0;
}