NX の 博客

思维导图 快读 12345678inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return s*w;} 逆序对 12345678910111213141516171819void msort(int s, int t){ if (s == t) return; //如果只有一个数字则返回，无须排序 int mid=(s+t)/2; msort(s,mid); //分解左序列 msort(mid+1,t); //分解右序列 int i = s, j = mid + 1, k = s; //接下来合并 while (i <= mid && j <= t) { if (a[i] <= a[j])r[k++] = a[i++]; else { r[k++] = a[j++]; ans += mid - i + 1; }//统计产生逆序对的数量 } while (i <= mid) r[k++] = a[i+ ...

试题：CZYZ2017 夏令营 NOIP 模拟赛（提高组） 2017 年 8 月 4 日 得分：40/300（不想说话了） T1:传送带（10分） 这题要用三分，但是我们没有学过，我考试的时候也没有想出其他方法，只考虑了特殊情况 较好的题解 T2:疯狂的火神（0分） 这道题用数学推关系，考场直接暴搜但是居然没有拿分，肯定有地方错了 菜就是菜啊。。。以后考场也要试着去推关系，另外，背包差不多被我忘光了 T3：火神的鱼(30分） 线段树 但是我一开始没有注意鱼只会往x与y的正方向游，所以不会打线段树，只好暴搜，30分

真TMD难啊！！！！我真的想*欧几里得 好吧难还是得学啊。。。9九月就初赛 ①欧几里得算法 这东西很简单啊。。就记个结论就可以了 1gcd(a,b)=gcd(b,a%b) 然后就没有了 ②欧几里得算法的应用 这东西就是用来求最大公约数的 1234int gcd(int a,int b){ return b?gcd(b,a%b):a;} 接下来的才是难点 ③欧几里得算法拓展 欧几里得算法拓展用于求 ax+by=gcd⁡(a,b)\text{ax}{+ by} = \gcd\left( a,b \right) ax+by=gcd(a,b) 的其中一组解 具体过程如下：  ax1+by1=gcd⁡(a,b)\text{\ ax}_{1}{+ by}_{1} = \gcd\left( a,b \right)  ax1​+by1​=gcd(a,b) 利用欧几里得公式 =>bx2+(a%b)y2=gcd⁡(b,a%b)= > \text{bx}_{2}{+ (a\% b)y}_{2} = \gcd\left( b,a\% b \right) =>bx2​+(a%b)y2​=gcd(b,a%b) 可以重复利用欧几里得公式，到最后一层b会变成0 =>(…)xi+(…)yi =gcd⁡(…,0)= > (\ldots)x_{i} + (\ldots)y_{i}\ = \gcd\left( \ldots,0\right) =>(…)xi​+(…)yi​ =gcd(…,0) 最终b变成0时，最后一层的x与y可以求出来 axi+byi=g ...

差分数组例题：P1083 借教室 12345678910111213141516171819202122232425262728293031323334#include<bits/stdc++.h>using namespace std;const int INF = 0x3f3f3f3f;int a[1000000],b[1000000],c[1000000],d[1000000],x[1000000],y[1000000],n,m;bool check(int k){ memset(b, 0, sizeof(b)); for (int i = 1; i <= k; i++) { b[x[i]] += d[i]; b[y[i]+1] -= d[i]; } for (int i = 1; i <= n; i++) { c[i] = c[i - 1] + b[i]; if (c[i] > a[i])return 0; } return 1;}int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++)scanf("%d", &a[i]); for (int i = 1; i <= m; i++)scanf("%d %d %d", &d[i], &x[i], &y[i]); int l = 1 ...

【字符串】总结KMP算法 buildtime:2019年7月15日 KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。 先放两篇比较好的资料: 从头到尾彻底理解KMP（2014年8月22日版） [KMP算法]NEXT数列手算演示 KMP的算法流程： 假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符； 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。 换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值，即移动的实际位数为：j - next[j]，且此值大于等于1。 计算NEXT数组流程： 将前缀后缀相同数组去掉最后一个值，在前面加上-1即可（某些版本还有总体+1） 代码： 1234567891011121314151617181920212223242526272829303132333435363738#include<bits/stdc++.h>using ...

【整理】树莓派搭建私有云服务器（Nextcloud） buildtime:2019年7月10日 刚刚考完期末考，真的是累死。这个项目其实我去年就做过，现在想重新总结一下。最详细也最正式地\colorbox{purple}{\color{white}{\text{最详细也最正式地}}}最详细也最正式地​ 教授大家如何实现这个项目。 我的配置 树莓派3A+一块 聪明的脑子一个 树莓派其实可以使用其他任意版本（zerow也可以，虽然很卡但是仍可以正常使用） 请事先调试好你的树莓派确保能正常上网和连接，如有异议请点击这里入门 好的我们开始！ Step0：基础知识 首先你需要有一个总体的概念才能一步步完成这个项目 好的，首先，我们要搭建一个私有云服务器 私有云服务器说白了就是运行私有云的一个网站服务器 要搭建一个网站，就不得不提一个词：LAMP\colorbox{purple}{\color{white}{\text{LAMP}}}LAMP​ 何为LAMP\colorbox{purple}{\color{white}{\text{LAMP}}}LAMP​ ？ 这里引用百度百科： LAMP是指一组通常一起使用来运行动态网站或者服务器的自由软件名称首字母缩写：\colorbox{brown}{\color{white}{\text{LAMP是指一组通常一起使用来运行动态网站或者服务器的自由软件名称首字母缩写：}}}LAMP是指一组通常一起使用来运行动态网站或者服务器的自由软件名称首字母缩写：​ Linux，操作系统 Apache，网页服务器 MariaDB或MySQL，数据库管理系统 ...

首先要先感谢树莓派实验室创客群-G的大佬：【管理员】辣鸡管理 话说我家的WiFi信号有些差劲，就想用树莓派中继一下，弄了一晚上之后成功，特此记录。 我的配置： 树莓派3A+一块 USB无线网卡一个（建议选择大功率的，我做出来网速就很慢） 树莓派其实可以用其他版本，zerow的话就需要MicroUSB转USB的线 之所以要用USB网卡是因为中继需要两张无线网卡：一张连接网络，一张开AP。 如果你想用网线开热点的话，就不要理这个，把下面的“连接到网络的网卡”改成eth0即可 请事先调试好你的树莓派确保能正常上网和连接，如有异议请点击这里入门 好的我们开始！ Step1：插上USB网卡 插上后要检查一下有没有被识别，一般都能够别识别的 键入命令以查看网络情况： 1ifconfig 之后应该有两张无线网卡：wlan0和wlan1，如图： 如果没有找到两张网卡，就是没有被识别，可以自行百度树莓派识别USB网卡 Step2：安装create_ap create_ap是GitHub上一个开源项目，专门用于开热点 1234567#把这个项目Git下来并安装sudo git clone https://github.com/oblique/create_apcd create_apsudo make install#安装依赖的库sudo apt-get install util-linux procps hostapd iproute2 iw haveged dnsmasq 这个东西的语法自己用-h去问，大概是这样的： 12345sudo create_ap 要使用的无线网卡 连接到网 ...

某有银用DP吗？？？ 其实这道题用来学习DP（动态规划）也挺好的 先创个数组a[i]用于存储每个数的约数 1int a[1000000]; 再将i从1枚举到n 1for(int i=1;i<=n;i++) 而且，可以从i的枚举i的倍数，且i绝对为i的倍数的约数 So。。。可设个变量j获得i的j倍 而且向前填数组的时候要注意i*j<=n即可 最后，1也算约数，所以a[i]++; 代码奉上 12345678910111213141516171819#include<bits/stdc++.h>using namespace std;int a[1000000],n,sum;int main(){ cin>>n; for(int i=1;i<=n;i++) { int j=2; while(j*i<=n) { a[j*i]++; j++; } a[i]++; } for(int i=1;i<=n;i++)sum+=a[i]; cout<<sum;}

不用那么麻烦 做个函数判断类型，再按照“左右根"的顺序分解即可 直接上代码吧 12345678910111213141516171819202122#include<bits/stdc++.h>using namespace std;string tree;int n;char get_kind(string x)//获得FBI类型 { if(x.find('0')!=x.npos&&x.find('1')!=x.npos)return 'F'; //find判断是不包含子串要用!=x.npos的形式（ x.npos即为没有找到） else if(x.find('0')!=x.npos)return 'B'; else return 'I';}void def(string tree)//“左右根”分解 { if(tree.length()==1){cout<<get_kind(tree);return;} def(tree.substr(0,tree.length()/2));//左 def(tree.substr(tree.length()/2));//右 cout<<get_kind(tree);//根 }int main(){ cin>>n>>tree; def(tree);}

标准答案（用sort+string） 先看长度，再用string的比较 12345678910111213141516171819202122232425262728#include<bits/stdc++.h>using namespace std;struct president{ string price; int n;}a[100];int m;bool cmp(president x,president y);int main(){ cin>>m; for(int i=1;i<=m;i++) { cin>>a[i].price; a[i].n=i; } sort(a+1,a+m+1,cmp); cout<<a[1].n<<endl<<a[1].price;}bool cmp(president x,president y){ if(x.price.length()!=y.price.length()) return x.price.length()>y.price.length(); else return x.price>y.price;}

好吧。。。感觉挺容易 关于质数的判断，我用了一种很高端的方法，没有见过的可以看一下 其他没有什么好说的。。。直接上代码 123456789101112131415161718192021222324252627282930313233343536373839404142#include<iostream>#include<cmath>using namespace std;int zhi(int);int main(){ int n; cin>>n; for(int a=2;a<=n;a++) { if(zhi(a)) { for(int b=2;b<=n;b++) { if(zhi(b)) { int c=n-a-b; if(zhi(c)) { cout<<a<<" "<<b<<" "<<c; goto end; } } } } } end: return 0;}int zhi(int n){ if(n==2|n==3) return 1; if(n%6!=1&&n%6!=5) return 0; int tmp=sqrt(n); for(int i=5;i<=tmp;i+=6) if(n ...