codeforces 261 div.2

题目链接：Pashmak and Buses

代码：

/*
 如果按列来看最后的答案矩阵，那么第i列代表的信息就是
 第i个人在这d天里面的坐车情况
 题目要求不能任意两个人在每一天都坐相同的车
 即不能出现两列，完全相同，也就是每一列都是不同的
 如果把每一列压缩成一个状态，那就是一个k进制数（一个长度为d的k进制数）
 所以答案就明显了，对于长度为n的k进制数有多少种可能,pow(k，d）
 只要这个总数大于n就能构成答案
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define MAXN 1010

int n,car,day,m;
int mat[MAXN][MAXN];

bool check() {
    LL tot = 1;
    for (int i = 0; i < day; i++) {
        tot *= car;
        if (tot >= n) return true;
    }
    return false;
}

void write(int x) {
    int id = x;
    for (int i = day-1; i >= 0 && x; i--){
        mat[i][id] = x % car;
        x /= car;
    }
}

bool solve() {
    if (!check()) return false;
    memset(mat, 0, sizeof(mat));
    for (int x = 0; x < n; x++) {
        write(x);
    }
    return true;
}

int main() {
    while (scanf("%d%d%d", &n, &car, &day) != EOF) {
        bool res = solve();
        if (res) {
            for (int i = 0; i < day; i++)
                for (int j = 0; j < n; j++)
                    printf("%d%c", mat[i][j]+1, j==n-1?'\n':' ');
        }
        else puts("-1");
    }
    return 0;
}

题目链接：Pashmak and Parmida’s problem

代码：

/*
 先将整个序列离散化
 开个10^6的二维vector，vector[x]保存x在序列中出现的所有位置
 数组head[i]对应f(1,i,a[i]); tail[j]对应f(j,n,a[j])
 计算head[],枚举i，对于a[i]，查看vector[a[i]]，二分它看有多少个a[i]
 在i位置钱，此为head[i]
 计算tail同理

 枚举i，得到head[i]，其实就是在（i+1,n）里面找到有多少个tail[j] < head[i]
 可以用二维树状数组的，但是空间太大，那么就用一维bit，一般更新一边查询
 tail[j]的值是bit的下标
 要先更新再求和，因为题目要求 1<=i<j<=n，先在bit中删除tail[i]

 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define MAXN 1000010

class BIT;

int n,m,a[MAXN],map[MAXN];
vector<int>pos[MAXN];
int head[MAXN], tail[MAXN];
BIT *bit;

class BIT {
public:
    int c[MAXN];
    BIT() { reset(); }
    void reset() { memset(c, 0, sizeof(c)); }
    inline int lowbit(int x) { return x & (-x); }
    void add(int pos, int val) {
        while (pos <= n) {
            c[pos] += val;
            pos += lowbit(pos);
        }
    }
    LL query(int pos) {
        LL ans = 0LL;
        while (pos) {
            ans += c[pos];
            pos -= lowbit(pos);
        }
        return ans;
    }
};

int create_map() {
    sort(map, map+n);
    m=1;
    for (int i = 1; i < n; i++)
        if (map[i] != map[i-1])
            map[m++] = map[i];
}

void create_a_pos() {
    for (int i = 0; i <= m; i++) pos[i].clear();
        for (int i = 0; i < n; i++) {
            a[i] = lower_bound(map, map+m, a[i]) - map;
            pos[a[i]].pb(i);
        }
}

void create_head_tail_bit() {
    memset(head, 0, sizeof(head));
    memset(tail, 0, sizeof(tail));
    bit->reset();
    for (int i = 0; i < n; i++) {
        int x = a[i];
        int size = pos[x].size();
        int p = lower_bound(pos[x].begin(), pos[x].end(), i) - pos[x].begin();
        head[i] = p+1;
        tail[i] = size - p;
        bit->add(tail[i], 1);
    }
}

LL solve() {
    LL ans = 0LL;
    for (int i = 0; i < n; i++) {
        bit->add(tail[i], -1);
        LL res = bit->query(head[i]-1);
        ans += res;
    }
    return ans;
}

int main() {
    bit = new BIT();
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            map[i] = a[i];
        }
        create_map();
        create_a_pos();
        create_head_tail_bit();
        cout << solve() << endl;
    }
    return 0;
}