洛谷OJ上的A+B花（zhuang）式（bi）解法

转眼间，快到八月了。我想我已经毕业很久了。我错过了在主要OJ上刷问题的时间。今天，我无意中在一个算法组中看到一个叫洛谷的OJ网站，这似乎很受欢迎，所以我注册了一个，进去看看，并轻松打开了A+B problem，然后……

突然觉得自己学了假A+B……

作者: Treeloveswater 更新时间: 2017-03-26 15:06 报告终于可以写A+B这么难的题了。咦？没人写LCT的题解？Link-Cut Tree 会很难过的！为了不让LCT难过，ORZ给我一个LCTA+B题解！送上代码：#include<iostream>#include<cstring>#include<cstdio>#include<cstring>using namespace std;struct node {    int data,rev,sum;    node *son[2],*pre;    bool judge();    bool isroot();    void pushdown();    void update();    void setson(node *child,int lr);}lct[233];int top,a,b;node *getnew(int x){    node *now=lct+ ++top;    now->data=x;    now->pre=now->son[1]=now->son[0]=lct;    now->sum=0;    now->rev=0;    return now;}bool node::judge(){return pre->son[1]==this;}bool node::isroot(){    if(pre==lct)return true;    return !(pre->son[1]=this|pree|->son[0]==this);}void node::pushdown(){    if(this==lct|！rev)return;    swap(son[0],son[1]);    son[0]->rev^=1;    son[1]->rev^=1;    rev=0;}void node::update(){sum=son[1]->sum+son[0]->sum+data;}void node::setson(node *child,int lr){    this->pushdown();    child->pre=this;    son[lr]=child;    this->update();}void rotate(node *now){    node *father=now->pre,*grandfa=father->pre;    if(!father->isroot()) grandfa->pushdown();    father->pushdown();now->pushdown();    int lr=now->judge();    father->setson(now->son[lr^1],lr);    if(father->isroot()) now->pre=grandfa;    else grandfa->setson(now,father->judge());    now->setson(father,lr^1);    father->update();now->update();    if(grandfa!=lct) grandfa->update();}void splay(node *now){    if(now->isroot())return;    for(;!=lct) grandfa->update();}void splay(node *now){    if(now->isroot())return;    for(;!now->isroot();rotate(now))    if(!now->pre->isroot())    now->judge()==now->pre->judge()?rotate(now->pre):rotate(now);}node *access(node *now){    node *last=lct;    for(;now!=lct;last=now,now=now->pre)    {        splay(now);        now->setson(last,1);    }    return last;}void changeroot(node *now){    access(now)->rev^=1;    splay(now);}void connect(node *x,node *y){    changeroot(x);    x->pre=y;    access(x);}void cut(node *x,node *y){    changeroot(x);    access(y);    splay(x);    x->pushdown();    x->son[1]=y->pre=lct;    x->update();}int query(node *x,node *y){    changeroot(x);    node *now=access(y);    return now->sum;}int main(){    scanf("%d%d",&a,&b);    node *A=getnew(a);    node *B=getnew(b);    //连边 Link        connect(A,B);    //断边 Cut        cut(A,B);    ///连边orz Link again        connect(A,B);    printf("%d\n",query(A,B));     return 0;}

