TJOI2014可以说是相对比较的容易（改起来很快），给冬令营的题目写篇题解。

Day1

匹配

看了题解后一眼看出是二分图最大权匹配

用匈牙利算法或者转换成费用流模型用Dinic，

暴力枚举删边，若最优匹配发生改变，说明这条边属于交集

排序即可

（由于站长还没切，代码先咕了~）

电源插排

题目大意就是完成以下要求：

  • 寻找最大区间（log⁡n\log n）
  • 分裂区间（log⁡n\log n）
  • 合并区间（log⁡n\log n）

本题非常适合练习STL

观察到QQ较小，于是将询问离线。

  1. 寻找最大区间可以用pairpair类型的优先队列prioritypriority_queuequeue来存区间的长和起点

    的特性就是先比较第一个值再比较第二个，因此firstfirst里存区间长，secondsecond存起点位置

    这样刚好满足了寻找最大最右区间的要求。

    假设我们找到的最大最右区间为[st,st+len−1][st,st+len-1]

    那么这名学生要把电源插在pos=⌊2st+len2⌋pos = \lfloor \frac{2st+len}{2} \rfloor位置上。

  2. 当学生把电源插到插排上的时候，原先的大区间[st,st+len−1][st,st+len-1]会分裂成两个小区间，即[st,pos−1][st,pos-1]和[pos+1，st+len−1][pos+1，st+len-1]

    再pushpush进堆里面就可以了

  3. 当学生将电源拔出时，两个区间合并成了一个新的大区间，但是显然，我们无法从堆中删除原来的两个小区间。

    那我们只好从获取的时候判断区间的合法性

    建立一个setset来模拟实验室的插排。

    我们发现，一个区间[l,r][l,r]合法当且仅当l−1,r+1l-1,r+1在setset中相邻。

    回到第1步添加一个判断，第2步添加一个insert(pos)insert(pos)表示setset中pospos位置上插着电源

    把电源拔出时，eraseerase掉pospos

  4. 与第1步同时，记录下来每一次要改变的位置chgchg

  5. 最后用树状数组之类的数据结构进行单点修改，区间求和

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
#include <set>
#include <map>
#include <queue>
#include <cstdio>
#include <algorithm>
#define Q 1000005
#define P pair<int,int>
#define sit set<int>::iterator
#define lb(x) ((x)&(-(x)))
#define w(x) (lower_bound(li+1,li+cnt+1,x)-li)
using namespace std;

set<int> s;
map<int, int> p;
priority_queue<P, vector<P>, less<P> > q;
int cnt, n, m, c[Q << 3], li[Q << 3];
int l[Q], r[Q], k[Q], chg[Q], zero = 0;

inline bool near(int x, int y) {
	sit a = s.lower_bound(x);
	if (*a != x) return 0;
	sit b = s.lower_bound(y);
	if (*b != y) return 0;
	++a;
	return *a == *b;}
void add(int w, int v) { for (; w <= cnt; w += lb(w)) c[w] += v; }
int qry(int w, int s = 0) {
	for(; w; w -= lb(w)) s += c[w];
	return s;}
void lisanhua(int tot = cnt) {
	sort(li + 1, li + cnt + 1), cnt = 1;
	for (int i = 2; i <= tot; ++i)
		if (li[cnt] < li[i]) li[++cnt] = li[i];}
int main() {
	freopen("switch.in", "r", stdin);
	freopen("switch.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		scanf("%d", k + i), p[k[i]] = 0;
		if (k[i]) continue;
		scanf("%d%d", l + i, r + i),
			  li[++cnt] = l[i], li[++cnt] = r[i];
	}
	q.push(make_pair(n, 1));
	s.insert(zero), s.insert(n + 1);
	for (int i = 1, len, st; i <= m; ++i) {
		if (!k[i]) continue;
		int kk = k[i];
		if (p[kk]) {
			sit it = s.lower_bound(p[kk]);
			sit p1 = it, p2 = it;
			--p1, ++p2;
			int beg = *p1 + 1, end = *p2 - 1;
			q.push(make_pair(end - beg + 1, beg));
			s.erase(it), p[kk] = 0;
			continue;
		}
		len = -1, st = 1;
		for (; !q.empty() && !near(st - 1, st + len); q.pop())
			len = q.top().first, st = q.top().second;
		int pos = (st + st + len) >> 1;
		s.insert(p[kk] = chg[i] = pos),
				 q.push(make_pair(pos - st, st)),
				 q.push(make_pair(st + len - 1 - pos, pos + 1));
		li[++cnt] = pos;
	}
	lisanhua();
	for (int i = 1; i <= m; ++i) p[k[i]] = 0;
	for (int i = 1; i <= m; ++i)
		if (!k[i]) printf("%d\n", qry(w(r[i])) - qry(w(l[i]) - 1));
		else if (p[k[i]]) add(w(p[k[i]]), -1), p[k[i]] = 0;
		else p[k[i]] = chg[i], add(w(p[k[i]]), 1);
	fclose(stdin), fclose(stdout);}

