[20151019]SCZ训练

题1：生日派对

题目描述：
小X过生日了，他邀请了很多小朋友来玩游戏。
共n个小朋友坐成一个大圆圈，第i个小朋友坐在第i-1和i+1个小朋友之间，第1个和第n个小朋友座位相邻。游戏开始了，每个小朋友写下一个整数，每次一个小朋友站起来沿着大家转一圈，看到一个小朋友写的整数是他写的因数，就拍一下那个小朋友的头，然后回到座位上。
小Y作为朋友的一员，突发奇想，想知道每个小朋友分别拍了别人几下头。

输入格式：
第1行：一个整数n。
第2..n+1行：第i+1行表示第i个小朋友写的数A_i。

输入样例：
5
2
1
2
3
4

输出格式：
第1..n行：每行一个数，表示第i个小朋友拍了别人几个头。

输出样例：
2
0
2
1
3

数据范围：
对于40%的数据 n<=5000。
对于100%的数据 n<=100000，1<=A_i<=1000000。

Solution :
模拟埃氏筛法，理论复杂度上限是$lim=\sum_{i = 1}^{10^5}$$\frac{10^6}{i}$，这个数大概是$1.2×10^6$，快的飞起来
【听说根号大力也能过

Code :

/*************************************************************************
    > File Name: patheads.cpp
    > Author: Archer
 ************************************************************************/

#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
#define REP(i, l, r) for (int i = l; i <= r; i++)
#define MP make_pair
const int N = 1111111;
PII a[N];
int n, cnt[N], h[N], ans[N];
inline void setIO(){
    freopen("patheads.in", "r", stdin);
    freopen("patheads.out", "w", stdout);
}
inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - '0' ; ch = getchar();}
    return f == 1 ? x : -x;
}
int main(){
    setIO();

    n = read();
    REP(i, 1, n) a[i] = MP(read(), i);
    REP(i, 1, n) cnt[a[i].first]++;
    sort(a + 1, a + 1 + n);

    REP(i, 1, n){
        ans[a[i].second] = h[a[i].first];
        if (a[i].first == a[i - 1].first) continue;
        ans[a[i].second] += cnt[a[i].first];
        int now = a[i].first; 
        while (now <= 1000000) h[now] += cnt[a[i].first], now += a[i].first;
    }

    REP(i, 1, n) printf("%d\n", ans[i] - 1);

    return 0;
}

题2：工作安排

题目描述：
假设当前有n（n<=12）个工作，共有8个工人。
现在每个工作需要占用一个工人的从[a，b]这个区间的时间（一个工人自然不可能在同一个时间做2个不同的工作），且一个工作不一定是所有工人都能够完成的。现在给出每个工作的描述，问是否存在一种安排方案使得所有工作都能完成。

输入格式：
输入文件有多组数据。
第一行一个数tot表示数据的组数（tot<=10），后面紧接tot组数据。
对于每一组数据的第一行有一个整数n，表示工作的数目。
后面n行每行描述一个工作。
对于一个工作，用a，b，k，h1，h2……hk来描述，表示这个工作需要占用一个工人[a，b]的时间，并且能够完成这个工作的工人只有k个，标号分别是h1，h2……hk。

输入样例：
2
2
1 1 1 1
2 2 1 1
2
1 2 1 1
2 2 1 1

输出格式：
对于每组输入数据，输出一行字符YES（如果可以安排一种方案使得工作完成）或者是NO（无法安排一种方案）。

输出样例：
YES
NO

Solution :
$Big Force Makes Miracle.$

Code :

/*************************************************************************
    > File Name: work.cpp
    > Author: Archer
 ************************************************************************/

