2020-09-03 / 04 test question solution

2020-09-03 test questions

Hobson's Trains

Title portal

General idea of the topic

Give a graph to ensure that each point has only one edge. For each point, add 1 to all the point answers on the path of \ (k \) step, and ask the answer of each last point.

\(n\le 5\times 10^5\)

thinking

It was sb time for the exam and I didn't figure out how to do it.

First of all, you can find that this is actually a base ring tree forest. For points that are not on the ring, the answer is actually the number of points whose depth in the subtree is no more than \ (k \). Considering the point on the ring, it is obvious that they also need to consider the contribution of other points on the ring to that point.

For specific implementation, we can disconnect an edge to turn it into a forest, and then calculate the number of points by using the tree array. Then, if it needs to be emptied every time, the time complexity will be reduced to \ (\ Theta(n^2) \), so we can only consider the growth. Time complexity \ (\ Theta(n\log n) \).

\(\texttt{Code}\)

vector <int> E[MAXN];
int n,k,cutu,cutv,f[MAXN],sum[MAXN],vis[MAXN],lim[MAXN],ans[MAXN];

int lowbit (int x){return x & (-x);}
void modify (int x){for (Int i = x;i <= n;i += lowbit (i)) sum[i] ++;}
int query (int x){int res = 0;for (Int i = min (n,x);i;i -= lowbit (i)) res += sum[i];return res;}

void dfs (int u,int dep){
	vis[u] = 1,ans[u] -= query (dep + k) - query (lim[u]),modify (dep);
	for (int v : E[u]) if (u != cutu || v != cutv) dfs (v,dep + 1);
	ans[u] += query (dep + k) - query (lim[u]);
}

signed main(){
	read (n,k);
	for (Int i = 1;i <= n;++ i) read (f[i]),E[f[i]].push_back (i);
	for (Int i = 1;i <= n;++ i){
		if (vis[i]) continue;
		int u = i,v;
		while (!vis[u]) vis[u] = 1,u = f[u];	
		v = f[u],cutu = v,cutv = u;
		for (Int len = k;v != u;v = f[v],len --) lim[v] = max (0,len);
		for (v = f[u];v != u;v = f[v]) ans[v] -= query (lim[v]);
		dfs (u,1);
		for (v = f[u];v != u;v = f[v]) ans[v] += query (lim[v]); 
	}
	for (Int i = 1;i <= n;++ i) write (ans[i]),putchar ('\n');
	return 0;
}

Save the dwarf

Portal title

General idea of the topic

There are \ (n \) points at the beginning, and each point has two weights \ (a,b \). If there is a set \ (s \) so that there is \ (a_i\{i\in s\}+b_k\ge h \) for \ (K \), then we can add 1 to the answer, but the subsequent set cannot contain this point.

Ask the maximum possible value of the answer\ (n\le 2\times 10^5\)

thinking

Like a retarded person in the exam, he wrote a false greed, and then wrote a balance tree. As a result, he only cheated the water data behind, and didn't get more points...

The positive solution is actually a repentance and greed. We sort according to \ (a+b \), and then you find that if we save the satisfied points, each time if the current point can be added directly, otherwise we will pull down the strongest one and save it.

Time complexity \ (\ Theta(n\log n) \).

\(\texttt{Code}\)

int n,H,ans;ll suma;

priority_queue <int> q;

struct node{
	int a,b;
	bool operator < (const node &p)const{return a + b < p.a + p.b;}
}peo[MAXN];

signed main(){
	read (n);
	for (Int i = 1;i <= n;++ i) read (peo[i].a,peo[i].b),suma += peo[i].a;
	sort (peo + 1,peo + n + 1),read (H);
	for (Int i = 1;i <= n;++ i){
		q.push (peo[i].a);
		if (suma + peo[i].b >= H) ans ++;
		else suma += q.top(),q.pop ();
		suma -= peo[i].a;
	}
	write (ans),putchar ('\n');
	return 0;
}

Easy

