Post 35

Veröffentlicht am | Edited on

本来想这段时间做做高级算法综合题，不过hz跟我说有场他们出的比赛，我就参加了。

结果发现D题卡SPFA，不然就跟AH学长并列第一260了qwq(Starrydream)

img

然后就下午了，感觉不睡午觉会困qwq

先看道POI的Hash题。

「POI2010」珍珠项链 Beads

题目描述

Byteasar 决定制造一条项链，她买了一串珠子，她有一个机器，能把这条珠子切成很多段，使得每段恰有 kk 个珠子 (k>0)(k>0) ，如果这条珠子的长度不是 kk 的倍数，最后一块长度小于 kk 的段就被丢弃了。
Byteasar 想知道，选择什么数字 kk 可以得到最多的不同的段。注意这里的段是可以反转的，即，子串 1,2,31,2,3 和 3,2,13,2,1 被认为是一样的。

输入格式

第一行一个正整数 nn ，表示珠子的长度。
第二行 nn 个空格隔开的正整数 a_1,a_2,\cdots a_na1​,a2​,⋯an​ ，描述这一串珠子的颜色。

输出格式

第一行两个空格隔开的正整数，第一个表示能获得的最大不同的段的个数，第二个表示能获得最大值的 kk 的个数。
第二行若干空格隔开的正整数 kk ，表示所有能够取得最大值的 kk ，请将kk按照从小到大的顺序输出。

样例

输入样例

1
2
21
1 1 1 2 2 2 3 3 3 1 2 3 3 1 2 2 1 3 3 2 1

输出样例

1
2
6 1
2

数据范围与提示

对于 $100\%$ 的数据， $1\le n\le 2\times 10^5$

题解

这题好像很好写，尤其是你在想出翻转只需要对后缀hash之后。

我们需要map来判断这个串是否之前有相同的或者反串相同的。

时间复杂度$O(nlog^2n)$

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#define _MAX 200005
int n , c[_MAX] , now;
unsigned long long h[2][_MAX];
std::vector<int> ans;
struct Node{
	unsigned long long k1, k2;
	bool operator < (const Node& x)const{
		if(k1 == x.k1) return k2 < x.k2;
		return k1 < x.k1;
	}
};

inline unsigned long long pow(int x , int y)
{
	unsigned long long ans = 1 , base = x;
	for( ; y ; y >>= 1 , base *= base)
		if(y & 1)
			ans *= base;
	return ans;
}

inline void pre()
{
	for(int i = 1 ; i <= n ; ++i)
		h[0][i] = h[0][i-1] * 178431 + c[i];
	for(int i = n ; i >= 1 ; --i)
		h[1][i] = h[1][i+1] * 178431 + c[i];
}

inline unsigned long long Prehash(int l , int r){
	return h[0][r] - h[0][l-1] * pow(178431 , r-l+1);
}

inline unsigned long long Sufhash(int l , int r){
	return h[1][l] - h[1][r+1] * pow(178431,r-l+1);
}

inline int solve(int k)
{
	int ans = 0;
	std::map<unsigned long long , bool> v1;
	for(int i = k ; i <= n ; i += k)
	{
		if(v1[Prehash(i-k+1,i)] || v1[Sufhash(i-k+1,i)]) continue;
		++ans;
		v1[Prehash(i-k+1,i)] = true , v1[Sufhash(i-k+1,i)] = true;
	}
	return ans;
}

int main()
{
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&c[i]);
	pre();
	for(int i = 1 ; i <= n ; ++i)
	{
		if(n/i < now) continue;
		int k = solve(i);
		if(k > now){
			ans.clear();
			now = k;
			ans.push_back(i);
		}
		else if(k == now) ans.push_back(i);
	}

	printf("%d %d\n",now,(int)ans.size());
	for(int i = 0 ; i < (int)ans.size() ; ++i)
		printf("%d ",ans[i]);

}

LOJ#144. DFS 序 1

题目描述

这是一道模板题。

给一棵有根树，这棵树由编号为 1\dots N1…N 的 NN 个结点组成。根结点的编号为 RR。每个结点都有一个权值，结点 ii 的权值为 v_ivi。
接下来有 MM 组操作，操作分为两类：

  • 1 a x，表示将结点 aa 的权值增加 xx；
  • 2 a，表示求结点 aa 的子树上所有结点的权值之和。

