首页 > 其他分享 >AtCoder Beginner Contest 367 A ~ F（无D题）题解

AtCoder Beginner Contest 367 A ~ F（无D题）题解

时间：2024-08-24 13:21:45浏览次数：9  
标签：pr AtCoder ch int 题解 mid 367 query pl

AtCoder Beginner Contest 367 A ~ F（ ̸ \not D）

几天前就已经vp过了，但是忘写题解了

今天才想起来

痛，早知道这么简单，我就不在家里摆烂了

A.Shout Everyday

罚了好几发，我打比赛一如既往的抽象

问题陈述

在 AtCoder 王国，居民们每天都要在 A A A 点大声喊出他们对章鱼烧的热爱。

住在 AtCoder 王国的高桥每天 B B B 点睡觉， C C C 点起床( 24 24 24 小时钟)。他醒着的时候可以喊出对章鱼烧的爱，但睡着的时候却不能。判断他是否每天都能喊出对章鱼烧的爱。这里，一天有 24 24 24 小时，他的睡眠时间小于 24 24 24 小时。

如果 B < C B < C B<C，那么 0 ∼ B − 1 ⋀ C + 1 ∼ 24 0 \sim B - 1 \bigwedge C + 1 \sim 24 0∼B−1⋀C+1∼24 是清醒的
如果 B > C B > C B>C，那么 C + 1 ∼ B − 1 C + 1 \sim B - 1 C+1∼B−1 是清醒的

AC-code:

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

int rd() {
	int x = 0, w = 1;
	char ch = 0;
	while (ch < '0' || ch > '9') {
		if (ch == '-') w = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + (ch - '0');
		ch = getchar();
	}
	return x * w;
}

void wt(int x) {
	static int sta[35];
	int f = 1;
	if(x < 0) f = -1,x *= f;
	int top = 0;
	do {
		sta[top++] = x % 10, x /= 10;
	} while (x);
	if(f == -1) putchar('-');
	while (top) putchar(sta[--top] + 48);
}

signed main() {

	int a = rd(),b = rd(),c = rd();
	if(b < c) {
		if(a < b || a > c) puts("Yes");
		else puts("No");
	}else {
		if(a < b && a > c) puts("Yes");
		else puts("No");
	}

	return 0;
}
B. Cut .0

赛时唐完了，jiangly好像也是用string（乐

问题陈述

一个实数 X X X 的小数点后第三位。

请在下列条件下打印实数 X X X 。

  • 小数部分不能有尾数 “0”。
  • 小数点后不能有多余的尾数。

这道题如果用 string ，那么恭喜你走了弯路！

这道题直接 cin >> 即可

#include<iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	double x;
	cin>>x;
	cout<<x;
	return 0;
}
C.Enumerate Sequences
问题陈述

按升序排列，打印所有满足以下条件的长度为 N N N 的整数序列。

  • 第 i i i 个元素介于 1 1 1 和 R i R_i Ri​ (含)之间。
  • 所有元素之和是 K K K 的倍数。

什么是序列的词典顺序？如果下面的 1. 或 2. 成立，则序列 A = ( A 1 , … , A ∣ A ∣ ) A = (A _ 1, \ldots, A _ {|A|}) A=(A1​,…,A∣A∣​) 在词法上**小于 B = ( B 1 , … , B ∣ B ∣ ) B = (B _ 1, \ldots, B _ {|B|}) B=(B1​,…,B∣B∣​) ：

  1. ∣ A ∣ < ∣ B ∣ |A|<|B| ∣A∣<∣B∣ 和 ( A 1 , … , A ∣ A ∣ ) = ( B 1 , … , B ∣ A ∣ ) (A _ {1},\ldots,A _ {|A|}) = (B _ 1,\ldots,B _ {|A|}) (A1​,…,A∣A∣​)=(B1​,…,B∣A∣​) 。
  2. 存在一个整数 1 ≤ i ≤ min ⁡ ∣ A ∣ , ∣ B ∣ 1\leq i\leq \min\\{|A|,|B|\\} 1≤i≤min∣A∣,∣B∣ ，且以下两个条件均为真：
  • ( A 1 , … , A i − 1 ) = ( B 1 , … , B i − 1 ) (A _ {1},\ldots,A _ {i-1}) = (B _ 1,\ldots,B _ {i-1}) (A1​,…,Ai−1​)=(B1​,…,Bi−1​)
  • A i < B i A _ i < B _ i Ai​<Bi​

