[国庆集训]Day6解题报告

发表于 | 阅读次数：

题目链接

戳我n(≧▽≦)n

注：T3换为跳跳棋

T1

我真是蒟蒻。。。

先放一段官方题解

在题目没有给出特殊约束的情况下永远不要考虑对背包算法的优化

因为这是不可能的事情

……

然后。。。我真的在想怎么优化这个01背包…QAQ

然后。。。就没然后了。。。果断交了一个$O(N^3)$的暴力。。。

那么，我们现在来讲正解。我们考虑做两次的01背包，先正着做一次，再倒着做一次。

（常用手法。一般取掉一个元素的话，就是让原来的序列变成两段。然后正着做一遍，倒着做一遍。）

  • 记录$f[i][j]$为从第$1 \sim i$个物品，花费钱数为$j$时，所能取到的最大喜好程度。
  • 记录$g[i][j]$为从第$i \sim N$个物品，花费钱数为$j$时，所能取到的最大喜好程度。

那么我们就可以在$O(2 \times N^2)$的时间内预处理出这两个数组。

然后对于每次询问，我们可以枚举买前面物品用的钱，然后统计答案，取最大值即可。

总的来说还是我太菜了。

$Mark$一下：

  • 在题目没有给出特殊约束的情况下永远不要考虑对背包算法的优化
  • 在题目没有给出特殊约束的情况下永远不要考虑对背包算法的优化
  • 在题目没有给出特殊约束的情况下永远不要考虑对背包算法的优化

重要的$Mark$要记$3$遍！

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
#include <stdio.h>
#include <iostream>
#define Re register int

int N,M,A[1005],B[1005],f[1005][1005],g[1005][1005],a,b;

template <typename T> inline void read(T &var)
{
	T x=0; int w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	var=w?-x:x;
}
inline int max(int a,int b) {return a>b?a:b;}
int main(int argc, char const *argv[])
{
	read(N);
	for (Re i=1,tmp; i<=N; ++i)
		read(A[i]),read(B[i]),read(tmp);
	for (Re i=1; i<=N; ++i)
		for (Re j=0; j<=1000; ++j)
		{
			f[i][j]=f[i-1][j];
			if (j>=A[i]) f[i][j]=max(f[i][j],f[i-1][j-A[i]]+B[i]);
		}
	for (Re i=N; i>=1; --i)
		for (Re j=0; j<=1000; ++j)
		{
			g[i][j]=g[i+1][j];
			if (j>=A[i]) g[i][j]=max(g[i][j],g[i+1][j-A[i]]+B[i]);
		}
	read(M);
	while (M--)
	{
		read(a),read(b); int ans=0;
		for (Re i=0; i<=b; ++i)
			ans=max(ans,f[a][i]+g[a+2][b-i]);
		printf("%d\n",ans);
	} return 0;
}

T2

虽然我会$Trie$树，但是，$O(N^2)$40分我觉得不错！（我想不到，我是蒟蒻）

初三翘掉晚自习到高中部上课听的$Trie$树，但是从来没用过。。。

讲正经的了。。。

首先来明确一下$lowbit(x)$的意义，它求的是$x$在二进制表示下，从低位到高位出现的第一个$1$的位置所对应的数。

再来考虑任意一对数$Ai,Aj$，我们要求$lowbit(Ai \space xor \space Aj)$，即$Ai,Aj$在二进制表示下从低到高第一次出现对应位置的数不同时，这一位所对应的数。

于是，我们考虑做一棵$Trie$树，由于$lowbit(x)$求的是最低位的$1$，所以我们考虑倒序将数字插入到$Trie$树中，每一位对应一个结点，这样这棵$Trie$树就是一棵二叉树。

那么怎么统计答案呢？

我们还是考虑任意一对数$Ai,Aj$，当$Ai,Aj$的二进制位第一次不同时，它对答案才会有贡献。

我们假设我们正在遍历一个数$x$，那么当$x$遍历到自己的某一位时（即某个结点），如果发现该节点有两个儿子，就代表说一定有其他的数从第一位一直到这一位的二进制表达式都与它相同，但在下一位，它们不同了。

那么这有什么意义呢？此时他们对应位的数字第一次不同，我们之前说明过，在此时，它对答案有贡献。

那么问题来了，怎么知道有多少个数在此时与我们正在遍历的数$x$不同呢？我们可以对每个结点维护经过这一个结点的数的个数，然后我们就可以直接统计答案了。

注意$long \space long$

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
#include <stdio.h>
#include <iostream>
#define Re register int

typedef unsigned long long LL;
int N,tot;
const LL MOD=199907210507;
LL A[100005],e2[61],cnt[6000005],tr[6000005][2],ans;

