EXGCD和EXCRT前言我与这两个算法有很深的渊源。第一次遇到是三年前的五校联考，\(\text{t1}\)需要用到，于是我成了全场唯一一个没切\(\text{t1}\)的。第二次是两年前湖南省集，我依稀记得这是第二场的\(\text{Day1T2}\)，我花了\(\text{2.5h}\)去推\(\text{exCRT}\)的式子

https://atcoder.jp/contests/abc378/tasks/abc378_ehttps://atcoder.jp/contests/abc378/editorial/11300#include<bits/stdc++.h>#definexfirst#defineysecond#defineall(x)(x).begin(),(x).end()#definelowbit(x)(x)&-(x)usingnamespacestd;ty

多校A层冲刺NOIP2024模拟赛18\(T1\)A.选彩笔（rgb）\(100pts/100pts\)观察到\(0\ler,g,b\le255\)且答案具有单调性，故考虑二分答案。将\(r,g,b\)分别抽象成三维坐标下的\(x,y,z\)。设当前二分出的答案为\(mid\)，由调整法分析可知若存在一个边长为\(mid\)的

A选彩笔（rgb）一眼转三维坐标系搞。但是最开始想歪了，以为要转曼哈顿距离，但是发现三维切比雪夫距离不支持转曼哈顿距离。补充一个知识点\(x\)维的曼哈顿距离支持转到\(2^{x-1}\)维的切比雪夫距离所以一维和二维可以直接转化，但是三维及以上就不行了。三维曼哈顿距离等同于某

Link。Sol好题！我不是DP高手吗，怎么这么简单的DP题没场切。考虑暴力枚举子串，显然最多有\(n\sqrtn\)个，这些子串一定包含答案。对于一个串\(t\)和原串\(s\)，考虑\(s\)是否能用\(t\)拼出来。设\(t\)的长度为\(len\)。令\(f_{i,j}\)表示\(i\simj\)最后不能

P6879[JOI2020Final]スタンプラリー3Solution首先这是一道最优值问题，再根据数据范围\(n\le200\)，那么正解可能会是\(O(n^3)\)的DP。根据题意，我们发现主角走过的雕像一定是个区间，可以考虑区间DP。想一想我们需要知道什么，然后把它放到DP状态里面。我们需要知道

疯狂写，结果卡在t3的分类讨论当场暴毙，切完t4困得受不了睡觉去了。A.Quintomania难度：红#include<bits/stdc++.h>#definelllonglong#definemxn100010usingnamespacestd;llt,n,k,ans,a[mxn],c;voidsolve(){cin>>n;for(inti=1;i<=n;i++)cin>>a[i];f

AtCoderBeginnerContest378总结A直接模拟，存\(1\)到\(4\)出现个数。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<vector>#include<queue>#include<map&g

