Xiaruize's Blog - Welcome to xiaruize's Blog!

KYOCERA Programming Contest 2022 (AtCoder Beginner Contest 271)

KYOCERA Programming Contest 2022 (AtCoder Beginner Contest 271)

Created2022-10-04|Updated2022-11-09|AtcoderAtcoder Beginner ContestABC 271 Tutorial|Atcoder•Atcoder Beginner Contest

KYOCERA Programming Contest 2022 (AtCoder Beginner Contest 271) By xiaruize D - Flip and Adjust 很明显，贪心容易有反例 ⇒\rArr⇒ 考虑 dpdpdp dp[i][j][0/1]dp[i][j][0/1]dp[i][j][0/1] 表示当前考虑到第i位，和为j，正/反面朝上是否可行可以O(NS)O(NS)O(NS)的完成转移如果可行，根据dp状态就可以找到序列 Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384/* Name: Author: xiaruize Date:*/#include <bits/stdc++.h& ...

CSP2022第一轮游记

CSP2022第一轮游记

Created2022-09-20|Updated2022-11-09|游记CSP|游记•CSP

CSP2022第一轮游记 By xiaruize 入门级单选题前两题签到第三题要注意并没有改变 xxx 的值，而是改变了一个指针，所以选 DDD 痛失2分 4~8题基础题第9题似乎没有指明是强连通还是弱连通后面的单选还算仁慈阅读程序今年阅读题普遍难度提升了亿些。。。 T1 好像就是手算位运算，需要注意优先级问题 16 A 因为不用unsigned那一位应该也不会炸 17 B 改成short就会输出数字 18 B 显然不对 19 B 输出为12 20 B 输出为12 21 B 手动模拟 T2 22 B 执行了448次 23 A 两种不同的实现 fff 是爆搜， ggg 是 dpdpdp 24 A 模拟 25 C 三重循坏，分别是 n,m,nn,m,nn,m,n 的 26 C 呃呃呃，手模一下( 数学不好，痛失3分 27 B 模拟几个小的找规律 T3 28 A 简单估一下，注意是+不是 ×\times×， (不要问我怎么知道的 29 A 取平方根 30 B 只会尽量接近，不会相等 31 B midmax=n2=23500mid_{ma ...

ARC-148

Created2022-09-11|Updated2022-11-09|AtcoderAtcoder Regular ContestARC 148 Tutorial[object Object]|Atcoder•Tutorial•Atcoder Regular Contest

Atcoder Regular Contest 148 By xiaruize A - mod M 很明显，答案仅有可能为1/2，因为当 M=2M=2M=2 时，任何序列的结果均不可能超过 222 那么，可以考虑什么情况下答案为111 那么，显然我们需要找一个数，使得 {A1≡A2(mod x)A2≡A3(mod x)⋯An−1≡An(mod x)\begin{cases} A_1 \equiv A_2 (mod\ x)\\ A_2 \equiv A_3 (mod\ x)\\ \cdots \\ A_{n-1} \equiv A_n (mod\ x) \end{cases} ⎩⎪⎪⎪⎨⎪⎪⎪⎧A1≡A2(mod x)A2≡A3(mod x)⋯An−1≡An(mod x) 显然，当 x=gcd(∣A1−A2∣,∣A2−A3∣,⋯ ,∣An−1−An∣)x=gcd(|A_1-A_2|,|A_2-A_3|,\cdots , |A_{n-1}-A_n|)x=gcd(∣A1−A2∣,∣A2−A3∣,⋯,∣An−1−An∣) 时，上述 ...

浅谈线段树Segment_Tree

浅谈线段树Segment_Tree

Created2022-09-10|Updated2022-11-09|CSP|OI•knowledge

浅谈线段树Segment_Tree By xiaruize 引言 OI中,有一种好玩的游戏,叫做码线段树,那么线段树是什么??? 线段树的目的线段树主要用于在区间上动态维护一些值(如最大值,最小值,和,积等) 线段树的实现以区间最大值为例,给定一个长度为 nnn 的数组,每次查询求 [l,r][l,r][l,r] 之间的最大值,或将 [l,r][l,r][l,r] 赋值为 valvalval 显然,如果暴力去维护这个问题,需要 O(NQ)O(NQ)O(NQ) 的时间复杂度, 并不能解决1≤n,q≤1051 \leq n,q \leq 10^51≤n,q≤105级别的问题此时,我们考虑将原问题分解为 ([l,mid][l,mid][l,mid] 的 maxmaxmax 与 [mid+1,r][mid+1,r][mid+1,r] 的 maxmaxmax) 的 maxmaxmax 接着,我们可以以此类推,细分到只有一个节点当 n=6n=6n=6 时, 线段树如下图线段树的存储一般线段树使用和二叉树类似的方式存储注意4倍空间\color{red}{注意4倍空间}注意4倍 ...

百度之星2021复赛游记

百度之星2021复赛游记

Created2022-09-10|Updated2022-11-09|百度之星2021复赛|游记•百度之星

百度之星2021复赛游记我emo了... 400名有T恤穿,我403啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊 T1 题目概述给一个长度为 nnn 的序列,求怎么分割后每一段的 xorxorxor 值最大,输出这个最大值思路显然,每个数为一段最大,答案为每个数的和 Code Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849/* Name: Author: xiaruize Date:*/#include <bits/stdc++.h>using namespace std;#define int long long#define ull unsigned long long#define ALL(a) (a).begin(), (a).end()#define pb push_back#define mk ...

ARC-146

Created2022-08-23|Updated2022-11-09|AtcoderAtcoder Regular ContestARC 146 Tutorial|Atcoder•Tutorial•Atcoder Regular Contest

Atcoder Reguler Contest 146 By xiaruize A - Three Cards 简单分析一下,我们发现最优解为在总长度最长的情况下使高位尽可能大那么可以先 O(nlogn)O(nlogn)O(nlogn) 找出长度最大的 333 个数显然,如果有两个数的位数相同,应该优先选择更大的此时,我们已经确定最终组成答案的数,可以从高位至低位做关键字排序 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283// Problem: A - Three Cards// Contest: AtCoder - AtCoder Regular Contest 146// URL: https://atcoder.jp/contests/ ...

Loading the Database