OI: olympiad in informatics 信息学奥林匹克竞赛
IOI: international olympiad in informatics 国际信息学奥林匹克竞赛
NOI: national olympiad in informatics 全国信息学奥林匹克竞赛
NOIP: national olympiad in informatics in province 全国信息学奥林匹克竞赛省赛
CSP: 非专业计算机能力认证 -J, -S。
J: junior: 低级的
S: senior: 高级的
进入提高组复赛，且得分非0的选手可以参加NOIP
CCF: China computer fundation 中国计算机协会
SMTP: 简单邮件传输协议(simple mail transport protocol)
POP3: 邮局协议版本3(Post Office Protocol - Version 3)
IMAP: 交互邮件访问协议（Internet Message Access Protocol)
面向过程: 只有C语言面向对象: 除了C语言的所有语言(C++, python, Java)
编译型语言和解释型语言编译型语言: C,C++,Pascal解释型语言: python, Java, PHP
计算机系统windows系统类unix系统: 除了windows系统以外的所有系统: android, ios, macOS, linux...
原码、反码、补码：8位二进制数表示的有符号整数
最左边一位是符号位(1:负数,0:正数)
反码: 原码的符号位不变，其他位取反
补码: 反码+1
补码:10101011
反码:10101010
原码:11010101
==> -85
-52
原码:10110100
反码:11001011
补码:11001100
\(x<<y= x\times 2^y\)
\(x>>y=\frac{x}{2^y}\)
| & | 按位与操作，按二进制位进行"与"运算。运算规则： 0&0=0; 0&1=0; 1&0=0; 1&1=1; | (A & B) 将得到 12，即为 0000 1100 |
|---|---|---|
| | | 按位或运算符，按二进制位进行"或"运算。运算规则： 0|0=0; 0|1=1; 1|0=1; 1|1=1; | (A | B) 将得到 61，即为 0011 1101 |
| ^ | 异或运算符，按二进制位进行"异或"运算。运算规则： 0^0=0; 0^1=1; 1^0=1; 1^1=0; | (A ^ B) 将得到 49，即为 0011 0001 |
| ~ | 取反运算符，按二进制位进行"取反"运算。运算规则： ~1=-2; ~0=-1; | (~A ) 将得到 -61，即为 1100 0011，一个有符号二进制数的补码形式。 |
| << | 二进制左移运算符。将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃，右边补0）。 | A << 2 将得到 240，即为 1111 0000\(x<<y= x\times 2^y\) |
| >> | 二进制右移运算符。将一个数的各二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃。 | A >> 2 将得到 15，即为 0000 1111\(x>>y=\frac{x}{2^y}\) |
\(∨\):或 -> 只要有一个为真，则表达式为真
\(∧\):且 -> 两个都是真才为真，有一个假为假
\(﹃（?）\)：非 -> 假为真，真为假
| 名称（按优先级从高到低） | 符号 | 顺序 |
|---|---|---|
| 后缀 | () [] -> . ++ - - | 从左到右 |
| 一元 | + - ! ~ ++ - - (type)* & sizeof | 从右到左 |
| 乘除 | * / % | 从左到右 |
| 加减 | + - | 从左到右 |
| 移位 | << >> | 从左到右 |
| 关系 | < <= > >= | 从左到右 |
| 相等 | == != | 从左到右 |
| 位与 AND | & | 从左到右 |
| 位异或 XOR | ^ | 从左到右 |
| 位或 OR | | | 从左到右 |
| 逻辑与 AND | && | 从左到右 |
| 逻辑或 OR | || | 从左到右 |
| 条件 | ?: | 从右到左 |
| 赋值 | = += -= *= /= %=>>= <<= &= ^= |= | 从右到左 |
| 逗号 | , | 从左到右 |
勾股定理：在直角三角形中，假设三条边长度为 \(a, b, c(a\leq b\lt c)\)。则\(a^2 + b ^ 2= c^2\)。
"小角对小边"：在直角三角形中，角度较小的角所对的边较短
角度制：一种表示角度的方法，一般写为 \(30^\circ, 75^\circ\)等。
单位圆：圆心在原点，半径为1的圆。
弧度制：高中的数学表示方法。角对应的单位圆上弧的长度
\(\pi = 180^\circ\)
正弦\(\sin \theta\) : 角\(\theta\)对边与斜边的比值， 余弦\(\cos \theta\): 角 \(\theta\) 邻边与斜边的比值，正切\(\tan\): 角 \(\theta\) 对比与邻边的比值
反三角函数: 反正弦函数 \(\arcsin x\) : 反余弦函数 \(\arccos x\): 反正切函数 \(\arctan x\) 。
排列：\(A_n^m=\frac{n!}{(n-m)!}\)（顺序有关）
组合：\(C_n^m=\frac{n!}{m!(n-m)!}\)（顺序无关）
\(C_n^m=(C^{m\div p} _{n\div p})(C^{m\mod p}_{n\mod p})\)
$ h(n)=h(0) \times h(n-1) + h(1) \times h(n-2)+……+h(n-1)\times h(0)$
\(= \sum h(i)\times h(n-i-1)\)
\(h(n)=C^n_{2n}-C^{n+1}_{2n}\)
\(h(n)=\frac{C_{2n}^n}{n+1}\)
圆排列：\(A^m_n=\frac{n!}{(n-m)!}\div m\)
错排序：\(D(n)=n!(\frac{(-1)^2}{2!}+\frac{(-1)^3}{3!}+…+\frac{(-1)^n}{n!})=n!\sum\limits^n_{k=2}\frac{(-1)^k}{k!}=\lbrack\frac{n!}{e}+\frac{1}{2}\rbrack\)
记录某个节点的父节点。（根表示为-1）
用链表来表示每个节点的所有子节点。
存储每个节点的子节点和兄弟节点。
对于二叉树的任意一个节点，左子树的所有结点都比他小，右子树所有节点都比他大。
深度为 \(\log n\) 的二叉树，查找一个点的时间复杂度为 \(O(\log n)\)。
度数为奇数的点为 \(0\) 或 \(2\)。
度数为奇数的点为 \(0\)。
#include <iomanip>cout <<fixed <<setprecision(2) <<a;printf("%.2f",a);int/double …… a[1005]; //设置数组a，类型为int/double……（变量类型 数组名[数组长度]）a[n]=n //将数组a的第n个赋值为ncout <<a[n]; //输出数组a的第n个arr[100]={0}; //将数组arr全设为0arr[100]={n1,n2,n3}; //将数组arr的第0个赋值为n1，第1个赋值为n2,第2个赋值为n31.数组长度不要用变量
2.数组长度可以多几个
3.数组的第一个元素下标为0，即第0个
4.*[n]={n};时，第0个设为n,其他位都为0
#include <algorithm> //头文件，导入排序的库sort(*+0,*+n+1,……) //按比较器排序（默认从小到大排序）sort(变量名+开始排序的下标，变量名+结束排序的下标+1，比较器)greater<int/double ……>()//从大到小排序 #include <cstring>memset(*,n,sizeof(*)) //把数组的每个值变成同一个值bool cmp(int x,int,y){ //布尔类型函数，名为cmp if(x>y){ return true; //如果x大于y，返回true } else{ return false; //否则返回false }}#include <string> //头文件，导入字符串string *; //设置变量*，类型为stringcout <<*; //输出变量*getline(cin,*); //输入一行忽略空格*.size() //求字符串*的长度*.find(s) //字符串*中第一个字符串s的位置,如果没有，返回string::npos*.insert(index,s) //在字符串*下标为index的位置插入字符串s*.replace(index,length,s) //在字符串*下标为index的位置选取长度为length的部分替换为s*.substr(index,length) //返回字符串*从下标为index的位置开始，长度为length的部分substring //子字符串（必须连续）subsequence //子序列（可以不连续） #include <cmath> //头文件pow(a,b) //a的b次方，参数类型double，返回值类型doublemax(a,b) //a与b的最大值，参数类型相同min(a,b) //a与b的最小值，参数类型相同ceil(x) //向上取整，参数类型doublefloor(x) //向下取整，参数类型doubleround(x) //四舍五入，参数类型doublesqrt(x) //开根，参数类型double，返回值类型double__gcd(x,y) //求x与y的最大公因数x*y/__gcd(x,y) //求x与y的最小公倍数 int/double …… *(int/double …… *, ……){ //函数类型 函数名称（参数类型 参数名，……） …… //函数执行的事 }当出现两个相同的变量时，按就近原则使用
函数内可以调用别的函数，也可以调用自己，即递归
//定义一种新的类型struct name{ //定义一个名为name的类型 int num; //一个整数类型num double num2; //一个实数类型num2 ...... //内含的其他变量（最后不用return） void print(){//成员方法 cout <<num; } name(int num,double num2):num(_num),num2(_num2){ }//构造函数初始化 name(){ num1=114514; num2=1919.810;//初始化 } name(): ......//用冒号初始化 name operator+(name num){//重载运算符 return node(y+num.x,y+num.y); }}; /、结尾有；name a; //定义一个类型为name的变量aa.num=114514; //变量a的num值为114514a.num2=1919.810 //变量a的num2值为1919.810a.print();//使用成员方法a=(1,1.1);//初始化name b;a=a+b;//重载后的运算符进行运算class a{ int x,y;//x和y是私有的 public: void print(){ cout <<x;//print()是公有的 } }struct node{ int val; node *nxt;//自引用};int main(){ node *head,*tail,*p; int x; cin >>x; //输入任意个整数， //在链表的末尾添加一个值为该整数的节点， //输入-1时结束。 head=new node; tail=head; while(x!=-1){ p=new node; //p->val <==> (*p).val; p->val=x; p->nxt=NULL; tail->nxt=p; tail=p; cin >>x; } //输出链表 p=head; while(p->nxt!=NULL){ p=p->nxt; cout <<p->val <<" "; } return 0;}priority_queue<int> q;//优先队列priority_queue<int,vector<int>,greater<int>> q;//从小到大q.push();//推入q.top();//队顶pair<int,int> x;//定义两个数据在x中x={1,2};//初始化，形同数组x.first=1;//第一个x.second=2;//第二个 pair<int,pair<int,int>> x;//套娃x.first;//第一个x.second.first;//第二个x.second.second;//第三个#include <set>set<int> s;//定义集合s.insert(1);//插入if(s.find(2)!=s.end())//查找2是否在s中#include <map>//map是映射的意思map<int,int> mp;//一个数据对应一个数据 mp[2]=3; mp[-1]=2; mp[114514]++;//map默认为0，可以直接使用，而且数据量大，只是慢P3366 【模板】最小生成树
#include <iostream>#include <vector>#include <queue>using namespace std;int n,m,ans=0,x=1;bool vi[200005];typedef pair<int,int> node;priority_queue <node,vector<node>,greater<node> > q;vector<node> e[200005];node a[200005];int main(){ cin >>n >>m; for(int i=1;i<=m;i++){ int u,v,l; cin >>u >>v >>l; e[u].push_back({l,v}); e[v].push_back({l,u}); } for(int i=1;i<=n;i++){ vi[i]=false; } vi[1]=true; for(int t=1;t<=n-1;t++){ for(int i=0;i<e[x].size();i++){ q.push(e[x][i]); } while(!q.empty() && vi[q.top().second]){ q.pop(); } if(q.empty()){ cout <<"orz"; return 0; } ans+=q.top().first; x=q.top().second; vi[x]=true; } cout <<ans; return 0;}#include <iostream>#include <queue>#include <vector>#include <cstring> using namespace std;struct node{ int v,l;};queue<int> q;vector<node> e[100005];int n,m,dis[100005];int main(){ memset(dis,0x3f,sizeof(dis)); int n,m,x; cin >>n >>m >>x; for(int i=1;i<=n;i++){ int u,v,l; cin >>u >>v >>l; node temp; temp.v=v,temp.l=l; e[u].push_back(temp); } int INF=dis[1]; q.push(1); dis[1]=0; while(!q.empty()){ int now=q.front(); q.pop(); for(int i=0;i<e[now].size();i++){ int len=e[now][i].l; int nxt=e[now][i].v; if(dis[nxt]>dis[now]+len){ q.push(nxt); dis[nxt]=dis[now]+len; } } } if(dis[x]!=INF)cout <<dis[x]; else cout <<-1; return 0;}关于SPFA,它死了
#include <iostream>#include <vector>#include <queue>#include <cstring>using namespace std;typedef long long ll;struct node{ int v, len;};ll dis[100005];vector<node> e[100005];typedef pair<int,int> PII;int main(){ int n, m, x; cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v, len; cin >> u >> v >> len; node temp; temp.v = v; temp.len = len; e[u].push_back(temp); } priority_queue<PII, vector<PII>, greater<PII> > q; q.push({0,1}); memset(dis, 0x3f, sizeof(dis)); long long INF = dis[0]; dis[1] = 0; while (!q.empty()) { while (!q.empty() && q.top().first > dis[q.top().second]) q.pop(); if (q.empty()) break; int now = q.top().second; q.pop(); for (int i = 0; i < e[now].size(); i++) { int nxt = e[now][i].v; int len = e[now][i].len; if (dis[nxt] > dis[now] + len) { q.push({dis[now]+len, nxt}); dis[nxt] = dis[now] + len; } } } for (int i = 1; i <= n; i++) { if (dis[i] != INF) cout << dis[i] << ' '; else cout << -1 << ' '; } return 0; }for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ f[i][j]=min(f[i][k],f[i][j]+f[k][j; } }}for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ f[i][j]|=f[i][j]&f[k][j; } }}最普通的筛法，也就是将前 \(n\) 个正整数一个一个来判断是否为素数，并且在判断素数的时候要从 \(2\) 枚举到 \(n-1\) 来判断。
for(int i=1;i<=n;++i){//枚举1到n bool flag=false; for(int j=2;j<i;++j){//枚举2到i if(i%j==0){//如果i%j=0,也就是i已经不为素数了 flg=1;//打上标记 break;//跳出循环，不用再枚举了 } } if(!flag)prime[i]=1;//如果没有被打上标记,标记这个数是素数。}这样的时间复杂度为 \(O(n^2)\)。
学过奥数的朋友们可能会发现，在判断素数的时候，不一定需要枚举到 \(i-1\) 只需要枚举到 \(\sqrt{n}\) 就可以判断出来了。
for(int i=1;i<=n;i++){//枚举1到n bool flag=false; for(int j=2;j*j<=i;j++){//枚举2到i if(i%j==0){//如果i%j=0,也就是i已经不为素数了 flag=true;//打上标记 break;//跳出循环，不用再枚举了 } } if(!flag)prime[i]=1;//如果没有被打上标记,标记这个数是为素数。}这样的时间复杂度为 \(O(n\sqrt{n})\)。
我们发现，上面两种筛法会筛到许多没有意义的数，所以我们必须换一种思想方式。
埃氏筛，就是先将 \(prime\) 数组全部赋值为 \(1\)。(记得将 \(prime_i\) 赋值为 \(0\) )。仍然是要从 \(1\) 枚举到 \(n\) 。我们先假设当前枚举到了 \(i\)。
如果 \(prime_i=1\)也就是 \(i\) 为质数，则我们可以知道 \(i\) 的倍数均为合数，所以我们就将 \(prime_{i\times k (2\leq k<n)}\) 赋值为 \(0\)。
最终筛完之后，如果 \(prime_i=1\), \(i\) 就是质数。
memset(prime,1,sizeof(prime));priem[1]=0;for(int i=1;i<=n;++i){ if(prime[i]){ for(int j=2;j*i<=n;++j){ prime[i*j]=0; } }}这样的时间复杂度为 \(O(nlogn)\)
我们发现，埃氏筛已经很快了，但是还是有所不足。
因为在埃氏筛中，有很多数有可能被筛到很多次（例如 \(6\),他就被 \(2\) 和 \(3\) 分别筛了一次）。 所以在欧拉筛中，我们就是在这个问题上面做了优化，使得所有合数只被筛了一次。
首先，我们定义 \(st_i\) 数组表示 \(i\) 是否为质数，\(primes_i\) 储存已经找到的所有质数，\(cnt\) 储存当前一共找到了多少质数。
如果当前已经枚举到了 \(i\)。如果 \(st_i=1\) ，也就是 \(i\) 为素数。则 \(primes_{cnt+1}=i\)。
然后我们每一次枚举都要做这个循环: 枚举 \(j\) 从 \(1\) 到 \(cnt\)。\(st_{primesj\times i}=0\)（因为 \(primes_j\) 为素数，\(i\) 就表示这个素数的多少倍，要把他筛掉。
注意，接下来是重点！如果 \(i\mod primes_j=0\)，跳出第二层循环。(因为欧拉筛默认每一个合数只能由他的最小质因数筛去，而满足以上条件之后，\(primes_j\) 就不是这个数字的最小质因数了，所以我们跳出第二层循环)。 因此，有了这一层优化之后，每一个合数就只能被筛掉一次了。
memset(st,0,sizeof(st));st[1]=0;for(i=2;i<=n;i++){ if(st[i]){ primes[cnt++]=i; for(j=0;primes[j]*i<=n&&j<=cnt;j++){ st[primes[j]*i]=0; if(i%primes[j]==0)break; } }}这样的时间复杂度为 \(O(n)\)
#include <iostream>using namespace std;int a[105],n,ans,m;void f(int now,int sum){ if(now==n+1){ if(sum==m){ ans++; } return ; } f(now+1,sum+a[now]); f(now+1,sum);}int main(){ cin >>n >>m; for(int i=1;i<=n;i++){ cin >>a[i]; } f(1,0); cout <<ans; return 0;}#include <iostream>#include <algorithm>using namespace std;int a[105],n,ans,m;bool flag;void f(int now,int sum,bool flag){ if(now==n+1){ if(sum==m){ ans++; } return ; } if(a[now-1]!=a[now] || flag){ f(now+1,sum+a[now],flag=true); } f(now+1,sum,flag=false);}int main(){ cin >>n >>m; for(int i=1;i<=n;i++){ cin >>a[i]; } sort(a+1,a+n+1); f(1,0,true); cout <<ans;}#include <iostream>using namespace std;int a[1005][1005],n,m,x1,y1,x2,y2,de_x[2]={1,0},de_y[2]={0,1},ans=-1e9;bool found=false,flag[1005][1005];bool c(int x,int y){ if(x<=0 || x>n || y<=0 ||y >m)return false;//必须在最前面 if(flag[x][y])return false; return true;}void f(int x,int y,int nows){ if(x==n && y==m){ ans=max(ans,nows); return ; } flag[x][y]=true; for(int i=0;i<4;i++){ int nx=x+de_x[i]; int ny=y+de_y[i]; if(c(nx,ny)){ f(nx,ny,nows+a[nx][ny]); } } flag[x][y]=false;}int main(){ cin >>n >>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin >>a[i][j]; } } f(1,1,a[1][1]); cout <<ans; return 0;}#include <iostream>using namespace std;int a[1005][1005],n,m,x1,y1,x2,y2,de_x[4]={-1,1,0,0},de_y[4]={0,0,-1,1};bool found=false,flag[1005][1005];bool c(int x,int y){ if(x<=0 || x>n || y<=0 ||y >m)return false;//必须在最前面 if(flag[x][y])return false; if(a[x][y]==1)return false; return true;}void f(int x,int y){ if(x==x2 && y==y2){ found=true; return ; } flag[x][y]=true; for(int i=0;i<4;i++){ int nx=x+de_x[i]; int ny=y+de_y[i]; if(c(nx,ny)){ f(nx,ny); } }}int main(){ cin >>n >>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin >>a[i][j]; } } cin >>x1 >>y1 >>x2 >>y2; f(x1,y1); cout <<(found?"yes":"no"); return 0;} #include <iostream> #include <vector> #include <queue> using namespace std; vector<int> e[100005]; int du[100005]; vector<int> ans; int main(){ int n, m; cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; e[u].push_back(v); du[v]++; } queue<int> q; for (int i = 1; i <= n; i++) { if (du[i] == 0){ q.push(i); } } while (!q.empty()){ // 2. 找队首 int now = q.front(); q.pop(); ans.push_back(now); // 3. 找相邻点 for (int i = 0; i < e[now].size(); i++) { int nxt = e[now][i]; du[nxt]--; if (du[nxt] == 0) { q.push(nxt); } } } if (ans.size() != n) cout << -1; else { for (int i = 0; i < ans.size(); i++) { cout << ans[i] << ' '; } } return 0; } #include <iostream> #include <queue> using namespace std; struct node { int x, y; }; int dx[4] = {0, 0, -1, 1}; int dy[4] = {-1, 1, 0, 0}; // dis[x][y]: (1,1)到(x,y)的距离 int dis[105][105], a[105][105]; bool visited[105][105]; int n, m; bool check(int x, int y) { if (x <= 0 || y <= 0 || x > n || y > m) return false; if (a[x][y] == 1) return false; if (visited[x][y]) return false; return true; } int main(){ cin >> n >> m; for (int i = 1; i <= n; i++){ for (int j = 1; j <= m; j++) { cin >> a[i][j]; } } queue<node> q; // 1. 放入起始点 node start; start.x = 1, start.y = 1; q.push(start); visited[1][1] = true; // 只要队列非空，继续循环 while (!q.empty()) { // 2. 弹出队首 node now = q.front(); q.pop(); // 3. 找到当前点所有相邻的点，入队,把相邻点设为已访问过 for (int i = 0; i < 4; i++) { node nxt; nxt.x = now.x + dx[i]; nxt.y = now.y + dy[i]; if (check(nxt.x, nxt.y)) { q.push(nxt); // plan2 visited[nxt.x][nxt.y] = true; dis[x][y]: (1,1)到(x,y)的最短距离 dis[nxt.x][nxt.y] = dis[now.x][now.y] + 1; } } } if (visited[n][m]) cout << dis[n][m]; else cout << -1; } #include <iostream> #include <queue> #include <vector> using namespace std; vector<int> e[10005]; bool flag[10005]; int main(){ int n; cin >>n; for(int i=1;i<=n-1;i++){ int u,v; cin >>u >>v; e[v].push_back(u); e[u].push_back(v); } queue<int> q; q.push(1); flag[1]=true; while(!q.empty()){ int now=q.front(); q.pop(); cout <<now <<" "; for(int i=0;i<e[now].size();i++){ int nxt=e[now][i]; if(flag[nxt])continue; q.push(nxt); flag[nxt]=true; } } return 0; }p3374
#include <iostream> using namespace std; int n,m,a[500005],b[500005]; int lowbit(int x){ return x & -x; } void init(){ for(int i=1;i<=n;i++){ b[i]+=a[i]; if(i+lowbit(i)<=n)b[i+lowbit(i)]+=b[i]; } } void add(int pos,int x){ while(pos<=n){ b[pos]+=x; pos=pos+lowbit(pos); } } int fi(int pos){ int ans=0; while(pos>=1){ ans+=b[pos]; pos-=lowbit(pos); } return ans; } int main(){ cin >>n >>m; for(int i=1;i<=n;i++){ cin >>a[i]; } init(); while(m--){ int q,x,y; cin >>q >>x >>y; if(q==1){ add(x,y); } else{ cout <<fi(y)-fi(x-1) <<endl; } } return 0; }p3368
#include <iostream> using namespace std; typedef long long ll; ll n,m,a[500005],b[500005],f[500005]; ll lowbit(int x){ return x & -x; } void init(){ for(int i=1;i<=n;i++){ f[i]+=a[i]; if(i+lowbit(i)<=n)f[i+lowbit(i)]+=f[i]; } } void add(int pos,int x){ while(pos<=n){ f[pos]+=x; pos=pos+lowbit(pos); } } ll fi(int pos){ int ans=0; while(pos){ ans+=f[pos]; pos-=lowbit(pos); } return ans; } int main(){ cin >>n >>m; for(int i=1;i<=n;i++){ cin >>b[i]; } init(); while(m--){ ll q; cin >>q; if(q==1){ ll x,y,k; cin >>x >>y >>k; add(x,k); add(y+1,-k); } else{ ll x; cin >>x; cout <<fi(x)+b[x] <<endl; } } return 0; }