Codeforces Round #474 (Div. 1 + Div. 2) - C, F

https://codeforces.com/contest/960

F. Pathwalks

题意
给定 n 个点，m 条边的有向图，每条边有权值 $w_i$。
找出一条路径（可能经过某个点若干次），满足路径中所有边按照输入给边的顺序相连，并且权值严格上升。
在所有满足的路径中，找到边数最多的一条，输出其边数。

$(1\le n\le 10^5,1\le m\le 10^5,0\le wi\le 10^5)$

思路
因为路径中所有边按照输入顺序相连，权值严格上升，所以每输入一条边，就可以转移得到以该边结尾的所有路径中最长的长度。
对于给出的边 $x,y,w$，找所有指向节点 x 的边，用这些边中权值小于 w 的来转移。

用 f[i] 表示，以边 i 结尾的最长满足路径的长度。

那么也就是，找到指向节点 x 的所有权值小于 w 的边，用这些边的 f[i] 最大值转移。

但是遍历所有指向 x 的边找权值小于 w 的 f[i] 来转移复杂度太高，当有 1e5 个边相互指向两个点时，每给出一个边就要遍历其余所有边，复杂度是 n^2 的。需要想办法优化。

可以看出，每次只需要权值小于 w 的边中，最大的 f[i] 来转移，可以对于每个节点建立一个树状数组，将所有指向该点的边的权值 w 作为下标，f[i] 作为对应值。每次找 [1, w-1] 权值中 f[i] 的最大值，树状数组求区间最大值，O(logn)。

但是注意权值 wi 可能为 0，也就是说树状数组中下标 0 的位置也有对应值，但是在插入和询问的时候，无法处理 0 的情况，所以需要搞个偏移量，将所有边的权值都+1。

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];
map<int, int> c[N];

int lbit(int x){
	return x & -x;
}

void update(int k, int x, int y)
{
	for(int i=x;i<=100000;i+=lbit(i)){
		c[k][i] = max(c[k][i], y);
	}
}

int query(int k, int x)
{
	int maxa = 0;
	for(int i=x;i>=1;i-=lbit(i)){
		maxa = max(maxa, c[k][i]);
	}
	return maxa;
}

signed main(){
	Ios;
	cin >> n >> m;
	
	int ans = 0;
	while(m--)
	{
		int x, y, z; cin >> x >> y >> z;
		z ++;
		
		int maxa = query(x, z-1);
		
		update(y, z, maxa+1);
		
		ans = max(ans, maxa + 1);
	}
	cout << ans;
	
	return 0;
}
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

妙用树状数组！

其实当看到权值大小只有 1e5 的时候就应该看到端倪，处理方式如果和权值没关系的话，完全可以开到 1e9，而这题只有 1e5，那就要想是不是在数值范围上建立树状数组！

---

C. Subsequence Counting

题意
对于一个长度为 n 的数列来说，其子序列有 $2^n-1$ 个。
现在有一个数列，经过下面操作筛选过后只有 X 个子序列：

• 对于一个子序列来说，如果序列中元素最大值 - 元素最小值 ≥ d，那么该子序列将会被删掉。

给出 X 和 d，构造一个满足的数列，输出长度 n 和各元素 ai。

$1\le X,d\le 10^9$，
$1\le n\le 10^4,1\le ai<10^{18}$

思路
想特殊情况！！

对于一段数列 1 1 1 1 d+1 d+1 d+1 d+1 来说，其前半段和后边段不会产生合法子序列，因为一旦 1 和 1+d 同时存在，这个子序列就会被删掉。所以说前后两段互不影响。
所以，其左右两段产生的子序列的个数总和就是整个数列的子序列个数。

那么，整个序列的就可以这样构造：1 1 ... 1, 1+d 1+d ... 1+d, 1+2d 1+2d ... 1+2d, ...，将其子序列数二进制拼凑成 X 即可。

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];

signed main(){
	Ios;
	int x, d; cin >> x >> d;
	
	bitset<30> f(x);
	
	int t = 0;
	vector<int> v;
	for(int i=0;i<30;i++)
	{
		if(!f[i]) continue;
		int cnt = 1<<i;
		for(int j=1;j<=i;j++) v.push_back(t*d + 1);
		t ++;
		v.push_back(t*d + 1), t ++;
	}
	cout << v.size() << endl;
	for(int x : v) cout << x << " ";
	
	return 0;
}
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