CSP-S考前复习
TempestMiku · · 个人记录
快读快写
namespace Testify{
inline int read(){
int f(1),x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
inline void WritE(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) WritE(x/10);
putchar(x%10+48);
}
inline void write(int x){
WritE(x);
puts("");
}
inline void Write(int x){
WritE(x);
putchar(' ');
}
};
using namespace Testify;树链剖分求lca
namespace Shupao{
int head[N],nxt[N<<1],to[N<<1],tot,val[N<<1];
inline void add(int x,int y,int v){
to[++tot]=y,nxt[tot]=head[x],head[x]=tot;
val[tot]=v;
return ;
}
int dep[N],siz[N],dfn[N],dfncnt(0),son[N],f[N],dis[N],rk[N],top[N];
inline void dfs1(int now,int fa){
dep[now]=dep[fa]+1;
siz[now]=1;
f[now]=fa;
for(register int i=head[now];i;i=nxt[i]){
int y=to[i];
if(y==fa) continue;
dis[y]=dis[now]+val[i];
dfs1(y,now);
siz[now]+=siz[y];
if(siz[son[now]]<siz[y]){
son[now]=y;
}
}
}
inline void dfs2(int now,int topp){
dfn[now]=++dfncnt;
top[now]=topp;
rk[dfncnt]=now;
if(son[now]){
dfs2(son[now],topp);
}
for(register int i=head[now];i;i=nxt[i]){
int y=to[i];
if(y==f[now]||y==son[now]) continue;
dfs2(y,y);
}
}
inline int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]){
swap(x,y);
}
x=f[top[x]];
}
return dep[x]<dep[y]?x:y;
}
inline int Dis(int x,int y){
return dis[x]+dis[y]-dis[lca(x,y)]*2;
}
}ST表
int lg[N],f[N][22],a[N];
inline int query(int x,int y){
int l=lg[y-x+1];
return max(f[x][l],f[y-(1<<l)+1][l]);
}
signed main(void){
n=read(),m=read();
for(register int i=1;i<=n;i++){
a[i]=read();
f[i][0]=a[i];
}
lg[1]=0;
for(register int i=2;i<=n;i++){
lg[i]=lg[i>>1]+1;
}
for(register int j=1;j<=lg[n];j++){
for(register int i=1;i<=n-(1<<j)+1;i++){
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
for(register int i=1;i<=m;i++){
register int x=read(),y=read();
write(query(x,y));
}
return 0;
}线性筛
int prime[N],cnt=0;
bool vis[N];
inline void pre(){
for(register int i=2;i<=n;i++){
if(!vis[i]){
prime[++cnt]=i;
}
for(register int j=1;j<=cnt&&i*prime[j]<=n;j++){
vis[i*prime[j]]=true;
if(i%prime[j]==0){
break;
}
}
}
}倍增求lca
欧拉函数
树状数组
struct BIT{
int t[N];
#define lowbit(x) (x&-x)
inline void add(int x,int v){
for(;x<=n;x+=lowbit(x)){
t[x]+=v;
}
}
inline int ask(int x){
int res=0;
for(;x;x-=lowbit(x)){
res+=t[x];
}
return res;
}
inline int query(int l,int r){
return ask(r)-ask(l-1);
}
}bit;Lucas
分块
exgcd
inline int exgcd(int a,int b,int &x,int &y){
if(!b){
x=1,y=0;
return a;
}
int gcd=exgcd(b,a%b,y,x);
y-=a/b*x;
return gcd;
}
int x,y;
signed main(void){
n=read(),m=read();
int gcd=exgcd(n,m,x,y);
int op=(m/gcd);
write((x%op+op)%op);
return 0;
}莫队
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace Testify{
inline int read(){
int f(1),x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
inline void WritE(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) WritE(x/10);
putchar(x%10+48);
}
inline void write(int x){
WritE(x);
puts("");
}
inline void Write(int x){
WritE(x);
putchar(' ');
}
};
using namespace Testify;
int n,m;
const int N=1e6+5;
int a[N];
int pos[N];
int B;
struct node{
int l,r,id;
friend inline bool operator<(const node&a,const node&b){
if(pos[a.l]!=pos[b.l]){
return pos[a.l]<pos[b.l];
}
if(pos[a.l]&1){
return a.r>b.r;
}
return a.r<b.r;
}
}q[N],q2[N];
int tong[N],Ans=0;
inline void add(int x){
Ans=(Ans+2*tong[x]+1);
tong[x]++;
}
inline void del(int x){
Ans=(Ans-2*tong[x]+1);
tong[x]--;
}
int ans[N];
inline int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
signed main(void){
n=read(),m=read();
B=sqrt(n);
for(register int i=1;i<=n;i++){
pos[i]=(i-1)/B+1;
a[i]=read();
}
for(register int i=1;i<=m;i++){
q[i].l=read(),q[i].r=read();
q[i].id=i;
q2[i].l=q[i].l,q2[i].r=q[i].r;
q2[i].id=q[i].id;
}
sort(q+1,q+m+1);
int l=1,r=0;
for(register int i=1;i<=m;i++){
int L=q[i].l,R=q[i].r;
while(l<L) add(a[l++]);
while(l>L) del(a[--l]);
while(r<R) del(a[++r]);
while(r>R) add(a[r--]);
ans[q[i].id]=Ans;
}
for(register int i=1;i<=m;i++){
int len=q2[i].r-q2[i].l+1;
if(len==1){
puts("0/1");
continue;
}
int fenzi=ans[i]-len;
int fenmu=len*(len-1);
int Gcd=gcd(fenzi,fenmu);
printf("%lld/%lld\n",fenzi/Gcd,fenmu/Gcd);
}
return 0;
}高斯消元
for(register int i=1;i<=n;i++){
register int maxn=i;
for(register int j=i+1;j<=n;j++){
if(fabs(a[j][i])>fabs(a[maxn][i])){
maxn=j;
}
}
swap(a[i],a[maxn]);
if(!a[i][i]){
puts("No Solution");
return 0;
}
for(register int j=1;j<=n;j++){
if(i==j) continue;
register double tmp=a[j][i]/a[i][i];
for(register int k=i+1;k<=n+1;k++){
a[j][k]-=a[i][k]*tmp;
}
}
}gcd
inline int gcd(int a,int b){
return b?gcd(b,a%b):a;
}点分治
拓扑排序
spfa
堆优化dijktra
模拟退火
manachar
inline int init(){
int len=strlen(s);
str[0]='@',str[1]='#';
int j=1;
for(register int i=0;i<=len;i++){
str[++j]=s[i];
str[++j]='#';
}
str[++j]='~';
return j;
}
inline int manacher(){
int id=1,mx=1,maxn=0,len=init();
for(register int i=1;i<len;i++){
if(i<mx){
p[i]=min(p[id*2-i],mx-i);
}
else{
p[i]=1;
}
while(str[i-p[i]]==str[i+p[i]]){
p[i]++;
}
if(i+p[i]>mx){
mx=i+p[i];
id=i;
}
maxn=max(maxn,p[i]-1);
}
return maxn;
}KMP
线段树
矩阵快速幂
struct node{
int a[22][22];
node(){memset(a,0,sizeof(a));}
friend inline node operator*(const node&a,const node&b){
node c;
for(register int i=1;i<=k+2;i++){
for(register int j=1;j<=k+2;j++){
for(register int l=1;l<=k+2;l++){
c.a[i][j]=(c.a[i][j]+a.a[i][l]*b.a[l][j])%mod;
}
}
}
return c;
}
};
inline node qpow(node a,int b){
node res;
for(register int i=1;i<=k+2;i++){
res.a[i][i]=1;
}
for(;b;b>>=1,a=a*a){
if(b&1){
res=res*a;
}
}
return res;
}单调栈
const int N=3e6+5;
int a[N],f[N];
int stk[N];
int top=0;
signed main(void){
n=read();
for(register int i=1;i<=n;i++){
a[i]=read();
}
for(register int i=n;i>=1;i--){
while(top&&a[stk[top]]<=a[i]){
top--;
}
f[i]=!top?0:stk[top];
stk[++top]=i;
}
for(register int i=1;i<=n;i++){
Write(f[i]);
}
return 0;
}