template <typename T> inline void read(T &var)
{
	T x=0; int w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	var=w?-x:x;
}
inline int max(int a,int b) {return a>b?a:b;}
LL Solve(LL x)
{
	LL ret=0;
	for (Re cur=0,i=0; i<60; ++i)
	{
		int c=(x&1);
		if (tr[cur][c^1])
			(ret+=cnt[tr[cur][c^1]]%MOD*e2[i]%MOD)%=MOD;
		cur=tr[cur][c]; x>>=1;
	} return ret;
}
int main(int argc, char const *argv[])
{
	read(N); e2[0]=1;
	for (Re i=1; i<=60; ++i) e2[i]=e2[i-1]<<1;
	for (Re i=1; i<=N; ++i)
	{
		read(A[i]); LL tmp=A[i];
		for (Re cur=0,d=0; d<60; ++d)
		{
			int c=(tmp&1); ++cnt[cur];
			if (!tr[cur][c]) tr[cur][c]=++tot;
			cur=tr[cur][c]; tmp>>=1;
		}
	}
	for (Re i=1; i<=N; ++i)
		(ans+=Solve(A[i]))%=MOD;
	printf("%llu\n",ans);
	return 0;
}

T3

emmm…虽然是Day6的题，但是我10月8号中午才打出来（卧槽作业真TM多，我TM写了一整天）

。。。

考试的时候看见这题，感觉好像在哪里见过。然后我考完后到Luogu上搜了一下。。。

[国家集训队]跳跳棋清华集训

顿时惊了，算了算了写作业。。。

好了不扯了。

我们考虑一组坐标(x,y,z)(x,y,z)，那么每一次的决策可以分成下面几种情况：

  1. 让中间的棋子往左跳，最后的坐标就是(2x−y,x,z)
  2. 让中间的棋子往左跳，最后的坐标就是(x,z,2z−y)
  3. 让旁边的棋子往中间跳，这里还要分两种情况，我就不细写了。

然后呢，我们来观察一下这种变换，我们考虑往中间跳的操作，(u,v,w)的u或v往中间跳，得到状态(x,y,z)，把这个操作反过来，就相当于(x,y,z)往外跳到了状态(u,v,w)

所以我们可以考虑建一棵树，操作1,2就相当于当前状态的两个儿子，而操作33就是跳到它的父亲。

但是我们又面临了一个问题，状态太多存不下。

因为棋子都是一样的，所以我们只需要存下他的相对位置。

那么不妨令t1=y−x,t2=z−y，不妨设t1>t2，那么显然(x,y,z)的父亲(u,v,w)，满足v−u=t1−t2,w−v=t2，定义状态(t1,t2)可以转移到状态(t1−t2,t2)。那么显然每一个状态(x,y,z)对应唯一一个(t1,t2)，我们发现了什么？如果t1>t2，那么(t1,t2)−>(t1−t2,t2)或(t1,t2−t1)，那么难道不可以用取模来加速运算吗？即(t1,t2)−>(t1%t2,t2)或(t1,t2%t1)，刚好和求gcd一样！因此这么做就变成O(log2t2)了！

于是我们可以用O(log2k)的时间得到状态(x,y,z)往中间跳k步得到的状态；那么，我们首先判断初始状态和目标状态是否在一颗树中（即根节点是否相同），如果不同输出”NO”；否则，回忆倍增求lca的过程，类似的我们可以把初始状态和目标状态先提到同一个深度，然后二分它们到其lca的距离即可。

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
#include <stdio.h>
#include <iostream>
#include <algorithm>
#define INF int(1e9)
#define Re register int
using namespace std;

struct Node{
	int p[4];
	void read() {scanf("%d%d%d\n",&p[1],&p[2],&p[3]);}
	bool operator != (const Node a) const
	{
		for (Re i=1; i<=3; ++i)
			if (this->p[i]!=a.p[i]) return 1;
		return 0;
	}
}S,T;
int deep;

Node GetStatus(Node s,int l)
{
	int k=0;
	for (deep=0; l; deep+=k)
	{
		int t1=s.p[2]-s.p[1],t2=s.p[3]-s.p[2];
		if (t1==t2) return s;
		if (t1<t2)
		{
			k=min((t2-1)/t1,l);
			l-=k; s.p[1]+=k*t1;
			s.p[2]+=k*t1;
		}
		else
		{
			k=min((t1-1)/t2,l);
			l-=k; s.p[2]-=k*t2;
			s.p[3]-=k*t2;
		}
	} return s;
}
int main(int argc, char const *argv[])
{
	S.read(),T.read();
	sort(S.p+1,S.p+4); sort(T.p+1,T.p+4);
	Node fa1=GetStatus(S,INF); int d1=deep;
	Node fa2=GetStatus(T,INF); int d2=deep;
	if (fa1!=fa2) {puts("NO"); return 0;}
	if (d1>d2) swap(d1,d2),swap(S,T);
	T=GetStatus(T,d2-d1);
	int l=0,r=d1;
	while (l<=r)
	{
		int mid=(l+r)>>1;
		if (GetStatus(S,mid)!=GetStatus(T,mid)) l=mid+1;
		else r=mid-1;
	}
	printf("YES\n%d\n",d2-d1+2*l);
	return 0;
}