作者: SW_Wind 更新时间: 2017-03-13 15:21 报告似乎没有人使用Splay，因为加法满足了交换律，所以我们可以翻转序列，所需的总和不变序列反转自然会想到Splay代码发送///资瓷区间加、区间翻转、区间求和的Splay#include <bits/stdc++.h>#define ll long long#define N 100000using namespace std;int sz[N], rev[N], tag[N], sum[N], ch[N][2], fa[N], val[N];int n, m, rt, x;void push_up(int x){    sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;    sum[x] = sum[ch[x][1]] + sum[ch[x][0]] + val[x];}void push_down(int x){    if(rev[x]){        swap(ch[x][0], ch[x][1]);        if(ch[x][1]) rev[ch[x][1]] ^= 1;        if(ch[x][0]) rev[ch[x][0]] ^= 1;        rev[x] = 0;    }    if(tag[x]){        if(ch[x][1]) tag[ch[x][1]] += tag[x], sum[ch[x][1]] += tag[x];        if(ch[x][0]) tag[ch[x][0]] += tag[x], sum[ch[x][0]] += tag[x];        tag[x] = 0;    }}void rotate(int x, int &k){    int y = fa[x], z = fa[fa[x]];    int kind = ch[y][1] == x;    if(y == k) k = x;    else ch[z][ch[z][1]==y] = x;    fa[x] = z; fa[y] = x; fa[ch[x][!kind]] = y;    ch[y][kind] = ch[x][!kind]] = y;    ch[y][kind] = ch[x][!kind]; ch[x][!kind] = y;    push_up(y); push_up(x);}void splay(int x, int &k){    while(x != k){        int y = fa[x], z = fa[fa[x]];        if(y != k) if(ch[y][1] == x ^ ch[z][1] == y) rotate(x, k);        else rotate(y, k);        rotate(x, k);    }}int kth(int x, int k){    push_down(x);    int r = sz[ch[x][0]]+1;    if(k == r) return x;    if(k < r) return kth(ch[x][0], k);    else return kth(ch[x][1], k-r);}void split(int l, int r){    int x = kth(rt, l), y = kth(rt, r+2);    splay(x, rt); splay(y, ch[rt][1]);}void rever(int l, int r){    split(l, r);    rev[ch[ch[rt][1][0]] ^= 1;}void add(int l, int r, int v){    split(l, r);    tag[ch[ch[rt][1][0]] += v;    val[ch[ch[rt][1][0]] += v;    push_up(ch[ch[rt][1][0]);}int build(int l, int r, int f){    if(l > r) return 0;    if(l == r){        fa[l] = f;        sz[l] = 1;        return l;    }    int mid = l + r >> 1;    ch[mid][0] = build(l, mid-1, mid);    ch[mid][1] = build(mid+1, r, mid);    fa[mid] = f;    push_up(mid);    return mid;}int asksum(int l, int r){    split(l, r);    return sum[ch[ch[rt][1][0]];}int main(){    //总共两个数    n = 2;    rt = build(1, n+2, 0);//建树    for(int i = 1; i <= n; i++){        scanf("%d", &x);        add(i, i, x);//区间加    }    rever(1, n);///区间翻转    printf("%d\n", asksum(1, n));///区间求和    return 0;}

作者: 爱国主义黑客 更新时间: 2017-03-09 19:39 用ios举报::tync_with_stdio感觉快多了#include<iostream>using namespace std;int main(){    ios::sync_with_stdio(false);    int a,b;    cin>>a>>b;    cout<<a+b;    return 0;}

作者: 周何 更新时间: 2017-03-01 22:32 看到大神们用的各种强大算法，魔芋我深深感受到自己的渺小，看到很多大佬选择最短路算法，我也试着写一些Bellman-Ford、SPFA、Dijkstra、Floyd等算法。这里只给出Floyd的解决方案，剩下的三个都在楼下。我不会献丑(其实我担心问题会被驳回)#include <cstdio>const int N=5,oo=1023741823;int f[N][N];inline int mn(int a,int b){    return a<b?a:b;}void floyd() {/floyd模板    for (int k=1; k<=N; k++)         for (int i=1; i<=N; i++) if (i==k) continue;        else for (int j=1; j<=N; j++) if (k==j||i==j) continue;        else f[i][j]=mn(f[i][j],f[i][k]+f[k][j]);}int main(){    int a,b;    for (int i=1;i<=N;i++)        for (int j=1;j<=N;j++)            f[i][j]=oo;    scanf ("%d %d",&a,&b);    f[1][2]=a;    f[2][3]=b;//构图，1->2的最短路径是a，2->3的最短路径是b，所以1->最短路的3是a+b    floyd();    printf ("%d",f[1][3]);//输出    return 0;}

作者: Num233 更新时间: 2017-02-21 21:28 举报A+B Problem下有很多神。我真的不知道几乎一半的算法。。。因此，我用两分来解决这个问题。看到没有大神不屑于用这个算法来解决这个问题，从数据范围的两分范围到找到答案。#include<cstdio>using namespace std;int a,b,c; int main(){long long l=-int(1e9)<<1,r=int(1e9)<<1;//左边界和右边界     scanf("%d%d",&a,&b);     while(r-l>1){c=(l+r)>>1;///二分步骤         if(c-b<a)l=c;         else if(c-b>a)r=c;             else return printf("%d\n",c),0;     }if(l!=r)return printf("%d\n",r),0; }

