首页 > 其他分享 >CSP-S2023 题解

CSP-S2023 题解

时间：2023-10-22 10:11:18浏览次数：44  
标签：addr int 题解 align second S2023 now CSP size

更好的阅读体验

CSP-S2023 游记

密码锁(lock)

\(10^5\) 枚举所有可能答案，然后判断。

代码 
#include <bits/stdc++.h>

int n;
int a[13][7], b[7];

bool check(int i) {
	int cnt = 0;
	for(int j = 1; j <= 5; j++) cnt += (a[i][j] != b[j]);
	if(cnt == 1) return true;
	else if(cnt != 2) return false;
	for(int j = 1; j < 5; j++)
		if(a[i][j] != b[j] && a[i][j + 1] != b[j + 1] && (b[j] - a[i][j] + 10) % 10 == (b[j + 1] - a[i][j + 1] + 10) % 10) return true;
	return false;
}
bool check() {
	for(int i = 1; i <= n; i++) if(!check(i)) return false;
	return true;
}

int main() {
	freopen("lock.in", "r", stdin);
	freopen("lock.out", "w", stdout);
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) for(int j = 1; j <= 5; j++) scanf("%d", &a[i][j]);
	int ans = 0;
	for(b[1] = 0; b[1] <= 9; b[1]++)
		for(b[2] = 0; b[2] <= 9; b[2]++)
			for(b[3] = 0; b[3] <= 9; b[3]++)
				for(b[4] = 0; b[4] <= 9; b[4]++)
					for(b[5] = 0; b[5] <= 9; b[5]++)
						ans += check();
	printf("%d\n", ans);
	return 0;
}

消消乐(game)

首先发现对于同一个局面会有多个方案，比如 abaaba 可以是 abAAba 也可以是 abaAbA （两个 a 匹配，两个 A 匹配）。那么我们钦定只考虑 abaAbA。怎么保证这一点呢？我们令 \(r(i)\) 等于最小的 \(j\) 满足 \([i, j]\) 这一段是可以被消除的。那么对于 abaaba 来说，\(r(1)=3,r(4)=6\)。我们把 \([i, r(i)]\) 叫做 一段。

然后我们令 \(cnt(i)\) 表示从 \(i\) 开始最多往后走多少个段能走到 \(n\)，也就是 \(cnt(i)=cnt(r(i)+1)+1\) 且 \(cnt(n+1)=0\)，那么答案就是所有位置的 \(cnt\) 加起来。

然后考虑怎么算 \(r\)。容易发现 \(r(i)\) 其实等于最小的 \(j\) 使得 \([i+1, j-1]\) 能被消除且 \(s_i=s_j\)，也就是从 \(i+1\) 开始往后一段一段跳，直到某一段结尾的后一个字符等于 \(s_i\)。那么我们对于每个 \(i\) 记 \(nxt(i,c)\) 表示从 \(i\) 开始往后一段一段跳，第一次跳到 \(c\) 时的下标，然后就可以计算 \(r\) 了。有了 \(r\)，\(nxt\) 也是好转移的。

代码 
#include <bits/stdc++.h>

typedef long long LL;

const int N = 2e6 + 5;

int n;
char s[N];

int cnt[N], nxt[N][26];

int main() {
	freopen("game.in", "r", stdin);
	freopen("game.out", "w", stdout);
	scanf("%d%s", &n, s + 1);
	for(int i = 1; i <= n; i++) s[i] -= 'a';
	for(int i = n - 1; i >= 1; i--) {
		if(s[i + 1] == s[i]) {
			for(int j = 0; j < 26; j++) nxt[i][j] = nxt[i + 2][j];
			if(i + 2 <= n) nxt[i][s[i + 2]] = i + 2;
			cnt[i] = cnt[i + 2] + 1;
//			printf("%d -> %d\n", i, i + 2);
		} else if(nxt[i + 1][s[i]]) {
			int i_ = nxt[i + 1][s[i]];
			for(int j = 0; j < 26; j++) nxt[i][j] = nxt[i_ + 1][j];
			if(i_ + 1 <= n) nxt[i][s[i_ + 1]] = i_ + 1;
			cnt[i] = cnt[i_ + 1] + 1;
//			printf("%d -> %d\n", i, i_ + 1);
		}
	}
	LL ans = 0;
	for(int i = 1; i <= n; i++) ans += cnt[i];
	printf("%lld\n", ans);
	return 0;
}

结构体(struct)

直接模拟即可。

