2025寒假专场4

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, h, k;

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
typedef pair<int, int> PII;
map<PII, bool>v;
int main(){
	cin >> n >> m >> h >> k;
	string steps;
	cin >> steps;
	for(int i = 1; i <= m; i ++ ){
		int x, y;
		cin >> x >> y;
		v[{x, y}] = 1;
	}
	int sx = 0, sy = 0, dir = 0;
	for(auto c : steps){
		if(c == 'U') dir = 0;
		if(c == 'R') dir = 1;
		if(c == 'D') dir = 2;
		if(c == 'L') dir = 3;
		
		sx += dx[dir];
		sy += dy[dir];
		h --;
		if(h < 0){
			puts("No");
			return 0;
		}
		if(v[{sx, sy}] && h < k) h = k, v[{sx, sy}] = 0;
		
	}
	puts("Yes");
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;

long long x, y, z;
char s[N];
int n;
long long f[N][2];
//当前需要选择第 i 个位置，Capslock 为大写 /小写所花的最小时间 

int main(){
	scanf("%lld%lld%lld", &x, &y, &z);
	scanf("%s", s + 1);
	n = strlen(s + 1);		// 获取长度 
	
	memset(f, 0x3f, sizeof f);
	f[0][1] = 1ll * 0;

	for (int i = 1; i <= n; i ++ )
		if (s[i] == 'A'){
			f[i][0] = min(f[i - 1][0] + min(x, z + y + z), f[i - 1][1] + min(z + x, y + z));
			f[i][1] = min(f[i - 1][0] + min(x + z, z + y), f[i - 1][1] + min(y, z + x + z));
		}
		else{
			f[i][0] = min(f[i - 1][0] + min(y, z + x + z), f[i - 1][1] + min(x + z, z + y));
			f[i][1] = min(f[i - 1][1] + min(x, z + y + z), f[i - 1][0] + min(z + x, y + z));
		}
	
	printf("%lld\n", min(f[n][0], f[n][1]));		// 答案为打完前 n 个字符后状态为大写或小写所需要花的最少时间 
	
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int d[N];
int n;
int main(){
	cin >> n;
	for(int i = 1; i < n; i ++ ){
		int a, b;
		cin >> a >> b;
		d[a] ++, d[b] ++;
	}
	vector<int> res;
	int cnt = n;
	for(int i = 1; i <= n; i ++ ){
		if(d[i] >= 3) res.push_back(d[i]), cnt -= d[i] + 1;
	}
	while(cnt){
		cnt -= 3;
		res.push_back(2);
	}
	sort(res.begin(), res.end());
	for(auto x : res)
		cout << x << " ";
	cout << endl;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 330;
int dis[N][N], f[N][N];
const int inf = 0x3f3f3f3f;
int n, m;
int main(){

	scanf("%d%d", &n, &m);
	memset(dis, 0x3f, sizeof dis);
	
	for(int i = 1; i <= m; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		dis[x][y] = 1;
		f[x][y] = 1;
	}
	
	for(int i = 1; i <= n; i++)
		dis[i][i] = 0;
	
	for(int k = 1; k <= n; k++)
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++){
				if(dis[i][k] + dis[k][j] < dis[i][j]){
					dis[i][j] = dis[i][k] + dis[k][j] ;
					f[i][j] = f[i][k] * f[k][j];;
				}
				else if(dis[i][k] + dis[k][j] == dis[i][j])
					f[i][j] += f[i][k] * f[k][j]; 
			}
	
	for(int i = 1; i <= n; i++) f[i][i] = 1;
	
	long long ans = 0;
	for(int k = 1; k <= n; k++){
		for(int u = 1; u <= n; u++){
			for(int v = 1; v <= n; v++){
				if(dis[u][v] < inf && dis[u][k] + dis[k][v] == dis[u][v] && f[u][k] * f[k][v] == f[u][v])
					ans ++;
			}
		}
	}
		
	printf("%lld\n", ans);
	return 0;
}

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e3+5;
int f[N][N],sum[N];
int n,a,b,c,d,x[N];
signed main() {

	cin >> n >> a >> b >> c >> d;
	
	for(int i = 1; i <= n; i++){
		cin >> x[i];
		sum[i] = sum[i - 1] + x[i];
	}
	for(int len = 1; len <= n; len++) { //  枚举区间长度 
		for(int i = 1; i + len - 1 <= n; i++) { // 枚举左端点 
			int j = i + len - 1; // 右端点 
			f[i][j] = max(x[j] - f[i][j - 1], x[i] - f[i+1][j]);
			
			int lenn = max(0ll, (j - i + 1) - b); // 剩余的长度 
			if(lenn == 0) f[i][j] = max(f[i][j], sum[j] - sum[i - 1] - a);
			else for(int k = i; k + lenn - 1 <= j; k++)
					f[i][j] = max(f[i][j], sum[j] - sum[i - 1] - (sum[k + lenn - 1] - sum[k - 1]) - f[k][k + lenn - 1] - a);
			
			lenn = max(0ll,(j - i + 1) - d);
			if(lenn == 0) f[i][j] = max(f[i][j], sum[j] - sum[i-1] - c);
			else for(int k = i; k + lenn - 1 <= j; k++)
					f[i][j] = max(f[i][j], sum[j] - sum[i - 1] - (sum[k + lenn - 1] - sum[k - 1]) - f[k][k + lenn - 1] - c);
		}
	}
	cout << f[1][n] << "\n";
	return 0;
}