作者: KingLolierl 更新时间: 2017-02-10 10:25 报道看到牛题解那么多，鄙人不才，只好写一个树状数组膜拜大神，神本不喷~#include<iostream>#include<cstring>using namespace std;int lowbit(int a){    return a&(-a);}int main(){    int n=2,m=1;    int ans[m+1];    int a[n+1],c[n+1],s[n+1];    int o=0;    memset(c,0,sizeof(c));    s[0]=0;    for(int i=1;i<=n;i++)    {        cin>>a[i];        s[i]=s[i-1]+a[i];        c[i]=s[i]-s[i-lowbit(i)];////树状数组创建前缀和优化    }    for(int i=1;i<=m;i++)    {        int q=2;        //if(q==1)        //{(未更改操作)        //    int x,y;        //    cin>>x>>y;        //    int j=x;        //    while(j<=n)        //    {        //        c[j]+=y;        //        j+=lowbit(j);        //    }        //}        //else        {            int x=1,y=2;/////+a[2]的和            int s1=0，s2=0，p=x-1;            while(p>0)            {                s1+=c[p];                p-=lowbit(p);///树形数组求和操作，用两个前缀和相减得到区间和            }            p=y;            while(p>0)            {                s2+=c[p];                p-=lowbit(p);            }                o++;            ans[o]=s2-s1;//存储答案        }    }    for(int i=1;i<=o;i++)        cout<<ans[i]<<endl;//输出    return 0;}

作者: frankchenfu 更新时间: 2017-01-24 22:18 举报作为A+B Problem第N条题解，采用输入输出优化的方式。getchar和putchar原本是字符的输入和输出，但由于速度快，更常用于输入输出优化。以下代码针对非负整数。int s(){    char ch=getchar();    int x=ch-'0';    for(;(ch=getchar())>='0'&&ch<='9';)         x=x*10+ch-'0';    return x;}bool w(int r){    if(r>9)        w(r/10);    putchar(r%10+'0');    return 1;}针对这个问题有负数，我做了一些修改。以下是代码，啊！#include<cstdio>#define reg registerinline int s(){    reg char ch=getchar();    reg int re=0;    reg bool fl=1;    if(ch=='-')    {        fl=0;        ch=getchar();    }    while(ch>='0'&&ch<='9')    {        re=re*10+ch-'0';        ch=getchar();    }    return fl?re:-re;}inline bool w(reg int r){    if(r>9)        w(r/10);    putchar(r%10+'0');    return 1;}int main(){    reg int a=s(),b=s();    if(a+b>=0)        return !w(a+b);    putchar('-');    return !w(a+b);    putchar('-');    return !w(-a-b);}祝大家编程愉快！天天开心！

作者: jacky_chen 更新时间: 2017-01-23 23:30 报告二进制下的a+b。如有重复，请忽略，如果没有，删了这句话#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<algorithm>using namespace std;int main(){    int a,b,s=0,s1=0,i=0,na=0,nb=0;    cin>>a>>b;    if(a<=0) na=1,a*=-1;    while(a!=0)    {        if(a%2!=0)    {        if(a%2!=0)        s+=pow(2,a%2*i);        a/=2;        i++;    }    i=0;    if(na==1) s*=-1;    if(b<=0) nb=1,b*=-1;    while(b!=0)    {        if(b%2!=0)        s1+=pow(2,b%2*i);        b/=2;        i++;    }    if(nb==1) s1*=-1;    cout<<s+s1;;    return 0;}

作者: 我只会说一种语言 更新时间: 2017-01-04 13:03 我是一个喜欢新方法的人。在这里，我想到了等差数列，然后我们可以使用以下新方法。#include<iostream>using namespace std;int s1、s2、s3、s4;int n,m;int main(){    cin>>n>>m;    s1=(1+n)*n/2;    算出1+2+3+...+n;    s2=(1+n-1)*(n-1)/2;  算出1+2+3+...+（n-1）;    s3=(1+m)*m/2;    算出1+2+3+...+m；    s4=(1+m-1)*(m-1)/2;   算出1+2+3+...+（m-1）；    cout<<(s1-s2)+(s3-s4);   输出就够了。    return 0;}你的新方法是什么？    return 0;}你的新方法是什么？想到新方法，你可以解决这些问题！

