2022.07.06 summer training personal qualifying (I)

2022.07.06 Summer training Individual qualifying （ One ）

Post game introspection

Reading questions is not smooth , Do the topic in the wrong direction , As a result, many questions have been repeatedly staggered .

Sensitivity to dynamic programming is still not enough , Fill in more questions .

Problem A

Source

Codeforces-793D

The question

Let's give a digraph , Find one that happens to pass by k The shortest path of a point , It is required that each selected edge cannot jump over the nodes that have passed before . That is, for the edges in the path $x\to y$ , There are no previous points t Make the numbers of the three meet $min(x,y)\le t\le max(x,y)$ .

Answer key

lcj Answer key

There are two forms of points in a path , Or as 1,10,2,8,4,6,5 So shrink from both ends to the middle , Or as 1,3,4,5,7,8,10 So expand in one direction （ It will be more vivid to draw on the number axis ）.
On the contrary, considering the two situations, it will be unified to expand the point outward , That is, the range of points that have passed continues to expand , use l,r Indicates the end point of the interval , What we need is all the experience k The minimum weight of the interval of points .
It can be used dp[i][j][K][0/1] Said by K Points pass by and the last point is i/j（ The fourth dimension 0 Corresponding i,1 Corresponding j） The range of [i,j] The minimum weight of , And then the interval dp.
There are four kinds of transfers , Almost. , Here is an example ：dp[i-d][j][k][0]=min(dp[i][j][k-1][0]+g[i][i-d]),（d Is the difference between the target interval length and the current interval length ）.
Chinese version of the title link

Code

// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm> 
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;


const int N = 105;
int n, T = 1, ki, m;
int dp[N][N][N][2];
int g[N][N];

void ready()
{
    
	cin >> n >> ki >> m;
	ffor(i, 1, m) {
    
		int u, v, c;
		cin >> v >> u >> c;
		if (g[u][v] == 0) g[u][v] = c;
		else g[u][v] = min(g[u][v], c);
	}
	if (ki > n) {
    
		cout << -1;
		return;
	}
	ffor(i, 1, n) {
    
		ffor(j, 1, n) {
    
			ffor(k, 1, n) {
    
				dp[i][j][k][0] = dp[i][j][k][1] = inf;
			}
		}
	}
	ffor(i, 1, n)  dp[i][i][1][1] = dp[i][i][1][0] = 0;
	ffor(len, 2, n) {
     // l r k 0/1
		ffor(l, 1, n) {
    
			ffor(r, l, n) {
    
				if (r - l + 1 == len) break;
				int las = len - (r - l + 1);
				ffor(k, 1, ki - 1) {
    
					if (dp[l][r][k][0] != inf) {
    
						if (l - las > 0 && g[l][l - las]) {
    
							dp[l - las][r][k + 1][0] = min(dp[l - las][r][k + 1][0], dp[l][r][k][0] + g[l][l - las]);
						}
						if (r + las <= n && g[l][r + las]) {
    
							dp[l][r + las][k + 1][1] = min(dp[l][r + las][k + 1][1], dp[l][r][k][0] + g[l][r + las]);
						}
					}
					if (dp[l][r][k][1] != inf) {
    
						if (l - las > 0 && g[r][l - las]) {
    
							dp[l - las][r][k + 1][0] = min(dp[l - las][r][k + 1][0], dp[l][r][k][1] + g[r][l - las]);
						}
						if (r + las <= n && g[r][r + las]) {
    
							dp[l][r + las][k + 1][1] = min(dp[l][r + las][k + 1][1], dp[l][r][k][1] + g[r][r + las]);
						}
					}
				}
			}
		}
	}
	int ans = inf;
	ffor(i, 1, n) {
    
		ffor(j, 1, n) {
    
			ans = min(ans, min(dp[i][j][ki][1], dp[i][j][ki][0]));
		}
	}
	if (ans == inf) ans = -1;
	cout << ans;
}