代码 
#include <bits/stdc++.h>
using std::string;
using std::cin;
using std::cout;

typedef long long LL;

const int N = 100 + 5;

int Q;

struct Type {
	std::vector<std::pair<string, Type *>> m;
	LL size;
	int align;
} buffer[N], *Byte, *Short, *Int, *Long;
int ctype;
Type *nw_type() { ctype++; return &buffer[ctype]; }

std::map<string, Type *> type;
std::vector<std::pair<string, Type *>> vars;

char tmp[21];

inline LL align_to(LL x, int y) { return x % y ? x - x % y + y : x; }

int main() {
	freopen("struct.in", "r", stdin);
	freopen("struct.out", "w", stdout);
	Byte = nw_type(), Short = nw_type(), Int = nw_type(), Long = nw_type();
	Byte->size = Byte->align = 1, Short->size = Short->align = 2, Int->size = Int->align = 4, Long->size = Long->align = 8;
	type["byte"] = Byte, type["short"] = Short, type["int"] = Int, type["long"] = Long;
	cin >> Q;
	while(Q--) {
		int t;
		cin >> t;
		if(t == 1) {
			string name;
			int cnt;
			cin >> name >> cnt;
			Type *now = nw_type();
			type[name] = now;
			while(cnt--) {
				string typname, varname;
				cin >> typname >> varname;
				Type *typ = type[typname];
				now->m.push_back({varname, typ});
				now->size = align_to(now->size, typ->align) + typ->size;
				now->align = std::max(now->align, typ->align);
			}
			now->size = align_to(now->size, now->align);
			std::cout << now->size << ' ' << now->align << '\n';
		} else if(t == 2) {
			string typname, varname;
			cin >> typname >> varname;
			LL addr = 0;
			for(int i = 0; i < (int)vars.size(); i++) addr = align_to(addr, vars[i].second->align), addr += vars[i].second->size;
			addr = align_to(addr, type[typname]->align);
			std::cout << addr << '\n';
			vars.push_back({varname, type[typname]});
		} else if(t == 3) {
			LL addr = 0;
			int now = 0, nxtnow = 0;
			string buf;
			cin >> buf;
			sscanf(buf.c_str() + now, "%[a-z]%n", tmp, &nxtnow), now += nxtnow;
			string varname = tmp;
			Type *tp;
			for(int i = 0; i < (int)vars.size(); i++) {
				addr = align_to(addr, vars[i].second->align);
				if(vars[i].first != varname) addr += vars[i].second->size;
				else { tp = vars[i].second; break; }
			}
			while(sscanf(buf.c_str() + now, ".%[a-z]%n", tmp, &nxtnow) == 1) {
				now += nxtnow;
				addr = align_to(addr, tp->align);
				string name = tmp;
				for(int i = 0; i < (int)tp->m.size(); i++) {
					addr = align_to(addr, tp->m[i].second->align);
					if(tp->m[i].first != name) addr += tp->m[i].second->size;
					else { tp = tp->m[i].second; break; }
				}
			}
			std::cout << addr << '\n';
		} else {
			LL addr, now_addr = 0;
			bool flag = true;
			string ans;
			cin >> addr;
			Type *now = 0;
			for(int i = 0; i < (int)vars.size(); i++) {
				now_addr = align_to(now_addr, vars[i].second->align);
				if(addr < now_addr) { flag = false; break; }
				if(addr >= now_addr + vars[i].second->size) now_addr += vars[i].second->size;
				else { ans += vars[i].first; now = vars[i].second; break; }
			}
			if(!now) flag = false;
			while(flag && !now->m.empty()) {
				now_addr = align_to(now_addr, now->align);
				if(addr < now_addr) { flag = false; break; }
				bool fl = false;
				for(int i = 0; i < (int)now->m.size(); i++) {
					now_addr = align_to(now_addr, now->m[i].second->align);
					if(addr < now_addr) { flag = false; break; }
					if(addr >= now_addr + now->m[i].second->size) now_addr += now->m[i].second->size;
					else { ans += "." + now->m[i].first; now = now->m[i].second; fl = true; break; }
				}
				if(!fl) { flag = false; break; }
			}
			if(flag) cout << ans << '\n';
			else cout << "ERR" << '\n';
		}
	}
	return 0;
}

种树(tree)

首先二分答案，那么我们要判断答案是否大于等于 \(m\)。首先对于每个点，我们可以计算出它最晚被种下去的时间 \(r_i\)，这个可以二分（用 \(O(1)\) 似乎会被卡精度？）