#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
#define REP(i, l, r) for (int i = l; i <= r; i++)
#define MP make_pair
const int N = 22;
int T, ed[N], n;
struct Node{int l, r, k, h[10]; } a[N];
inline void setIO(){
    freopen("work.in", "r", stdin);
    freopen("work.out", "w", stdout);
}
inline bool cmp(Node x, Node y){ return x.r < y.r; }
inline bool dfs(int dep){
    if (dep > n) return true;
    for (int i = 1; i <= a[dep].k; i++)
        if (a[dep].l > ed[a[dep].h[i]]){
            int _ = ed[a[dep].h[i]]; ed[a[dep].h[i]] = a[dep].r;
            if (dfs(dep + 1)) return true;
            ed[a[dep].h[i]] = _;
        }
    return false;
}
int main(){
    setIO();

    scanf("%d", &T);
    while (T--){
        memset(ed, 0, sizeof(ed));
        scanf("%d", &n);
        REP(i, 1, n){
            scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].k);
            REP(j, 1, a[i].k) scanf("%d", &a[i].h[j]);
        }
        sort(a + 1, a + 1 + n, cmp);
        if (dfs(1)) puts("YES"); else puts("NO");
    }

    return 0;
}

【其实这里有一个更快的dp

【其实这里有一个正确的dp，通俗易懂，直接看代码

/*************************************************************************
    > File Name: work.cpp
    > Author: Archer
 ************************************************************************/

#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
#define REP(i, l, r) for (int i = l; i <= r; i++)
#define MP make_pair

const int INF = 0x7fffffff;
const int N = 15, M = 1 << N;
vector<int> s[15];
int a[N][N], f[M], l[N], r[N];

inline void setIO(){
    freopen("work.in", "r", stdin);
    freopen("work.out", "w", stdout);
}
inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - '0' ; ch = getchar();}
    return f == 1 ? x : -x;
}
int main(){
    setIO();
    int T = read();
    while(T--){
        int n = read();
        REP(i, 1, 8) s[i].clear();
        memset(a, 0, sizeof(a));
        memset(f, 0, sizeof(f));

        REP(i, 0, n - 1){
            l[i] = read(), r[i] = read();
            int k = read();
            REP(j, 1, k) a[i][read()] = 1;
        }

        REP(now, 0, (1 << n) - 1){
            int flag = 0;
            REP(i, 0, n - 1) REP(j, 0, n - 1)
                    if ((now >> i) & (now >> j) & 1)
                        if ((i != j) && (r[i] >= l[j] && r[j] >= l[i])) flag = 1;
            if (flag) continue;
            REP(j, 1, 8){
                int nflag = 0;
                REP(i, 0, n - 1){
                    if ((now >> i) & 1) if (a[i][j] == 0) nflag = 1;
                }
                if (nflag) continue;
                s[j].PB(now);
            }
        }
        f[0] = 1;
        REP(i, 1, 8) PER(j, (1 << n) - 1, 0)
            if (f[j]) REP(k, 0, s[i].size() - 1) f[j | s[i][k]] = 1;

        if (f[(1 << n) - 1]) puts("YES");
        else puts("NO");
    }
}

题3：兔子计算

问题描述：
兔子们有一个计算器。奇怪的是，这个计算器只有一个寄存器X。兔子们每次可以把寄存器中的数字取出，进行如下四种运算的一种后，将结果放回寄存器中。
X=X+X
X=X-X
X=X*X
X=X/X
已知初始时寄存器里的值为A，兔子们想要知道，是否能通过若干次操作，使得最终寄存器里的值是B。如果可能，它们还想知道最少的操作次数。

输入格式：
输入文件一行包含两个正整数A，B。

输入样例：
3 4

输出格式：
输出文件一行一个整数，即最少操作次数，如果不存在方案，则输出-1。

输出样例：
3

样例解释：
第一次：3 / 3 = 1
第二次：1 + 1 = 2
第三次：2 * 2 = 4

数据范围：
对于40%的数据， A，B ≤ 1000；
对于100%的数据，1 ≤ A，B ≤ 1000000000。

Solution :
$Big Force Makes Miracle.$

Code :

/*************************************************************************
    > File Name: great.cpp
    > Author: Archer
 ************************************************************************/

#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;

