#Codeforces Round 918 (Div. 4)

D:本题从实现上来说正难则反，应该倒着做

在我正着做的时候，由于在访问后面元素的时候没有判边界，导致数组越界，出现奇怪字符在最后答案中。

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
int n, m;
int a[N];
bool check(char c){
	if(c=='a'||c=='e')return true;
	else return false;
}
void solve(){
	cin>>n;
	string s;cin>>s;
	string ans;
	string tmp=".";
	for(int i=0;i<n;){
		//cerr<<i<<" ";
	
		if(check(s[i])==0){
			if(i)ans+=tmp;
			ans+=s[i];ans+=s[i+1];
			if(check(s[i+2])==0){
				if(check(s[i+3])){
					i+=2;
				}
				else {
					//if(i+2>=n)
					if(i+2<n)ans+=s[i+2];
					i+=3;
				///	cerr<<ans<<endl;
				}
			}
			else {
				i+=2;
			}
		}
		//cerr<<i<<endl;
		//ans+=tmp;
	}
	//cerr<<ans.size();
	cout<<ans<<endl;
}

E题：给定数组，问是否存在一段连续子数组满足奇数项的和等于偶数项。

Solution1：我们可以不去考虑奇偶性，而去考虑前缀和.-我们令原数组偶数项全部变为相反数，如果出现前缀和之前出现过或者为0，则存在
Solution2:对奇数位置和偶数位置做前缀和，分别记作p1,p2。

限制条件变成p1[R]−p1[L−1]==p2[R]−p2[L−1]p1[R]-p1[L-1]==p2[R]-p2[L-1]

交换位置，p2[L−1]−p1[L−1]==p2[R]−p1[R]p2[L-1]-p1[L-1]==p2[R]-p1[R]

把所有位置的 {奇偶前缀和之差,位置} 存入set 枚举L，在set里面二分找合法的R即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	set<int>s;
	int sum=0;
	s.insert(0LL);
	for(int i=1;i<=n;i++){
		if(i%2){
			sum+=a[i];
			
		}
		else {
			sum-=a[i];
			
		}
		if(s.count(sum)){
			cout<<"YES"<<endl;
		return ;
		}
		else s.insert(sum);
	}
	cout<<"NO"<<endl;
}

F:需要找到起点在自己后面，但是终点在自己前面的人的数量

Solution:对起点排序，省去一维，只看终点在自己前面的人，按照上述方式，我们需要倒着遍历。实现上由于值域很大，我们需要保序离散化。对于每个人的贡献由于需要动态加点和区间和查询，使用树状数组维护。
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
//每次要找到在排序后的a[i]的后面并且第二维小于b[i]的数需要，需要动态添加
//不能提前排序无法区分，使用树状数组
 
void solve(){
	// cin>>n;
	// vector<int>v;
	// for(int i=1;i<=n;i++){
		// int x,y;cin>>x>>y;
		// a[i]={x,y};
		// v.push_back(y);
	// }
	// sort(v.begin(),v.end());
	// for(auto x:v)cerr<<x<<" ";
	// cerr<<endl;
	// sort(a+1,a+1+n);
	// int ans=0;
	// //题目保证不重复
	// for(int i=1;i<=n;i++){
		// int val=a[i].second;
	// int pos=lower_bound(v.begin(),v.end(),val)-v.begin()+1;
		// ans+=pos-i;
		// cerr<<a[i].first<<" ";
		// cerr<<val<<" "<<pos-1<<endl;
	// }
	// cout<<ans<<endl;
	cin>>n;
	vector<int>ls;
	//这里需要有序离散化
	
	
	Fenwick<int>c(n+1);
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
	ls.push_back(y);
		a[i]={x,y};
		
	}
	sort(ls.begin(),ls.end());
	auto id=[&](int x){
	int pos=lower_bound(ls.begin(),ls.end(),x)-ls.begin()+1;
		return pos;
	};
	
//每个数关注比自己起点大的数的终点是不是比自己小
	sort(a+1,a+1+n);
	int ans=0;
	for(int i=n;i>=1;i--){
		auto [x,y]=a[i];
		y=id(y);
		ans+=c.sum(y);
		c.add(y,1);
	}
	cout<<ans<<endl;
}

G:求从1-n的最短路，特别的是加入自行车限制，在每个点可以选择使用当前点的自行车，或者继续使用自己之前的自己车，不同车对边权影响。

Solution：从思想上来说可以从分层图上理解，多加一维实现自行车的转移。也有人说就是二维dijstra,因为算法的正确性保证是在此基础上。对于当前每个点我们可以选择换城市不换自行车，或者换车不换城市(只能一次)
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
int n, m;
int a[N];
//dij加一维状态表示自行车信息
struct edge{int v,w;};
vector<edge>e[N];
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)e[i].clear();
	vector<int>s(n+1);
	for(int i=1;i<=m;i++){
		int u,v,w;cin>>u>>v>>w;
		e[u].push_back({v,w});
		e[v].push_back({u,w});
	}
 for(int i=1;i<=n;i++)cin>>s[i];
 priority_queue<a3, vector<a3>, greater<a3>>q; 
 vector<vector<int>>dis(n+1,vector<int>(n+1,1e18));
 vector<vector<bool>>vis(n+1,vector<bool>(n+1,0));
 q.push({0,1,1});
 dis[1][1]=0;
 while(q.size()){
 	auto [d,u,b]=q.top();q.pop();
 	if(vis[u][b]==true)continue;
 	vis[u][b]=true;
 	
 	
 	
 		for(auto [v,w]:e[u]){
 			if(dis[v][b]>d+w*s[b]){
 				dis[v][b]=d+w*s[b];
 				q.push({dis[v][b],v,b});
 			}
 		}
 		if(b!=u){
 		q.push({d,u,u});
 		dis[u][u]=d;
 		}
 	}
 
cout << *min_element(dis[n].begin() + 1, dis[n].begin() + n);
cout<<endl;

}