Title portal

General idea of the topic

The definition of \ (\ {a \} \) is legal. If and only if \ (\ sum {I = 1} ^ {K} a_i = n \), the definition of \ (\ {B \} \) is legal. If and only if \ (\ sum {I = 1} ^ {K} b_i = m \), the weight of \ (\ {a,b \} \) is defined as \ (\ prod {I = 1} ^ {K} \ min (a _i, B} \), ask the sum of the weights of all legal \ (\ {a,b \} \).

There are \ (t \) queries, and each time \ (n, m, K \) is given\ (t\le 100,n,m,k\le 5\times 10^5\)

thinking

I pushed it casually during the exam and cheated \ (60 \) points and didn't think about it, mainly because I didn't expect the binary generating function. After thinking about it, it's very simple. Just push the formula directly.

You find that the answer is:

\[(\sum_{a,b}\min(a,b)x^ay^b)^k[x^ny^m] \]

The proof is obvious.

Then you write the above thing, and you find that it is actually:

\[1xy+1xy^2+1xy^3+...\\1x^2y+2x^2y^3+2x^2y^4+...\\1x^3y+2x^3y^2+3x^3y^3+3x^3y^4+... \]

Then you use the formula of equal difference ratio and find that it is actually equivalent to:

\[\frac{xy}{(1-x)(1-y)(1-xy)} \]

Then find the \ ([x^ny^m] \) of this thing directly by using the partition method. Specifically, it is the number of enumeration \ (xy \).

Time complexity \ (\ Theta(tn) \) (assuming that \ (n,m \) is of the same order).

\(\texttt{Code}\)

read (N,M,K);
int ans = 0;
for (Int i = 0;i <= N - K && i <= M - K;++ i)
      ans = add (ans,mul (binom (K + i - 1,i),mul (binom (N - i - 1,N - K - i),binom (M - i - 1,M - K - i))));
write (ans),putchar ('\n');

2020-09-04 test questions

Tried the head iron and exploded...

express

General idea of the topic

Give a diagram with \ (n \) points and \ (m \) weighted edges. You need to access \ (2k \) points in turn. You have two portals. When the portals are placed, they must be guaranteed to be in the current position. The portals can be transmitted instantly. Ask the minimum path length after accessing all points.

\(n\le 300,m\le 4000,k\le 300\)

thinking

I guessed an obvious conclusion in the exam. I didn't expect to use dp, and then...

First of all, there is an obvious conclusion that there must be a portal right under my feet. Then we can set \ (dp[i][j] \) to indicate that the first \ (I \) point is accessed, and the minimum path length of the other portal is \ (j \). Obviously, \ (dp[0][1]=0 \). In the case of transfer type, we can think that it will only transfer between \ (dp[i-1][k] \), where \ (K \) is the position of the last portal. Then you can get the transfer type by enumerating the situation. See the code for details.

\(\texttt{Code}\)

dp[0][1] = 0,a[0] = 1;
for (Int i = 1;i <= k * 2;++ i){
      for (Int j = 1;j <= n;++ j){
	for (Int K = 1;K <= n;++ K)
	      dp[i][j] = min (dp[i][j],dp[i - 1][K] + dist[a[i - 1]][j] + dist[K][a[i]]),
	      dp[i][j] = min (dp[i][j],dp[i - 1][K] + dist[a[i - 1]][j] + dist[j][a[i]]),
	      dp[i][j] = min (dp[i][j],dp[i - 1][K] + dist[a[i - 1]][a[i]] + dist[K][j]),
	      dp[i][j] = min (dp[i][j],dp[i - 1][K] + dist[K][j] + dist[j][a[i]]);		
	}
}
int ans = dp[k * 2][1];
for (Int i = 1;i <= n;++ i) ans = min (ans,dp[k * 2][i]);
write (ans),putchar ('\n');

Graph

General idea of the topic

