首页 > 其他分享 >AtCoder Beginner Contest 322

AtCoder Beginner Contest 322

时间：2023-10-01 14:45:18浏览次数：40  
标签：AtCoder cur Beginner int res tr long 322 ++

A - First ABC 2

解题思路

签到

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

void solve() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	int p = s.find("ABC");
	if (p == -1) cout << p << '\n';
	else cout << p + 1 << '\n';
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	t = 1;
	while (t--) {
		solve();
	}
	
   return 0; 
}

B - Prefix and Suffix

解题思路

签到

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

void solve() {
	int n, m;
	string s, t;
	cin >> n >> m >> s >> t;
	int ok1 = t.substr(0, n) == s;
	int ok2 = t.substr(m - n, n) == s;
	if (ok1 && ok2) {
		cout << 0 << '\n';
	} else if (ok1) {
		cout << 1 << '\n';
	} else if (ok2) {
		cout << 2 << '\n';
	} else {
		cout << 3 << '\n';
	}
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	t = 1;
	while (t--) {
		solve();
	}
	
   return 0; 
}

C - Festival

解题思路

倒过来枚举，\(last\) 维护从后往前的第一个放烟花的位置。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

void solve() {
	int n, m;
	cin >> n >> m;
	vector<bool> st(n + 1, false);
	vector<int> ans(n + 1, 0);
	for (int i = 1; i <= m; i++) {
		int x;
		cin >> x;
		st[x] = true;
	}
	int last;
	for (int i = n; i >= 1; i--) {
		if (st[i]) last = i;
		ans[i] = last - i;
	}
	for (int i = 1; i <= n; i++) {
		cout << ans[i] << "\n";
	}
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	t = 1;
	while (t--) {
		solve();
	}
	
   return 0; 
}

D - Polyomino

解题思路

直接暴力模拟 \(3\) 个矩阵的旋转和平移，然后看看 # 能不能不重叠的填满 \(4\times 4\) 的矩阵。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

 
void solve() {
	array<string, 4> a, b, c;
	for (int i = 0; i < 4; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < 4; i++) {
		cin >> b[i];
	}
	for (int i = 0; i < 4; i++) {
		cin >> c[i];
	}
	auto rotate = [&](array<string, 4> &s) {
		array<string, 4> t;
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				t[i] += s[3 - j][i];
			}
		}	
		s = t;
	};
	for (int da = 0; da < 4; da++) {
		for (int db = 0; db < 4; db++) {
			for (int dc = 0; dc < 4; dc++) {
				for (int dxa = -3; dxa <= 3; dxa++) {
					for (int dya = -3; dya <= 3; dya++) {
						for (int dxb = -3; dxb <= 3; dxb++) {
							for (int dyb = -3; dyb <= 3; dyb++) {
								for (int dxc = -3; dxc <= 3; dxc++) {
									for (int dyc = -3; dyc <= 3; dyc++) {
										array<string, 4> s;
										bool ok = true;
										auto cover = [&](auto &a, int dx, int dy) {
											for (int i = 0; i < 4; i++) {
												for (int j = 0; j < 4; j++) {
													int x = i + dx;
													int y = j + dy;
													if (a[i][j] == '#') {
														if (x < 0 || x >= 4 || y < 0 || y >= 4 || s[x][y] == '#') {
															ok = false;
														} else {
															s[x][y] = '#';
														}
													}
												}
											}	
										};
										s.fill("....");
										cover(a, dxa, dya);
                              cover(b, dxb, dyb);
                              cover(c, dxc, dyc);
                              for (int i = 0; i < 4; i++) {
                              	if (s[i] != "####") {
                              		ok = false;
											}
										}
										if (ok) {
											cout << "Yes\n";
											return ;
										}
									}
								}
							}
						}
					}
				}
				rotate(c);
			}
			rotate(b);
		}
		rotate(a);
	}	
	
	cout << "No\n";
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	t = 1;
	while (t--) {
		solve();
	}
	
   return 0; 
}

E - Product Development

解题思路

\(6\) 维 DP，记 \(dp(i,a,b,c,d,e)\) 为考虑前 \(i\) 个计划，第 \(1-5\) 个物品目前的价值至少为 \(a,b,c,d,e\)，然后和背包一样正常转移即可。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL dp[110][6][6][6][6][6];

