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

Codeforces-1720-Div2

Codeforces-1720-Div2

Created2022-08-18|Updated2022-11-09|CodeforcesDiv.2Contest 1720|Tutorial•Codeforces•Codeforces Div.2

Codeforces Round #815 (Div.2) By xiaruize A. Burenka Plays with Fractions 分情况考虑 a=0a=0a=0或b=0b=0b=0时,一次 a×d=b×ca\times d=b\times ca×d=b×c,两分数已经相等,答案为000 (a×d,b×c)(a\times d,b\times c)(a×d,b×c)有非111倍的倍数关系时,答案为111 其他情况,答案为222 Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263// Problem: A. Burenka Plays with Fractions// Contest: Codeforces Round #815 (Div. 2)// URL: https://codeforces.com/con ...

AGC-058

Created2022-08-14|Updated2022-11-09|AtcoderAtcoder Grand ContestAGC 058 Tutorial|Atcoder•Tutorial•Atcoder Grand Contest

Atcoder Grand Contest 058 By xiaruize A - Make it Zigzag 对于每一个PiP_iPi i为偶数如果Pi+1>PiP_{i+1}>P_iPi+1>Pi，则有两种选择 Pi+2<PiP_{i+2}<P_iPi+2<Pi 交换(Pi+1,Pi+2)(P_{i+1},P_{i+2})(Pi+1,Pi+2) 否则交换(Pi,Pi+1)(P_{i},P_{i+1})(Pi,Pi+1) i为奇数如果Pi+1<PiP_{i+1}<P_iPi+1<Pi，则有两种选择 Pi+2>PiP_{i+2}>P_iPi+2>Pi 交换(Pi+1,Pi+2)(P_{i+1},P_{i+2})(Pi+1,Pi+2) 否则交换(Pi,Pi+1)(P_{i},P_{i+1})(Pi,Pi+1) 一定是步数最少的可行方案感性理解：因为如果相邻两数不满足要求，那么一定需要交换来解决如果满足条件111，那么一次交换可以解决两个不满足要求的排序 ...

ABC-264-Tutorial

ABC-264-Tutorial

Created2022-08-13|Updated2022-11-09|AtcoderAtcoder Beginner ContestABC 261 Tutorial|Atcoder•Atcoder Beginner Contest•Tutorial

Atcoder Beginner Contest 264 By xiaruize A - “atcoder”.substr() 模拟题 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647/* 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 make_pair#define pii pair<int,int>#define pis pair<int,string>#define sec second#define fir firs ...

Codeforces-1714-Div3

Codeforces-1714-Div3

Created2022-08-02|Updated2022-10-04|CodeforcesDiv.3Div.3 (Contest 1714)|Tutorial•Codeforces•Codeforces Div.3

Codeforces Round #811 (Div. 3) By xiaruize A. Everyone Loves to Sleep’ 模拟 Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687// Problem: A. Everyone Loves to Sleep// Contest: Codeforces Round #811 (Div. 3)// URL: https://codeforces.com/contest/1714/problem/A// Memory Limit: 256 MB// Time Limit: 2000 ms//// Powered by CP Editor (https://cpeditor.o ...

ARC-145-Tutorial

ARC-145-Tutorial

Created2022-08-01|Updated2022-11-09|AtcoderAtcoder Regular ContestARC 145 Tutorial|Atcoder•Tutorial•Atcoder Regular Contest

Atcoder Regular Contest 145 By xiaruize A - AB Palindrome Stop Learning useless algorithms. --Um_nik 当你在想dp，想贪心，想hash时，都不会的Beginner已经AC\color{green}{AC}AC了！！！先特判n=2n=2n=2的情况其他的s[0]=As[0]=As[0]=A且s[n−1]=Bs[n-1]=Bs[n−1]=B的是NoNoNo 其他都是YesYesYes Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667// Problem: A - AB Palindrome// Contest: AtCoder - AtCoder Regular Contest 145// URL: http ...

并查集

Created2022-07-23|Updated2022-11-09|CSP|OI•knowledge

并查集基本框架并查集是一种树形数据结构，主要有以下的两个操作查找一个元素位于那个集合合并两个集合用一个fafafa数组表示当前元素的祖先是谁初始状态下fai=ifa_i=ifai=i 我们把一个集合记作这个集合组成的树的根节点，查询操作可以O(n)O(n)O(n)的完成 123456int find(int x){ if(fa[x]==x) return x; return find(fa[x]);} 而unionunionunion操作只需要把fa[find(x)]fa[find(x)]fa[find(x)]赋值为find(y)find(y)find(y)即可但是这个时间复杂度显然不够优秀，考虑去优化它路径压缩显然，我们每次找祖先是都会把同样的一条路重复走过，这显然不是最优的，因为祖先不可能下降，所以可以在find时把fa[x]fa[x]fa[x]赋值为find(fa[x])find(fa[x])find(fa[x])来简化以后的查询虽然表面上似乎这是小优化，但是路径压缩后的实际复杂度接近O(1)O(1)O ...

Loading the Database