NOIP 2015 Day 1 详细题解

Published on 2015-11-21

感觉网上的题解很不全，只有只言片语，零零散散的，于是自己写了一份。
如果题目有些遗忘了，最好回忆一下题目再看题解。有些题目的解很可能不是最优的，欢迎各路神犇留言。

神奇的幻方

题目地址

描述

幻方是一种很神奇的 N×NN \times N 矩阵：它由数字 构成，且每行、每列及两条对角线上的数字之和都相同。
当 NN 为奇数时，我们可以通过下方法构建一个幻方：
首先将 11 写在第一行的中间。
之后，按如下方式从小到大依次填写每个数 ：
1.若 在第一行但不在最后一列，则将 KK 填在最后一行， 所在列的右一列；
2.若 在最后一列但不在第一行，则将 KK 填在第一列， 所在行的上一行；
3.若 在第一行最后一列，则将 KK 填在 的正下方；
4.若 既不在第一行，也最后一列，如果 的右上方还未填数，则将 KK 填在 的右上方，否则将 L 填在 的正下方。
现给定 NN ，请按上述方法构造 N×NN \times N 的幻方。

分析

主要考察条件语句的使用。
先直接放置第一个数，用 lastx,lasty\mathrm{lastx}, \mathrm{lasty} 分别记录上一次放置数的位置，然后根据题意模拟就可以了。

代码

/* Sengxian */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 39 + 3;
int n;
int magic[maxn][maxn];

void solve() {
    memset(magic, 0, sizeof(magic));
    int lastx, lasty;
    magic[0][n / 2] = 1;
    lastx = 0; lasty = n / 2;
    for(int i = 2; i <= n * n; ++i) {
        if(!lastx && lasty + 1 != n) {
            lastx = n - 1;
            lasty = lasty + 1;            
        }else if(lasty + 1 == n && lastx) {
            lasty = 0;
            lastx = lastx - 1;
        }else if(!lastx && lasty + 1 == n) {
            lastx = lastx + 1;
        }else if(!magic[lastx - 1][lasty + 1]) {
            lastx = lastx - 1;
            lasty = lasty + 1;
        }else {
            lastx = lastx + 1;
        }
        magic[lastx][lasty] = i;
    }
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            printf("%d%c", magic[i][j], j + 1 == n ? '\n' : ' ');
}

int main() {
        scanf("%d", &n);
        solve();
        return 0;
}

信息传递

题目地址

描述

有 nn 个同学（编号为 11 到 nn ）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 ii 的同学的信息传递对象是编号为 TiT_{i} 的同学。
游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息， 但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自 己的生日时，游戏结束。请问该游戏一共可以进行几轮？

提示

n,m≤200000 n, m \le 200000

分析

主要考察图论，以及拓扑排序的思想。
根据题目建图，如果同学 ii 的对象是 TiT_{i}，那么就从 ii 到 TiT_{i} 连一条有向边，那么题目就转化为找有向图中最短的环的长度。
我们可以知道，对于那些入度为 00 的点，它肯定无法走回自己（被告知自己的生日），删掉他不影响。
然后循环删去所有入度为 00 的点，剩下的都是环，DFS 一遍ok。
复杂度 O(n) O(n) （我的代码没写好，采用队列优化可以降到 O(n)O(n)）。

代码

/* Sengxian */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 200000 + 5;
int G[maxn];
int in[maxn];
int n;
bool vis[maxn];

bool deleteV() {
    bool updated = false;
    for(int i = 0; i < n; ++i)
        if(!in[i] && !vis[i]) {
            updated = true;
            in[G[i]]--;
            G[i] = -1;
            vis[i] = true;
        }
    return updated;
}

int dfs(int cur, int ori) {
    if(cur == ori && vis[ori]) return 0;
    vis[cur] = true;
    return dfs(G[cur], ori) + 1;
}

void solve() {
    int ans = n + 10;
    while(deleteV()); 
    for(int i = 0; i < n; ++i)
        if(!vis[i])
            ans = min(ans, dfs(i, i));
    printf("%d", ans);
}

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        int to; scanf("%d", &to); to--; //0 - indexed
        in[to]++;
        G[i] = to;
    }
    solve();
    return 0;
}

