[BZOJ 3523] [POI 2014] Bricks

题意

  给定 n 种颜色, 第 i 种颜色有 c[i] 个.

  构造序列 L , 用完所有的颜色, L[1] = S, L[M] = E , 任意相邻两个都不同.

  n, m <= 1000000.

分析

  一点点来考虑, 如果不要求 L[1] = S, L[M] = E .

  每次我们肯定会尽可能选剩余次数大的, 因为这样才能尽可能避免出现相邻相同, 用堆维护每种的个数.

  如果要求 L[1] = S , 那么我们将 c[S] 减去 1 , 强制首位为 S 即可.

  如果要求末尾为 L[M] , 我们将 c[E] 减去 1, 强制末尾为 E .

  但是这样可能会导致倒数第二位与最后一位相同.

  我们将倒数第二位与倒数第三位交换, 倒数第 4 位与倒数第 5 位交换, ..., 以此类推, 直到不用交换.

  如果交换到 i <= 2 的时候, 仍然 L[i] = L[i+1] , 说明 E 的个数超过了一半, 所以一定无解.

  细节: 当 n = 1 的时候特判.

实现

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cctype>
 5 #include <queue>
 6 using namespace std;
 7 #define F(i, a, b) for (register int i = (a); i <= (b); i++)
 8 inline int rd(void) {
 9     int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == ‘-‘) f = -1;
10     int x = 0; for (; isdigit(c); c = getchar()) x = x*10+c-‘0‘; return x*f;
11 }
12
13 const int N = 1000005;
14
15 int n, S, E;
16 int M, cnt[N];
17 struct cmp { inline bool operator () (int i, int j) { return cnt[i] < cnt[j]; } };
18 priority_queue< int, vector<int>, cmp > q;
19 int List[N], tot;
20 int Last;
21
22 inline void Maintain(int id) {
23     q.pop();
24     cnt[id]--;
25     if (cnt[id] > 0) q.push(id);
26     List[++tot] = id;
27     Last = id;
28 }
29
30 int main(void) {
31     #ifndef ONLINE_JUDGE
32         freopen("klo.in", "r", stdin);
33     #endif
34
35     n = rd(), S = rd(), E = rd();
36     F(i, 1, n) {
37         cnt[i] = rd();
38         M += cnt[i];
39     }
40
41     if (M == 1) {
42         int Has = 1;
43         while (!cnt[Has]) Has++;
44         return printf("%d\n", Has == S && Has == E ? Has : 0), 0;
45     }
46
47     cnt[S]--, cnt[E]--;
48     if (cnt[S] < 0 || cnt[E] < 0) return puts("0"), 0;
49     F(i, 1, n) if (cnt[i] > 0) q.push(i);
50     List[++tot] = S;
51     Last = S;
52     F(i, 2, M-1) {
53         int id = q.top();
54         if (id != Last)
55             Maintain(id);
56         else {
57             q.pop();
58             if (q.empty()) return puts("0"), 0;
59             int id2 = q.top();
60             Maintain(id2);
61             q.push(id);
62         }
63     }
64     List[++tot] = E;
65
66     if (List[M-1] == List[M]) {
67         for (int i = M-1; i >= 1; i -= 2)
68             if (List[i] == List[i+1]) {
69                 if (i <= 2) return puts("0"), 0;
70                 swap(List[i-1], List[i]);
71             }
72             else break;
73     }
74
75     F(i, 1, M) printf("%d ", List[i]); puts("");
76
77     return 0;
78 }
时间: 09-14

[BZOJ 3523] [POI 2014] Bricks的相关文章

Poi 2014 解题报告( 1 - 4 ,6 )

撸了一下Poi 2014 ,看了一下网上题解不多,所以决定写一下.有的题应该是数据不强水过去了,等北京回来在写一下复杂度比较靠谱的代码 o(╯□╰)o 第一题: 题意是给定一个长度不大于1000000,只包括p和j的串,求一个最长的子串,要求子串任何一个前缀和后缀都满足p的数量不少于j的数量. 首先把p当做1,把j当做0,算出前缀和 sum[] ,原来的问题就转化为求一个最长区间 [l,r] ,使得任意的i∈[l,r],都有 sum[i] - sum[l-1] >= 0 并且 sum[r] -

[BZOJ 3747] [POI 2015] Kinoman【线段树】