数据范围这么小！

这道题是直接暴搜！

AC-code:

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

int rd() {
	int x = 0, w = 1;
	char ch = 0;
	while (ch < '0' || ch > '9') {
		if (ch == '-') w = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + (ch - '0');
		ch = getchar();
	}
	return x * w;
}

void wt(int x) {
	static int sta[35];
	int f = 1;
	if(x < 0) f = -1,x *= f;
	int top = 0;
	do {
		sta[top++] = x % 10, x /= 10;
	} while (x);
	if(f == -1) putchar('-');
	while (top) putchar(sta[--top] + 48);
}
const int N = 10;
int n,k;
int a[N],b[N];

void dfs(int now,int s) {
	if(now == n + 1) {
		if(s % k == 0) {
			for(int i = 1;i<=n;i++)	wt(b[i]),putchar(' ');
			putchar('\n');
		}
		return;
	}
	for(int i = 1;i<=a[now];i++) {
		b[now] = i;
		dfs(now + 1,s + i);
	}
}

signed main() {
	n = rd(),k = rd();
	for(int i = 1;i<=n;i++) a[i] = rd();
	dfs(1,0);
	return 0;
}
E.Permute K times
问题陈述

给你一个长度为 N N N 的序列 X X X ，其中每个元素都在 1 1 1 和 N N N 之间(包括首尾两个元素)，以及一个长度为 N N N 的序列 A A A 。
打印在 A A A 上执行以下操作 K K K 次的结果。

  • 将 A A A 替换为 B B B ，使得 B i = A X i B _ i = A _ {X _ i} Bi​=AXi​​ .

将 X i X_i Xi​ 看做 i i i 的父亲，其实这道题就是基环树上求 k t h kth kth 父亲

直接考虑倍增

AC-code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int rd() {
	int x = 0, w = 1;
	char ch = 0;
	while (ch < '0' || ch > '9') {
		if (ch == '-') w = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + (ch - '0');
		ch = getchar();
	}
	return x * w;
}

void wt(int x) {
	static int sta[35];
	int f = 1;
	if(x < 0) f = -1,x *= f;
	int top = 0;
	do {
		sta[top++] = x % 10, x /= 10;
	} while (x);
	if(f == -1) putchar('-');
	while (top) putchar(sta[--top] + 48);
}
const int N = 2e5+5;
int n,k,a[N],b[N];
int f[60][N];

signed main() {

	n = rd(),k = rd();
	for(int i = 1;i<=n;i++) f[0][i] = rd();
	for(int i = 1;i<=n;i++) a[i] = rd();
	for(int i = 1;i<=n;i++) b[i] = i;
	for(int j = 1;j<60;j++)
		for(int i = 1;i<=n;i++)	
			f[j][i] = f[j - 1][f[j - 1][i]];
	for(int j = 59;j >= 0;j--)
		if((k >> j) & 1) 
			for(int i = 1;i<=n;i++)
				b[i] = f[j][b[i]];
	for(int i = 1;i<=n;i++)
		wt(a[b[i]]),putchar(' ');
	return 0;
}
F.Rearrange Query
问题陈述

给你长度为 N N N 的正整数序列： A = ( A 1 , A 2 , … , A N ) A=(A _ 1,A _ 2,\ldots,A _ N) A=(A1​,A2​,…,AN​) 和 B = ( B 1 , B 2 , … , B N ) B=(B _ 1,B _ 2,\ldots,B _ N) B=(B1​,B2​,…,BN​) .