作者: doby 更新时间: 2016-12-24 17:16 这是洛谷的经典报道...这里有一些基本的A+B方法SPFA：#include<cstdio>using namespace std;int n,m,a,b,op,head[200009],next[200009],dis[200009],len[200009],v[200009],l,r,team[200009],pd[100009],u,v1,e;int lt(int x,int y,int z){    op++,v[op]=y;    next[op]=head[x],head[x]=op,len[op]=z;}int SPFA(int s,int f)//SPFA……{    for(int i=1;i<=200009;i++){dis[i]=999999999;}    l=0,r=1,team[1]=s,pd[s]=1,dis[s]=0;    while(l!=r)    {        l=(l+1)%90000,u=team[l],pd[u]=0,e=head[u];        while(e!=0)        {            v1=v[e];            if(dis[v1]>dis[u]+len[e])            {                dis[v1]=dis[u]+len[e];                if(!pd[v1])                {                    r=(r+1)%90000,                    team[r]=v1,                    pd[v1]=1;                }            }            e=next[e];        }     }    return dis[f];}int main(){    scanf("%d%d",&a,&b);    lt(1,2,a);lt(2,3,b);/1到2是a，2到3是b，1到3是a+b……    printf("%d",SPFA(1,3));    return 0;}Floyd：#include<iostream>#include<cstring>using namespace std;long long n=3,a,b,dis[4][4];int main(){    cin>>a>>b;    for(int i=1;i<=n;i++)    {        for(int j=1;j<=n;j++)        {            dis[i][j]=2147483647;        }    }    dis[1][2]=a,dis[2][3]=b;    for(int k=1;k<=n;k++)    {        for(int i=1;i<=n;i++)        {            for(int j=1;j<=n;j++)            {                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);//Floyd……            }        }    }    cout<<dis[1][3];}递归：#include<iostream>using namespace std;long long a,b,c;long long dg(long long a){    if(a<=5){return a;}//防超时....    return (dg(a/2)+dg(a-a/2));}int main(){    cin>>a>>b;    c=dg(a)+dg(b);    cout<<c;}高精：#include<iostream>#include<cstring>using namespace std;int main(){    char a1[1000],b1[1000];      int a[1000]={0}，b[1000]={0}，c[1000]={0}，la,lb,lc,i,x;      cin>>a1>>b1;      la=strlen(a1);      lb=strlen(b1);      for(i=0;i<=la-1;i++){a[la-i]=a1[i]-48;}    for(i=0;i<=lb-1;i++){b[lb-i]=b1[i]-48;}      lc=1,x=0;    while(lc<=la||lc<=lb){c[lc]=a[lc]+b[lc]+x,x=c[lc]/10,c[lc]%=10,lc++;}    c[lc]=x;    if(c[lc]==0){lc--;}    for(i=lc;i>=1;i--){cout<<c[i];}    cout<<endl;    return 0;}压位高精：#include <cstdio>  #include <cstring>  #include <cstdlib>  #include <iostream>  #define p 8#define carry 100000000using namespace std;  const int Maxn=50001;  char s1[Maxn],s2[Maxn];  int a[Maxn],b[Maxn],ans[Maxn];  int change(char s[],int n[])   {      char temp[Maxn];       int len=strlen(s+1),cur=0;      while(len/p)    {          strncpy(temp,s+len-p+1,p);        n[++cur]=atoi(temp);         len-=p;    }      if(len)    {        memset(temp,0,sizeof(temp));          strncpy(temp,s+1,len);          n[++cur]=atoi(temp);       }      return cur;}  int add(int a[],int b[],int c[],int l1,int l2)  {      int x=0,l3=max(l1,l2);      for(int i=1;i<=l3;i++)    {          c[i]=a[i]+b[i]+x;          x=c[i]/carry;        c[i]%=carry;      }      while(x>0){c[++l3]=x%10;x/=10;}      return l3;}  void print(int a[],int len)  {       printf("%d",a[len]);    for(int i=len-1;i>=1;i--)printf("%0*d",p,a[i]);    printf("\n");  }  int main()  {    scanf("%s%s",s1+1,s2+1);    int la=change(s1,a);    int lb=change(s2,b);    int len=add(a,b,ans,la,lb);        print(ans,len);}

作者: XY星系质量PK 更新时间: 2016-12-18 20:06 举报P1001题解中有很多大神，用了很多很棒的算法！！！我不称职，只能在这里写一个使用math库的sumsandsquares函数的程序。。。uses math;var a:array[0..3] of float;    i,p:longint;    c,b:float;    s:ansistring;begin  for i:=1 to 2 do read(a[i]);  sumsandsquares(a,b,c);  p:=trunc(b);  str(p,s);  for i:=1 to length(s) do write(s[i]);  writeln; end.

