Codeforces Round #319 (Div. 2) B C D

這場題目挺水的。。感覺半小時能出3題。。可惜沒有注冊。。

B. Modulo Sum

題意：給100w個數，問是否存在子序列使得整個子序列的和能夠整除m。

思路：将所有數對m取模，然後問題就轉化成了一個多重背包問題，數比較多需要優化一下。不知道為什麼過的人這麼少。。

#include <cstdio>
#include <cstring>
int nums[100000], mod[3010], cnt;
bool dp[3010], dp2[3010];
main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) {
        long long a;
        scanf("%I64d", &a);
        mod[a % m]++;
    }
    for(int i = 0; i < m; i++){
        if(mod[i] == 0) continue;
        int total = mod[i];
        long long a = 1;
        while(total >= a){
            nums[cnt++] = (i * a) % m;
            total -= a;
            a <<= 1;
        }
        if(total > 0) nums[cnt++] = (i * total) % m;
    }
    for(int i = 0; i < cnt; i++){
        memset(dp2, 0, sizeof dp2);
        for(int j = 0; j < m; j++){
            dp2[(j + nums[i]) % m] |= dp[j];
        }
        for(int j = 0; j < m; j++)
            dp[j] |= dp2[j];
        dp[nums[i]] = true;
    }
    if(dp[0]) puts("YES");
    else puts("NO");
}
           

C. Vasya and Petya's Game

題意：兩個人玩遊戲，V君想一個1~n的整數，P君可以詢問V君這個數是否可以整除某個整數數K，詢問次數不限，問最少需要詢問多少次可以确定這個數。

思路：這題看樣例也能猜個差不多。。也很容易就能想到：任意一個大于等于2的自然數都是若幹質數的乘積，是以隻要詢問1~n範圍内所有的質數和質數的若幹次方能否被這個數整除就可以了。

#include <cstdio>
bool vis[1010], ans[1010];
int prim[1010], cnt;
main() {
    int n;
    scanf("%d", &n);
    for(int i = 2; i <= n; i++){
        if(vis[i] == false){
            prim[cnt++] = i;
            for(int j = i * i; j <= n; j += i) vis[j] = true;
        }
    }
    int total = 0;
    for(int i = 0; i < cnt; i++){
        for(int j = prim[i]; j <= n; j *= prim[i])
            ans[j] = true;
    }
    for(int i = 2; i <= n; i++) if(ans[i]) total++;
    printf("%d\n", total);
    for(int i = 2; i <= n; i++) if(ans[i]) printf("%d ", i);
}
           

D. Invariance of Tree

題意：給一個序列P1P2...Pn，若一棵樹上任意兩點u和v有一條邊相連，那麼這棵樹上Pu和Pv也有一條邊相連，問這棵樹是否存在，如果存在輸出任意一種樹的n-1條邊。

思路：這個題不是很有想法。。雖然想到找環但是沒有想清楚。。看了tutorial才明白：

這些數字可以分成若幹組，每組都會形成一個互不相交的環（集合）， 可以通過i=Pi遞歸找到每個環。

讓所有環和一個”中心環“建邊（可以把環想成點），這樣就形成了一棵樹，也不會再次構成環。

但是在建邊的時候邊需要錯開，這樣其他環的點的個數必須是中心環的整數倍（畫個圖就很容易想明白）。

因為其他所有環都要和中心環相連構成樹，是以中心環内的點之間需要建邊構成樹。

而中心環的點要循環和其他環建邊，是以中心環的點的個數要少于3個（大于等于3個的時候就會形成環）。

這樣我們就需要做這幾件事情：

1.尋找環内點個數為1或2的環作為“中心環”，沒有則不能成樹；

2.如果中心環點數為1，那麼一定可以成樹，讓這個點和其他各點建邊即可；

   如果中心環點數為2，那麼其他環的點的個數必須是偶數，否則不能成樹，然後中心環兩點循環與其他環建邊，中心環兩點間也要建邊。

#include <cstdio>
#include <vector>
using namespace std;

vector<int>link[100020];
bool vis[100020];
int p[100020];
main() {
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &p[i]);
    int one = 0, two = 0;
    for(int i = 1; i <= n; i++){
        if(vis[i]) continue;
        int v = i;
        while(!vis[v]){
            link[i].push_back(v);
            vis[v] = true;
            v = p[v];
        }
        if(link[i].size() == 1) one = i;
        else if(link[i].size() == 2) two = i;
    }
    if(one){
        puts("YES");
        for(int i = 1; i <= n; i++){
            if(i != one) printf("%d %d\n", one, i);
        }
    }
    else if(two){
        bool flag = true;
        for(int i = 1; i <= n; i++)
            if(link[i].size() % 2)
                flag = false;
        if(!flag) puts("NO");
        else {
            puts("YES");
            printf("%d %d\n", link[two][0], link[two][1]);
            for(int i = 1; i <= n; i++){
                if(two != i){
                    for(int j = 0; j < link[i].size(); j++)
                        printf("%d %d\n", link[two][j & 1], link[i][j]);
                }
            }
        }
    }
    else puts("NO");
}