给你 Q Q Q 个查询，让你按顺序处理。下面将对 i i i -th 查询进行解释。

  • 给定正整数 l i , r i , L i , R i l _ i,r _ i,L _ i,R _ i li​,ri​,Li​,Ri​ 。如果可以重新排列子序列 ( A l i , A l i + 1 , … , A r i ) (A _ {l _ i},A _ {l _ i+1},\ldots,A _ {r _ i}) (Ali​​,Ali​+1​,…,Ari​​) 以匹配子序列 ( B L i , B L i + 1 , … , B R i ) (B _ {L _ i},B _ {L _ i+1},\ldots,B _ {R _ i}) (BLi​​,BLi​+1​,…,BRi​​) ，则打印 “是”，否则打印 “否”。

查询区间多重集元素是否相同？

仙人指路：P3792

可以Hash 做，但是我不会

考虑正确性高的做法，维护 n n n 次方和

用线段树维护 ∑ l r x 1 ∼ 3 \sum_{l}^r x^{1\sim 3} ∑lr​x1∼3

我赛时维护到了 7 7 7 次方(比较唐)

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
int rd() {
	int x = 0, w = 1;
	char ch = 0;
	while (ch < '0' || ch > '9') {
		if (ch == '-') w = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + (ch - '0');
		ch = getchar();
	}
	return x * w;
}

void wt(int x) {
	static int sta[35];
	int f = 1;
	if(x < 0) f = -1,x *= f;
	int top = 0;
	do {
		sta[top++] = x % 10, x /= 10;
	} while (x);
	if(f == -1) putchar('-');
	while (top) putchar(sta[--top] + 48);
}
const int N =2e5+5;
int n,q;
struct sgt{
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid ((pl + pr) >> 1)
int o[N];
int s[N<<2],s2[N<<2],s3[N<<2],mx[N<<2],mn[N<<2],s4[N<<2],s5[N<<2],s6[N<<2],s7[N<<2];

void push_up(int p) {
	mx[p] = max(mx[ls],mx[rs]);
	mn[p] = min(mn[ls],mn[rs]);
	s[p] = s[ls] + s[rs];
	s2[p] = s2[ls] + s2[rs];
	s3[p] = s3[ls] + s3[rs];
	s4[p] = s4[ls] + s4[rs];
	s5[p] = s5[ls] + s5[rs];
	s6[p] = s6[ls] + s6[rs];
	s7[p] = s7[ls] + s7[rs];
}

void build(int p,int pl,int pr) {
	if(pl == pr) {
		mx[p] = mn[p] = s[p] = o[pl];
		s2[p] = o[pl] * o[pl];
		s3[p] = o[pl] * o[pl] * o[pl];
		s4[p] = o[pl] * o[pl] * o[pl]* o[pl];
		s5[p] = o[pl] * o[pl] * o[pl]* o[pl]* o[pl];
		s6[p] = o[pl] * o[pl] * o[pl]* o[pl]* o[pl]* o[pl];
		s7[p] = o[pl] * o[pl] * o[pl]* o[pl]* o[pl]* o[pl]* o[pl];
		return;
	}
	build(ls,pl,mid);
	build(rs,mid+1,pr);
	push_up(p);
}

int query_s(int p,int pl,int pr,int l,int r) {
	if(l <= pl && pr <= r) return s[p];
	int re = 0;
	if(l <= mid) re += query_s(ls,pl,mid,l,r);
	if(r > mid) re += query_s(rs,mid+1,pr,l,r);
	return re;
}

int query_s2(int p,int pl,int pr,int l,int r){
	if(l <= pl && pr <= r) return s2[p];
	int re = 0;
	if(l <= mid) re += query_s2(ls,pl,mid,l,r);
	if(r > mid) re += query_s2(rs,mid+1,pr,l,r);
	return re;
}

int query_s3(int p,int pl,int pr,int l,int r) {
	if(l <= pl && pr <= r) return s3[p];
	int re = 0;
	if(l <= mid) re += query_s3(ls,pl,mid,l,r);
	if(r > mid) re += query_s3(rs,mid+1,pr,l,r);
	return re;
}
int query_s4(int p,int pl,int pr,int l,int r) {
	if(l <= pl && pr <= r) return s4[p];
	int re = 0;
	if(l <= mid) re += query_s4(ls,pl,mid,l,r);
	if(r > mid) re += query_s4(rs,mid+1,pr,l,r);
	return re;
}
int query_s5(int p,int pl,int pr,int l,int r) {
	if(l <= pl && pr <= r) return s5[p];
	int re = 0;
	if(l <= mid) re += query_s5(ls,pl,mid,l,r);
	if(r > mid) re += query_s5(rs,mid+1,pr,l,r);
	return re;
}
int query_s6(int p,int pl,int pr,int l,int r) {
	if(l <= pl && pr <= r) return s6[p];
	int re = 0;
	if(l <= mid) re += query_s6(ls,pl,mid,l,r);
	if(r > mid) re += query_s6(rs,mid+1,pr,l,r);
	return re;
}
int query_s7(int p,int pl,int pr,int l,int r) {
	if(l <= pl && pr <= r) return s7[p];
	int re = 0;
	if(l <= mid) re += query_s7(ls,pl,mid,l,r);
	if(r > mid) re += query_s7(rs,mid+1,pr,l,r);
	return re;
}

int query_mx(int p,int pl,int pr,int l,int r) {
	if(l <= pl && pr <= r) return mx[p];
	int re = 0;
	if(l <= mid) re = max(re,query_mx(ls,pl,mid,l,r));
	if(r > mid) re = max(re,query_mx(rs,mid+1,pr,l,r));
	return re;
}

int query_mn(int p,int pl,int pr,int l,int r) {
	if(l <= pl && pr <= r) return mn[p];
	int re = INT_MAX;
	if(l <= mid) re = min(re,query_mn(ls,pl,mid,l,r));
	if(r > mid) re = min(re,query_mn(rs,mid+1,pr,l,r));
	return re;
}

}A,B;