斗地主

题目地址

描述

牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的 AA 到 KK加上大小王的共 5454 张牌来进行的扑克牌游戏。在斗地主中，牌的大小关 系根据牌的数码表示如下： 3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王，而花色并不对牌的大小产生影响。每一局游戏中，一副手牌由 nn 张牌组成。游戏者每次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。
现在，牛牛只想知道，对于自己的若干组手牌，分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。
需要注意的是，本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。具体规则如下：

牌型牌型说明牌型举例
火箭即双王（双鬼牌）♂ ♀
炸弹四张同点牌。♠A ♥A ♣A ♦A
单张牌单张牌♠3
对子牌两张码数相同的牌♠2 ♥2
三张牌三张码数相同的牌♠3 ♥3 ♣3
三带一三张码数相同的牌 + 一张单牌♠3 ♥3 ♣3 ♠4
三带二三张码数相同的牌 + 一对牌♠3 ♥3 ♣3 ♠4 ♥4
单顺子五张或更多码数连续的单牌（不包括 2 点和双王）♠7 ♣8 ♠9 ♣10 ♣J
双顺子三对或更多码数连续的对牌（不包括 2 点和双王）♣3 ♥3 ♠4 ♥4 ♠5 ♥5
三顺子二个或更多码数连续的三张牌（不能包括 2 点和双王）♠3 ♥3 ♣3 ♠4 ♥4 ♣4 ♠5 ♦5 ♥5
四带二四张码数相同的牌+任意两张单牌（或任意两对牌）♠5 ♥5 ♣5 ♦5 ♣3 ♣8

提示

n≤23,caseNum≤100 n \le 23, \mathrm{caseNum} \le 100

分析

主要考察模拟、搜索及其优化。
看到整整 1G1G 内存，瞬间想到了状态压缩dp，每次出牌转移，但是最多的状态数足足有 2232^{23} 种，转移的代价也是不小，还有多组数据，不足以在规定的时限内通过。
乍一想，因为有单牌的情况，所以记忆递归应该与状态压缩dp的状态数是一样的，好像并不可行。
不难想到，结果与出牌顺序一定没有关系，单牌一张张出，和单牌一口气都出完，一定是一样的。
所以在每次转移的时候，我们先不考虑单牌。如果当前的牌面可以出组合牌，那么我们就不考虑单牌。如果不能出组合牌，只能出单牌了，那就一口气出完，出牌次数直接加剩余的牌的数量就可以了。
这样，可以避免涉及全部的状态。在搜索中，如何精简状态数，是至关重要的。
更优的方法，可以 BFS，决策与刚才一样，一旦出完就可以跳出，干净利落。
如何压状态以及细节见代码。

代码

//  Created by Sengxian on 11/20/15.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  搜索
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
const int maxk = 14;
typedef long long ll;
int n, cards[maxk];
map<ll, int> mem;

//将当前牌压缩
inline ll Zip() {
    ll state = 0;
    for(int i = 0; i < maxk; ++i) {
        state = state * 5 + cards[i];
    }
    return state;
}

