Aurouki

线性DP题目链接：https://codeforces.com/contest/1547/problem/E

应用场景    一般用于快速找到一个子数组是否完整地出现，主要是利用了异或的性质和哈希降低冲突的原理 . 原理介绍    异或满足交换律，判断某一段数字是否一一出现(排序后相同)，可以通过其区间异或值是否相同判定 .    区间异或值需要先维护前缀异或和，区间 $[l,r]$ 的区间异或值为$Sum[r] \oplus Sum[l-1]$ . 代码模版  例：判断区间[l,r]的数字是否包含数字 $l - r$12345678910111213141516171819202122#include<bits/stdc++.h>#define endl '\n' using i64 = long long;using namespace std;mt19937_64 rnd(time(0)); //随机数生成int n, q, l,r,a[300010];i64 base[300010], Xor[300010], Ha ...

E. 安 (思维/贪心)时间复杂度 ：$O(n)$题意    ​$May$ 和 $Ray$ 分别拥有一支有 $n$ 个骑士的军队，第 $i$ 个骑士的血量分别为 $a_i$ 和 $b_i$ 。每次操作可以选择下标 $i$ ，指挥自己的军队去攻击对方下标为 $i$ 的军队，将对方骑士的血量值减一，当血量值为零时，该骑士被消灭。由 $May$ 作为先手，两人轮流交替操作，都会最大化自己幸存的骑士数量。请问最后$May$ 能幸存多少支骑士？ 数据范围 $1 \le n \le 10^5 , \sum n \le 10^5$ $1 \le a_i,b_i \le 10^9$ 思路​    从贪心的角度考虑，当$May$ 作为先手时，设 $May$ 最终幸存的骑士数量为 $cnt$ ，由于攻击对象只会是下标相同的骑士，分三种情况考虑： 当$a_i < b_i$ 的军队，$May$ 的攻击”无效”，因为 $Ray$ 作为后手一定会偿还伤害，无法摆脱 $a_i < b_i$ 的命运 当$a_i>b ...

A. Surrender to My Will(模拟)时间复杂度:$O(|S|)$题意    游戏有投降机制，一共有5个人，当投降赞成人数高于4票及以上时视为投降成功，反之则失败。现在给定一个长度为 $5$ 的字符串，字符种类有 $3$ 种类型：$’Y’$（赞成） $ ‘N’$（反对） $’-‘$(尚未投票)，请问最终的结果是什么？如果是赞成，则输出” $1$ “，反对则输出” $-1$ “，如不能确定答案，则输出 “ $0$ ” . 数据范围 $S_i \in \{ ’Y’ , ’N’ , ’-’ \}$ 思路    简单模拟题，当 $’Y’$ 的数量不小于 $4$ ，则结果一定赞成；当 $’N’$ 的数量不小于 $2$ ，则结果一定反对；剩下的情况显然不能确定答案 . Code:12345678910111213141516171819202122#include<bits/stdc++.h>#define endl '\n' using i64 = long long ...

K.Haitang and Ava(模拟)时间复杂度：$O(|S|)$题意    给定一个字符串$S$，有如下几个构造操作： 起始该字符串为空 转换为$S+ava$或者$ava+S$ 转换为$S+avava$或者$avava+S$     可以使用无数次上述操作，给定字符串，请问字符串是否能通过上述构造操作完成？若可以，则输出”Yes”,反之则输出”No”. 数据范围 $3 \le |S| \le 5 \times 10^5$ $\sum |S| \le 5 \times 10^5$ 分析    模拟题，根据构造规则，不难发现，满足构造规则的字符串有且只有一种构造方案，因为每个$ava$ 和 $avava$ 不存在重叠。手玩样例可知，每一项的分隔标志就是连续出现两个$a$,所以只需记录连续出现两个$a$的先后位置并暴力判断(长度不超过5)子串是否符合要求即可~ Code:123456789101112131415161718192021222324252 ...

J.Ball(数学)时间复杂度：$O(T)$题意    有一根水平放置且左端点位于$(0,0)$点的木棍，长度为$L$,在该木棍上选择一个支点进行旋转，请问其是否能经过给定的点$(x,y)$,如果能，则输出”Yes”并给出任意满足条件的支点横坐标$x’(x’ \in [1,L])$;如果不能，则输出”No”. 数据范围 $1 \le T \le 10^4$ $1 \le l \le 10^5,-10^5 \le x,y \le 10^5$ 思路    签到模拟题，取两端点的极端情况，其实就是找点$(x,y)$是否在$a^2+b^2=l^2$和$(a-l)^2+b^2=l^2$的圆内，直接比较判断.    注意数据类型开$long long$，因为乘式会爆$int$~~ Code:123456789101112131415161718192021#include<bits/stdc++.h>#define endl '\n' using ...

H. Genshin Impact’s Fault(模拟)时间复杂度：$O(|S|)$题意    有四种许愿结果：3星武器，4星武器，5星非促销武器和5星促销武器，分别用字符$’3’、’4’、’5’$和$’U’$表示,给定愿望清单，必须满足以下规则： 对于每个连续的10个愿望，不能只存在3星武器 对于每个连续的90个愿望，至少存在一件5星武器，不管是否促销 对于每两个相邻的5星武器之中，必须有一个是促销武器     给定愿望清单的字符串，请问是否符合所有规则？若满足，输出”$valid$”，反之则输出”$invalid$”. 数据范围 $c \in [‘3’,’4’,’5’,’U’]$ $\sum |S| \le 10^6$ 思路    设字符串长度为$n$,对三个规则进行转化： 当$n \ge 10$时，每个长度为10的连续区间是否满足不止存在字符$’3’$ 所有$’5’$或$’U’$的间隔距离，必不超过90，记得特判开头第一个和最后一个 相邻的两个五星武器 ...

Atcoder Beginner Contest 365A.Leap Year(模拟)    判断$n$是否为闰年，根据题意直接模拟即可. Code:12345678910111213141516171819#include<bits/stdc++.h>#define endl '\n' using i64 = long long;using namespace std;signed main(){ std::ios::sync_with_stdio(false);cin.tie(0); int y, d; cin >> y; if(y % 4) d = 365; else if(y % 100) d = 366; else if(y % 400) d = 365; else d = 366; cout << d << endl; return 0;} ...

题目链接：https://codeforces.com/contest/1771/problem/C题意    有n个正整数$a_i$，如果存在一个$x(x \ge 2)$使得$x$能够同时整除$a_i$和$a_j$，则称$i$与$j$成功配对。请问是否存在一对数能够成功配对？ 数据范围 $2 \le n \le 10^5$ $1 \le a_i \le 10^9$ $\sum n \le 10^5$

Codeforces Round 962(Div.3) (A-E)A.Legs    签到题，直接放代码 Code:123456789101112131415161718192021#include<bits/stdc++.h>#define endl '\n' using i64 = long long;using namespace std;signed main(){ std::ios::sync_with_stdio(false);cin.tie(0); int t; cin >> t; while(t--){ int n, ans; cin >> n; if(n==2) ans = 1; else if(n%4==0) ans = n / 4; else ans = n / 4 + 1; c ...