signed main() {

	n = rd(),q = rd();
	for(int i = 1;i<=n;i++) A.o[i] = rd();
	for(int i = 1;i<=n;i++) B.o[i] = rd();
	A.build(1,1,n);B.build(1,1,n);
	while(q--) {
		int l = rd(),r = rd(),L = rd(),R = rd();
		bool flag1 = (A.query_s(1,1,n,l,r) == B.query_s(1,1,n,L,R));
		bool flag2 = A.query_s2(1,1,n,l,r) == B.query_s2(1,1,n,L,R);
		bool flag3 = A.query_s3(1,1,n,l,r) == B.query_s3(1,1,n,L,R);
		bool flag4 = A.query_mn(1,1,n,l,r) == B.query_mn(1,1,n,L,R);
		bool flag5 = A.query_mx(1,1,n,l,r) == B.query_mx(1,1,n,L,R);
		bool flag6 = A.query_s4(1,1,n,l,r) == B.query_s4(1,1,n,L,R);
		bool flag7 = A.query_s5(1,1,n,l,r) == B.query_s5(1,1,n,L,R);
		bool flag8 = A.query_s6(1,1,n,l,r) == B.query_s6(1,1,n,L,R);
		bool flag9 = A.query_s7(1,1,n,l,r) == B.query_s7(1,1,n,L,R);
		if(flag1 && flag2 && flag3 && flag4 && flag5&& flag6&& flag7&& flag8&& flag9) puts("Yes");
		else puts("No");
	}

	return 0;
}

标签：pr,AtCoder,ch,int,题解,mid,367,query,pl
From： https://blog.csdn.net/qq_49785217/article/details/141498438