Problem Link : BZOJ 3747 题解:ZYF-ZYF 神犇的题解 解题的大致思路是,当区间的右端点向右移动一格时,只有两个区间的左端点对应的答案发生了变化. 从 f[i] + 1 到 i 的区间中的答案增加了 W[A[i]], 从 f[f[i]] + 1 到 f[i] 的区间的答案减少了 W[A[i]] ,其余区间的答案没有发生变化. 那么就是线段树的区间修改和区间最值查询. 代码如下: #include <iostream> #include <cstdio>

BZOJ 3503 CQOI 2014 和谐矩阵 高斯消元

题目大意:给出m和n,求出一种方案使得每一个点和周围的四个点的1的个数为偶数. 思路:根据题意可以列出m*n个异或方程,然后组成异或方程组.解这个异或方程组然后输出任意一个解就可以了. PS:值得注意的是,全是0肯定是一个解,显然你不能输出这个解.所以你需要让一个或一些自由元的值为1,至于怎么做,随便yy就行了. PS2:这个题的样例吞掉了空格,然而又是SPJ,所以就是wa..然后我wa了一下午.. CODE: #include <cstdio> #include <cstring>

[BZOJ 1103][POI 2007]大都市(DFS求拓扑序+树状数组)

题目链接:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1103 题目大意:给你一个树,刚开始所有树边边权均为1,不断地将其中的某些边边权改为0,其间问你某个点到根节点之间路径上的边权和. 此题和POJ的Apple Tree很相近... 首先DFS生成整棵树的拓扑序,DFS时每个结点i进入的时间l[i]和离开的时间r[i],然后对每次更改操作,维护树状数组即可. #include <iostream> #include <stdi

[BZOJ 2790] [POI 2012] Distance

题意 给定长度为 n 的序列 a[1], a[2], ..., a[n] . 对于每个数 i , 求出 j , 满足 dist(a[i], a[j]) 最小, 且 i != j . dist(x, y) 表示由 x 变为 y 的最小步数, 每次变换可以乘上素数 p , 或除以素数 p . 2 <= n <= 100000 , 1 <= a[i] <= 1000000 . 分析 从前往后扫一遍, 从后往前扫一遍, 来满足 i != j 的条件. 记 Min[i] 表示访问到点 i 的

POI 2014 HOTELS (树形DP)

题目链接 HOTELS 依次枚举每个点,以该点为中心扩展. 每次枚举的时候,从该点的儿子依次出发,搜完一个儿子所有的点之后进行答案统计. 这里用了一个小trick. 1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define rep(i, a, b) for(int i(a); i <= (b); ++i) 6 #define for_edge(i, x) for(int i = H[x]; i; i = X[i]) 7

BZOJ 3533 sdoi 2014 向量集

设(x,y)为Q的查询点,分类讨论如下:1.y>0:  最大化a*x+b*y,维护一个上凸壳三分即可 2.y<0:最大化a*x+b*y  维护一个下凸壳三分即可 我们考虑对时间建出一棵线段树 对于每个区间,如果满了就做出两个凸壳 总时间复杂度是O(n*log^2n) 之后我们考虑查询,每个区间最多被分解为log(n)个区间 在每个区间的凸壳上三分最优解即可 至于优化,可以设定一个阈值,当区间长度小于阈值时不用做凸壳,查询时直接暴力就可以了 #include<cstdio> #inc

BZOJ 3747 POI 2015 Kinoman 线段树

题目大意:给出电影院的放映电影顺序,一个电影只有看过一次的时候会获得电影的权值.没看过或者看两次或以上都不能获得权值.问看连续区间的电影能够获得的最大权值是多少. 思路:利用线段树维护前缀和.将出现第一次的地方的权值加上那部电影的权值,第二次出现的时候权值减去那部电影的权值.枚举起点,先更新答案,然后在当前节点减去权值的二倍,然后再在下一次出现的地方加上权值(我感觉我没说明白,总之看代码吧... CODE: #include <cstdio> #include <cstring>

BZOJ 3613 HEOI 2014 南园满地堆轻絮 二分+贪心

题目大意 给出一个数字序列,要求将这个数字序列变成单调不降的序列.若原来的数字是A[i],变化之后的数字是B[i],那么花费是|A[i]?B[i]| .求出一种方案,使得最大的花费最小. 思路 一眼就能看出是二分,然后贪心什么的随便yy一下就行了. CODE #define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <cstring> #include <iostream> #include <algor

BZOJ 3506 CQOI 2014 排序机械臂 Splay

题目大意:给出一个序列,给出一种排序方式,模拟这种排序方式排序,并输出每次找到的节点的位置. 思路:它让你做什么你就做什么,无非就是个Reverse,很简单.注意一下排序的时候权值相等的情况就行了. CODE: #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 100010 #define INF 0x3f3f3f3f using