康复训练 - ZigZagK的博客

康复训练

ZigZagK

2020年8月1日 20:33

Online Judge

查看标签

9 条评论

准备打ACM了，进行康复训练。

洛谷P1045 麦森数

快速幂+高精度，因为要的是最后500位，所以只存500位就行了。

示例程序

#include<cmath>
#include<cstdio>
using namespace std;
const int maxl=500;

int p,a[maxl+5],w[maxl+5],c[maxl+5];

void Mul(int *a,int *b){
    for (int i=0;i<maxl;i++) c[i]=0;
    for (int k=0;k<maxl;k++)
        for (int i=0;i<=k;i++)
            c[k]+=a[i]*b[k-i];
    for (int k=0;k<maxl;k++) c[k+1]+=c[k]/10,a[k]=c[k]%10;
}
int main(){
    scanf("%d",&p);int len=ceil(log(2)/log(10)*p);
    printf("%d\n",len);a[0]=1;w[0]=2;
    while (p){
        if (p&1) Mul(a,w);
        if (p>>=1) Mul(w,w);
    }
    a[0]--;
    for (int i=maxl-1,tem=50;~i;i--){
        putchar(a[i]+48);
        if ((--tem)==0) puts(""),tem=50;
    }
    return 0;
}

洛谷P1439 【模板】最长公共子序列

经典LCS转LIS，适用于两个序列元素相同但排列不同。

个人认为二分求LIS也是DP而不是贪心，存下来的队列que[i]表示长度为i的上升子序列中末尾最小的值，很显然que[i]是递增的，因此可以利用二分来进行DP转移。

示例程序

#include<cstdio>
using namespace std;
const int maxn=100000;

int n,a[maxn+5],ID[maxn+5],ans,que[maxn+5];

void Insert(int x){
    if (x>que[ans]) {que[++ans]=x;return;}
    for (int L=1,R=ans,mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)){
        if (que[mid-1]<x && x<que[mid]) {que[mid]=x;return;}
        if (x>que[mid]) L=mid+1; else R=mid-1;
    }
}
int main(){
    scanf("%d",&n);
    for (int i=1,x;i<=n;i++) scanf("%d",&x),ID[x]=i;
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=n;i++) Insert(ID[a[i]]);
    printf("%d\n",ans);return 0;
}

洛谷P3374 【模板】树状数组 1

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const int maxn=500000;

int n,m;LL c[maxn+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return Eoln(ch);
}
void Add(int x,int y) {for (int i=x;i<=n;i+=i&-i) c[i]+=y;}
LL Sum(int x) {LL sum=0;for (int i=x;i;i-=i&-i) sum+=c[i];return sum;}
int main(){
    freopen("3374.in","r",stdin);freopen("3374.out","w",stdout);
    readi(n);readi(m);
    for (int i=1,x;i<=n;i++) readi(x),Add(i,x);
    for (int i=1;i<=m;i++){
        int tp,x,y;readi(tp);readi(x);readi(y);
        if (tp==1) Add(x,y); else printf("%lld\n",Sum(y)-Sum(x-1));
    }
    return 0;
}

洛谷P2085 最小函数值

保证了A,B,C是正数，因此F(x)是单调递增的。

用二叉堆每次取出最小的，然后增加x就行了。

可以调用algorithm库里的二叉堆函数偷懒QwQ。

示例程序

#include<cstdio>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=10000;

int n,m,A[maxn+5],B[maxn+5],C[maxn+5],X[maxn+5];
int si;pair<int,int> Heap[maxn+5];

inline bool cmp(pair<int,int> a,pair<int,int> b) {return a.fr>b.fr;}
#define Push(x) (Heap[++si]=(x),push_heap(Heap+1,Heap+1+si,cmp))
#define Pop() (pop_heap(Heap+1,Heap+1+si--,cmp))
int F(int i,int x) {return A[i]*x*x+B[i]*x+C[i];}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d%d%d",&A[i],&B[i],&C[i]);
    for (int i=1;i<=n;i++) X[i]=1,Push(mp(F(i,X[i]),i));
    for (int i=1,fst=1;i<=m;i++){
        if (fst) fst=0; else putchar(' ');
        printf("%d",Heap[1].fr);int ID=Heap[1].sc;
        Pop();Push(mp(F(ID,++X[ID]),ID));
    }
    return 0;
}

