2020年算法入门训练
二分答案
- 较好的Blog：《二分答案和三分入门》、《浅谈二分答案》
- 训练例题：二分答案专题、经典例题1 - 砍树、经典例题2 - 跳石头
并查集
- 较好的Blog：《OI-WIKI》、《并查集入门》、《并查集进阶》
- 训练例题：并查集专题、PID331 / 家族、[NOIP2010]关押罪犯、PID577 / 团伙
#include<stdio.h>
#include<stdlib.h>
#include <bits/stdc++.h>
#define fcin freopen("C:/Users/Administrator/Desktop/input.txt","r",stdin)
using namespace std;
typedef long long ll;
const int maxn=2e5+7;
int f[maxn]; //上级数组
int rk[maxn]; //数的高度
int sz[maxn]; //每个联通块的里元素个数
int mi[maxn],mx[maxn];
int find(int x){ //查找上级
return f[x]==x?x:f[x]=find(f[x]);
}
void add(int x,int y){ //不是同源，替换
if((x=find(x))!=(y=find(y))){
if(x>y){
f[y]=x,sz[y]+=sz[x];sz[x]=0;
mi[x]=min(mi[x],mi[y]); //维护最小值
mx[x]=max(mx[x],mx[y]); //维护最大值
}
else{
f[x]=y,sz[x]+=sz[y];sz[y]=0;
mi[y]=min(mi[y],mi[x]); //维护最小值
mx[y]=max(mx[y],mx[x]); //维护最大值
}
}
}
bool IsSame(int x,int y){ //检测连通性
if(find(x)==find(y))return true;
return false;
}
void Init(int n){ //初始化f，rk
for(int i=1;i<=n;i++)f[i]=i,rk[i]=1,sz[i]=1;
}
int main(){
fcin;
}
/*树层次优化add*/
void add(int x,int y){
if((x=find(x))!=(y=find(y))){
if(rk[x]>rk[y])f[y]=x; //令y的上级的上级为x的上级
else{
if(rk[x]==rk[y])rk[y]++;
f[x]=y;
}
}
}
矩阵快速幂
- 较好的Blog：《矩阵快速幂——入门》，《矩阵快速幂——进阶》，《矩阵快速幂——实战》
- 训练例题：矩阵快速幂专题
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
int mod;
struct Matix{
static const int _size=2;
ll m[50][50];
Matix(){
memset(m, 0, sizeof(m));
}
void InitC(ll a=1){
for(int i=0;i<_size;++i)m[i][i]=a;
}
Matix operator*(const Matix &m2){
Matix t;
for (int i = 0; i < _size; ++i)
for (int j = 0; j < _size; ++j)
for (int k = 0; k < _size; ++k)
t.m[i][j] = (t.m[i][j] + m[i][k] * m2.m[k][j]) % mod;
return t;
};
ll* const operator [] (const int i){
return m[i];
}
Matix operator^(int k) {
Matix x = *this, ans;
ans.InitC(); //初始化对角矩阵
while (k) {
if (k&1)
ans = ans * x;
x = x * x;
k >>= 1;
}
return ans;
}
Matix operator^(char *s){ //10进制快速幂
Matix g = *this,res;
res.InitC();
int len=strlen(s);
for(int i=len-1;i>=0;--i){
if(s[i]!='0')res=res*(g^(s[i]-'0'));
g=g^10;
}
return res;
}
}g, u;
ll x[10];
char n[maxn];
int main(){
ll a,b,ans=0;
scanf("%lld%lld%lld%lld",&x[0],&x[1],&a,&b);
scanf("%s%lld",n,&mod);
g[0][0]=0,g[0][1]=1,g[1][0]=b,g[1][1]=a;
u=g^n; //求g的n次方
for(int i=0;i<2;i++)ans=(ans+x[i]*u[0][i])%mod;
printf("%lld\n",ans);
}素数筛
- 较好Blog：《快速线性筛详解》、《线性筛》、《OI-WIKI -- 筛法》
- 训练例题：P3383 【模板】线性筛素数、素数筛专题
- 建议：有兴趣的可以自己了解下线性筛筛各类积性函数，因难度相对较大且涉及东西较多不在这里列出
const int MAX=1e7+7;//求MAX范围内的素数
long long su[MAX],cnt;
bool isprime[MAX];
void prime()
{
cnt=1;
memset(isprime,1,sizeof(isprime));//初始化认为所有数都为素数
isprime[0]=isprime[1]=0;//0和1不是素数
for(long long i=2;i<=MAX;i++)
{
if(isprime[i])
su[cnt++]=i;//保存素数i
for(long long j=1;j<cnt&&su[j]*i<MAX;j++)
{
isprime[su[j]*i]=0;//筛掉小于等于i的素数和i的积构成的合数
}
}
}
//欧拉筛 --线性,效率目前较高切代码量较短的筛法
int p[maxn], check[maxn], tot = 0;
void prime()
{
check[1]=1;
check[0]=1;
for(int i=2;i<maxn;i++)
{
if(!check[i])p[++tot]=i;
for(int j=1;j<=tot&&i*p[j]<maxn;j++)
{
check[i*p[j]]=1;
if(!(i%p[j]))break;//*****关键
}
}
}
//埃式筛法
int vis[maxn];
void Prime(){
mem(vis,0); //初始化都是素数
vis[0] = vis[1] = 1; //0 和 1不是素数
for (int i = 2; i <maxn; i++) {
if (!vis[i]) { //如果i是素数，让i的所有倍数都不是素数
if(i*i>=maxn)break;
for (int j = i*i; j <maxn; j += i) { //i*i开始比i+i有一定优化
vis[j] = 1;
}
}
}
}
线段树
- 较好Blog：《浅谈线段树》
- 较好视频讲解：《线段树入门》、《线段树进阶-lazy标记》、《线段树》
- 训练例题：线段树
#include<stdio.h>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
struct SegTree{
#define ls rt<<1
#define rs ls|1
#define mid ((l+r)>>1)
ll sum[maxn<<2],lz[maxn<<2];
void Down(int l,int r,int rt){ // 区间加lazy传递
if(lz[rt]){
ll v=lz[rt];
sum[ls]+=(mid-l+1)*v;
sum[rs]+=(r-mid)*v;
lz[ls]+=v;lz[rs]+=v;lz[rt]=0;
}
}
void Build(int l,int r,int rt,ll *a){
sum[rt]=lz[rt]=0;
if(l==r){sum[rt]=a[l];return;};
Build(l,mid,ls,a);
Build(mid+1,r,rs,a);
sum[rt]+=sum[ls]+sum[rs];
}
//rt l r是一块的，代表当前节点的编号和区间
//ql qr是你查询的区间
//可单点修改可区间修改，单点修改就ql=qr
void Add(int l,int r,int ql,int qr,ll v,int rt){
if(ql<=l&&r<=qr){
sum[rt]+=(r-l+1)*v;
lz[rt]+=v;
return;
}
Down(l,r,rt);
if(ql<=mid)Add(l,mid,ql,qr,v,ls);
if(qr>mid)Add(mid+1,r,ql,qr,v,rs);
sum[rt]=sum[ls]+sum[rs];
}
//区间查询
ll Query(int l,int r,int ql,int qr,int rt){
if(ql<=l&&r<=qr)return sum[rt];
Down(l,r,rt);
ll ans=0;
if(ql<=mid)ans+=Query(l,mid,ql,qr,ls);
if(qr>mid)ans+=Query(mid+1,r,ql,qr,rs);
return ans;
}
}seg;
ll a[maxn];
char opt[5];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
seg.Build(1,n,1,a);
while(m--){
int l,r;
ll v;
scanf("%s",opt);
if(opt[0]=='Q'){
scanf("%d%d",&l,&r);
printf("%lld\n",seg.Query(1,n,l,r,1));
}
else {
scanf("%d%d%lld",&l,&r,&v);
seg.Add(1,n,l,r,v,1);
}
}
return 0;
}树状数组
- 较好Blog：《树状数组彻底入门》、《线段树简单易懂的详解》、《二维树状数组模板》
- 训练例题：树状数组专题
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
struct BinaryTree{
int a[maxn]; //原数组
int tree[maxn],n;
int d[maxn]; //a[i]*i的树状数组，用于维护区间修改区间查询
#define lowbit(x) (x&(-x))
void add(int x,int v){ //单点修改
while(x<=n)tree[x]+=v,x+=lowbit(x);
}
ll query(int x){ //区间查询
ll sum=0;
while(x)sum+=tree[x],x-=lowbit(x);
return sum;
}
void Add(int x,int v){ //区间修改版本
int p=x;
while(x<=n){
tree[x]+=v,d[x]+=v*p;
x+=lowbit(x);
}
}
ll Query(int x){ //区间查询版本
ll sum=0,p=x;
while(x){
sum+=(p+1)*tree[x]-d[x];
x-=lowbit(x);
}
return sum;
}
}bt,Bt;
int main(){
scanf("%d",&bt.n);
for(int i=1;i<=bt.n;i++){
scanf("%d",&bt.a[i]),bt.add(i,bt.a[i]);
}
printf("%lld\n",bt.query(5)-bt.query(2));
scanf("%d",&Bt.n);
for(int i=1;i<=Bt.n;i++){
scanf("%d",&Bt.a[i]),Bt.Add(i,Bt.a[i]),Bt.Add(i+1,-Bt.a[i]);
}
int l,r,x;
scanf("%d%d%d",&l,&r,&x); //修改区间
Bt.Add(l,x),Bt.Add(r+1,-x);
printf("%lld\n",Bt.Query(5)-Bt.Query(2)); //区间查询
return 0;
}
One comment
niubi