void solve() {
	int n, k, p;
	cin >> n >> k >> p;
	memset(dp, 0x3f, sizeof dp);
	LL INF = dp[0][1][0][0][0][0];
	dp[0][0][0][0][0][0] = 0;
	for (int i = 1; i <= n; i++) {
		int val;
		cin >> val;
		vector<int> cur(6, 0);
		for (int j = 1; j <= k; j++) {
			cin >> cur[j];
		}
		for (int a = 0; a <= p; a++) {
			for (int b = 0; b <= p; b++) {
				for (int c = 0; c <= p; c++) {
					for (int d = 0; d <= p; d++) {
						for (int e = 0; e <= p; e++) {
							dp[i][a][b][c][d][e] = min(dp[i][a][b][c][d][e], dp[i - 1][a][b][c][d][e]);
							dp[i][a][b][c][d][e] = min(dp[i][a][b][c][d][e], dp[i - 1][max(0, a - cur[1])][max(0, b - cur[2])][max(0, c - cur[3])][max(0, d - cur[4])][max(0, e - cur[5])] + val);
						}
					}
				}
			}
		}
	}
	LL ans;
	if (k == 1) ans = dp[n][p][0][0][0][0];
	else if (k == 2) ans = dp[n][p][p][0][0][0];
	else if (k == 3) ans = dp[n][p][p][p][0][0];
	else if (k == 4) ans = dp[n][p][p][p][p][0];
	else ans = dp[n][p][p][p][p][p];
	
	if (ans == INF) ans = -1;
	cout << ans << "\n";
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	t = 1;
	while (t--) {
		solve();
	}
	
   return 0; 
}

F - Vacation Query

解题思路

比较套路的线段树题，我们只要在线段树维护一下几个变量：
\(maxlen[2],mxl[2],mxr[2],tl,tr,l,r\)：分别表示 \(0/1\) 的最长连续段，和前缀最长，后缀最长，区间左边，右边的字符事啥，以及区间左右端点。
然后在维护一个懒标记 \(tag\) 实现区间修改，区间修改等价于把 \(maxlen[0],mxl[0],mxr[0]\) 和 \(maxlen[1],mxl[1],mxr[1]\) 交换了一下。

Code

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

struct info {
	int cur[2][3], tl, tr, l, r;
	info operator + (const info &x) {
		info res = {};
		res.tl = tl, res.tr = x.tr;
		res.l = l, res.r = x.r;
		for (int i = 0; i < 2; i++) {
			res.cur[i][0] = max(cur[i][0], x.cur[i][0]);
			res.cur[i][1] = cur[i][1];
			res.cur[i][2] = x.cur[i][2];
			if (cur[i][1] == r - l + 1) {
				res.cur[i][1] = max(res.cur[i][1], cur[i][0] + (tr == i && tr == x.tl) * x.cur[i][1]);
			}
			if (x.cur[i][2] == x.r - x.l + 1) {
				res.cur[i][2] = max(res.cur[i][2], x.cur[i][0] + (tr == i && tr == x.tl) * cur[i][2]);
			}
			res.cur[i][0] = max(res.cur[i][0], (tr == i && tr == x.tl) * (cur[i][2] + x.cur[i][1]));
		}
		return res;
	};
};
struct node {
	info val;
	int tag;
} tr[4 * N];
string s;

void pushup(int u) {
	tr[u].val = tr[u << 1].val + tr[u << 1 | 1].val;
}

void build(int u, int l, int r) {
	tr[u].val.l = l, tr[u].val.r = r;
	if (l == r) {
		tr[u].val.tl = tr[u].val.tr = s[l] - '0';
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 3; j++) {
				tr[u].val.cur[i][j] = i == tr[u].val.tl;
			}
		}
		return ;
	}
	int mid = (l + r) >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	pushup(u);
}

void pushdown(int u) {
	if (tr[u].tag) {
		tr[u << 1].tag ^= 1;
		tr[u << 1 | 1].tag ^= 1;
		swap(tr[u << 1].val.cur[0], tr[u << 1].val.cur[1]);
		swap(tr[u << 1 | 1].val.cur[0], tr[u << 1 | 1].val.cur[1]);
		tr[u << 1].val.tl ^= 1;
		tr[u << 1].val.tr ^= 1;
		tr[u << 1 | 1].val.tl ^= 1;
		tr[u << 1 | 1].val.tr ^= 1;
		tr[u].tag = 0;
	}
}

void modify(int u, int l, int r) {
	if (tr[u].val.l >= l && tr[u].val.r <= r) {
		swap(tr[u].val.cur[0], tr[u].val.cur[1]);
		tr[u].val.tl ^= 1;
		tr[u].val.tr ^= 1;
		tr[u].tag ^= 1;
		return ;
	}
	pushdown(u);
	int mid = (tr[u].val.l + tr[u].val.r) >> 1;
	if (l <= mid) modify(u << 1, l, r);
	if (r > mid) modify(u << 1 | 1, l, r);
	pushup(u);
} 

info query(int u, int l, int r) {
	if (tr[u].val.l >= l && tr[u].val.r <= r) return tr[u].val;
	pushdown(u);
	int mid = (tr[u].val.l + tr[u].val.r) >> 1;
	if (r <= mid) return query(u << 1, l, r);
	else if (l > mid) return query(u << 1 | 1, l, r);
	return query(u << 1, l, r) + query(u << 1 | 1, l, r);
}