洛谷P3372 【模板】线段树 1

线段树我都打不来了，康复一下。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=100000,maxt=maxn<<2;

int n,m;LL a[maxn+5],sum[maxt+5],tag[maxt+5],l[maxt+5],r[maxt+5];

void Build(int L,int R,int p=1){
    l[p]=L;r[p]=R;if (L==R) {sum[p]=a[L];return;}
    int mid=L+(R-L>>1);Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);
    sum[p]=sum[p<<1]+sum[p<<1|1];
}
void Addtag(int p,LL k) {sum[p]+=k*(r[p]-l[p]+1);tag[p]+=k;}
void Pushdown(int p) {if (tag[p]) Addtag(p<<1,tag[p]),Addtag(p<<1|1,tag[p]),tag[p]=0;}
void Add(int L,int R,LL k,int p=1){
    if (L==l[p]&&r[p]==R) return Addtag(p,k);
    int mid=l[p]+(r[p]-l[p]>>1);Pushdown(p);
    if (R<=mid) Add(L,R,k,p<<1); else if (L>mid) Add(L,R,k,p<<1|1);
    else Add(L,mid,k,p<<1),Add(mid+1,R,k,p<<1|1);
    sum[p]=sum[p<<1]+sum[p<<1|1];
}
LL Sum(int L,int R,int p=1){
    if (L==l[p]&&r[p]==R) return sum[p];
    int mid=l[p]+(r[p]-l[p]>>1);Pushdown(p);
    if (R<=mid) return Sum(L,R,p<<1); else if (L>mid) return Sum(L,R,p<<1|1);
    else return Sum(L,mid,p<<1)+Sum(mid+1,R,p<<1|1);
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]);Build(1,n);
    for (int i=1;i<=m;i++){
        int tp,L,R;LL k;scanf("%d%d%d",&tp,&L,&R);
        if (tp==1) scanf("%lld",&k),Add(L,R,k);
        else printf("%lld\n",Sum(L,R));
    }
    return 0;
}

洛谷P5656 【模板】二元一次不定方程(exgcd)

exgcd的推导

$$ \begin{cases} bx+(a\ mod\ b)y=(a,b)\\ aX+bY=(a,b)\\ a\ mod\ b=a-\lfloor{a\over b}\rfloor b \end{cases} $$

联立可知：

$$ aX+bY=ay+b(x-\lfloor{a\over b}\rfloor b) $$

所以一组可行解为 $\begin{cases}X=y\\Y=x-\lfloor{a\over b}\rfloor b\end{cases}$

任意解：$(X+k{b\over(a,b)},Y-k{a\over(a,b)}),k\in\mathbb{Z}$

代码实现的时候通过一个技巧可以避免引入临时变量：

int exgcd(int a,int b,LL &x,LL &y){
    if (!b) {x=1;y=0;return a;}
    int r=exgcd(b,a%b,y,x); //递归传参数时直接交换x,y的顺序
    y-=a/b*x;return r;
}

不定方程的推导

$ax+by=c$ ，显然如果 $(a,b)\not\mid c$ 那么方程无解。

令 $d={c\over(a,b)}$ ，求出 $ax+by=(a,b)$ 的一组可行解 $(x,y)$ ，令 $x_0=xd,y_0=yd$ ，那么 $(x_0,y_0)$ 就是不定方程的一组可行解。

任意解：$(x_0+k{b\over(a,b)},y_0-k{a\over(a,b)}),k\in\mathbb{Z}$

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;

int te,a,b,c;

#define EOLN(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
int exgcd(int a,int b,LL &x,LL &y){
    if (!b) {x=1;y=0;return a;}
    int r=exgcd(b,a%b,y,x);y-=a/b*x;return r;
}
int main(){
    freopen("5656.in","r",stdin);freopen("5656.out","w",stdout);
    for (readi(te);te;te--){
        readi(a);readi(b);readi(c);
        LL x,y;int r=exgcd(a,b,x,y),d=c/r;
        int Tx=b/r,Ty=a/r;LL T;
        if (c%r) {puts("-1");continue;}
        x*=d;y*=d;
        if (x<=0) T=-x/Tx+1,x+=Tx*T,y-=Ty*T;
        if (y<=0) T=-y/Ty+1,y+=Ty*T,x-=Tx*T;
        if (x<=0 || y<=0){
            if (x<=0) T=-x/Tx+1,x+=Tx*T,y-=Ty*T; printf("%lld ",x);
            if (y<=0) T=-y/Ty+1,y+=Ty*T,x-=Tx*T; printf("%lld\n",y);
        } else {
            int Lx,Rx,Ly,Ry;
            T=(x-1)/Tx;x-=Tx*T;y+=Ty*T;Lx=x;Ry=y;
            T=(y-1)/Ty;y-=Ty*T;x+=Tx*T;Rx=x,Ly=y;
            printf("%d %d %d %d %d\n",T+1,Lx,Ly,Rx,Ry);
        }
    }
    return 0;
}

