ZigZagK的博客
康复训练
2020年8月1日 20:33
洛谷
查看标签

准备打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;
}

版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!