typedef long long ll;
typedef pair<ll, int> PII;
#define REP(i, l, r) for (int i = l; i <= r; i++)
#define MP make_pair
ll A, B;
queue<PII> q;
map<ll, bool> hash; 
inline void setIO(){
    freopen("great.in", "r", stdin);
    freopen("great.out", "w", stdout);
}
inline void bfs(){
    hash[A] = 1;
    q.push(MP(A, 0));
    while (!q.empty()){
        PII now = q.front(); q.pop();
        if (now.first == B){ printf("%d\n", now.second); return; }
        if (hash.find(now.first << 1) == hash.end() && (now.first << 1) <= B){
            q.push(MP(now.first << 1, now.second + 1)); hash[now.first << 1] = 1;
        }
        if (hash.find(1) == hash.end() && 1 <= B){
            q.push(MP(1, now.second + 1)); hash[1] = 1;
        }
        if (hash.find(0) == hash.end() && 0 <= B){
            q.push(MP(0, now.second + 1)); hash[0] = 1;
        }
        if (hash.find(now.first * now.first) == hash.end() && now.first * now.first <= B){
            q.push(MP(now.first * now.first, now.second + 1)); hash[now.first * now.first] = 1;
        }
    }
    printf("-1\n");
}
int main(){
    setIO();

    scanf("%lld%lld", &A, &B);
    bfs();

    return 0;
}

题4：最长序列

问题描述：
有一种序列按照如下定义：
1．1在这个序列中；
2．这个序列是按照从小到大的顺序排列的；
3．如果一个数i出现在这个序列中，那么2i+1和4i+5也一定存在在这个序列中。
现在要求你写一个程序，将这个序列前n个数连接成一个长串，并且在这个基础上，从得到的长串中删除m个数字，使得这个长串的字典序最大。

输入格式：
输入文件一行两个整数n，m。

输入样例：
4 2

输出格式：
输出文件2行，第一行是未删除数字之前的原串。第二行是删除数字之后的数字串。

输出样例：
1379
79

数据范围：
对于30%的数据，n，m ≤ 10000；
对于100%的数据，n ≤ 30000；0 ≤ m ≤ 50000。

Solution :
堆找出串，然后贪心删去。

Code :

/*************************************************************************
    > File Name: number.cpp
    > Author: Archer
 ************************************************************************/

#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
#define REP(i, l, r) for (int i = l; i <= r; i++)
#define PER(i, r, l) for (int i = r; i >= l; i--)
#define MP make_pair
const int INF = 1111111;
const int N = 444444;
int n, m, tail;
int shut[N], lst[N];
map<int, int> hash;
priority_queue <int, vector<int>, greater<int> > q;
struct Node{ int last, num, nxt; }ans[N];

inline void setIO(){
    freopen("number.in", "r", stdin);
    freopen("number.out", "w", stdout);
}
inline void PREPARE(){
    q.push(1); tail = 0;
    while(tail < n){
        int x = q.top(); q.pop(); lst[++tail] = x;
        int _ = x * 2 + 1, __ = x * 4 + 5;
        if (!hash[_]) { q.push(_); hash[_] = 1; }
        if (!hash[__]) { q.push(__); hash[__] = 1; }
    }
    tail = 0;
    REP(i, 1, n){
        int x = lst[i];
        int number[20], nn = 0;
        while(x){ number[++nn] = x % 10; x /= 10; }
        PER(j, nn, 1) ans[++tail].num = number[j];
    }
    REP(i, 1, tail) printf("%d", ans[i].num);
    printf("\n");
}
inline void solve(){
    ans[1].last = -1; ans[1].nxt = 2;
    REP(i, 2, tail) { ans[i].nxt = i + 1; ans[i].last = i - 1; }
    ans[tail + 1].num = INF; ans[tail + 1].last = tail; ans[tail + 1].nxt = -1;
    int ptr = 0, l = 1, r = 2;
    while(ptr < m) {
        if (ans[l].num < ans[r].num){
            shut[l] = 1;
            if (ans[l].last == -1){ ans[r].last = -1; l = r; r = ans[r].nxt;
            }else{ ans[ans[l].last].nxt = r; ans[r].last = ans[l].last; l = ans[l].last; }
            ptr++;
        }else{ r = ans[r].nxt; l = ans[l].nxt; }
    }
    REP(i, 1, tail) if (!shut[i]) printf("%d", ans[i].num);
    printf("\n");
}
int main() {
    setIO();

    scanf("%d%d", &n, &m);
    PREPARE();
    solve();

    return 0;
}