void work()
{
    

}

signed main()
{
    
	IOS;
	// cin>>T;
	while (T--) {
    
		ready();
		work();
	}
	return 0;
}

Problem B

Source

Codeforces-803E

The question

A string of characters is n, Contains only L（ Failure ）、W（ victory ）、D（ It ends in a draw ）、？（ Forget the result ）. Need to put ？ use L/W/D To replace , So that when the last character is reached L The number of W The absolute value of the difference of the number of is k, And can't reach halfway k That is, the above . Restore the original sequence , If the output cannot be completed NO.

Answer key

Method 1 ： Memory search

Ordinary search will timeout , So add memorization . Why is memorization effective ？ When you search for u A place , And for sum when , If this status has been searched , If correct , Then the search will be over . And being able to search this state again means that all States after this state have been searched , And cannot meet the conditions , So when you step into the same state again, prune it directly .

// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm> 
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;



const int N = 1e4;
int n, T = 1,k;
char ch[N];
map<int, int> mp[N];

void ready()
{
    
	cin >> n >> k;
	cin >> ch + 1;
}

bool dfs(int u, int sum) {
    
	if (u == n + 1 && abs(sum) == k) return true;
	if (u == n + 1 || abs(sum) >= k) return false;
	if (mp[u][sum]) return false;
	mp[u][sum] = 1;
	if (ch[u] == 'W') return dfs(u + 1, sum + 1);
	if (ch[u] == 'L') return dfs(u + 1, sum - 1);
	if (ch[u] == 'D') return dfs(u + 1, sum);
	if (dfs(u + 1, sum + 1)) {
    
		ch[u] = 'W';
		return true;
	}
	if (dfs(u + 1, sum - 1)) {
    
		ch[u] = 'L';
		return true;
	}
	if (dfs(u + 1, sum)) {
    
		ch[u] = 'D';
		return true;
	}
	return false;
}

void work()
{
    
	if (dfs(1, 0)) cout << ch + 1;
	else cout << "NO";
}

signed main()
{
    
	IOS;
	// cin>>T;
	while (T--) {
    
		ready();
		work();
	}
	return 0;
}

Method 2 ：DP

Lnn Brother problem solution ：

B. character string 、 Class backpack dp
1.n Only 1000, Prefix and scope -1000 To 1000
2. Consider enumerating all States , utilize dp
3.dp[i][j] For position i At value j when , What is the last status value ;-1 Represents that the state is not feasible
4. enumeration i, Enumerate the last state j, if $dp[i-1][j]!=-1$, According to the current letter
if $a[i]{=}^{\prime }{W}^{\prime }{/}^{\prime }{L}^{\prime }{/}^{\prime }{D}^{\prime },val=1/-1/0,dp[i][j+val]=j$
5. Check out $dp[n][k]/dp[n][-k]$ Is it feasible , Continue to move to the previous state , Get the answer string

// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm> 
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;


const int N = 1e3 + 5;
int dp[N][2 * N];
int zero = 1000;
int n, T = 1, k;
char ch[N];
char chan[3] = {
     'W','L','D'};
vector<char> ans;

void ready()
{
    
	cin >> n >> k;
	cin >> ch + 1;
	mst(dp, -1);
}


void work()
{
    
	dp[0][zero] = 0;
	for (int i = 1; i <= n; i++) {
    
		ffor(ki, 0, 2) {
    
			if (ch[i] != chan[ki] && ch[i] != '?') continue;
			int val = 0;
			if (ki == 0) val = 1;
			if (ki == 1) val = -1;
			ffor(j, zero - k + 1, zero + k - 1) {
    
                // Because you can't exceed k, So all States should be from less than k Push in , So left section +1, The right range -1
				if (dp[i - 1][j] != -1) {
    
					dp[i][j + val] = j;
				}
			}
		}
	}
	if (dp[n][zero + k] != -1 || dp[n][zero - k]!= -1) {
    
		int now;
		if (dp[n][zero + k] == -1) {
    
			now = zero - k;
		}
		else {
    
			now = zero + k;
		}
		rrep(i, n, 1) {
    
			if (now == dp[i][now]) ans.push_back('D');
			if (now == dp[i][now] + 1) ans.push_back('W');
			if (now == dp[i][now] - 1) ans.push_back('L');
			now = dp[i][now];
		}
		rrep(i, ans.size() - 1, 0) cout << ans[i];
	}
	else {
    
		cout << "NO";
	}
}

