题目限制一览
| 题目 |
时间限制 |
空间限制 |
| 1. pudding |
$1000$ MS |
$256$ M |
| 2. trouble |
$1000$ MS |
$256$ M |
| 3. tree |
$1000$ MS |
$256$ M |
Description
N个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.例如颜色分别为1,2,2,1的四个布丁一共有3段颜色.
第一行给出N,M表示布丁的个数和好友的操作次数.
第二行N个数A1,A2…An表示第i个布丁的颜色从第三行起有M行,对于每个操作,若第一个数字是1表示要对颜色进行改变，其后的两个整数X,Y表示将所有颜色为X的变为Y，X可能等于Y.
若第一个数字为2表示要进行询问当前有多少段颜色，这时你应该输出一个整数.
Output
针对第二类操作即询问，依次输出当前有多少段颜色.
Sample Output
Hint
1<=n,m<=100,000; 0<Ai,x,y<1,000,000
分析
做法一：暴力（50分）
考试时想的暴力方法，用 $fir[x]$ 和 $las[x]$ 记录颜色 $x$ 第一次和最后一次出现的位置，修改时只需要在这两个点之间循环修改即可
合并 $x$ 到 $y$ 就是 $fir[y]=min(fir[x],\;fir[y])$，$las[y]=max(las[x],\;las[y])$ 得了一半的分
做法二：暴力 + 启发式合并（100分）
应该算是考试时的想法更进一步，考虑用类似前向星的方式存储颜色 $x$ 出现的所有位置，然后统计一次原序列得到最初的 $ans$，可以发现好友操作之后的 $ans’\leq ans$ ，因此只需在原来的 $ans$ 上做减法即可
结合启发式合并，用 $siz(x)$ 存颜色 $x$ 出现的次数，每次覆盖时 $x\to y$ 选择把 $siz$ 较小的那一个合并到较大的那一个上去，由于最后的零散颜色段长度会越来越短，因此合并的时间复杂度会逐步降低（最后甚至达到近似 $O(1)$ 的复杂度），但是这样做有些时候会违背题目的要求，因此用 $vis(x)$ 表示 $x$ 经过修改后的实际颜色，合并时若 $siz(x)>siz(y)$ 则 $swap(vis(x),\;vis(y))$ 再合并
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
| #include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define maxn 1000001
using namespace std;
template<typename t>inline void fcin(t &x){
int sign=1; x=0; char op=getchar();
while(op<'0'||op>'9'){if(op=='-') sign=-1;op=getchar();}
while(op>='0'&&op<='9'){x=x*10+(op-48);op=getchar();}
x*=sign;
}
int fir[maxn],las[maxn],nex[maxn];
int vis[maxn];int n,m,siz[maxn];
int ans;int a[maxn];
inline void merge(int x,int y){
for(int i=las[x];i;i=nex[i]) ans-=(a[i-1]==y)+(a[i+1]==y);
for(int i=las[x];i;i=nex[i]) a[i]=y;
nex[fir[x]]=las[y];las[y]=las[x];siz[y]+=siz[x];
fir[x]=siz[x]=las[x]=0;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("pudding.in","r",stdin);
freopen("pudding.out","w",stdout);
#endif
fcin(n);fcin(m);
for(int i=1;i<=n;i++){
fcin(a[i]);vis[a[i]]=a[i];
ans+=a[i]!=a[i-1];
if(!las[a[i]]) fir[a[i]]=i;
siz[a[i]]++;nex[i]=las[a[i]];las[a[i]]=i;
}
int op,x,y;
while(m--){
fcin(op);
if(op==1){
fcin(x);fcin(y);if(x==y) continue;
if(siz[vis[x]]>siz[vis[y]]) swap(vis[x],vis[y]);
if(!siz[vis[x]]) continue;
merge(vis[x],vis[y]);
}else printf("%d\n",ans);
}
return 0;
}
|
Description
经过多年的杀戮，秦皇终于统一了中国。为了抵御外来的侵略，他准备在国土边境安置n名将军。不幸的是这n名将军羽翼渐丰，开始展露他们的狼子野心了。他们拒绝述职、拒绝接受皇帝的圣旨。
秦皇已经准备好了秘密处决这些无礼的边防大将。
不过为防兵变，他决定先授予这些将军一些勋章，为自己赢得战略时间。将军们听说他们即将被授予勋章都很开心，他们纷纷上书表示感谢。第i个将军要求得到ai枚不同颜色的勋章。但是这些将军都很傲气，如果两个相邻的将军拥有颜色相同的勋章他们就会认为皇帝不尊重他们，会立即造反（编号为i的将军和编号为i+1的将军相邻；因为他们驻扎的边境可以类似看成一个圆形，所以编号1和编号n的将军也相邻）。
皇帝不得不满足每个将军的要求，但对他们的飞扬跋扈感到很气愤。于是皇帝决定铸造尽量少种类的勋章来满足这些狂妄者的要求。请问他至少要铸造多少种颜色的勋章？
第一行有一个整数n(1<=n<=20000)。
接下来n行每行一个整数ai，表示第i个将军要求得到多少种勋章。(1<=ai<=100000)
Output
输出一个整数，即最少需要多少种勋章。
Sample Output
Hint
1<=n,m<=100,000; 0<Ai,x,y<1,000,000
分析
做法一：瞎搞（60分）
考试时，手算了几个样例（都是n=4）发现最小的勋章数就是序列中相邻元素和的最大值，即
$ans=max(a[1]+a[n],\; a[i]+ai+1)$
考完了才发现 没有考虑奇数情况，例如一个反例就是 $5\quad 5\quad 5$ ，答案应是 15，但是程序输出 10
做法二：二分 + 递推（100分）
二分最大的勋章数 $mid$，设 $max(i)$ 为 $i$ 号将军和 1 号将军最多会有多少个相同的勋章，$min(i)$ 则表示最少的相同数，对于 $max(i)$，因为 $i$ 号将军最多有 $a[i]$ 个勋章，又 $i$ 号将军和 $i-1$ 号将军不能有相同的勋章，则最多有 $a[1]-max(i-1)$ 个勋章和 1 号将军相同，即
$max(i)=min(a[i],\;a[1]-max(i-1))$
又根据容斥原理可以得出 $min(i)$ 的表达式
$min(i)=max(0,\;a[1]+a[i-1]-max(i-1)+a[i]-mid)$
其中也可不写 $max$，只要 $min(n)\leq0$ 就能说明 $n$ 号将军不会与 1 号将军冲突，当前的勋章数还可以更少，否则只能增加勋章数
做法三：数学原理（100分）
做法一在 n 为偶数时是可行的，因为总能给将军们两两配对，于是可以单独考虑 n 为奇数的情况，由于奇数条件下，$n$ 和 1 的相邻关系不可忽略，因此每一个种类的勋章都只能使用$\lfloor \frac{n}{2} \rfloor$ (表示向下取整) 的次数，那么就可以推出
$ans=\lceil sum\div \lfloor \frac{n}{2} \rfloor \rceil$ （因为不能发放不足一个的勋章，所以 $ans$ 向上取整）
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
| #include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define maxn 20002
using namespace std;
template<typename t>inline void fcin(t &x){
int sign=1; x=0; char op=getchar();
while(op<'0'||op>'9'){if(op=='-') sign=-1;op=getchar();}
while(op>='0'&&op<='9'){x=x*10+(op-48);op=getchar();}
x*=sign;
}
int a[maxn],n;
int ans=0,sum;
int main(){
#ifndef ONLINE_JUDGE
freopen("trouble.in","r",stdin);
freopen("trouble.out","w",stdout);
#endif
fcin(n);for(int i=1;i<=n;i++) fcin(a[i]),sum+=a[i];
ans=max(ans,a[1]+a[n]);
for(int i=1;i<=n-1;i++) ans=max(ans,a[i]+a[i+1]);
if(!n&1) printf("%d\n",ans);
else{
n=n/2;
printf("%d",max((int)ceil((double)sum/(double)n),ans));
}
return 0;
}
|
3. 二叉树（tree.cpp）
Description
现在有一棵二叉树，所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有n个叶子节点，满足这些权值为1..n的一个排列)。可以任意交换每个非叶子节点的左右孩子。
要求进行一系列交换，使得最终所有叶子节点的权值按照中序遍历写出来，逆序对个数最少。
第一行n下面每行，一个数x
如果x==0，表示这个节点非叶子节点，递归地向下读入其左孩子和右孩子的信息，
如果x!=0，表示这个节点是叶子节点，权值为x。
Output
一行，最少逆序对个数。
Sample Output
Hint
一行，最少逆序对个数。
分析
做法一：瞎搞（4分）
考试时想的是只能交换叶子节点，那么那些只有一个叶子节点的非叶子节点就不能动，因此把所有的叶子节点按照升序交换之后直接中序遍历，然后树状数组求遍历后的序列的逆序对数
做法二：暴力 + 主席树（100分）
可以对每个叶子节点建立一颗线段树来统计逆序对数，每次访问到一个非叶子节点都暴力地来交换一下左右子树的位置，看交换前和交换后形成的逆序对数哪一个更少，由此得出答案
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
| #include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define maxn 400003
#define mid ((L+R)>>1)
using namespace std;
typedef long long ll;
template<typename t>inline void fcin(t &x){
int sign=1; x=0; char op=getchar();
while(op<'0'||op>'9'){if(op=='-') sign=-1;op=getchar();}
while(op>='0'&&op<='9'){x=x*10+(op-48);op=getchar();}
x*=sign;
}
int ch[maxn][2],w[maxn],newp=1;
int lc[maxn<<4],rc[maxn<<4],nodes;
ll val[maxn<<4],cnt[2];int root[maxn];
inline void pushup(int k){
val[k]=val[lc[k]]+val[rc[k]];
}
void init(int k){
fcin(w[k]);
if(!w[k]){
ch[k][0]=++newp;
init(ch[k][0]);
ch[k][1]=++newp;
init(ch[k][1]);
}
}
void build(int &k,int L,int R,int pos){
if(!k) k=++nodes;
if(L==R){val[k]=1;return;}
if(pos<=mid) build(lc[k],L,mid,pos);
else build(rc[k],mid+1,R,pos);
pushup(k);
}
int unite(int x,int y){
if(!x||!y) return x?x:y;
cnt[0]+=(ll)val[rc[x]]*val[lc[y]];
cnt[1]+=(ll)val[lc[x]]*val[rc[y]];
lc[x]=unite(lc[x],lc[y]);
rc[x]=unite(rc[x],rc[y]);
pushup(x);return x;
}
ll ans;int n;
void dfs(int k){
if(!k) return;
dfs(ch[k][0]);dfs(ch[k][1]);
if(!w[k]){
memset(cnt,0,sizeof(cnt));
root[k]=unite(root[ch[k][0]],root[ch[k][1]]);
ans+=min(cnt[0],cnt[1]);
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
#endif
fcin(n);init(1);
for(int i=1;i<=newp;i++)
if(w[i]) build(root[i],1,n,w[i]);
dfs(1);printf("%lld",ans);
return 0;
}
|
