首页 > 其他分享 >Educational Codeforces Round 20 E. Roma and Poker

Educational Codeforces Round 20 E. Roma and Poker

时间:2024-11-01 18:42:15浏览次数:1  
标签:Poker le 20 matrix int Educational right using dis

差分约束

我们记W表示\(1\),L表示\(-1\),D表示\(0\),然后记前\(i\)位的前缀和是\(dis[i]\)。则我们可以根据题面得到如下约束。

当前位是W,则有

\[\left\{\begin{matrix} dis[i] - dis[i-1] \le 1 \\ dis[i-1] - dis[i] \le -1 \end{matrix}\right. \]

当前位是L,则有

\[\left\{\begin{matrix} dis[i] - dis[i-1] \le -1 \\ dis[i-1] - dis[i] \le 1 \end{matrix}\right. \]

当前位是D,则有

\[\left\{\begin{matrix} dis[i] - dis[i-1] \le 0 \\ dis[i-1] - dis[i] \le 0 \end{matrix}\right. \]

前缀和的绝对值小于\(k\),则有

\[\left\{\begin{matrix} dis[i] - dis[0] \le k-1 \\ dis[i] - dis[i] \le k-1 \end{matrix}\right. \]

所有位置的和的绝对值等于\(k\),则有

\[\left\{\begin{matrix} dis[0] - dis[n] \le -k \\ dis[n] - dis[0] \le k \end{matrix}\right. \or\left\{\begin{matrix} dis[0] - dis[n] \le k \\ dis[n] - dis[0] \le -k \end{matrix}\right. \]

考虑除了绝对值等于\(k\)外的约束都是唯一的,因此我们可以在最后先加入绝对值等于\(k\)的其中一种约束,跑一遍差分约束后,删边,再加入另一种约束,再跑一遍差分约束。如果都没有解,就是无解。

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;

#define int i64

using vi = vector<int>;
using pii = pair<int,int>;

const i64 inf = LLONG_MAX / 2;

i32 main(){
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int n, k;
	cin >> n >> k;

	string s;
	cin >> s;
	s = " " + s;

	vector<vector<pii>> e(n + 1);

	for(int i = 1; i <= n; i ++) {
		if(s[i] == 'W') {
			e[i].emplace_back(i - 1, -1);
			e[i - 1].emplace_back(i , 1);
		} else if(s[i] == 'L') {
			e[i].emplace_back(i - 1, 1);
			e[i - 1].emplace_back(i, -1);
		} else if(s[i] == 'D') {
			e[i].emplace_back(i - 1, 0);
			e[i - 1].emplace_back(i, 0);
		} else {
			e[i].emplace_back(i - 1, 1);
			e[i - 1].emplace_back(i, 1);
		}
	}

	for(int i = 1; i < n; i ++) { 
		e[i].emplace_back(0, k - 1);
		e[0].emplace_back(i, k - 1);
	}

	vi dis;
	auto bellman_ford = [n, &e, &dis]() -> bool {
		vi vis(n + 1, 0), tot(n + 1, 0);
		dis = vi(n + 1, inf);

		dis[0] = 0, vis[0] = 1;
		queue<int> q;
		q.push(0);
		while(not q.empty()) {
			int x = q.front();
			q.pop();
			vis[x] = 0;
			for(auto [y, w] : e[x]) {
				if(dis[y] <= dis[x] + w) continue;
				dis[y] = dis[x] + w;
				if(vis[y]) continue;
				if(++ tot[y] == (n + 1)) return false;
				vis[y] = 1;
				q.push(y);
			}
		}
		return true;
	};


	e[n].emplace_back(0, -k);
	e[0].emplace_back(n, k);
	if(bellman_ford()) {
		for(int i = 1, x; i <= n; i ++) {
			x = dis[i] - dis[i - 1];
			cout << "LDW"[x + 1];
		}
		return 0;
	}

	e[n].pop_back(), e[n].emplace_back(0, k);
	e[0].pop_back(), e[0].emplace_back(n, -k);
	if(bellman_ford()) {
		for(int i = 1, x; i <= n; i ++) {
			x = dis[i] - dis[i - 1];
			cout << "LDW"[x + 1];
		}
		return 0;
	}
	cout << "NO";
	return 0; 
}

DP

W表示\(1\),L表示\(-1\),D表示\(0\)。

设状态\(f[i][j]\)表示前\(i\)位和为\(j\)的是否成立。如果是问号的话我们就枚举当前位的状态。转移过程中记录一下前序状态即可。

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;

#define int i64

using vi = vector<int>;
using pii = pair<int,int>;

const i64 inf = LLONG_MAX / 2;

i32 main(){
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int n, k;
	cin >> n >> k;

	string s;
	cin >> s;
	s = " " + s;

	vector<map<int,bool>> f(n + 1);
	vector<map<int,int>> lst(n + 1);

	f[0][0] = true;

	for(int i = 1, K; i <= n; i ++) {
		K = k - (i != n);
		if(s[i] == '?') {
			for(int d = -1; d <= 1; d ++) {
				for(int j = -K; j <= K; j ++)
					if(f[i - 1][j - d]) f[i][j] = true, lst[i][j] = j - d;
			}
		} else {
			int d = 0;
			if(s[i] == 'W') d = 1;
			else if(s[i] == 'L') d = -1;
			for(int j = -K, l; j <= K; j ++) 
				if(f[i - 1][j - d]) f[i][j] = true, lst[i][j] = j - d;
		}
	}

	if(f[n][k]) {
		string res;
		for(int i = n, j = k, l, x; i > 0; i --) {
			l = lst[i][j], x = j - l;
			res += "LDW"[x + 1];
			j = l;
		}
		ranges::reverse(res);
		cout << res;
	}else if(f[n][-k]) {
		string res;
		for(int i = n, j = -k, l, x; i > 0; i --) {

			l = lst[i][j], x = j - l;
			res += "LDW"[x + 1];
			j = l;
		}
		ranges::reverse(res);
		cout << res;
	} else {
		cout << "NO";
	}
	return 0; 
}

标签:Poker,le,20,matrix,int,Educational,right,using,dis
From: https://www.cnblogs.com/PHarr/p/18521047

相关文章

  • 2024.11.1总结
    本文于github博客同步更新。OI相关:A:分为两种情况处理:\(u\)到\(lca\)和\(lca\)到\(v\)。我的做法是先树剖,将每条链单独拿出来拉出来,根据\(a_i\)和\(b_i\)连边,正反各建一棵树,维护一下\(k\)级祖先。然后从\(u\)到\(v\)的时候每次根据从dfs序由小到大还是由......
  • 如何在 iPhone 上关闭闹钟 [2023]
    ​关闭iPhone上的闹钟需要遵循以下步骤:1.打开“时钟”应用;2.选择“闹钟”选项;3.找到设置的闹钟并关闭;4.若需要,删除不再使用的闹钟;5.确保已设置的闹钟时间与实际需求相符。首先,我们需要确定要操作的闹钟。1.打开“时钟”应用从iPhone的主屏幕中找到并点击“时钟”图......
  • 《上海市计算机学会竞赛平台2024年8月月赛丙组题目T1 统计得分 T2 等差数列的素性 T3
    T1统计得分内存限制: 256 Mb时间限制: 1000 ms题目描述在一场知识竞赛中,选手答对一题得 11 分,答错不得分且要倒扣 11 分,但扣分不能让分数小于 00。给定一个由 Y 及 N 构成的字符序列,答对记为 Y,答错记为 N。选手一开始从 00 分开始,请输出选手最后的得分......
  • 『模拟赛』多校A层冲刺NOIP2024模拟赛17
    Rank一般A.网络签不上的签到题。首先考虑枚举路径的做法,如果先枚举再计算的话复杂度会是\(\mathcal{O(\binom{n+m-2}{n-1}(n+m))}\)的,稍微优化一点的过程中可以去掉后面的\((n+m)\)。考虑此时我们要记什么,首先遇到加号其前面的值\(z\)就确定了,若上个符号为乘号那么......
  • 浏览器指纹修改指南2024 - 分析Geolocation API实现(十)
    在geolocation.h文件中,可以找到一个私有成员Member<GeoNotifierSet>one_shots_;Member<GeolocationWatchers>watchers_;//GeoNotifiersthatareinthemiddleofinvocation.////|HandleError(error)|and|MakeSuccessCallbacks|needtoclear|one_sho......
  • NOIP2024 模拟赛 #12
    学长出的模拟赛,风格挺好。赛时8:00T1会了一个\(O(n^2\logn)\)的做法,先写一下,看看能不能过样例。8:20过了小样例,大样例跑得慢但是是对的。8:40发现一个好的做法,可以枚举\(c_i\)最小的那一天选了哪个,再枚举\(k\)天,这样纯枚举复杂度是\(O(k)\)的。但是有些细节不太......
  • [BJDCTF2020]The mystery of ip
    打开靶机,根据题目提示找到如下页面抓包,尝试修改ip发现回显改变第一印象以为是xss漏洞,控制回显点,alert弹框也能正常触发却不知道接下来该怎么进行下去查阅资料发现此处是ssti模板漏洞,也就是说此处ip值作为一个变量会被执行并回显所以尝试{system("ls/")}发现目标获取flag{s......
  • 2024年大湾区杯数学建模竞赛 A 题 证券市场投资风险控制模型设计 思路和代码(持续更新)
    目录任务一:风险计量指标计算与分析1.1平均收益率计算1.2市场流动性(换手率)1.3市场情绪指标(波动率)指标的经济意义和分析任务二:系统性风险预测模型构建2.1多因子模型示例2.2使用GARCH模型预测波动性任务三:事前风控体系构建任务四:合理收益预期设定任务一:风险计量......
  • 2024年大湾区杯数学建模竞赛 B 题 粤港澳大湾区经济预测数学模型 思路和代码
    目录任务一2.数据预处理3.因子分析和主成分分析4.建立多元回归模型5.模型验证与筛选重要因素6.对未来5-10年的趋势预测示例代码代码解释任务二1.选择预测模型2.时间序列预测模型步骤3.多元回归模型预测4.代码示例5.结果分析与策略设计任务三1.选......
  • 2025年计算机专业小程序选题大全
    weixin001基于小程序的购物系统设计与实现+ssmweixin002家庭记账本的设计与实现+ssmweixin003教学辅助微信小程序设计+ssmweixin004校园水电费管理微信小程序的设计与实现+ssmweixin005基于小程序的老孙电子点菜系统开发设计与实现+ssmweixin006优购电商小程序的设计与......