noip模板整理
NOIP模板整理
By:Licher
By:Licher
- 數論
- 快速冪
- 高精度
- 加法
- 減法
- 乘法
- 除法
- 線性篩素數
- 埃氏篩法 O(nlglgn)
- 最大公約數(gcd)
- 最小公倍數(lcm)
- 擴展歐幾里德
- 數據結構
- 并查集
- 樹狀數組
- 單點修改
- 區間修改
- 線段樹
- ST表
- 圖論
- 單源最短路
- dijkstra
- SPFA
- 多源最短路
- floyd
- 最小生成樹
- kruskal
- 單源最短路
- 奇技淫巧
- 快讀
數論
快速冪
洛谷P1266
int quickPower(int a, int b)//是求a的b次方 {int ans = 1, base = a;//ans為答案，base為a^(2^n)while(b > 0)//b是一個變化的二進制數，如果還沒有用完{if(b & 1)//&是位運算，b&1表示b在二進制下最后一位是不是1，如果是：{ans *= base;//把ans乘上對應的a^(2^n)//ans %= p; //如果需要取模}base *= base;//base自乘，由a^(2^n)變成a^(2^(n+1))//base %= p; //同上，取模運算b >>= 1;//位運算，b右移一位，如101變成10（把最右邊的1移掉了），10010變成1001。現在b在二進制下最后一位是剛剛的倒數第二位。結合上面b & 1食用更佳}return ans; }高精度
洛谷P1601
加法
string add(string str1,string str2)//只能是兩個正數相加 {string str;int len1=str1.length();int len2=str2.length();//前面補0，弄成長度相同if(len1<len2){for(int i=1;i<=len2-len1;i++)str1="0"+str1;}else{for(int i=1;i<=len1-len2;i++)str2="0"+str2;}len1=str1.length();int cf=0;int temp;for(int i=len1-1;i>=0;i--){temp=str1[i]-'0'+str2[i]-'0'+cf;cf=temp/10;temp%=10;str=char(temp+'0')+str;}if(cf!=0) str=char(cf+'0')+str;return str; }減法
string sub(string str1,string str2)只能是兩個正數相減，而且要大減小 {string str;int tmp=str1.length()-str2.length();int cf=0;for(int i=str2.length()-1;i>=0;i--){if(str1[tmp+i]<str2[i]+cf){str=char(str1[tmp+i]-str2[i]-cf+'0'+10)+str;cf=1;}else{str=char(str1[tmp+i]-str2[i]-cf+'0')+str;cf=0;}}for(int i=tmp-1;i>=0;i--){if(str1[i]-cf>='0'){str=char(str1[i]-cf)+str;cf=0;}else{str=char(str1[i]-cf+10)+str;cf=1;}}str.erase(0,str.find_first_not_of('0'));//去除結果中多余的前導0return str; }乘法
string mul(string str1,string str2)//只能是兩個正數相乘 {string str;int len1=str1.length();int len2=str2.length();string tempstr;for(int i=len2-1;i>=0;i--){tempstr="";int temp=str2[i]-'0';int t=0;int cf=0;if(temp!=0){for(int j=1;j<=len2-1-i;j++)tempstr+="0";for(int j=len1-1;j>=0;j--){t=(temp*(str1[j]-'0')+cf)%10;cf=(temp*(str1[j]-'0')+cf)/10;tempstr=char(t+'0')+tempstr;}if(cf!=0) tempstr=char(cf+'0')+tempstr;}str=add(str,tempstr);}str.erase(0,str.find_first_not_of('0'));return str; }除法
//compare比較函數：相等返回0，大于返回1，小于返回-1 int compare(string str1,string str2) {if(str1.length()>str2.length()) return 1;else if(str1.length()<str2.length()) return -1;else return str1.compare(str2); }//兩個正數相除，商為quotient,余數為residue //需要高精度減法和乘法 void div(string str1,string str2,string "ient,string &residue) {quotient=residue="";//清空if(str2=="0")//判斷除數是否為0{quotient=residue="ERROR";return;}if(str1=="0")//判斷被除數是否為0{quotient=residue="0";return;}int res=compare(str1,str2);if(res<0){quotient="0";residue=str1;return;}else if(res==0){quotient="1";residue="0";return;}else{int len1=str1.length();int len2=str2.length();string tempstr;tempstr.append(str1,0,len2-1);for(int i=len2-1;i<len1;i++){tempstr=tempstr+str1[i];tempstr.erase(0,tempstr.find_first_not_of('0'));if(tempstr.empty())tempstr="0";for(char ch='9';ch>='0';ch--)//試商{string str,tmp;str=str+ch;tmp=mul(str2,str);if(compare(tmp,tempstr)<=0)//試商成功{quotient=quotient+ch;tempstr=sub(tempstr,tmp);break;}}}residue=tempstr;}quotient.erase(0,quotient.find_first_not_of('0'));if(quotient.empty()) quotient="0"; }線性篩素數
洛谷P1601
埃氏篩法 O(nlglgn)
const int MAXN = 1000000； void get_list() {int i, j;for (i=0; i<MAXN; i++) prime[i] = 1;prime[0] = prime[1] = 0;for (i=2; i<MAXN; i++){if (!prime[i]) continue;for (j=i*2; j<MAXN; j+=i) prime[j] = 0;} }最大公約數(gcd)
int gcd(int a,int b) {if(a==0) return blreturn gcd(b%a,a); }最小公倍數(lcm)
int lcm(int a,int b) {int c = a/gcd(a,b);return c*b; }擴展歐幾里德
同余方程 P1082
int exgcd(int a,int b,int &x,int &y){if (b==0){x=1,y=0;return a;}int d=gcd(b,a%b,y,x);y-=a/b*x;return d; }數據結構
并查集
洛谷P3367
int n, m; int fa[200005];int find(int x) //尋找祖宗節點 {if (fa[x] == x)return x;return fa[x] = find(fa[x]); }void add(int x, int y) {fa[find(x)] = find(y);//將y的祖宗節點變成x祖宗節點的父節點 }int main() {cin >> n >> m;for (int i = 1; i <= n; i++){fa[i] = i; //初始化，使每一個節點的父節點都是自己}for (int i = 1; i <= m; i++){int z, x, y;cin >> z >> x >> y;if (z == 1)add(x, y);if (z == 2)if (find(x) == find(y))cout << 'Y' << endl;elsecout << 'N' << endl;} }樹狀數組
單點修改
洛谷P3374
int n,m; int tree_array[1000010];//樹狀數組int lowbit(int x){return x&(-x);}void update(int point,int num)//在序列第point的位置加num {while(point<=n){tree_array[point] += num;point += lowbit(point);} }int sum(int point)//計算序列中1~point的和 {int res=0;while(point > 0){res += tree_array[point];point -= lowbit(point);}return res; }int main() {scanf("%d %d",&n,&m);for(int i = 1;i<=n;i++){int num;scanf("%d",&num);update(i,num);//初始值是0，直接更新即可}for(int i = 1;i<=m;i++){int z,x,y;scanf("%d %d %d",&z,&x,&y);if(z == 1){update(x,y);}if(z == 2){int ans = sum(y)-sum(x-1);//用[1,y]的和減去[1,x-1]的和就是[x,y]的和printf("%d\n",ans);}}return 0; }區間修改
洛谷P3368
差分處理
線段樹
洛谷P3372
long long n,m; long long a[100010]; struct TREE {long long l,r,num,lazy; }tree[400050];void build(long long left,long long right,long long index) {tree[index].l = left;tree[index].r = right;if(left == right){tree[index].num = a[left];return;}long long mid = (tree[index].l+tree[index].r)/2;build(left,mid,index*2);build(mid+1,right,index*2+1);tree[index].num = tree[index*2].num+tree[index*2+1].num; }void spread(long long index) {if(tree[index].lazy){long long nowlazy = tree[index].lazy;tree[index*2].num += nowlazy*(tree[index*2].r-tree[index*2].l+1);tree[index*2+1].num += nowlazy*(tree[index*2+1].r-tree[index*2+1].l+1);tree[index*2].lazy += nowlazy;tree[index*2+1].lazy += nowlazy;tree[index].lazy = 0;} }void add(long long index,long long left,long long right,long long value) {if(left<=tree[index].l && right>=tree[index].r){tree[index].num += value*(tree[index].r-tree[index].l+1);tree[index].lazy += value;return;}spread(index);long long mid = (tree[index].l+tree[index].r)/2;if(left <= mid) add(index*2,left,right,value);if(right > mid) add(index*2+1,left,right,value);tree[index].num = tree[index*2].num + tree[index*2+1].num; }long long search(long long index,long long left,long long right) {if((left <= tree[index].l) && (right >= tree[index].r)){return tree[index].num;}spread(index);long long mid = (tree[index].l+tree[index].r)/2;long long res = 0;if(left <= mid) res += search(index*2,left,right);if(right > mid) res += search(index*2+1,left,right);return res; }int main() {n = read();m = read();for(long long i = 1;i<=n;i++){a[i] = read();}build(1,n,1);for(long long i = 1;i<=m;i++){long long type,x,y,k;type = read();if(type == 1){x = read();y = read();k = read();add(1,x,y,k);}if(type == 2){x = read();y = read();long long ans = search(1,x,y);printf("%lld\n",ans);}}return 0; }ST表
洛谷P3865
int n,m; ll a[100010]; ll f[100010][21]; int l,r; void init() {for(int i = 1;i<=n;i++){f[i][0] = a[i];}for(int i = 1;i<21;i++){for(int j = 1;j+(1<<i)-1<=n;j++){f[j][i] = max(f[j][i-1],f[j+(1<<(i-1))][i-1]);}} }int search() {int k = log2(r-l+1);//<cmath>頭文件不要忘return max(f[l][k],f[r-(1<<k)+1][k]); }int main() {scanf("%d%d",&n,&m);for(int i = 1;i<=n;i++) scanf("%lld",a+i);init();while(m--){scanf("%d%d",&l,&r);printf("%d\n",search());}return 0; }圖論
單源最短路
洛谷P3371
dijkstra
int n,m,s; ll d[100010]; int num; int head[100010]; bool vis[100010]; struct EDGE{int v,ne;ll w; }e[200010]; priority_queue<P,vector<P>,greater<P> >q; void add(int x,int y,ll z) {num++;e[num].ne = head[x];e[num].v = y;e[num].w = z;head[x] = num; }inline int read() {int X=0,w=1; char c=getchar();while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();return X*w; }void dij() {d[1] = 0;for(int i = 2;i<=n;i++){d[i] = INF;}q.push(make_pair(0,1));while(!q.empty()){int x = q.top().second;q.pop();if(vis[x]) continue;vis[x] = 1;for(int i = head[x];i;i = e[i].ne){int v = e[i].v;ll w = e[i].w;if(d[v]>d[x]+w){d[v] = d[x]+w;q.push(make_pair(d[v],v));}}} }int main() {n = read();m = read();s = read();for(int i = 1;i<=m;i++){int x,y;ll z;x = read();y = read();z = read();add(x,y,z);}dij();for(int i = 1;i<=n;i++){printf("%lld ",d[i]);}return 0; }SPFA
int n,m,s; int num,head[10010]; ll d[10010]; bool v[10010]; queue<int> q; struct EDGE{int v,ne,w; }e[500010]; void add(int x,int y,int z) {num++;e[num].v = y;e[num].w = z;e[num].ne = head[x];head[x] = num; }void spfa() {for(int i = 1;i<=n;i++){d[i] = INF;}d[s] = 0;v[s] = 1;q.push(s);while(!q.empty()){int x = q.front();q.pop();v[x] = 0;for(int i = head[x];i;i=e[i].ne){int ver = e[i].v;int w = e[i].w;if(d[ver]>d[x]+w){d[ver] = d[x]+w;if(!v[ver]){v[ver] = 1;q.push(ver);}}}} }int main() {n=read();m=read();s=read();for(int i = 1;i<=m;i++){int x,y,z;x=read();y=read();z=read();add(x,y,z);}spfa();for(int i = 1;i<=n;i++){printf("%lld ",d[i]);}return 0; }多源最短路
floyd
int d[310][310],n,m;void floyd() {for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)d[i][j] = min(d[i][j],d[i][k]+d[k][j]); }int main() {cin>>n>>m;//把d數組初始化為鄰接矩陣memset(d,0x3f,sizeof(d));for(int i=1;i<-=n;i++) d[i][i] = 0;for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);d[x][y] = min(d[x][y],z);}floyd();//d[x][y]就是x到y的最短距離return 0; }最小生成樹
kruskal
洛谷P3366
int n,m; int fa[5005]; int ans = 0; struct EDGE{int x,y,w;friend bool operator<(EDGE A,EDGE B){return A.w>B.w;} }; priority_queue<EDGE> q;int find(int x) {if(fa[x]==x)return x;return fa[x] = find(fa[x]); }void add(int x,int y) {fa[find(x)] = find(y); }bool kurscal(){int cnt = 0;while(!q.empty()){int x = q.top().x;int y = q.top().y;int w = q.top().w;q.pop();if(find(x)!=find(y)){ans += w;add(x,y);cnt++;}}return cnt==n-1; }int main() {scanf("%d%d",&n,&m);for(int i = 1;i<=n;i++) fa[i] = i;for(int i = 1;i<=m;i++){EDGE e;scanf("%d%d%d",&e.x,&e.y,&e.w);q.push(e);}if(kurscal()){printf("%d",ans);}else{puts("orz");}return 0; }奇技淫巧
快讀
inline int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; }轉載于:https://www.cnblogs.com/lichers/p/9917164.html
總結