拼图

状压dp或者暴力随意。

将每一块积木压成二进制如

1
2
101
111

会被压成

1
2
3
4
1010 = v1
1110 = v2
0000 = v3
0000 = v4

那如何进行平移？

观察到当每一行最后一位都为0（(v1|v2|v3|v4) \\& 1 \oplus 1）时，可以右移

当最后一行都为0（v4==0v4==0）时，可以下移

设fi,sf_{i,s}，表示枚举到第ii种积木，当前状态为ss的方案数，gi,sg_{i,s}记录fi,sf_{i,s}从哪里转移

暴力枚举积木的状态v=v1<<12∣v2<<8∣v3<<4∣v4v = v1<<12|v2<<8|v3<<4|v4，从某个状态ss转移，

则有转移方程式

f_{i,s|v} += f_{i,s} (s \\& v ==0)

举一个方案可以从gi,65535g_{i,65535}回溯至gi−1,...g_{i-1,...}，gi−2,...g_{i-2,...}一直到g1,...g_{1,...}

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
#include <cstdio>
#include <cstring>
using namespace std;
int f[20][66000], g[20][66000], n;
int v[20][10], las, a[20];
char s[10];
int main()
{
	freopen("puzzle.in", "r", stdin);
	freopen("puzzle.out", "w", stdout);
	f[0][0] = 1;
	while (~scanf("%d", &n)) {
		las = (1 << 16) - 1;
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= 4; ++j)
				v[i][j] = 0;
		for (int i = 1, r, c; i <= n; ++i) {
			scanf("%d%d", &r, &c);
			for (int j = 1; j <= r; ++j) {
				scanf("%s", s);
				int l = strlen(s);
				for (int k = 0; k < l; ++k)
					v[i][j] <<= 1, v[i][j] |= (s[k] ^ 48);
				for (int k = l; k < 4; ++k) v[i][j] <<= 1;
			}
		}
		for (int i = 1; i <= n; ++i)
			for (int s = 0; s < (1 << 16); ++s)
				f[i][s] = 0;
		for (int i = 1; i <= n; ++i) {
			int v1 = v[i][1], v2 = v[i][2];
			int v3 = v[i][3], v4 = v[i][4];
			while (1) {
				int p1 = v1, p2 = v2, p3 = v3, p4 = v4, pp;
				while (1) {
					int val = (p1 << 12) | (p2 << 8) | (p3 << 4) | p4;
					for (int s = 0; s < (1 << 16); ++s)
						if (!(s & val) && f[i - 1][s])
							g[i][s | val] = s, f[i][s | val] += f[i - 1][s];
					if (p4) break;
					pp = p4, p4 = p3, p3 = p2, p2 = p1, p1 = pp;
				}
				if ((v1 | v2 | v3 | v4) & 1) break;
				v1 >>= 1, v2 >>= 1, v3 >>= 1, v4 >>= 1;
			}
		}
		if (f[n][las] == 0) puts("No solution");
		else if (f[n][las] > 1) puts("Yes, many!");
		else {
			puts("Yes, only one!");
			for (int i = n, j = las; i; j = g[i][j], --i)
				for (int k = 16, l = j; k; --k, l >>= 1)
					if (l & 1) a[k] = i;
			for (int i = 1; i <= 16; ++i) {
				printf("%d", a[i]);
				if (i % 4 == 0) putchar('\n');
			}
		}
	}
	fclose(stdin), fclose(stdout);
}

Day2

上升子序列

先将aia_i离散化，发现这样一个事实

1
2
3
4
1    2    3    4    3    2   [3]   4
|----a----|----b----|----c----|
真正有贡献的只有c段
若a，b段产生贡献，就会与c段算重

（以上以最后一个33为基准点）

那就设f[i]f[i]表示区间(pre[ai],i](pre[a_i],i]中产生的贡献（小于aia_i的数的个数）