void solve() {
	int n, q;
	cin >> n >> q >> s;
	s = '?' + s;
	build(1, 1, n);
	while (q--) {
		int c, l, r;
		cin >> c >> l >> r;
		if (c == 1) modify(1, l, r);
		else {
			cout << query(1, l, r).cur[1][0] << "\n";
		} 
	}
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	t = 1;
	while (t--) {
		solve();
	}
	
   return 0; 
}

标签：AtCoder,cur,Beginner,int,res,tr,long,322,++
From： https://www.cnblogs.com/xiaole-jackle/p/17738837.html

相关文章

  • 《AT_abc322_g Two Kinds of Base》解题报告
    好题，考场上想到做法了，没写出来，被薄纱了，记录一下。主要是做的比较顺一下就想到了。我们先转换一下\(f\)函数\(f(S,a,b)=\sum\limits_{i=1}^kS_i\times(a^{k-i}-b^{k-i})\)我们可以发现对于位数\(>2\)的，一定满足\(a\le\frac{(x+1)}2\)，因为如果不是的话\(a^2-(a-1)^2=......
  • 加训日记 Day3——atcoder ABC321乐子场
    Day3，9.23  ·打了场acwing周赛，第三题差点就想出来了，想歪到组合数上乱选了呜呜呜  ·ABC321场写的太抽象了，A题上来wa两次，B题少考虑情况乱wa  ·C题更是重量级，想不出来正确做法直接暴力，结果打表最后少写了几个数，纯纯犯病场  ·最后加了36分没绷住acwing周赛排名atcod......
  • AtCoder Regular Contest 123 F Insert Addition
    洛谷传送门AtCoder传送门用\((x,y)\)表示\(Ax+By\)，那么这个等价于SB树。那么直接在SB树上二分，遍历一遍找到\(n\)个点就好了。可以采用类似线段树查询的方式。于是现在还剩下一个子问题：给定\(a,b\)，求\(ax+by\len\)且\(\gcd(x,y)=1\)的正整数\((x,y......
  • AtCoder Regular Contest 127 F ±AB
    洛谷传送门AtCoder传送门非常妙的题。先直观感受一下，显然当\(M\)大到一定程度后，\([0,M]\)的所有数都能被取到。考虑\(V\getsV+Ax+By\)，其中\(V+Ax+By\in[0,M]\)。如果\(x,y\)都是正数显然可以取到。如果一正一负，比如\(x>0,y\le0\)，那可以先把\(V\)......
  • Atcoder ABC321 笔记
    A-321-likeChecker\(\color{gray}{22}\)直接模拟voidsolve(){intn;cin>>n;intlst=-1;for(inti=n;i;i/=10){intu=i%10;if(u<=lst){cout<<"No"<<endl;......
  • AtCoder Grand Contest 025
    A-DigitsSum按题意模拟即可。#include<iostream>#include<cstdio>usingnamespacestd;constintINF=1061109567;intn;intcalc(intx){intres=0;while(x)res+=x%10,x/=10;returnres;}intmain(){scanf("%d",&......
  • AtCoder Grand Contest 026
    A-ColorfulSlimes2可以发现，对于连续的一段长度为\(m\)的相同的字符，我们可以花费\(\lfloor\frac{m}{2}\rfloor\)的代价将它改为符合要求的。#include<iostream>#include<cstdio>usingnamespacestd;constintN=105;intn;inta[N];intmain(){scanf("%d"......
  • AtCoder Grand Contest 022
    A-DiverseWord如果至少有一个字符没有出现过，只要在原字符串后面加入一个没有出现过的字符中最小的那个字符就好了。如果所有字符都出现过，找到一个尽量靠后的位置\(i\in[1,n)\)，使得\(s_i\lts_{i+1}\)，最优字符串将\(s_i\)换成\([i+1,n]\)里面比\(s_i\)大的最小的那个......
  • AtCoder Grand Contest 023
    A-Zero-SumRanges令\(s_n=\sum\limits_{i=1}^na_i\)，相当于找满足\(l\ler,s_r-s_{l-1}\)的点对\((l,r)\)的个数，直接搞就完事了。#include<iostream>#include<cstdio>#include<unordered_map>usingnamespacestd;constintN=200005;intn;inta[N]......
  • AtCoder Grand Contest 024
    A-Fairness每次操作后\(a_i-b_i=b_{i-1}-a_{i-1}\)，对\(k\)的奇偶性讨论一下即可。#include<iostream>#include<cstdio>usingnamespacestd;inta,b,c;longlongk;intmain(){scanf("%d%d%d%lld",&a,&b,&c,&k);if(k%2==0)......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99