洛谷P3379 【模板】最近公共祖先（LCA）

欧拉序：DFS进入 $x$ 节点时记录一次 $x$ ，$x$ 每个儿子访问完毕后记录一次 $x$ 。

求 $x$ 和 $y$ 的LCA时，找到 $x$ 进入的位置和 $y$ 进入的位置，求他们之间深度最小的点就是LCA。

这是个RMQ问题，可以用ST表解决。

示例程序

#include<cstdio>
#include<vector>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=500000,Log=20;

int n,ro,te,E,son[(maxn<<1)+5],nxt[(maxn<<1)+5],lnk[maxn+5];
int dis[maxn+5],ID[maxn+5],RMQ[(maxn<<1)+5][Log+5],lg[(maxn<<1)+5];

#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
void Dfs(int x,int pre=0){
    dis[x]=dis[pre]+1;ID[x]=++ID[0];RMQ[ID[0]][0]=x;
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Dfs(son[j],x),RMQ[++ID[0]][0]=x;
}
#define Miner(x,y) (dis[x]<dis[y]?(x):(y))
void Make(){
    for (int j=1;(1<<j)<=ID[0];j++)
        for (int i=1;i+(1<<j)-1<=ID[0];i++)
            RMQ[i][j]=Miner(RMQ[i][j-1],RMQ[i+(1<<j-1)][j-1]);
    for (int i=2;i<=ID[0];i++) lg[i]=lg[i>>1]+1;
}
int LCA(int x,int y){
    int L=ID[x],R=ID[y];if (L>R) swap(L,R);int k=lg[R-L+1];
    return Miner(RMQ[L][k],RMQ[R-(1<<k)+1][k]);
}
int main(){
    scanf("%d%d%d",&n,&te,&ro);
    for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x);Dfs(ro);Make();
    for (int x,y;te;te--) scanf("%d%d",&x,&y),printf("%d\n",LCA(x,y));return 0;
}

HDU1403 Longest Common Substring

康复下后缀数组。显然两个串所有后缀的LCP中最大的就是答案。

我们把两个串接起来，中间加一个没出现的字符隔开两个串，构造后缀数组，然后求满足条件的 $Height$ 中的最大值即可。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200001;

int n,m,ans;char s[maxn+5];
int SA[maxn+5],rk[maxn+5],t[(maxn<<1)+5],ha[maxn+5],H[maxn+5];

