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

提示

n,m200000 n, m \le 200000

分析

主要考察图论,以及拓扑排序的思想。
根据题目建图,如果同学 ii 的对象是 TiT_{i},那么就从 iiTiT_{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;
}

斗地主

题目地址

描述

牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的 AAKK加上大小王的共 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

提示

n23,caseNum100 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;
}