manacher马拉车算法（，OI-Wiki算法介绍：线性复杂度内找出以每个字符为回文中心的最长回文半径存下模板代码：intl=0,r=-1;for(inti=1;i<=n;i++){intk=i>r?1:min(d[l+r-i],r-i+1);while(i-k>0andk+i<=nands[i-k]==s[i+k])k++;d[

A.玩游戏贪心贪心假做法A了，左指针从一直向左移，右指针暴跳到最远的位置被hack了，没关系，特判一下

问题描述C++代码编译错误：usingnamespacestd;usingll=longlong;constintN=1e6+7;llprev[N];原因分析在C++的标准库中，std命名空间包含一个名为std::prev的函数，该函数用于获取容器中的前一个迭代器。在上述代码中，通过usingnamespacestd;语句，所

牛客周赛ROUND66-C题题解题目描述:小苯有一个正整数n，他想让n尽可能小，为此他可以做如下的操作任意次：将n的第一个数位放在最后一位。（例如n=123，则操作完后n=231）。小苯想知道他最小可以将n变为多少，请你帮他算一算吧。输入描述:每个测试文件内都包含多组测试数据。第一

二进制序列额运算题意：面对一个长度为n的数列a。∑(i,j,k,l=1~n)(a_iora_j)xor(a_kanda_l)结果对2^32取模思路：遇到相邻的数又加又减，大脑灵光一现，认为这题有规律可以找，于是乎，杨辉三角数就有了着落，一开始，使用暴力O(n^2)计算杨辉三角数，TLE了后来看了jzjr的题解，知道

NOIP2024模拟1\(T1\)HZTG2080.玩游戏\(24pts\)强化版：HDU6326ProblemH.MonsterHunter部分分\(24pts\)：\(O(n^{2})\)枚举所有可能的状态进行转移。点击查看代码lla[100010],sum[100010],f[2][100010];intmain(){ llt,n,k,i,j,len,l,r; cin>>t; for(

ABC378光速切掉前四题，结果倒在了第五题。A-Pairing难度：红。弱智题，不解释。#include<bits/stdc++.h>usingnamespacestd;intmain(){inta[5]={0};for(inti=1;i<=4;i++){intx;cin>>x;a[x]++;}intans=0;for(inti=1;i<=4;i++){

这场好难。A网格队列里的结构体数组开大了导致RE。。。正解很简洁，对于现在有的字符串，添加一个数字或符号的转移是相对固定的：添加一个数字，如果前一位是运算符，那么久新加一个数字，否则，让现在的数字乘以10加上它；添加运算符同理。点击查看代码#include<bits/stdc++.h>us

ShichikujiandPowerGrid题意还是很简单，每个点有点权，每个点之间也有边权求最小生成森林，每个一颗最小生成树的权值等于边权+最小点权思路边权我们很好处理，有模板，但如何处理这个点权，便成了主要的问题如果我们以边权的思路思考点权，那么点权就是某个点从到该点的边权而我们可

扩展欧几里得算法（Exgcd）裴蜀定理对于任意一组整数\(a,b\)，存在一组整数\(x,y\)，满足\(ax+by=\gcd(a,b)\)。Proof：考虑数学归纳法。当\(b=0\)时，由于\(\gcd(a,0)=a\)，则对于\(ax+0y=a\)这个不定方程，\(x=1\)，\(y\)取任意整数。假设存在一组整数\(x,y\)，满足$bx+(a\bmodb)y

总结\(t1\)看起来好简单啊，\(5min\)切了。\(t2\)看起来好简单啊，\(15min\)切了。\(t3\)看起来好难啊，\(50min\)跳了。一开始想到了二分答案，迟迟想不到\(O(n)\)的\(check\)，于是思维开始发散，从贪心想到\(dp\)。考完发现大家都是\(O(n^2)\)的\(check\)，wssb。\(t4\)

A最坏的情况就是所有开着的开关尽可能配对最好的情况就是所有开着的开关尽可能不配对#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<int,int>PII;constintN=1e6+10;constintmod=998244353;constintINF=0x3f3f3f3f;constllI

啊啊啊，S的内容已经把我整红温了！！！常用符号&运用:容斥原理中，有这几种常用的符号:如果想表示一个集合的元素数量，那么我们用\(|\mathbb{\mathbb{A}}|\)来表示，记作A的基数.定义\(\mathbb{\mathbb{A}}\cup\mathbb{\mathbb{B}}\)表示A与B的并集，即在A中有或在B中有的元素

也是打上搜了。小木棍曾经在题库上做过，数据水就过了，交洛谷发现只有87pts。《剪枝盛宴》钦定长度：最小肯定是最长的那根木棍，最长肯定是所有木棍的总和，并且这个长度一定只能是总和的因数。选择顺序：如果选一个长的合法，那么选若干个和相同的短的一定合法但不优，因此按长度倒

题目思路 是k的倍数  &&     && 代码#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;typedeflonglongll;lls[N],cnt[N];intmain(){intn,k;cin>>n>>k;for(inti=1;i<=n;i++){

模拟赛水题场。T1colorful签。感觉题挺好，正难则反，找出四角都相同的。在这两排有6个四角相同的矩形对于两排来说，我们只需要记录相同的列的个数，然后能直接算出个数。发现桶排每次清空复杂度太高，考虑每次只开一排的桶，只会有\(n\)个。code#include<bits/stdc++.h>u

动态规划。f[i][0/1]表示前i个且最后选A或B的方案的集合。所以f[i][0]=max(f[i-1][0],f[i-2][1])+A[i]。f[i][1]同理。1typedeflonglongLL;2constintN=1e5+10;3LLf[N][2];4classSolution{5public:6LLmaxEnergyBoost(vector<int>&A,vector<i