输入格式

第一行有三个整数 N,MN,M 和 RR。
第二行有 NN 个整数，第 ii 个整数表示 v_ivi​。
在接下来的 N-1N−1 行中，每行两个整数，表示一条边。
在接下来的 MM 行中，每行一组操作。

输出格式

对于每组 \texttt{2 a}2 a 操作，输出一个整数，表示「以结点 aa 为根的子树」上所有结点的权值之和。

样例

样例输入 1

1
2


样例输出 1

1
2


样例输入 2

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
10 14 9
12 -6 -4 -3 12 8 9 6 6 2
8 2
2 10
8 6
2 7
7 1
6 3
10 9
2 4
10 5
1 4 -1
2 2
1 7 -1
2 10
1 10 5
2 1
1 7 -5
2 5
1 1 8
2 7
1 8 8
2 2
1 5 5
2 6

样例输出 2

1
2
3
4
5
6
7
21
34
12
12
23
31
4

数据范围与提示

$1\leqslant N, M\leqslant 10^6 1\leqslant R\leqslant N -10^6\leqslant v_i, x\leqslant 10^6$

题解

这道题只需要dfs，是不是很简单

树的dfs序可过，HPD大概率不可过。

我们通过树的dfs将树的每个节点连续编号，并且由于dfs的性质总是深度优先，所以只有一个点的子树全被编号才会回溯进入下一个点， 然后一个点$k$的子树在序编号上就是$k+sz_k$了，然后我们就可以用小常数的树状数组在序列上轻松完成题目要求了。

时间复杂度$O((n+m)logn)$

Code:

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <vector>
#define _max 1000005
int idx , dfn[_max] , n , v[_max] , sz[_max] , r , m ;
long long bit[_max] ;
std::vector<int> g[_max];

void dfs(int x , int fx)
{
	sz[x] = 1;
	dfn[x] = ++idx;
	for(int i = 0 ; i < (int)g[x].size() ; ++i)
	{
		int v = g[x][i];
		if(v == fx) continue;
		dfs(v , x) , sz[x] += sz[v];
	}
}

inline long long query(int pos)
{
	if(pos == 0) return 0;
	long long ans = 0;
	for( ; pos ; pos -= pos & -pos)
		ans += bit[pos];
	return ans;
}

inline void update(int pos , int val)
{
	for( ; pos <= n ; pos += pos & -pos)
		bit[pos] += val;
}

int main()
{
	scanf("%d%d%d",&n,&m,&r);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&v[i]);
	for(int i = 1 ; i <= n - 1 ; ++i)
	{
		int x , y ;
		scanf("%d%d",&x,&y);
		g[x].push_back(y) , g[y].push_back(x);
	}
	dfs(r,r);
	for(int i = 1 ; i <= n ; ++i)
		update(dfn[i],v[i]);
	for(int i = 1 ; i <= m ; ++i)
	{
		int op , pos , val;
		scanf("%d",&op);
		if(op == 1)
		{
			scanf("%d%d",&pos,&val);
			update(dfn[pos], val);
		}
		else if(op == 2)
		{
			scanf("%d",&pos);
			printf("%lld\n",query(dfn[pos] + sz[pos] - 1) - query(dfn[pos]-1));
		}
	}
}

「BalticOI 2014 Day 1」三个朋友

题目描述

本题译自 BalticOI 2014 Day1 T2「Three Friends」

给定一个字符串 SS，先将字符串 SS 复制一次（变成双倍快乐），得到字符串 TT，然后在 TT 中插入一个字符，得到字符串 UU。

给出字符串 UU，重新构造出字符串 SS。

所有字符串只包含大写英文字母。

输入格式

第一行一个整数 NN，表示字符串 UU 的长度。

第二行一个长度为 NN 的字符串，表示字符串 UU。

输出格式

一行一个字符串，表示字符串 SS。

特别地：

  • 如果字符串不是按照题述方法构造的，输出 NOT POSSIBLE；
  • 如果字符串 SS 不唯一，输出 NOT UNIQUE。

样例

样例输入 1

1
2
7
ABXCABC

样例输出 1