void Sort(int n,int m){
    for (int i=0;i<=m;i++) ha[i]=0;for (int i=1;i<=n;i++) ha[rk[i]]++;
    for (int i=1;i<=m;i++) ha[i]+=ha[i-1];for (int i=n;i;i--) SA[ha[rk[t[i]]]--]=t[i];
}
void Make(int n,int m=255){
    for (int i=1;i<=n;i++) rk[i]=s[i],t[i]=i,t[i+n]=0;Sort(n,m);
    for (int k=1,p=0;p<n;m=p,k<<=1){
        p=0;for (int i=n-k+1;i<=n;i++) t[++p]=i;
        for (int i=1;i<=n;i++) if (SA[i]>k) t[++p]=SA[i]-k;
        Sort(n,m);for (int i=1;i<=n;i++) t[i]=rk[i];rk[SA[1]]=p=1;
        for (int i=2;i<=n;i++) rk[SA[i]]=(p+=t[SA[i-1]]!=t[SA[i]] || t[SA[i-1]+k]!=t[SA[i]+k]);
    }
    for (int i=1,k=0;i<=n;i++) {if (k) k--;while (s[i+k]==s[SA[rk[i]-1]+k]) k++;H[rk[i]]=k;}
}
int main(){
    freopen("1403.in","r",stdin);freopen("1403.out","w",stdout);
    while (~scanf("%s",s+1)){
        n=strlen(s+1);s[n+1]='%';scanf("%s",s+n+2);m=strlen(s+1);
        Make(m);ans=0;
        for (int i=2;i<=m;i++){
            if (SA[i-1]<=n && SA[i]>n+1) ans=max(ans,H[i]);
            if (SA[i-1]>n+1 && SA[i]<=n) ans=max(ans,H[i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

HDU3045 Picnic Cows

排个序，显然分组在排过序的数组上是连续的，可以DP。

转移方程：$f_i=min\{f_j+sum_i-sum_j-(i-j)a_{j+1}\}$

考虑斜率优化（ $k<j<i$ ）：

$$ f_j+sum_i-sum_j-(i-j)a_{j+1}\le f_k+sum_i-sum_k-(i-k)a_{k+1}\\ f_j-sum_j+j\cdot a_{j+1}-(f_k-sum_k+k\cdot a_{k+1})\le i(a_{j+1}-a_{k+1})\\ {f_j-sum_j+j\cdot a_{j+1}-(f_k-sum_k+k\cdot a_{k+1})\over a_{j+1}-a_{k+1}}\le i $$

注意在算出 $i$ 时不能立刻入队，需要将 $i+1-T$ 入队。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=800000;

int n,m;LL a[maxn+5],sum[maxn+5],f[maxn+5];
int Head,Tail,que[maxn+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
#define X(i,j) (a[(j)+1]-a[(i)+1])
#define Y(i,j) (f[j]+a[(j)+1]*(j)-sum[j]-(f[i]+a[(i)+1]*(i)-sum[i]))
int main(){
    freopen("3045.in","r",stdin);freopen("3045.out","w",stdout);
    while ((readi(n),readi(m))!=EOF){
        for (int i=1;i<=n;i++) readi(a[i]);
        sort(a+1,a+n+1);for (int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
        Head=1;Tail=0;que[++Tail]=0;
        for (int i=m;i<=n;i++){
            while (Head<Tail && Y(que[Head],que[Head+1])<=X(que[Head],que[Head+1])*i) Head++;
            int j=que[Head];f[i]=f[j]+sum[i]-sum[j]-a[j+1]*(i-j);
            if ((j=i+1-m)>=m){
                while (Head<Tail && Y(que[Tail-1],que[Tail])*X(que[Tail],j)>=Y(que[Tail],j)*X(que[Tail-1],que[Tail])) Tail--;
                que[++Tail]=j;
            }
        }
        printf("%lld\n",f[n]);
    }
    return 0;
}

洛谷P3203 [HNOI2010]弹飞绵羊

康复LCT板子。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=200000;

int n,te,a[maxn+5];
int si[maxn+5],fa[maxn+5],son[maxn+5][2];bool flip[maxn+5];

#define is_ro(p) (son[fa[p]][0]!=(p) && son[fa[p]][1]!=(p))
#define Son(p) ((p)==son[fa[p]][1])
void Pushup(int p) {si[p]=si[son[p][0]]+1+si[son[p][1]];}
void Rotate(int t){
    int p=fa[t],d=Son(t);son[p][d]=son[t][d^1];son[t][d^1]=p;
    if (!is_ro(p)) son[fa[p]][Son(p)]=t;Pushup(p);Pushup(t);
    if (son[p][d]) fa[son[p][d]]=p;fa[t]=fa[p];fa[p]=t;
}
void Addflip(int p) {swap(son[p][0],son[p][1]);flip[p]^=1;}
void Pushdown(int p) {if (flip[p]) Addflip(son[p][0]),Addflip(son[p][1]),flip[p]^=1;}
void Splay(int p){
    static int top,stk[maxn+5];stk[top=1]=p;
    for (int i=p;!is_ro(i);i=fa[i]) stk[++top]=fa[i];
    while (top) Pushdown(stk[top--]);
    for (int pre=fa[p];!is_ro(p);Rotate(p),pre=fa[p])
        if (!is_ro(pre)) Rotate(Son(p)==Son(pre)?pre:p);
}
void Access(int p) {for (int lst=0;p;lst=p,p=fa[p]) Splay(p),son[p][1]=lst,Pushup(p);}
void Makero(int x) {Access(x);Splay(x);Addflip(x);}
void Link(int x,int y) {Makero(x);Makero(y);fa[x]=y;}
void Cut(int x,int y) {Makero(x);Access(y);Splay(x);son[x][1]=fa[y]=0;Pushup(x);}
int Ask(int x) {Makero(n);Access(x);Splay(x);return si[x]-1;}
int main(){
    freopen("3203.in","r",stdin);freopen("3203.out","w",stdout);
    scanf("%d",&n);n++;for (int i=1;i<=n;i++) si[i]=1;
    for (int i=1;i<n;i++) scanf("%d",&a[i]),Link(i,min(i+a[i],n));
    for (scanf("%d",&te);te;te--){
        int tp,x,y;scanf("%d%d",&tp,&x);x++;
        if (tp==1) printf("%d\n",Ask(x));
        else scanf("%d",&y),Cut(x,min(x+a[x],n)),a[x]=y,Link(x,min(x+a[x],n));
    }
    return 0;
}

洛谷P3376 【模板】网络最大流

康复网络流板子。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200,maxm=10000;

int n,m,S,T,dis[maxn+5];
int E,lnk[maxn+5],son[maxm+5],nxt[maxm+5],e[maxm+5];
int que[maxn+5],cur[maxn+5],ti,vis[maxn+5];

void Add(int x,int y,int z){
    son[E]=y;e[E]=z;nxt[E]=lnk[x];lnk[x]=E;E++;
    son[E]=x;e[E]=0;nxt[E]=lnk[y];lnk[y]=E;E++;
}
bool BFS(int s,int t){
    int Head=0,Tail=0;que[++Tail]=s;vis[s]=++ti;cur[s]=lnk[s];dis[s]=0;
    while (Head!=Tail){
        int x=que[++Head];
        for (int j=lnk[x],u;~j;j=nxt[j])
            if (e[j] && vis[u=son[j]]<ti) que[++Tail]=u,vis[u]=ti,cur[u]=lnk[u],dis[u]=dis[x]+1;
    }
    return vis[t]==ti;
}
LL DFS(int x,int t,int MIN=2147483647){
    if (x==t || !MIN) return MIN; LL f=0;int now;
    for (int &j=cur[x],u;~j;j=nxt[j])
        if (dis[x]+1==dis[u=son[j]] && (now=DFS(u,t,min(MIN,e[j]))))
            {e[j]-=now;e[j^1]+=now;f+=now;MIN-=now;if (!MIN) break;}
    return f;
}
LL Dinic(int s,int t) {LL MF=0;while (BFS(s,t)) MF+=DFS(s,t);return MF;}
int main(){
    scanf("%d%d%d%d",&n,&m,&S,&T);
    for (int i=1;i<=n;i++) lnk[i]=-1;
    for (int i=1,x,y,z;i<=m;i++) scanf("%d%d%d",&x,&y,&z),Add(x,y,z);
    printf("%lld\n",Dinic(S,T));return 0;
}

本文链接：https://zigzagk.top/2020/08/01/RecoveryTraining

请不要发毫无意义或内容不文明的评论。与本文无关评论请发留言板！

邮箱格式错误

网址请用http://或https://开头

支持Markdown和LaTeX数学公式

Emoji QwQ 贴吧 QQ Orz

😀 😁 😂 🤣 😃 😄 😅 😆 😉 😊 😋 😎 😍 😘 🥰 😗 😙 😚 🙂 🤗 🤩 🤔 🤨 😐 😑 😶 🙄 😏 😣 😥 😮 🤐 😯 😪 😫 😴 😌 😛 😜 😝 🤤 😒 😓 😔 😕 🙃 🤑 😲 ☹️ 🙁 😖 😞 😟 😤 😢 😭 😦 😧 😨 😩 😬 😰 😱 🥵 🥶 😳 🤪 😵 😡 😠 🤬 😷 🤒 🤕 🤢 🤮 🤧 😇 🤠 🥳 🥴 🥺 🤥 🤫 🤭 🧐 🤓 👻 🤲 👐 🙌 👏 🤝 👍 👎 👊 ✊ 🤛 🤜 🤞 ✌️ 🤟 🤘 👌 👈 👉 👆 👇 ✋ 🤚 🖐 🖖 👋 🤙 💪 🦵 🦶 🖕 ✍️ 🙏 👀 👴 🐴 🍋