TEST 11

A. 拆盒子

• 贪心贪过去就好了

  signed main() {
      IOS;
      string s;
      cin >> s;
      int len = s.size();
      int sum = 0;
      for (int i = 0; i < len; i++) {
          if (s[i] == '(') sum++;
          else if(s[i] == ')') sum--;
          else break;
      }
      cout << sum << endl;
  
      return 0;
  }

B. 数组调整

• 枚举最小值，算最大值就好了

  signed main() {
      IOS;
      int n;
      cin >> n;
      vector<int> v(n);
      for (int i = 0; i < n; i++) {
          cin >> v[i];
      }
      ll ans = 1e18;
      for (int i = 0; i <= 100; i++) {
          ll res = 0;
          for (int j = 0; j < n; j++) {
              int x = v[j];
              if (x > i + 17) res += (x - i - 17) * (x - i - 17);
              else if (x < i) res += (i - x) * (i - x);
          }
          ans = min(ans, res);
      }
      cout << ans << endl;
      return 0;
  }

C. 密码

• 递归搜索

  int dfs(string s) {
      if ((s.size() % 2) == 0) return 1;
      int m = s.size() >> 1;
      int sumL = (s.substr(1, m) == s.substr(m + 1, m)) + (s.substr(0, m) == s.substr(m + 1, m));
      int sumR = (s.substr(0, m) == s.substr(m + 1, m)) + (s.substr(0, m) == s.substr(m, m));
      return (sumL ? dfs(s.substr(0, m + 1)) * sumL : 0) + (sumR ? dfs(s.substr(m, m + 1)) * sumR : 0) + 1;
  }
  
  signed main() {
      IOS;
      string s;
      cin >> s;
      cout << dfs(s) - 1 << endl;
  
      return 0;
  }

D. 序列操作

• 从前往后贪心就好了，然后加一个特判

  signed main() {
      IOS;
      int n;
      cin >> n;
      vector<int> a(n + 1);
      for(int i = 1; i <= n; i++) {
          cin >> a[i];
      }
      ll ans = 0;
      for (int i = 1; i <= n; i++) {
          int x;
          cin >> x;
          a[i] -= x;
          ans += max(0, a[i] - a[i - 1]);
      }
      ans += max(0, -1 * a[n]);
      cout << ans << endl;
  
      return 0;
  }

E. 交错序列

int n, k;
#define MAX 30
int DP[MAX][MAX][2], st[MAX];

void init() {
	DP[1][1][0] = 1, DP[1][1][1] = 1;
	for (int i = 2; i <= 20; i++) {
		for (int j = 1; j <= i; j++) {
			for (int k = 1; k < j; k++) {
				DP[i][j][1] += DP[i - 1][k][0];
			}
			for (int k = j; k < i; k++) {
				DP[i][j][0] += DP[i - 1][k][1];
			}
			//cout << DP[i][j][0] << ' ' << DP[i][j][1] << endl;
		}
	}
}

void solve() {
	cin >> n >> k;
	memset(st, 0, sizeof(st));
	int lst = 0, id = 0;
	for (int i = 1; i <= n; i++) {
		if (DP[n][i][1] >= k) {
			lst = i, id = 1;
			break;
		}
		k -= DP[n][i][1];
		if (DP[n][i][0] >= k) {
			lst = i, id = 0;
			break;
		}
		k -= DP[n][i][0];
	}
	cout << lst << ' ';
	st[lst] = 1;
	for (int i = n - 1; i >= 1; i--) {
		id ^= 1;
		int cnt = 0;
		for (int j = 1; j <= n; j++) {
			if (st[j])
				continue;
			cnt++;
			if ((id == 0 && j < lst) || (id == 1 && j > lst)) {
				if (DP[i][cnt][id] >= k) {
					lst = j; break;
				}
				else
					k -= DP[i][cnt][id];
			}
		}
		st[lst] = 1;
		cout << lst << ' ';
	}
	cout << endl;
}