1
ABC

样例输入 2

1
2
6
ABCDEF

样例输出 2

1
NOT POSSIBLE

样例输入 3

1
2
9
ABABABABA

样例输出 3

1
NOT UNIQUE

数据范围与提示

子任务 分数 数据范围
1 3535 2\le N\le 20012≤N≤2001
2 6565 2\le N\le 20000012≤N≤2000001

题解

这题思路不难想。

首先分类讨论，要么在左半边要么右半边，然后枚举字符，利用hash快速算出删除那部分的hash和没删除的一半的hash，然后比较相等不相等就行了。

关键在于如何快速合并两个hash，这感觉是数学了吧。。

我们将删除左边的那部分串的绝对hash算出来（就是前缀hash通过快速幂相减），然后*base在加上另一部分。

然后这个值整体乘base在$2^{64}$下的逆元就可以了。。

不知道这个口胡的方法对不对，总之大体思路就是这样的，等有心情写代码就试试。

LOJ#10064. 「一本通 3.1 例 1」黑暗城堡

题目描述

你知道黑暗城堡有 NN 个房间，MM 条可以制造的双向通道，以及每条通道的长度。

城堡是树形的并且满足下面的条件：

设 D_iDi 为如果所有的通道都被修建，第 ii 号房间与第 11 号房间的最短路径长度；

而 S_iSi 为实际修建的树形城堡中第 ii 号房间与第 11 号房间的路径长度；

要求对于所有整数 ii (1\le i\le N1≤i≤N)，有 S_i= D_iSi=Di 成立。

你想知道有多少种不同的城堡修建方案。当然，你只需要输出答案对 2^{31} -1231−1 取模之后的结果就行了。

输入格式

第一行为两个由空格隔开的整数 N, MN,M;

第二行到第 M+1M+1 行为 33 个由空格隔开的整数 x, y, lx,y,l：表示 xx 号房间与 yy 号房间之间的通道长度为 ll。

输出格式

一个整数：不同的城堡修建方案数对 2^{31} -1231−1 取模之后的结果。

样例

样例输入

1
2
3
4
5
6
7
4 6
1 2 1
1 3 2
1 4 3
2 3 1
2 4 2
3 4 1

样例输出

1
6

样例说明

一共有 44 个房间，66 条道路，其中 11 号和 22 号，11 号和 33 号，11 号和 44 号，22 号和 33 号，22 号和 44 号，33 号和 44 号房间之间的通道长度分别为 11，22，33，11，22，11。

而不同的城堡修建方案数对 $2^{31}$ -1取模之后的结果为 66。

数据范围与提示

对于全部数据，$1\le N\le 10001≤N≤1000，1\le M\le \frac{N(N-1)}{2}1≤M≤2N(N−1)$

题解

这个题我似乎受一道高难度图论省选题的启发想出了一个做法。

首先一眼看出这是让你求最短路径生成树的个数。

我们大概知道一个最短路径生成树怎么求。

但是求个数的话。

不妨联想如果我们把所有最短路加到一个图里，是不是可以通过某些神奇的组合原理统计答案呢？

答案是肯定的。

这个所有最短路都被加入的图是有拓扑性质的，为什么呢？

证明命题：最短路图中不存在正环（0环和负环题目必须保证不存在）

从定义出发，如果图中有正环，那么从左和右必有一个更小的，因此不能有环。

严谨证明By shadowice：

原理，我们发现如果有最短路就不可以有负环，因此，我们考虑走过属于一条最短路的一条边的过程，我们会发现，一定是从dis值低的点走到了dis值高的点(因为没零环)，相当于我们一直在上坡，而显然，一个一直上坡的环是不存在的

因此我们在DIJKSTRA的过程中建出这个图（反向，不然怎么统计呢？），然后通过拓扑排序+dp可以在$O(n+m)$

的时间里求出这个方案数。

然后由于现在非常懒，所以不想写代码。

话说我能想出这道题还真是被HAOI的道路那道题启发了呢。

关于用Dijkstra如何求严格次短路。

显然有些奇怪的人严格次短路也不想让你用SPFA，那么我们就应该想想如何使用DIJKSTRA求次短路。

严格次短路还是挺简单的，非严格次短路可能比较麻烦，也许得记录最短路的更新点然后再枚举边。。