用树状数组记录a+b+ca+b+c的值为ww，sum[a_i]=\sum f_j ((i

则ans+=(fi=w−sum[ai])ans+=(f_i = w - sum[a_i])，更新一下sum

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
#include <cstdio>
#include <algorithm>
#define N 100005
#define MOD 1000000007
#define lb(x) ((x)&(-(x)))
#define low(x) (lower_bound(li+1,li+n+1,x)-li)
using namespace std;
long long n,a[N],tot,li[N],ans,sig[N],c[N];
void add(long long w,long long v)
	{ for (;w<=n+1;w+=lb(w)) c[w]+=v; }
long long qry(long long w,long long s=0)
	{ for (;w;w-=lb(w)) s+=c[w];return s; }
int main()
{
	freopen("subsequence.in","r",stdin);
	freopen("subsequence.out","w",stdout);
	scanf("%lld",&n);
	for (int i=1;i<=n;++i)
		scanf("%lld",a+i),li[i]=a[i];
	sort(li+1,li+n+1),add(1,1);
	tot=unique(li+1,li+n+1)-li-1;
	for (int i=1;i<=n;++i) a[i]=low(a[i])+1;
	for (long long i=1,x,f,u;i<=n;++i) {
		u=a[i],x=qry(u-1);
		f=(x-sig[u]+MOD)%MOD,
		add(u,f),ans=(ans+f)%MOD,
		sig[u]=(sig[u]+f)%MOD;
	}printf("%lld",(ans-tot+MOD)%MOD);
	fclose(stdin),fclose(stdout);
}

Alice and Bob

由题知，xx至少有一种11~nn的排列

不妨假设xix_i互不相同

用贪心的思想来向，一个前面的数比后面的大可以增加更多的得分

发现如下性质

  • 对于ii和jj，有i<ji<j，则当ai=aja_i = a_j时，有xi>xjx_i>x_j
  • 对于ii，jj和kk，有i<j<ki<j<k，则当ai=aj=aka_i=a_j=a_k时，让xj>xkx_j>x_k会更优

由此，可以以<<为边建立一张图，再拓扑排序

可以证明，此时图的dfndfn序为一种可行方案

再从后往前，求出每一个以xix_i为开头的最长下降子序列，最后求和

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
#include <cstdio>
#include <vector>
#define N 100005
#define lb(x) ((x)&(-(x)))
using namespace std;
long long ans;
vector<int> g[N];
int cnt=-1,num[N],f[N],n,pre[N];
void dfs(int x) {
	num[x]=++cnt;
	for (int i=g[x].size()-1;i>=0;)
		dfs(g[x][i--]);
}
int qry(int w,int s=0) {
	for (;w;w-=(w&(-w))) s=max(f[w],s);
	return s;
}
void upd(int w,int v) {
	for (;w<=n;w+=w&(-w))
		f[w]=max(f[w],v);
}
int main()
{
	freopen("alice.in","r",stdin);
	freopen("alice.out","w",stdout);
	scanf("%d",&n);
	for (int i=1,a;i<=n;++i) scanf("%d",&a),
		g[pre[a-1]].push_back(i),pre[a]=i;
	dfs(0);for (int i=n,t;i;--i)
		t=qry(num[i]-1)+1,
		upd(num[i],t),ans+=t;
	printf("%lld",ans);
	fclose(stdin),fclose(stdout);
}

电影评分

题目大意，动态修改，查询第kk大

观察到n≤10000n \le 10000，因此n2n^2做法和nlog⁡nn \log n做法都可以过

先说说做法

  • 暴力修改，排序查询，时间复杂度为O(n2log⁡n)O(n^2 \log n)，在强数据下会超时
  • 瓶颈在于查询，可以用快排来求第kk大，做法是O(n)O(n)的，因此总复杂度为O(n2)O(n^2)，在常数小的时候可以过，而且跑的还挺快
  • 用平衡树或者权值线段树，时间复杂度为O(nlog⁡n)O(n \log n)

我选择的是第二种做法，优化了常数，码量较小，实在是考场必备良药

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
#include <cstdio>
#include <algorithm>
#define N 10005
using namespace std;
struct MOVIE { int id,time;double score; } m[N],b[N];
int cnt,lat[N*10],tim[N*10],n;

bool cmp(MOVIE x,MOVIE y) {
	if (x.score>y.score) return 1;
	if (x.score<y.score) return 0;
	return (x.time<y.time) ;
}
int qsort(int l,int r,int k)
{
	if (l>r) return b[k].id;
	swap(b[l],b[(l+r)>>1]);
	int i=l,j=r;MOVIE base=b[l];
	while (i<j)
	{
		while (cmp(base,b[j])&&i<j) --j;
		swap(b[i],b[j]);
		while (cmp(b[i],base)&&i<j) ++i;
		swap(b[i],b[j]);
	}b[i]=base;
	if (k==i) return base.id;
	if (k<i) return qsort(l,i-1,k);
	else return qsort(i+1,r,k);
}
void query()
{
	int x;scanf("%d",&x);
	for (int i=1;i<=cnt;++i) b[i]=m[i];
	printf("%d\n",qsort(1,cnt,x));
}
void release()
{
	int x,id,a,mx=0;
	scanf("%d%d",&id,&x);
	tim[id]=++cnt;
	for (int i=1;i<=x;++i) {
		scanf("%d",&a);
		if (lat[a]>mx) mx=lat[a];
		lat[a]=cnt;
	}m[cnt]=MOVIE{id,cnt,m[mx].score};
}
void score()
{
	int x;double sc;
	scanf("%d%lf",&x,&sc);
	m[tim[x]].score+=sc;
	m[tim[x]].score/=2;
}
int main()
{
	freopen("movie.in","r",stdin);
	freopen("movie.out","w",stdout);
	scanf("%d",&n);
	for (char op[1];n--;) {
		scanf("%s",op);
		if (op[0]=='Q') query();
		else if (op[0]=='C') score();
		else release();
	}fclose(stdin),fclose(stdout);
}

总结

呃，作为一套市选的题目，还算是较为简单，但是考场只切了两题，所以以后还是要提升一下思维的敏捷性。