codeforces 261 div.2

本文从WordPress迁移而来, 查看全部WordPress迁移文章

题目链接:Pashmak and Buses

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
如果按列来看最后的答案矩阵,那么第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

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
/*
先将整个序列离散化
开个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;
}