int Search() {
    ll state = Zip();
    int ans = 30;
    if(state == 0) return 0;
    if(mem.count(state)) return mem[state];
    bool flag = false;

    //炸弹
    for(int i = 0; i < maxk - 1; ++i)
        if(cards[i] == 4) {
            cards[i] -= 4;
            ans = min(ans, Search() + 1); flag = true;
            cards[i] += 4;
        }

    //对子&火箭
    for(int i = 0; i < maxk; ++i)
        if(cards[i] >= 2) {
            cards[i] -= 2;
            ans = min(ans, Search() + 1); flag = true;
            cards[i] += 2;
        }

    //三张牌
    for(int i = 0; i < maxk - 1; ++i)
        if(cards[i] >= 3) {
            cards[i] -= 3;
            ans = min(ans, Search() + 1); flag = true;
            cards[i] += 3;
        }

    //三带一（可以带火箭）
    for(int i = 0; i < maxk - 1; ++i)
        if(cards[i] >= 3) {
            cards[i] -= 3;
            for(int j = 0; j < maxk; ++j)
                if(cards[j] > 0) {
                    cards[j]--;
                    ans = min(ans, Search() + 1); flag = true;
                    cards[j]++;
                }
            cards[i] += 3;
        }

    //三带二（不能带火箭）
    for(int i = 0; i < maxk - 1; ++i)
        if(cards[i] >= 3) {
            cards[i] -= 3;
            for(int j = 0; j < maxk - 1; ++j)
                if(cards[j] >= 2) {
                    cards[j] -= 2;
                    ans = min(ans, Search() + 1); flag = true;
                    cards[j] += 2;
                }
            cards[i] += 3;
        }

    //单顺子
    for(int i = 0; i < maxk - 2 - 4; ++i)
        if(cards[i] && cards[i+1] && cards[i+2] && cards[i+3] && cards[i+4]) {
            cards[i]--; cards[i+1]--; cards[i+2]--; cards[i+3]--; cards[i+4]--;
            ans = min(ans, Search() + 1); flag = true;
            int j;
            for(j = i + 5; j < maxk - 2; ++j) {
                if(!cards[j]) {
                    break;
                }else {
                    cards[j]--;
                    ans = min(ans, Search() + 1);
                }
             }
            for(int k = i; k < j; ++k)
                cards[k]++;
        }

    //双顺子
    for(int i = 0; i < maxk - 2 - 2; ++i)
        if(cards[i] >= 2 && cards[i+1] >= 2 && cards[i+2] >= 2) {
            cards[i] -= 2; cards[i+1] -= 2; cards[i+2] -= 2;
            ans = min(ans, Search() + 1); flag = true;
            int j;
            for(j = i + 3; j < maxk - 2; ++j) {
                if(cards[j] < 2) {
                    break;
                }else {
                    cards[j] -= 2;
                    ans = min(ans, Search() + 1);
                }
             }
            for(int k = i; k < j; ++k)
                cards[k] += 2;
        }

    //三顺子
    for(int i = 0; i < maxk - 2 - 1; ++i)
        if(cards[i] >= 3 && cards[i+1] >= 3) {
            cards[i] -= 3; cards[i+1] -= 3;
            ans = min(ans, Search() + 1); flag = true;
            int j;
            for(j = i + 2; j < maxk - 2; ++j) {
                if(cards[j] < 3) {
                    break;
                }else {
                    cards[j] -= 3;
                    ans = min(ans, Search() + 1);
                }
            }
            for(int k = i; k < j; ++k)
                cards[k] += 3;
        }

    //四带二    
    for(int i = 0; i < maxk - 1; ++i)
        if(cards[i] == 4) {
            cards[i] -= 4;
            for(int j = 0; j < maxk; ++j) {
                if(!cards[j]) continue;
                cards[j]--;
                for(int k = 0; k < maxk; ++k) {
                    if(!cards[k]) continue;
                    cards[k]--;
                    ans = min(ans, Search() + 1); flag = true;
                    cards[k]++;
                }
                cards[j]++;
            }
            for(int j = 0; j < maxk; ++j) {
                if(cards[j] < 2) continue;
                cards[j] -= 2;
                for(int k = 0; k < maxk; ++k) {
                    if(cards[k] < 2) continue;
                    cards[k] -= 2;
                    ans = min(ans, Search() + 1); flag = true;
                    cards[k] += 2;
                }
                cards[j] += 2;
            }
            cards[i] += 4;
        }

    //一口气出完单牌
    if(!flag) {
        ans = 0;
        for(int i = 0; i < maxk; ++i)
            ans += cards[i];
    }
    return mem[state] = ans;
}

int main() {
    int caseNum = 0;
    scanf("%d%d", &caseNum, &n);
    while(caseNum--) {
        fill(cards, cards + maxk, 0);
        for(int i = 0; i < n; ++i) {
            int a, b; scanf("%d%d", &a, &b);
            if(a == 0) cards[13]++;
            else if(a == 1) cards[11]++;
            else if(a == 2) cards[12]++;
            else cards[a - 3]++;
        }
        printf("%d\n", Search());
        mem.clear();
    }
    return 0;
}
NOIP 2015 Day 2 详细题解