分享一下你们此题的做法

P1001 A+B Problem

xujian @ 2019-09-26 17:25:55

#include<algorithm>
#include<bitset>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<complex>
#include<csignal>
#include<csetjmp>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<iomanip>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#pragma GCC diagnostic error "-std=c++14"
#pragma GCC target("avx")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#define maxn 1000000 + 5
#define maxm 
#define ls (p<<1)
#define rs (p<<1|1)
#define lb(x) (x&(-x))
#define qmid ((l+r)>>1)
#define inf 123456789
#define iinf 1000000007
#define mod 10000000000000000
#define re register
#define il inline
#define rep(i,l,r) for(re int i=l;i<=r;++i)
#define dep(i,l,r) for(re int i=r;i>=l;--i)
#define nxt(i,u) for(int i=h[u];i;i=e[i].next)
#define mem(f,x) memset(f,x,sizeof(f))
#define file(a) freopen(#a".in","r",stdin); freopen(#a".out","w",stdout);
using namespace std;
typedef long long ll;
typedef double D;
using namespace std;
typedef long long lint;
lint n,m,p;
lint a[5001000];
lint read(){
    char c;lint x=0,f=1;
    c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return f*x;
}
void write(lint x){
    if(x<0)putchar('-'),x=-x;
    lint y=10,len=1;
    while(y<=x)y*=10,len++;
    while(len--)y/=10,putchar(x/y+48),x%=y;
    putchar(' ');
}
struct QAQ{
    string name;
    int score;
}stu[110];
bool cmp(QAQ a,QAQ b){
    return a.score>b.score;
}
struct node{
    lint left,right;
    lint data;
    lint lazy1,lazy2;
}tree[5001000];
void build(lint i,lint l,lint r){
    tree[i].left=l;tree[i].right=r;
    tree[i].lazy2=0;tree[i].lazy1=1;
    if(tree[i].left==tree[i].right){
        tree[i].data=a[l];
        return;
    }
    lint mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    tree[i].data=(tree[i<<1].data+tree[i<<1|1].data)%p;
    return;
}
void pushdown1(lint i){
    if(tree[i].lazy1==1)return;
    tree[i<<1].lazy1=(tree[i<<1].lazy1*tree[i].lazy1)%p;
    tree[i<<1|1].lazy1=(tree[i<<1|1].lazy1*tree[i].lazy1)%p;
    tree[i<<1].lazy2=(tree[i<<1].lazy2*tree[i].lazy1)%p;
    tree[i<<1|1].lazy2=(tree[i<<1|1].lazy2*tree[i].lazy1)%p;
    tree[i<<1].data=tree[i<<1].data*tree[i].lazy1%p;
    tree[i<<1|1].data=tree[i<<1|1].data*tree[i].lazy1%p;
    tree[i].lazy1=1;
    return;
}
void pushdown2(lint i){
    if(tree[i].lazy2==0)return;
    tree[i<<1].lazy2=(tree[i<<1].lazy2+tree[i].lazy2)%p;
    tree[i<<1|1].lazy2=(tree[i<<1|1].lazy2+tree[i].lazy2)%p;
    tree[i<<1].data=(tree[i<<1].data+(tree[i<<1].right-tree[i<<1].left+1)*tree[i].lazy2%p)%p;
    tree[i<<1|1].data=(tree[i<<1|1].data+(tree[i<<1|1].right-tree[i<<1|1].left+1)*tree[i].lazy2%p)%p;
    tree[i].lazy2=0;
    return;
}
void modify1(lint i,lint l,lint r,lint k){
    if(tree[i].left>r||tree[i].right<l)return;
    if(tree[i].left>=l&&tree[i].right<=r){
        pushdown1(i);
        pushdown2(i);
        tree[i].lazy1=(tree[i].lazy1*k)%p;
        tree[i].data=tree[i].data*k%p;
        return;
    }
    pushdown1(i);
    pushdown2(i);
    modify1(i<<1,l,r,k);
    modify1(i<<1|1,l,r,k);
    tree[i].data=(tree[i<<1].data+tree[i<<1|1].data)%p;
    return;
}
void modify2(lint i,lint l,lint r,lint k){
    if(tree[i].left>r||tree[i].right<l)return;
    if(tree[i].left>=l&&tree[i].right<=r){
        pushdown1(i);
        pushdown2(i);
        tree[i].lazy2=(tree[i].lazy2+k)%p;
        tree[i].data=(tree[i].data+(tree[i].right-tree[i].left+1)*k%p)%p;
        return;
    }
    pushdown1(i);
    pushdown2(i);
    modify2(i<<1,l,r,k);
    modify2(i<<1|1,l,r,k);
    tree[i].data=(tree[i<<1].data+tree[i<<1|1].data)%p;
    return;
}
lint query(lint i,lint l,lint r){
    if(tree[i].left>r||tree[i].right<l)return 0;
    if(tree[i].left>=l&&tree[i].right<=r)return tree[i].data%p;
    pushdown1(i);
    pushdown2(i);
    tree[i].data=(tree[i<<1].data+tree[i<<1|1].data)%p;
    return query(i<<1,l,r)+query(i<<1|1,l,r);
}
void quicksort(int left,int right){
    int i,j,base;
    i=left;j=right;
    base=a[(i+j)/2];
    while(i<=j){
        while(a[i]<base)i++;
        while(a[j]>base)j--;
        if(i<=j){
            int t=a[i];
            a[i]=a[j];a[j]=t;
            i++;
            j--;
        }
    }
    if(left<j)quicksort(left,j);
    if(i<right)quicksort(i,right);
}
int mian(){
    n=1;m=2;p=2147483647;
    for(lint i=1;i<=n;i++)a[i]=read();
    build(1,1,n);
    lint q,l,r,k;
    for(lint i=1;i<=m;i++){
        q=i==1?2:3;l=1;r=1;
        if(q==1)k=read(),modify1(1,l,r,k%p);
        else if(q==2)k=read(),modify2(1,l,r,k%p);
        else write(query(1,l,r)%p);
    }
    return 0;
}
//刚好250行,完美AC <a+b problem> ! 

看了题解感觉自己十分的菜,于是蒟蒻想知道还有没有什么高级的算法QAQ


by Tarsal @ 2019-09-26 17:27:13

@xujian 苣!


by ✨USTCJYZ✨ @ 2019-09-26 17:28:37

int mian()。。。


by ♘GoldHookDream♞ @ 2019-09-26 17:31:46

flody


by xujian @ 2019-09-26 17:42:59

@eason0511 Floyd太菜了,不如dij


by xujian @ 2019-09-26 17:44:49

@eason0511 主要是Floyd和dij代码都太短了QAQ何况我还不会链式前向星/堆优化


by xujian @ 2019-09-26 17:45:07

写出来多丢人QAQ


by xujian @ 2019-09-26 17:45:41

@Flash_plus 您最巨好吗


by qwerty0862 @ 2019-09-26 17:45:43

%%%


by 1saunoya @ 2019-09-26 17:54:04

@xujian 学了两年+连最基本的东西都不会……这个有什么好显摆的。。。


by Ynoi @ 2019-09-26 18:01:40

@清风ღ Orz

我学了三年,啥都不会/kk


| 下一页