signed main() {
	IOS;
	int T;
	cin >> T;
	init();
	while (T--) {
		solve();
	}

	return 0;
}

F. 动态建边

• 树上前缀和 + dfs序 + 并查集 + 离线
• 虽然每个都不难但合在一起就是很有意思

  #define MAX 300005
  int n, m, w[MAX];
  int tot, L[MAX], R[MAX], d[MAX], dis[MAX], f[MAX][20];
  vector<int> G[MAX];
  
  struct dat {
  	string s;
  	int x, y, ans;
  } a[MAX];
  int F[MAX];
  int find(int x) {
  	if (x == F[x]) {
  		return x;
  	}
  	else {
  		return F[x] = find(F[x]);
  	}
  }
  int c[MAX];
  void add(int x, int k) {
  	for (; x <= n; x += (x & (-x)))
  		c[x] += k;
  }
  
  int ask(int x) {
  	int ans = 0;
  	for (; x; x -= (x & (-x)))
  		ans += c[x];
  	return ans;
  }
  
  void dfs(int x, int fa) {
  	L[x] = ++tot;
  	d[x] = d[fa] + 1;
  	f[x][0] = fa;
  	dis[x] = dis[fa] + w[x];
  	add(L[x], dis[x]), add(L[x] + 1, -dis[x]);
  	for (int i = 1; i <= 18; i++) {
  		f[x][i] = f[f[x][i - 1]][i - 1];
  	}
  	for (int y : G[x]) {
  		if (y == fa) {
  			continue;
  		}
  		dfs(y, x);
  	}
  	R[x] = tot;
  }
  int LCA(int x, int y) {
  	if (d[x] < d[y]) {
  		swap(x, y);
  	}
  	for (int i = 18; ~i; i--) {
  		if (d[f[x][i]] >= d[y])
  			x = f[x][i];
  	}
  	if(x == y)
  		return x;
  	for (int i = 18; ~i; i--) {
  		if(f[x][i] == f[y][i])
  			continue;
  		x = f[x][i], y = f[y][i];
  	}
  	return f[x][0];
  }
  
  
  signed main() {
  	IOS;
  	cin >> n;
  	for (int i = 1; i <= n; i++) {
  		cin >> w[i];
  		F[i] = i;
  	}
  	cin >> m;
  	for (int i = 1, x, y, ans; i <= m; i++) {
  		string s;
  		cin >> s >> x >> y;
  		ans = 0;
  		if (s == "bridge") {
  			int fx = find(x), fy = find(y);
  			if (fx != fy) {
  				ans = 1;
  				F[fy] = fx;
  				G[x].push_back(y), G[y].push_back(x);
  			}
  		}
  		if (s == "excursion") {
  			int fx = find(x), fy = find(y);
  			if (fx != fy)
  				ans = 1;
  		}
  		a[i] = {s, x, y, ans};
  	}
  	for (int i = 1; i <= n; i++) {
  		if (!L[i])
  			dfs(i, 0);
  	}
  	for (int i = 1; i <= m; i++) {
  		//auto [s, x, y, ans] = a[i];
  		string s = a[i].s;
  		int x = a[i].x, y = a[i].y, ans = a[i].ans;
  		if (s == "bridge")
  		{
  			cout << (ans ? "yes" : "no") << endl;
  		}
  		else if (s == "penguins")
  		{
  			add(L[x], y - w[x]);
  			add(R[x] + 1, w[x] - y);
  			w[x] = y;
  		}
  		else {
  			//cout << ans << ' ';
  			if (ans) {
  				cout << "impossible" << endl;
  				continue;
  			}
  			//cout << ans << ' ';
  			int t = LCA(x, y);
  			cout << ask(L[x]) + ask(L[y]) - ask(L[t]) - ask(L[f[t][0]]) << endl;
  		}
  	}
  
  		return 0;
  }