For a weighted tree with \ (n \) points, you can add or delete edges every time, but you need to ensure that the value of the weight XOR on the ring existing at any time is \ (0 \). Ask the sum of the minimum edge weights of the last \ (n-1 \) edge.

\(n\le 10^5\)

thinking

I was cheated by wxk and llsw. In fact, this topic is not very difficult (it may also be because I didn't do it myself)

We can find that if an edge is added between two points, the edge weight must be fixed, because if the variable edge weight on the ring is the same no matter how it is formed (the XOR value is \ (0 \)), it can be thought that if \ (p[u] \) is defined to represent the path XOR value of \ (1\to u \), the edge weight between \ (u,v \) is \ (p[u]\otimes p[v] \). So we can make the minimum spanning tree for \ (n^2 \) edges.

But it's obviously slow. We can think that if we consider from high to low, for the current bit, we should try to minimize the number of edges adjacent to two points, and the edges with \ (0,1 \) respectively. Obviously, only \ (1 \) edges are connected, and it is convenient not to consider the problem of disconnection (there are \ (n^2 \) edges). Then we can divide and conquer directly. Each time, divide and conquer with the bit \ (0 \) into a tree, and divide and conquer with the bit \ (1 \) into a tree, and then connect an edge with the least edge weight between the two trees. So the problem is how to find the edge with the least edge weight, and then you find that this thing can be solved directly with 01trie tree.

Time complexity \ (\ Theta(n\log^2 n) \)

\(\texttt{Code}\)

ll ans;
int n,tot,p[MAXN],rt[MAXN],cnt[MAXN * 31],son[MAXN * 31][2];

void ins (int a,int b,int t,int x)
{
	if (t < 0) return ;
	int i = x >> t & 1;
	son[a][i] = ++ tot;
	son[a][i ^ 1] = son[b][i ^ 1];
	cnt[son[a][i]] = cnt[son[b][i]] + 1;
	ins (son[a][i],son[b][i],t - 1,x);
}

int query (int a,int b,int t,int x)
{
	if (t < 0) return 0;
	int i = x >> t & 1;
	if (cnt[son[b][i]] > cnt[son[a][i]]) return query (son[a][i],son[b][i],t - 1,x);
	else return (1 << t) + query (son[a][i ^ 1],son[b][i ^ 1],t - 1,x);
}

int toop = 1,to[MAXN << 1],wei[MAXN << 1],nxt[MAXN << 1],head[MAXN];

void Add_Edge (int u,int v,int w){
	to[++ toop] = v,wei[toop] = w,nxt[toop] = head[u],head[u] = toop;
	to[++ toop] = u,wei[toop] = w,nxt[toop] = head[v],head[v] = toop;
}

void dfs (int u,int fa){
	for (Int i = head[u];i;i = nxt[i]){
		int v = to[i],w = wei[i];
		if (v == fa) continue;
		p[v] = p[u] ^ w,dfs (v,u);
	}
}

void dfs (int t,int l,int r){
	if (l >= r || t < 0) return ;
	int pos = r + 1,tmp = INF;
	for (Int i = l;i <= r;++ i) if (p[i] >> t & 1){pos = i;break;}
	dfs (t - 1,l,pos - 1),dfs (t - 1,pos,r);
	if (pos - 1 >= l && pos <= r){
		for (Int i = pos;i <= r;++ i) tmp = min (tmp,query (rt[l - 1],rt[pos - 1],29,p[i]));
		ans += tmp,tot = 0;
	}
}

signed main(){
	read (n);
	for (Int i = 2,u,v,w;i <= n;++ i) read (u,v,w),u ++,v ++,Add_Edge (u,v,w);
	dfs (1,0),sort (p + 1,p + n + 1);
	for (Int i = 1;i <= n;++ i) ins (rt[i] = ++ tot,rt[i - 1],29,p[i]);dfs (29,1,n);
	write (ans),putchar ('\n');
	return 0;
}

Tags: Graph Theory greedy algorithm partitioning dp

Posted by frosero on Wed, 18 May 2022 15:53:14 +0300