严格只需要枚举每条边，然后这条边的边权加上源点到这条边一个点的距离加上终点到另一个的最短路大于源点到终点的最短路即可，至于为什么这样做是正确的，好像只需要从最短路的定义出发就不难证明。。

证明：对于枚举的边，如果在最短路上，两端点必然都是最短路的值，否则，根据仅次于最短路，我们应该让到达这条边和从这条边到终点都尽可能小。可能这种贪心保证最后答案一定正确且最优吧。。

不会证明qwq

Color a Tree

Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 8640 Accepted: 2980

Description

Bob is very interested in the data structure of a tree. A tree is a directed graph in which a special node is singled out, called the “root” of the tree, and there is a unique path from the root to each of the other nodes.

Bob intends to color all the nodes of a tree with a pen. A tree has N nodes, these nodes are numbered 1, 2, …, N. Suppose coloring a node takes 1 unit of time, and after finishing coloring one node, he is allowed to color another. Additionally, he is allowed to color a node only when its father node has been colored. Obviously, Bob is only allowed to color the root in the first try.

Each node has a “coloring cost factor”, Ci. The coloring cost of each node depends both on Ci and the time at which Bob finishes the coloring of this node. At the beginning, the time is set to 0. If the finishing time of coloring node i is Fi, then the coloring cost of node i is Ci * Fi.

For example, a tree with five nodes is shown in Figure-1. The coloring cost factors of each node are 1, 2, 1, 2 and 4. Bob can color the tree in the order 1, 3, 5, 2, 4, with the minimum total coloring cost of 33.
img
Given a tree and the coloring cost factor of each node, please help Bob to find the minimum possible total coloring cost for coloring all the nodes.

Input

The input consists of several test cases. The first line of each case contains two integers N and R (1 <= N <= 1000, 1 <= R <= N), where N is the number of nodes in the tree and R is the node number of the root node. The second line contains N integers, the i-th of which is Ci (1 <= Ci <= 500), the coloring cost factor of node i. Each of the next N-1 lines contains two space-separated node numbers V1 and V2, which are the endpoints of an edge in the tree, denoting that V1 is the father node of V2. No edge will be listed twice, and all edges will be listed.

A test case of N = 0 and R = 0 indicates the end of input, and should not be processed.

Output

For each test case, output a line containing the minimum total coloring cost required for Bob to color all the nodes.

Sample Input

1
2
3
4
5
6
7
5 1
1 2 1 2 4
1 2
1 3
2 4
3 5
0 0

Sample Output

1
33

Source

Beijing 2004

题解

算法竞赛进阶指南上一道挺神的贪心。

用到了等效替代的思想，贪心里用这个东西一定要注意完全等效，是需要数学推导的。

发现还是不会，贪心好难啊qwq，以后还会回来看的。。

Dynamic Rankings

Description

给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1

],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改

变后的a继续回答上面的问题。

Input

第一行有两个正整数n(1≤n≤10000)，m(1≤m≤10000)。

分别表示序列的长度和指令的个数。

第二行有n个数，表示a[1],a[2]……a[n]，这些数都小于10^9。

接下来的m行描述每条指令

每行的格式是下面两种格式中的一种。

Q i j k 或者 C i t

Q i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1）

表示询问指令，询问a[i]，a[i+1]……a[j]中第k小的数。

C i t (1≤i≤n，0≤t≤10^9)表示把a[i]改变成为t

m,n≤10000

Output

对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。

Sample Input

5 3

3 2 1 4 7

Q 1 4 3

C 2 6

Q 2 5 3

Sample Output

3

6

题解

终于想明白带修改的整体二分该怎么做，再写今天最后一篇口胡题解。

我们还是按照值域划分。不过把修改拆成删除原数加入新数两个修改。

设计一个函数$solve(l,r,s,t)$表示分治值域$l,r$对于在这个值域内的修改$s,t$

然后利用权值树状数组进行统计。

然后对于个数小于等于$k$的把询问加在分治左边，大于$k$的放在右边，这里和静态整体二分是一样的。

唯一不同的是我们对修改也这么分类（按照值域），然后将同一类的复制到原数组使其连续然后继续分治。

终于明白了。