signed main()
{
    
	IOS;
	// cin>>T;
	while (T--) {
    
		ready();
		work();
	}
	return 0;
}

Problem C

Source

Codeforces-909E

The question

Yes n A mission , And by the m A dependency . To complete a task , Then all previous dependent tasks must be completed . Each task has two states , Or the status is 1, Or the status is 0. Every time I finish 1 Task No. 1 will cost 1 Time cost , But you can complete a group 1 Task , The premise is that these 1 The dependent tasks of task No. are all completed . Ask what the minimum cost is .

Answer key

Open two queues for two tasks for topology , Finish topology first 0 Task , Finish again 1 Task , That is, try to set as a group 1 All tasks are completed together .

Code

#include <iostream>
#include <queue>

using namespace std;

const int N=1e5+5;
int n,m;
vector<int> ve[N];
int in_[N];
int ans;

int e[N];

int main()
{
    
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>e[i];
    for(int i=1;i<=m;i++){
    
        int x,y;
        cin>>x>>y;
        in_[x]++;
        ve[y].push_back(x);
    }
    queue<int> q0,q1;
    for(int i=0;i<n;i++){
    
        if(in_[i]==0)
        {
    
            if(e[i]==0) q0.push(i);
            else q1.push(i);
        }
    }
    while(q0.size() || q1.size()){
    
        if(q0.size()){
    
            while(q0.size()){
    
                int u=q0.front();
                q0.pop();
                for(auto v:ve[u]){
    
                    in_[v]--;
                    if(in_[v]==0){
    
                        if(e[v]==0) q0.push(v);
                        else q1.push(v);
                    }
                }
            }
        }
        if(q1.size()){
    
            ans++;
            while(q1.size()){
    
                int u=q1.front();
                q1.pop();
                for(auto v:ve[u]){
    
                    in_[v]--;
                    if(in_[v]==0){
    
                        if(e[v]==0) q0.push(v);
                        else q1.push(v);
                    }
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

Problem F

Source

Codeforces 638-C

The question

n A tree formed by a city , The side is the road connecting the two cities . Now we have to start building roads , For a road <u,v> It needs workers from two cities to repair at the same time , And there is only one worker in each city , A worker can only build one road in a day . How many days will it take to complete all the roads at least ？

Answer key

By reason , The minimum number of days must be the maximum degree . After knowing the number of days , Is to arrange the road .

Open a bucket with the minimum number of days . Start from any root node , Conduct dfs. Every time we reach one side , Put it in the bucket , Then the index of the bucket ++. That is to say, it is guaranteed that dfs In , All sides of a point exist in different buckets .

Code

#include <iostream>
#include <vector>
#include<algorithm>
#include <map>
using namespace std;

const int N = 2e5 + 5;
bool vis[N], f[N];
int ansi;
int n;
vector<int> ve[N]; 
vector<int> ans[N];

struct Edge {
    
    int x, y;
}e[N];

void dfs(int u,int k) {
    
    vis[u] = true;
    for (auto id : ve[u]) {
    
        int ex = e[id].x, ey = e[id].y;
        int v = (ex == u ? ey : ex);
        if (!vis[v]) {
    
            ans[k].push_back(id);
            k++;
            if (k > ansi) k = 1;
        }
    }
    for (auto id : ve[u]) {
    
        int ex = e[id].x, ey = e[id].y;
        int v = (ex == u ? ey : ex);
        if (!vis[v]) {
    
            dfs(v,k);
        }
    }
}

int main()
{
    
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
    
        int x, y;
        cin >> x >> y;
        ve[x].push_back(i);
        ve[y].push_back(i);
        e[i].x = x; e[i].y = y;
        int vex = ve[x].size(), vey = ve[y].size();
        ansi = max(ansi, max(vex, vey));
    }
    dfs(1,1);
    cout << ansi << '\n';
    for(int i=1;i<=ansi;i++) {
    
        cout << ans[i].size() << ' ';
        for (auto v : ans[i]) {
    
            cout << v << ' ';
        }
        cout << '\n';
    }
    return 0;
}

Problem E

Source

Codeforces-746G

The question

Build a tree ,1 Root , There is $t$ layer . The first $i$ The number of root nodes of the layer is $a_i$, Finding a connection method requires that the number of final leaf nodes is given $k$.

Answer key

Lnn Brother's solution

E. Trees 、 leaf 、 structure

1. Assign values to nodes directly in sequence , such as a[] = {2,3,2}
   first floor ：1
   The second floor ：2 3
   The third level ：4 5 6
   The fourth level ：7 8 （ In this way, it is convenient to find the corresponding nodes of the upper and lower layers
2. The structure is simpler ： First construct the scheme with the least leaves , Not enough
   Directly connect each point to the node directly above , such as 1-2,3-5,5-8
   If there is no , It's the first one on the upper floor , such as 6-2
3. You can think of it , Some nodes must be leaves , such as 6、7、8
   If you want to patch leaves , It is necessary to remove all the child nodes of a point
   A unified , Move the child node to the current layer 1 individual , such as 5-8 To 4-8
4. Ensure the nature of the tree , The first node in each row cannot be a leaf
5. Last , There are not enough leaves or More , It outputs -1

Code

// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm> 
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;

const int N = 2e5 + 5;

int n, T = 1, t, k;
int a[N], fa[N], ans;
bool f[N];
vector<int> tree[N];

void ready()
{
    
	int temp = 1;
	cin >> n >> t >> k;
	t += 1;
	a[1] = 1;
	tree[1].push_back(1);
	ffor(i, 2, t) {
    
		cin >> a[i];
		ffor(j, 1, a[i]) {
    
			temp++;
			tree[i].push_back(temp);
		}
	}
	for (int i = 2; i <= t; i++) {
    
		int las = tree[i - 1].size();
		for (int j = 0; j < tree[i].size(); j++) {
    
			if (j >= las) fa[tree[i][j]] = tree[i - 1][0];
			else fa[tree[i][j]] = tree[i - 1][j];
		}
	}
	ffor(i, 1, n)  f[fa[i]] = true;
	ffor(i, 1, n) if (!f[i]) ans++;
	for (int i = 1; i <= t; i++) {
    
		//for (auto item : tree[i]) cout << item << ' ';
		//cout << '\n';
	}
	//cout << ans << '\n';
}

void out() {
    
	cout << n << '\n';
	ffor(i, 2, n) {
    
		cout << i << ' ' << fa[i] << '\n';
	}
	return;
}

void work()
{
    
	if (ans > k) {
    
		cout << -1;
		return;
	}
	if (ans == k) {
    
		out();
		return;
	}
	rrep(i, t, 2) {
    
		ffor(j, 1, a[i]-1) {
    
			if (fa[tree[i][j]] != tree[i - 1][0]) {
    
				ans++;
				fa[tree[i][j]] = tree[i - 1][0];
			}
			if (ans == k) {
    
				out();
				return;
			}
		}
	}
	if (ans < k) {
    
		cout << -1;
		return;
	}
}

signed main()
{
    
	IOS;
	// cin>>T;
	while (T--) {
    
		ready();
		work();
	}
	return 0;
}