好久没刷题了，前几天做google笔试生疏了很多，还是需要刷刷题，保持头脑灵活。不过codeforces题目一般都在晚上，真心没精力熬夜，只能改天起来再搞。这次是几天前的比赛。

A.Olesya and Rodion

简单题

B.Kolya and Tanya

简单题

C.Marina and Vasya

  题意：给定两个字符串s1, s2，给定t，问是否存在一个相同长度的字符串与s1, s2各有t个字符不一致（位置不变）。
  思路：判断s1和s2存在几个相同字符（相同位置），记为nr。记t=n-t，意味着找出n-t个一样的字符即可。则若不满足t - nr > (n - nr) / 2则不存在，反之存在。若t<=nr则这几个相同字符之内选t个即可，否则再把不一样的字符里面选t-nr个变为一样。
  代码：

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <memory.h>

using namespace std;  
const int SIZE = 100100;  
#define Clear(f, nr) memset(f, nr, sizeof(f))

char different(char a, char b) {  
    char tmp = min(a, b);
    tmp = (tmp - 'a' + 1) % 26 + 'a';
    if(tmp == a || tmp == b)
        tmp = (tmp - 'a' + 1) % 26 + 'a';
    return tmp;
}

int main() {  
    int n, t;
    string a, b;
    bool mark[SIZE];
    while(cin >> n >> t) {
        cin >> a >> b;
        t = n - t;
        string c = a;
        Clear(mark, 0);
        int nr = 0;
        for(int i = 0; i < a.size(); i ++) {
            if(a[i] == b[i]) {
                mark[i] = 1;
                nr ++;
            }
        }
        if(t > nr && t - nr > (n - nr) / 2)
            puts("-1");
        else {
            if(t <= nr) {
                int cnt = t;
                for(int i = 0; i < a.size(); i ++) {
                    if(mark[i] && cnt > 0) {
                        c[i] = a[i];
                        cnt --;
                    }
                    else {
                        c[i] = different(a[i], b[i]);
                    }
                }
            }
            else {
                int cnt = t - nr;
                int rec = -cnt;
                for(int i = 0; i < a.size(); i ++) {
                    if(mark[i])
                        c[i] = a[i];
                    else if(cnt > 0) {
                        c[i] = a[i];
                        cnt --;
                    }
                    else if(cnt > rec) {
                        c[i] = b[i];
                        cnt --;
                    }
                    else {
                        c[i] = different(a[i], b[i]);
                    }
                }
            }
            cout << c << endl;
        }
    }
} 

D.Dima and Lisa

  题意：给定任意一个奇数，表示成三个素数加和，三个素数可以相同。
  思路：将这个奇数减去3后即为哥德巴赫猜想：任何一个大于等于4偶数都可以表示成两个质数的相加。n为10^9次，没必要把素数表打到10^9，只要打到sqrt(10^9)次即可。素数判断以及打表模板参考别人的。剩下的暴力即可。
  代码：

#include <iostream>
#include <vector>
#include <cstdio>
#include <memory.h>

using namespace std;

#define Clear(f, nr) memset(f, nr, sizeof(f))
const int INF = 1 << 30;  
const int SIZE = 10000100;  
typedef long long ll;

vector<int> prime;  
bool isPrime[SIZE];

void getPrime() {  
    Clear(isPrime, 1);
    isPrime[1] = 0;
    for(int i = 2; i < SIZE - 1; i ++) {
        if(!isPrime[i])
            continue;
        for(int j = i * 2; j < SIZE - 1; j += i)
            isPrime[j] = 0;
    }
    for(int i = 2; i < SIZE; i ++) {
        if(isPrime[i])
            prime.push_back(i);
    }
}

bool judge(int x) {  
    int cnt = 0;
    ll tmp;
    for(int i = 0; i < prime.size(); i ++) {
        tmp = prime[i];
        if(tmp * tmp >= x)
            break;
        while(x % tmp == 0) {
            x /= tmp;
            cnt ++;
        }
    }
    while(x % tmp == 0) {
        x /= tmp;
        cnt ++;
    }
    if(x != 1) cnt ++;
    return cnt == 1;
}

int main() {  
    getPrime();
    int n;
    while(cin >> n) {
        if(judge(n)) {
            printf("1\n%d\n", n);
            continue;
        }
        n -= 3;
        if(n == 4) {
            printf("3\n3 2 2\n");
            continue;
        }
        if(judge(n)) {
            printf("2\n3 %d\n", n);
            continue;
        }
        int i = n / 2;
        if(i % 2 == 0) 
            i --;
        for(; i >= 2; i -= 2) {
            if(judge(i) && judge(n - i)) {
                printf("3\n3 %d %d\n", i, n - i);  
                break;
            }
        }
    }
}

E.Anton and Ira

  题意：给定p，s序列，p可以通过两两置换得到s，置换p[i]和p[j]的代价为abs(i - j)，输出最小的置换代价，以及置换次数和置换序列。
  思路：一开始以为是置换群问题，后来发现置换次数没必要取最小，只要保证置换代价最小即可。首先将s序列看成1-n排列，再根据s的映射顺序将p依次求映射后的号码，比如对于p: 7 4 6 2 5 1 3; s: 7 5 6 1 3 2 4，首先将s映射成1 2 3 4 5 6 7，则根据s映射规则，p变成1 7 3 6 2 4 5。然后只要操作p就可以，每次将大的元素向右置换，但必须保证与其置换的元素必须小于等于当前位置，比如7与2换。这是为了保证当前元素向右靠近最终位置的同时，小的元素也向左靠近其本来位置。原理是因为：1移到5，1可以通过2到5，也可以通过3,4到5，也可以直接到5，代价都一致，所以贪心保证移动过程小的元素在本次左移动中获益。
  代码：

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <memory.h>
#include <map>

using namespace std;

#define Clear(f, nr) memset(f, nr, sizeof(f))
const int INF = 1 << 30;  
const int SIZE = 2020;  
typedef long long ll;

int main() {  
    int n;
    map<int, int> locate;
    int s[SIZE], p[SIZE];
    bool vis[SIZE];
    vector<pair<int, int> > ans;
    while(scanf("%d", &n) != EOF) {
        locate.clear();
        Clear(vis, 0);
        ans.clear();
        for(int i = 1; i <= n; i ++)
            scanf("%d", &p[i]);
        for(int i = 1; i <= n; i ++) {
            scanf("%d", &s[i]);
            locate[s[i]] = i;
        }
        for(int i = 1; i <= n; i ++)
            p[i] = locate[p[i]];

        int cost = 0, cnt = 0;
        for(int i = n; i >= 1; i --) {
            if(p[i] == i)
                continue;
            int pos;
            for(int j = 1; j <= n; j ++)
                if(p[j] == i) {
                    pos = j;
                    break;
                }
            for(int j = pos + 1; j <= n; j ++) {
                if(p[j] <= pos) {
                    ans.push_back(make_pair(pos, j));
                    swap(p[j], p[pos]);
                    cost += abs(pos - j);
                    cnt ++;
                    pos = j;
                } 
            }
        }
        printf("%d\n%d\n", cost, cnt);
        for(int i = 0; i < ans.size(); i ++)
            //cout << ans[i].first << " " << ans[i].second << endl;
            printf("%d %d\n", ans[i].first, ans[i].second);
    }
}

参考：

http://www.bubuko.com/infodetail-1129420.html