相关文章

  • AtCoder Beginner Contest 358
    C-Popcorn思路：从集合S中选出非空子集，使得子集中糖果口味有M种。观察到集合S中的元素数量n<=10。因此，总共的子集数为C<=2^10-1，考虑枚举所有的子集。代码：#include<bits/stdc++.h>#defineintlonglong#defineullunsignedlonglong#defineiosios::sync_with_s......
  • CF1326F2 Wise Men (Hard Version) 题解
    题目链接点击打开链接题目解法挺难的。可能一步一步推下来也没那么复杂（？基本copytzc_wk的题解/bx肯定不能像\(F1\)用普通的状压求，一个技巧是容斥考虑令\(f_S\)表示\(S\)中为\(1\)的位置\(p_i\)和\(p_{i+1}\)必须认识，为\(0\)的位置随便\(f\)数组相当于答案......
  • P6348 [PA2011] Journeys 题解
    Description一个星球上有\(n\)个国家和许多双向道路，国家用\(1\simn\)编号。但是道路实在太多了，不能用通常的方法表示。于是我们以如下方式表示道路：\((a,b),(c,d)\)表示，对于任意两个国家\(x,y\)，如果\(a\lex\leb,c\ley\led\)，那么在\(x,y\)之间有一条道路。首都位于......
  • 2018年安徽省赛小学组题解
    T1：移动石子（stone）题目描述期待已久的“清明”假期终于到了。清明节是中华民族几千年来留下的优良传统，它有利于弘扬孝道亲情，唤醒家庭共同记忆,促进家庭成员乃至民族的凝聚力和认同感。小学生卡卡西非常高兴，因为清明前后正是踏青的好时光，他终于可以和小伙伴们一起出去踏青了！然而，天......
  • CF1514D Cut and Stick 题解
    题目传送门前置知识可持久化线段树解法若区间内不存在绝对众数，直接保持这一段即可。若存在绝对众数，贪心地想肯定要尽可能地把其分开还要限制出其他数使其不成为绝对众数。容易发现设绝对众数出现次数为\(cnt\)，取\(cnt-1\)个其他数和绝对众数配对最优。但可能其他数不够\(......
  • AtCoder Beginner Contest 050
    基本上独立做出来了。A-AdditionandSubtractionEasy模拟。#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ ios::sync_with_stdio(false),cin.tie(nullptr); intA,B; charC; cin>>A>>C>>B; if(C==......
  • 题解：P10906 [蓝桥杯 2024 国 B] 合法密码
    本来以为字符串多大，结果就这点，直接暴力。枚举起始点，对于每个起始点枚举后面\(8\sim16\)位有没有能用的即可。最后答案为\(400\)。附：计算代码枚举代码如下：for(inti=0;i<n;++i){for(intlength=8;length<=16;++length){if(i......
  • 题解：P10903 [蓝桥杯 2024 省 C] 商品库存管理
    题目大意有一个初始化为\(0\)的长度为\(n\)的序列，现有\(m\)个操作，每次将区间\([L,R]\)中的数量加\(1\)，求如果不做某个操作将会有多少个数量为\(0\)的量。解题思路当看见这句话时就想到了差分，这题我们可以使用差分先处理将所有的操作执行后的数组，然后在算出如果减......
  • P10404 「XSOI-R1」原神数 题解
    一篇题解需要一张头图。容易发现超过十位的数都不是原神数，因为只有十个数字，不可能保证十一个位置互不相同。同时恰好十位的数也不可能是原神数，因为数位互不相同的十位数的数位和为\(45\)，被\(3\)整除，一定是\(3\)的倍数。于是把原神数的范围缩小到\([1,10^9)\)。显然不......
  • P10528 [XJTUPC2024] 崩坏：星穹铁道 题解
    求方案数，分多种情况，不难想到DP。设\(dp_{i,j}\)表示已经行动\(i\)次，剩余战技点个数为\(j\)的方案数，容易得到以下转移方程。\(a_i=1\)时，有\[dp_{i,j}=\begin{cases}0,&j=0,\\dp_{i-1,j-1},&1\leqslantj\leqslant4,\\dp_{i-1,j-1}+dp_{i......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99