Codeforces Round #315 (Div. 2)

A. Music

题意较难懂。只是仅仅要推公式就好了

注意到S+(q - 1) * t = q * t;

仅仅须要t等于S就可以。即每次添加S秒，就须要又一次听一次歌

AC代码：

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <sstream>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>
#define LL long long
#define INF 0x7fffffff
using namespace std;

int main() {
    int T, S, q;
    scanf("%d %d %d", &T, &S, &q);
    int ans = 0;
    while(S < T) {
        S = S * q;
        ans ++;
    }
    cout << ans << endl;
    return 0;
}

B. Inventory

水题。。

AC代码：

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <sstream>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>
#define LL long long
#define INF 0x7fffffff
using namespace std;

int n;
int vis[100005];

int ans[100005];

int pos[100005];
int pos_cnt;

int main() {
    pos_cnt = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++){
        int t;
        scanf("%d", &t);
        if(t <= n && t >= 1 && vis[t] == 0) {
            ans[i] = t;
            vis[t] = 1;
        }
        else {
            pos[pos_cnt ++] = i;
        }
    }

    int p = 1;
    for(int i = 0; i < pos_cnt; i ++) {
        for(;p <= n; p ++) {
            if(vis[p] == 0) {
                ans[pos[i]] = p;
                vis[p] = 1;
                break;
            }
        }
    }
    for(int i = 1; i < n; i ++) {
        printf("%d ", ans[i]);
    }
    printf("%d
", ans[n]);
    return 0;
}

C. Primes or Palindromes?

枚举大法好。。

AC代码：

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <sstream>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>
#include <ctime>
#define LL long long
#define INF 0x7fffffff
using namespace std;

const int maxn = 2000005;
int pi[maxn];
int vis[maxn];

int hw[maxn];

void init() {
    pi[1] = 0;
    for(int i = 2; i < maxn; i ++) {
        if(!vis[i]) {
            pi[i] = pi[i - 1] + 1;
            for(int j = 2 * i; j < maxn; j += i) {
                vis[j] = 1;
            }
        }
        else pi[i] = pi[i-1];
    }
}

int p, q;

int search() {
    for(int i = maxn - 1; i >= 0; i --) {
        if((LL)pi[i] * q <= (LL)hw[i] * p) return i;
    }
}

bool fun(int n) {
    int m = 0;
    int t = n;
    while(t) {
        m = m * 10 + t % 10;
        t /= 10;
    }
    //cout << m << " " << n << endl;
    return m == n;
}

int main() {
    init();
    hw[0] = 0;
    for(int i = 1; i < maxn; i++) {
        if(fun(i)) hw[i] = hw[i-1] + 1;
        else hw[i] = hw[i-1];
    }

    scanf("%d %d", &p, &q);


    int ans = search();
    printf("%d
", ans);
    return 0;
}

D. Symmetric and Transitive

题意：就是去求在一个含有n个元素的集合里。满足对称性和传递性。不满足自反性的关系有多少种。

这里有一个奇怪的东西——Bell数

Bell数，表示基数为n的集合划分数目，也就是相应的等价关系个数

能够发现一个奇怪的规律：ans[n] = Bell[n +１] - Bell[n];

然后依据Bell三角形打表就能够了

AC代码：

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <sstream>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>
#define LL long long
#define INF 0x7fffffff
using namespace std;

const int MOD = 1e9+7;

LL Bell[4005][4005];

int main() {
    int n;
    scanf("%d", &n);
    Bell[0][0] = 1;
    for(int i = 1; i <= n; i ++) {
        Bell[i][0] = Bell[i - 1][i - 1];
        for(int j = 1; j <= i; j ++) {
            Bell[i][j] = (Bell[i][j - 1] + Bell[i - 1][j - 1]) % MOD;
        }
    }
    printf("%I64d
", Bell[n][n - 1]);
    return 0;
}