先考虑没有“必须先种父亲再种儿子”的限制。我们令 \(s_i\) 表示有多少个 \(r_j\) 小于等于 \(i\)，那么我们只需要判断 \(s_i\le i\)。正确性显然。（其实这个也可以贪心做，本质上是一样的）

现在考虑有这个限制怎么做。一个显然的事情是 \(r_u<r_v\)（\(v\) 是 \(u\) 的儿子），所以我们用这个限制来更新 \(r\)。然后就不需要考虑这个限制，直接按照上面的做法去做就好了。

为什么呢？令 \(t_i\) 表示一个合法方案中 \(i\) 实际上是第几天被种下去的，那么显然 \(t\) 互不相同且 \(t_i\le r_i\)。接下来我们只需要证明能找到一个 \(t'_i\) 满足“先种父亲再种儿子”的限制就行了。考虑调整法，如果对于一对拥有祖先关系的 \(u,v\)，\(t_u>t_v\)，那么我们有 \(t_v<t_u\le r_u<r_v\)，那么我们可以将 \(t_u,t_v\) 交换，这样也是合法的。所以这个结论是对的。

代码 
#include <bits/stdc++.h>

typedef long long LL;

const int N = 1e5 + 5;

int n;
LL a[N], qk[N], qb[N];
struct Edge { int to, nxt; } edge[N << 1];
int head[N];
void add_edge(int u, int v) { static int k = 1; edge[k] = (Edge){v, head[u]}, head[u] = k++; }

int bd[N], cnt[N];
void dfs(int u, int fa) {
	for(int i = head[u]; i; i = edge[i].nxt) if(edge[i].to != fa) {
		int v = edge[i].to;
		dfs(v, u);
		bd[u] = std::min(bd[u], bd[v] - 1);
	}
}
inline LL div_ceil(LL x, LL y) { if(y < 0) x = -x, y = -y; return x < 0 ? x / y : (x + y - 1) / y; }
inline LL div_floor(LL x, LL y) { if(y < 0) x = -x, y = -y; return x < 0 ? (x - y + 1) / y : x / y; }
inline bool calc(LL k, LL b, LL x, LL m, LL target) {
	if(k == 0) return (m - x + 1) * b < target;
	else if(k > 0) {
		LL y = div_ceil(1 - b, k); __int128_t ret = 0;
		if(m >= y) ret += (m - std::max(x, y) + 1) * b + (__int128_t)(m + std::max(x, y)) * (m - std::max(x, y) + 1) / 2 * k;
		if(x < y) ret += std::min(m + 1, y) - x;
		return ret < target;
	} else {
		LL y = div_floor(1 - b, k); __int128_t ret = 0;
		if(x <= y) ret += (std::min(m, y) - x + 1) * b + (__int128_t)(std::min(m, y) + x) * (std::min(m, y) - x + 1) / 2 * k;
		if(m > y) ret += m - std::max(x - 1, y);
		return ret < target;
	}
}
bool check(int m) {
//	printf("check %d\n", m);
	for(int i = 1; i <= n; i++) {
		int l = 1, r = n + 1;
		while(l < r) {
			int mid = (l + r) >> 1;
			if(calc(qk[i], qb[i], mid, m, a[i])) r = mid;
			else l = mid + 1;
		}
		bd[i] = l - 1;
//		printf("bd[%d] = %d\n", i, bd[i]);
	}
	dfs(1, 0);
	for(int i = 1; i <= n; i++) if(bd[i] < 1) return false;
//	for(int i = 1; i <= n; i++) printf("bd[%d] = %d\n", i, bd[i]);
	for(int i = 1; i <= n; i++) cnt[i] = 0;
	for(int i = 1; i <= n; i++) cnt[bd[i]]++;
	int sum = 0;
	for(int i = 1; i <= n; i++) {
		sum += cnt[i];
		if(sum > i) return false;
	}
	return true;
}

int main() {
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%lld%lld%lld", &a[i], &qb[i], &qk[i]);
	for(int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); add_edge(u, v), add_edge(v, u); }
//	for(int i = 1; i <= n; i++) if(calc(qk[i], qb[i], 1, 1000000000, a[i])) { printf("%lld %lld\n", qk[i], qb[i]); return 0; }
	int l = n, r = 1e9;
	while(l < r) {
		int mid = (l + r) >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%d\n", l);
	return 0;
}

标签：addr,int,题解,align,second,S2023,now,CSP,size
From： https://www.cnblogs.com/xxeray/p/csp-s-2023-solution.html

相关文章

  • 「回忆录」CSP - S 2023 游记
    Day-13今天照常竞赛，明天文化课。下午问了问我的充电宝，大抵会在后天到达，终于快要来了（兴奋）！Day-12~Day-11whking……Day-10中午起床有点热盖着个厚被子捂得，然后作死没穿褂子来的机房，之后，get新技能：半小时卫生纸瘦身大法！擤个鼻子擤到耳鸣……Day-9~Day-8whking…......
  • 【HAL 库复盘】自己手动创建工程模版Undefined symbol HAL_NVIC_SetPriority 问题解决
    1问题说明学习自己手动搭建一个STM32HAL库工程模板文件的时候，我发现了有6个错误，6个错误的类型是一样的，其中有3个通过添加hal_rcc.h和hal_gpio.c文件得以解决。所以另外3个我也想到了时缺少了对应的.c文件导致的错误。但是在STM32F1xx_HAL_Driver文件夹中，我没有找到类似如有“rcc......
  • CSP-S 2023 游记
    Day-1前一天晚上逃晚自习出来的，感觉来晚了（，想去五一广场的没去成QAQ，不过十一月还有一场，问题不大嘿嘿。高铁上敲了对拍，虽然最后并没有用到。地铁的服务小姐姐挺好看的！晚上到了酒店，感觉挺不错的，甚至还有厨房。就是墙面看起来装修不是特别好，（偏少女系，但总体来说非常舒服！好评！床是软的......
  • CSP2023 游记
    day-inf初赛出分了，91分。应该不会被CQ整的花活创死。day-inf+114514过了，哈哈哈。day1考前和@PosVII面积，太牛啦。然后他被男神披上八中校服，还拍了张照。然后是@E_firework在众人面前干抽象事情。呃呃。。然后进场。呃呃，游记在代码里的。先别急，我等等。我好像感......
  • CSP-S2023游寄 / CSP-S2023退役记
    Day\(-1\)敲板子。为什么分块，平衡树，可并堆，exKmp，Manacher都有可能考啊。Day  \(\texttt{-499122177mod998244353}\)敲板子。完蛋，板子敲不完。是不是会考串串题啊。exKmp还是Manacher？复习了一下，加深印象。（乐）Day0\(\texttt{-2h}\)睡大觉。Day0\(\texttt{-0.......
  • CSP-S 2023 游记
    Day-1919810初赛。没考J。S挂成90.5。Day-114514停课。Day1寄寄寄。T1怎么这么低能。T2怎么不会做。T3怎么是大模拟。T4怎么是神秘贪心。好好好，直接顺序开题。很快啊，T1切了。急急急，T2怎么做T2怎么做T2怎么做T2怎么做T2怎么做T2怎么做T2怎么做......
  • CSP-S2023 游记
    S190pts。S2\(14:30\)全机房都打不开题，然后用U盘拷的题，乐。全机房补了\(20\operatorname{min}\)。\(14:50\)这是T1？这是T1？这是T1？这是T1？这是T1？一眼爆搜，\(10\operatorname{min}\)写完过了。\(15:00\)开T2。一眼感觉枚举\(r\)，然后DS维护。推了一下感觉不好......
  • CSP2023又寄
    推销丑死了的你谷博客\(\texttt{Day-?}\)初赛，轻轻松松寄掉，惊险S组踩线过。\(\texttt{Day-1}\)赛前动员，见到了老K/se敲了敲板子，然而屁用没有。\(\texttt{Day0}\)J组T1傻逼题，秒了数学题，打个暴力浅浅拿\(90\)分跑路。T2傻逼题，秒了。贪心，前缀最小值维护就行了。......
  • CSP 2023 游记
    省流：把#defineintlonglong写在快读下面，荣获全场最佳小丑奖。Day-1手速大赛很有趣，但有人不认识Aigony我不说是谁。Day0睡大觉，给小朋友讲考场注意事项。晚上试图向学妹传教vscode，但被反向传教了一顿code::blocks。怎么回事呢（做出一副努力学习的样子，但是我也很想玩......
  • P9752 [CSP-S 2023] 密码锁 题解
    分析最水S组T1。每次可以转动一个拨圈，或者转动相邻的两个拨圈，且幅度相同。那么就有一个简单粗暴的思路，枚举修改的方案，用vector来储存修改后的方案，存到map当中，当然也可以转换为数字存进去。切记要用两个map来储存，一个存方案，下文称为\(mp\)，一个存这个方案在这个状态下......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99