作者: little_gift 更新时间: 2016-12-10 12:49 举报P1001题解大神多啊- -然而，我写了一个高精度的模板include <bits/stdc++.h>using namespace std;class cint{ //定义private:int c_number[100001],c_len,c_d,c_fh; //属性，包括数字、长度、进制，符号public:        cint();         ~cint();        cint(int x);         cint(string st); //结构和分析函数        cint operator+(cint& b); //重载+，用于更方便的操作        cint read_cint(); //读入        void write_cint(); //输出};cint::cint(){    c_d=10;}cint::~cint(){}cint::cint(int x){    c_d=10;    if (x<0)    {        c_fh=-1;        x=-x;    }    else c_fh=1;    c_len=0;    while (x)    {        c_len++;        c_number[c_len]=x%c_d;        x/=c_d;    }}cint::cint (string st){    int i;    if (st[0]=='''')     {        c_fh=-1;        st.erase(0,1);    }    else c_fh=1;    while (st[0]="0"="0"&&st.length()>1)        st.erase(0,1); //去除前导0    c_len=st.length();    for (i=1;i<=c_len;i++)        c_number[i]=(st[c_len-i]-48)*c_fh; ///将字符的ascii码-48存储在数组中} //构造函数，cintt将字符串存入类中 cint::operator+(cint& b){    int i;    cint c;    if (c_len>=b.c_len) c.c_len=c_len;    else c.c_len=b.c_len;    for (i=1;i<=c.c_len;i++)    {        c.c_number[i]+=c_number[i]+b.c_number[i]; //将两位相加        c.c_number[i+1]=c.c_number[i]/c.c_d;        c.c_number[i]%=c.c_d; //处理进位    }    while (c.c_number[c.c_len+1])        c.c_len++;    return c;} //核心部分，高精度加cint cint::read_cint(){    string st;    cin>>st;    return cint(st);}void cint::write_cint(){    int i;    for (i=1;i<=c_len;i++)        cout<<c_number[c_len-i+1]; //输出部分，很容易理解}很容易理解}istream& operator>>(istream& is,cint &c){    c=c.read_cint();    return is;} //重载>>,输入ostreamm方便& operator<<(ostream& os,cint c){    c.write_cint();    return os;} //重载<<,输出方便。以下是美丽的主程序int main(){    cint a,b;    cin>>a>>b;    cout<<a+b<<endl;}

作者: NoNoSSoft 更新时间: 2016-11-20 21:38 报告采用fread和fwrite输入输出优化，速度相当快#include <cstdio>const size_t fSize = 1 << 15;char iFile[fSize], *iP = iFile, oFile[fSize], *oP = oFile;inline char readchar() {    if (*iP && iP - iFile < fSize) { char t = *iP; iP++; return t; } else return EOF;}template<typename T> inline void readint(T &x) {    x = 0; char c; bool neg = 0;    while ((c = readchar()) < '0' || c > '9') if (c == '-') neg = !neg;    while (c >= '0' && c <= '9')        x = x * 10 + (c ^ 48), c = readchar();    x = neg ? -x : x;}inline void writechar(const char &c) { *oP = c, ++oP; }template<typename T> inline void _writeint(const T &x) {    if (!x)        return;    _writeint(x / 10);    writechar(x % 10 ^ 48);}template<typename T> inline void writeint(T x, const char &c) {    if (x < 0) {        writechar('-');        x = -x;    }    if (!x) {        writechar('0');        return;    }    _writeint(x);    writechar(c);}int main() {    fread(iFile, 1, fSize, stdin);    int a, b;    readint(a); readint(b);    writeint(a + b, '\n');    fwrite(oFile, 1, oP - oFile, stdout);    return 0;}

作者: hycuihz 更新时间: 2016-11-19 11:19 举报看到大家都写了一大串奇怪的代码(让pascal猿表示一脸蒙逼)，于是我决定写最简单的代码vara，b:longint;begin  assign(input,'P1001.in');  //NOIP/NOI必备 否则CENA不承认  reset(input); //NOIP/NOI必备 否则CENA不承认  readln(a,b);  //输入  close(input); //NOIP/NOI必备 否则CENA不承认  assign(output,'P1001.in'); //NOIP/NOI必备 否则CENA不承认  rewrite(output); //NOIP/NOI必备 否则CENA不承认  writeln(a+b);  //输出  close(output); //NOIP/NOI必备 否则CENA不承认end.  //结束了，当然，本代码运行会RE(因为没有告诉我们输入输出文件的名称)，所以我们可以删除输入输出文件233vara，b:longint;begin  readln(a,b);  //输入  writeln(a+b);  ///输出end.  ///结束了，一个非常简单的源码。

作者: zhjian 更新时间: 2016-11-15 21:23 报告看楼下也有运算，用递归做的，我就贴个非递归吧。。。#include <cstdio>int m, n;int main(){    scanf("%d%d", &m, &n);    int u = m & n;    int v = m ^ n;    while (u) {        int s = v;        int t = u << 1;        u = s & t;        v = s ^ t;    }    printf("%d\n", v);}

作者: Zyan丶 更新时间: 2016-11-10 20:46 举报大神都用网络流啊 最短路啊解决这个问题，那么既然是可以求最短路的，为什么不能从树上跑呢？怀着这个想法，我努力思考(划掉)，发现###我可以用LCA做这个问题~但是我没有天赋，也不会做任何Tarjan和ST手表，只会用一倍来求LCA，所以我有权利抛砖引玉。但是我估计应该没什么想学LCA的。来这个问题看看LCA题解。所以大部分都是写着玩~~先说想法(这还是用说的？）：建一棵有三个节点的树，1是树根，2 三分别是左右儿子。其中1 2之间的距离是a，2 3之间的距离是b，然后要求1 LCA与LCA的距离，加起来就是1->3的最短路其实是题目中要求的a+b。好吧，闲话不说。 上代码(大部分是LCA板)：#include<cstdio>                                                  //头文件#define NI 2                                                          ///我从来不喜欢算logo，所以一般用常数 不知道是不是坏习惯 因为3个节点 所以log3(当然以2为底)得到了2struct edge{    int to,next,data;                                              //分别表示边缘的终点，下一条边的编号和边的权值}e[30];                                                                     //邻接表，点少边少开30是为了浪，int v[10],d[10],lca[10][NI+1],f[10][NI+1],tot=0;      ///数组开到10仍然是为了波//数组解释，v表示第一边在邻接表中的编号，d是深度，lca[x][i]表示x向上跳2^i的节点，f[x][i]x向上跳2^i和void之间的距离 build(int x,int y,int z)                                      //建边{    e[++tot].to=y; e[tot].data=z; e[tot].next=v[x]; v[x]=tot;    e[++tot].to=x; e[tot].data=z; e[tot].next=v[y]; v[y]=tot;}void dfs(int x)                                                        ///递归建树{    for(int i=1;i<=NI;i++)                                   //懒，所以常数懒得优化        f[x][i]=f[x][i-1]+f[lca[x][i-1]][i-1],        lca[x][i]=lca[lca[x][i-1]][i-1];                   ////同时预处理成果    for(int i=v[x];i;i=e[i].next)                              ///遍历每个连接点    {        int y=e[i].to;        if(lca[x][0]==y) continue;        lca[y][0]=x;                                       //小技巧：lca[x][0]是x的父亲~~(跳2^0=1不是父节点)        f[y][0]=e[i].data;        d[y]=d[x]+1;        dfs(y);                                            ///以这个节点为根建子树[这里真的有用吗？？】    }}int ask(int x,int y)                                             //询问，也是关键{                                                                            if(d[x]<d[y]) {int t=x;x=y;y=t;}                  //把x变成深点    int k=d[x]-d[y],ans=0;    for(int i=0;i<=NI;i++)        if(k&(1<<i))                                      //如果你能跳，跳x            ans+=f[x][i],                              ///更新信息            x=lca[x][i];    for(int i=NI;i>=0;i--)                                  //不知道能不能正在循环，好像倒着优，反正记得倒着就好        if(lca[x][i]!=lca[y][i])                            //如果x跳2^i和y跳2^j没有跳到一起，让他们跳            ans+=f[x][i]+f[y][i],            x=lca[x][i],y=lca[y][i];    return ans+f[x][0]+f[y][0];                           ///跳到LCA(每步跳跃时更新信息，跳跃前更新信息~)}int main(){    int a,b;    scanf("%d%d",&a,&b);    build(1,2,a);    build(1,3,b);                                                       //分别建1 2、1 3之间的边    dfs(1);                                                                ///以1为根建树    printf("%d",ask(2,3));                                         //求解2 3到LCA的距离和输出}BINGO~~

作者: Linbom 更新时间: 2016-10-31 10:06 报告明显的字典树建立每个数字的字典树一次查询spj正负 下面上代码#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>using namespace std;struct node{    int str[26];    int sum;}s[1000];char str1[100];int t=0,tot=0,ss=0;bool f1;void built(){    t=0;    for(int i=0;i<strlen(str1);i++)    {         if(str1[i]=='-'){             f1=true;continue;         }         if(!s[t].str[str1[i]-'0'])         s[t].str[str1[i]-'0']=++tot;         t=s[t].str[str1[i]-'0'];         s[t].sum=str1[i]-'0';    }}int query(){   int t=0;int s1=0;   for(int i=0;i<strlen(str1);i++)   {           if(str1[i]=='-') continue;           if(!s[t].str[str1[i]-'0']) return s1;           t=s[t].str[str1[i]-'0'];           s1=s1*10+s[t].sum;   }   return s1;}int main(){      for(int i=1;i<=2;i++)  {      f1=false;      scanf("%s",str1);    built();    if(f1)      ss-=query();      else ss+=query();  }  printf("%d",ss);  return 0;    }

作者: chenleyu 更新时间: 2016-10-28 16:37 举报一个很棒的模拟题，可以模拟人工操作的方法。#include <iostream> #include <cmath>using namespace std;int fu=1,f=1,a,b,c=0;int main(){    cin>>a>>b;    if(a<0&&b>0)fu=2;    if(a>0&&b<0)fu=3;    if(a<0&&b<0)f=-1;    if(a==0){cout<<b;return 0;}    if(b==0){cout<<a;return 0;}     a=abs(a);    b=abs(b);    if(a>b&&fu==3)f=1;    if(b>a&&fu==3)f=-1;    if(b>a&&fu==2)f=1;    if(b<a&&fu==2)f=-1;    if(fu==1)c=a+b;    if(fu>1)c=max(a,b)-min(a,b);    c*=f;    cout<<c;    return 0;}

作者: dph754132771 更新时间: 2016-10-28 09:08 举报/*P: 1001Au: Small_Ash说我加了一点读入和输出优化。。。。为什么要占坑？主要是发送读入输出优化代码，顺便教新生C++超快读入输出方法。。。一般来说，c++读入的方式有三种 scanf cin 以及读入优化。。。cin 在添加ios优化之前，它非常慢 其次是scanf 读入优化（read）以下是我做的测试数据，当读到从1开始到10^7的数列数据时：cin耗时6.02s，scanf耗时2.23s，同理，read只需要0.58s的时间 cont>scanf>输出优化可用于处理大数据问题（前提是数据输入输出是纯数据，没有符号[包括英文字母]）新生可以直接背诵，而无需了解实现原则。可以使用这些优化NOIP。以下是代码*///#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;int read(){    int out=0,fh=1;    char cc=getchar();    if (cc=='-') fh=-1;    while (cc>||cc<'0') cc=getchar();    while (cc>='0'&&cc<='9') {out=out*10+cc-'0';cc=getchar();}    return out*fh;}void write(int x)  {      if (x==0){        putchar('0');        return;    }    int num = 0; char c[15];    while(x) c[++num] = (x%10)+48, x /= 10;    while(num) putchar(c[num--]);    putchar(' '); }int main(){    write(read()+read());    return 0;}

作者: ghj1222 更新时间: 2016-10-27 23:01 cpp版的报告位运算，注释已经添加。我认为计算机在执行时也是如此。大意是按十进制垂直加法计算二进制。先计算不进位值(通过xor)，再计算进位(通过and)，然后递归调用，两者加起来就行了#include <iostream>using namespace std;int plus(int a,int b)///这是加法运算函数{    if(b==0)///如果b(进位)是0(没有进位)，返回a的值        return a;    else    {        int xor,carry;        xor=a^b;//xor是a和b不进位加法的值        carry=(a&b)<<1;//carry是a和b的进位值(只有两者都是1，所以是和操作。左移一位是因为二进制加法和十进制加法垂直进位要加在左边一位。        return plus(xor,carry);///不进位加法和进位值的和是结果    }}int main(){    int a,b;    cin >> a >> b;    cout << plus(a,b) << endl;    return 0;}正解#include <iostream>using namespace std;int main(){    int a,b;    cin >> a >> b;    cout << a+b << endl;    return 0;}最短代码#include <cstdio>int main(int a,int b){    return (scanf("%d%d",&a,&b),printf("%d\n",a+b))&0;}

作者: yzz2016 更新时间: 2016-10-14 21:40 举报//c++ 快速读入版a+b，自行体会#include <cstdio>int read(){    int f=1,x=0;char ch=getchar();    while(ch<"0"||ch>'9') {if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}    return f*x;}int main(){    printf("%d",read()+read());    return 0;}

5ms , 1371kb线段树附在下65行线段树代码上#include<cstdio>#include<algorithm>#include<cstdlib>#include<cmath>#include<cstring>#include<iostream>using namespace std;struct node{    int val,l,r;};node t[5];int a[5],f[5];int n,m;void init(){    for(int i=1;i<=2;i++){        scanf("%d",&a[i]);    }}void build(int l,int r,int node){//这是一棵树    t[node].l=l;t[node].r=r;t[node].val=0;    if(l==r){        f[l]=node;        t[node].val=a[l];        return;    }    int mid=(l+r)>>1;    build(l,mid,node*2);    build(mid+1,r,node*2+1);    t[node].val=t[node*2].val+t[node*2+1].val;}void update(int node){    if(node==1)return;    int fa=node>>1;    t[fa].val=t[fa*2].val+t[fa*2+1].val;    update(fa);}int find(int l,int r,int node){    if(t[node].l==l&&t[node].r==r){        return t[node].val;    }    int sum=0;    int lc=node*2;int rc=lc+1;    if(t[lc].r>=l){        if(t[lc].r>=r){            sum+=find(l,r,lc);        }        else{            sum+=find(l,t[lc].r,lc);        }    }    if(t[rc].l<=r){        if(t[rc].l<=l){            sum+=find(l,r,rc);        }        else{            sum+=find(t[rc].l,r,rc);        }    }    return sum;}int main(){    init();    build(1,2,1);    printf("%d",find(1,2,1));}

Dijkstra+优化STL优先队列。48ms.#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <cctype>#include <climits>#include <algorithm>#include <map>#include <queue>#include <vector>#include <ctime>#include <string>#include <cstring>using namespace std;const int N=405;struct Edge {    int v,w;};vector<Edge> edge[N*N];int n;int dis[N*N];bool vis[N*N];struct cmp {    bool operator()(int a,int b) {        return dis[a]>dis[b];    }};int Dijkstra(int start,int end){    priority_queue<int,vector<int>,cmp> dijQue;    memset(dis,-1,sizeof(dis));    memset(vis,0,sizeof(vis));    dijQue.push(start);    dis[start]=0;    while(!dijQue.empty()) {        int u=dijQue.top();        dijQue.pop();        vis[u]=0;        if(u==end)            break;        for(int i=0; i<edge[u].size(); i++) {            int v=edge[u][i].v;            if(dis[v]==-1 || dis[v]>dis[u]+edge[u][i].w) {                dis[v]=dis[u]+edge[u][i].w;                if(!vis[v]) {                    vis[v]=true;                    dijQue.push(v);                }            }        }    }    return dis[end];}int main(){    int a,b;    scanf("%d%d",&a,&b);    Edge Qpush;    Qpush.v=1;    Qpush.w=a;    edge[0].push_back(Qpush);    Qpush.v=2;    Qpush.w=b;    edge[1].push_back(Qpush);    printf("%d",Dijkstra(0,2));    return 0;}

作者: Acheing 更新时间: 2016-08-01 12:41 最好举报最小生成树。#include <cstdio>#include <algorithm>#define INF 2140000000using namespace std;struct tree{int x,y,t;}a[10];bool cmp(const tree&a,const tree&b){return a.t<b.t;}int f[11],i,j,k,n,m,x,y,t,ans;int root(int x){if (f[x]==x) return x;f[x]=root(f[x]);return f[x];}int main(){    for (i=1;i<=10;i++) f[i]=i;    for (i=1;i<=2;i++){        scanf("%d",&a[i].t);        a[i].x=i+1;a[i].y=1;k++;    }    a[++k].x=1;a[k].y=3,a[k].t=INF;    sort(a+1,a+1+k,cmp);    for (i=1;i<=k;i++){    //    printf("%d %d %d %d\n",k,a[i].x,a[i].y,a[i].t);        x=root(a[i].x);y=root(a[i].y);        if (x!=y) f[x]=y,ans+=a[i].t;     }    printf("%d\n",ans);}

作者: xxhxhwsq 更新时间: 2016-07-25 18:22 举报楼下说的不对vara，b:longint;beginreadln(a,b);writeln(a+b);end.不是唯一的问题解决方案 不要胡说八道，附上位运算版：var  a,b,ans:longint;procedure plus(e,f:longint);var  x1,x2:longint;begin  x1:=e xor f; x2:=(e and f) shl 1;  if e=0 then begin ans:=f; exit; end;  If f=0 then begin ans:=e; exit; end;  plus(x1,x2);end;begin  readln(a,b);  ans:=0;  plus(a,b);  writeln(ans);end.因为水平不高，如果有错误，请指正！

看完之后，我的表情是这样的...