想知道各位大佬还有什么奇怪的解题方式

P1001 A+B Problem

zhengpie @ 2023-12-20 22:21:11

该题看似简单,实则却很险恶 请求各位大佬有没有什么奇怪的方法解题,本人想收集一波~~~

by zengyukai2012 @ 2024-01-04 21:35:16

这个

by zyh071 @ 2024-01-13 09:52:40

#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,n;
  cin>>a>>n;
  for(int i=1;i<=n;i++){
    a++;
  cout<<a;
  return 0;
}

by LIGASIA @ 2024-01-15 13:26:29

树套树能做 （但本蒟蒻实在不想再打一遍替罪羊套树桩数组了)

by _anll_ @ 2024-01-15 13:33:05

一眼就看出是很板的分块阿

#include<iostream>
#include<cmath>
#define int long long
using namespace std;
struct Pie{
    int l,r,sum;
}pie[10];
int n=2,bl,ans,num[10],pos[10];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    for(int i=1;i<=n;i++) cin>>num[i];
    bl=sqrt(n);
    for(int i=1;i<=bl;i++){
        pie[i].l=pie[i-1].r+1;
        pie[i].r=i*bl;
    }
    if(bl*bl!=n) bl+=1,pie[bl].l=pie[bl-1].r+1,pie[bl].r=n;
    for(int i=1;i<=bl;i++)
        for(int j=pie[i].l;j<=pie[i].r;j++)
            pos[j]=i,pie[i].sum+=num[j];
    int l=1,r=2;
    if(pos[l]==pos[r])
        for(int i=l;i<=r;i++) ans+=num[i];
    else{
        for(int i=l;i<=pie[pos[l]].r;i++) ans+=num[i];
        for(int i=pie[pos[r]].l;i<=r;i++) ans+=num[i];
        for(int i=pos[l]+1;i<=pos[r]-1;i++)
            ans+=pie[i].sum;
    }
    cout<<ans<<endl;
    return 0;
}

by Igallta @ 2024-01-19 15:50:01

没有 lazy 的线段树不得来一发？

#include<bits/stdc++.h>
#define LL k<<1
#define RR k<<1|1
#define int long long
using namespace std;
int a[10];
struct Node{
    int l,r,v,sum;
}t[10001];
void pushup(int k){
    t[k].sum=t[LL].sum+t[RR].sum;
}
void build(int k,int l,int r){
    t[k].l=l;
    t[k].r=r;
    if(l==r){
        t[k].sum=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(LL,l,mid);
    build(RR,mid+1,r);
    pushup(k);
}
int ask(int k,int l,int r){
    int ans=0;
    if(t[k].l>=l && t[k].r<=r){
        return t[k].sum;
    }
    int mid=t[k].l+t[k].r>>1;
    if(l<=mid){ans+=ask(LL,l,r);}
    if(r>mid){ans+=ask(RR,l,r);}
    return ans; 
}
signed main(){
    cin>>a[1]>>a[2];
    build(1,1,2);
    cout<<ask(1,1,2);
    return 0;
}

by hayoon @ 2024-01-20 16:19:09

@zhengpie 没人二分答案吗

by IJN_Shokaku @ 2024-01-20 18:00:28

线段树```cpp

include<bits/stdc++.h>

define int long long

using namespace std;

define N 100010

const int L=0,R=1; int v[3]; struct xds{ int son[2]; int sum;//区间和 int addtag;//区间加标记 }a[N*2];int cnt; void build(int &k,int l,int r){//建立线段树 k=++cnt; if(l==r){ a[k].sum=v[l];//初始化信息 }else{ int mid=(l+r)>>1; build(a[k].son[L],l,mid);//递归建立左儿子 build(a[k].son[R],mid+1,r);//递归建立右儿子 a[k].sum=a[a[k].son[L]].sum+a[a[k].son[R]].sum;//合并左右儿子信息 } }

void addtag(int k,int l,int r,int val){//节点k上做区间加 a[k].sum+=(r-l+1)*val; a[k].addtag+=val; }

void modify(int k,int l,int r,int ql,int qr,int val){//区间修改操作，比如区间加 if(ql==l&&r==qr){//全区间操作 addtag(k,l,r,val); }else{ int mid=(l+r)>>1; //下传并清空节点k的所有标记

    addtag(a[k].son[L],l,mid,a[k].addtag);
    addtag(a[k].son[R],mid+1,r,a[k].addtag);
    a[k].addtag=0;

    if(qr<=mid) modify(a[k].son[L],l,mid,ql,qr,val);
    else if(ql>mid) modify(a[k].son[R],mid+1,r,ql,qr,val);
    else modify(a[k].son[L],l,mid,ql,mid,val),modify(a[k].son[R],mid+1,r,mid+1,qr,val);
    a[k].sum=a[a[k].son[L]].sum+a[a[k].son[R]].sum;//下传后更新
}

}

int query(int k,int l,int r,int ql,int qr){//区间查询操作，比如问区间和 if(ql==l&&r==qr){//全区间查询 return a[k].sum; }else{ int mid=(l+r)>>1; //下传并清空节点k的所有标记 addtag(a[k].son[L],l,mid,a[k].addtag); addtag(a[k].son[R],mid+1,r,a[k].addtag); a[k].addtag=0;

    int ret = 0;
    if(qr<=mid) ret=query(a[k].son[L],l,mid,ql,qr);
    else if(ql>mid) ret=query(a[k].son[R],mid+1,r,ql,qr);
    else ret=query(a[k].son[L],l,mid,ql,mid)+query(a[k].son[R],mid+1,r,mid+1,qr);
    a[k].sum=a[a[k].son[L]].sum+a[a[k].son[R]].sum;//下传后更新
    return ret;
}

} int root; int n=2; signed main(){ cin>>v[1]>>v[2]; build(root,1,n); cout<<query(1,1,n,1,n); return 0; }

by IJN_Shokaku @ 2024-01-20 18:02:33

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define N 100010
const int L=0,R=1;
int v[3];
struct xds{
    int son[2];
    int sum;//区间和
    int addtag;//区间加标记
}a[N*2];int cnt;
void build(int &k,int l,int r){//建立线段树
    k=++cnt;
    if(l==r){
        a[k].sum=v[l];//初始化信息
    }else{
        int mid=(l+r)>>1;
        build(a[k].son[L],l,mid);//递归建立左儿子
        build(a[k].son[R],mid+1,r);//递归建立右儿子
        a[k].sum=a[a[k].son[L]].sum+a[a[k].son[R]].sum;//合并左右儿子信息
    }
}

void addtag(int k,int l,int r,int val){//节点k上做区间加
    a[k].sum+=(r-l+1)*val;
    a[k].addtag+=val;
}

void modify(int k,int l,int r,int ql,int qr,int val){//区间修改操作，比如区间加
    if(ql==l&&r==qr){//全区间操作
        addtag(k,l,r,val);
    }else{
        int mid=(l+r)>>1;
        //下传并清空节点k的所有标记

        addtag(a[k].son[L],l,mid,a[k].addtag);
        addtag(a[k].son[R],mid+1,r,a[k].addtag);
        a[k].addtag=0;

        if(qr<=mid) modify(a[k].son[L],l,mid,ql,qr,val);
        else if(ql>mid) modify(a[k].son[R],mid+1,r,ql,qr,val);
        else modify(a[k].son[L],l,mid,ql,mid,val),modify(a[k].son[R],mid+1,r,mid+1,qr,val);
        a[k].sum=a[a[k].son[L]].sum+a[a[k].son[R]].sum;//下传后更新
    }
}

int query(int k,int l,int r,int ql,int qr){//区间查询操作，比如问区间和
    if(ql==l&&r==qr){//全区间查询
        return a[k].sum;
    }else{
        int mid=(l+r)>>1;
        //下传并清空节点k的所有标记
        addtag(a[k].son[L],l,mid,a[k].addtag);
        addtag(a[k].son[R],mid+1,r,a[k].addtag);
        a[k].addtag=0;

        int ret = 0;
        if(qr<=mid) ret=query(a[k].son[L],l,mid,ql,qr);
        else if(ql>mid) ret=query(a[k].son[R],mid+1,r,ql,qr);
        else ret=query(a[k].son[L],l,mid,ql,mid)+query(a[k].son[R],mid+1,r,mid+1,qr);
        a[k].sum=a[a[k].son[L]].sum+a[a[k].son[R]].sum;//下传后更新
        return ret;
    }
}
int root;
int n=2;
signed main(){
    cin>>v[1]>>v[2];
    build(root,1,n);
    cout<<query(1,1,n,1,n);
    return 0;
}

by hwc2012 @ 2024-01-23 17:46:05

递归写法，不o2会MLE，o2会TLE

#include<iostream>
using namespace std;
int solve(int x,int y){
    if(y==0)return x;
    return solve(x++,y--);
}
int main()
{
    int a,b;
    cin >> a >> b;
    cout << solve(a,b);
}

by __O_v_O__ @ 2024-02-05 19:36:24

#include<bits/stdc++.h>
using namespace std;
struct no{
    int da,re,su;
    no*so[2],*pr;
    bool ju();
    bool ir();
    void pd();
    void up();
    void ss(no*ch,int lr);
}l[233];int to,a,b;
no*gn(int x){
    no*n=l+ ++to;
    n->da=x,n->pr=n->so[1]=n->so[0]=l,n->su=0,n->re=0;
    return n;
}
bool no::ju(){
    return pr->so[1]==this;
}
bool no::ir(){
    if(pr==l)return true;
    return!(pr->so[1]==this||pr->so[0]==this);
}
void no::pd(){
    if(this==l||!re)return;
    swap(so[0],so[1]),so[0]->re^=1,so[1]->re^=1,re=0;
}
void no::up(){
    su=so[1]->su+so[0]->su+da;
}
void no::ss(no*ch,int lr){
    this->pd(),ch->pr=this,so[lr]=ch,this->up();
}
void rtt(no*n){
    no*father=n->pr,*grandfa=father->pr;
    if(!father->ir())grandfa->pd();
    father->pd(),n->pd();
    int lr=n->ju();
    father->ss(n->so[lr^1],lr);
    if(father->ir())n->pr=grandfa;
    else grandfa->ss(n,father->ju());
    n->ss(father,lr^1),father->up(),n->up();
    if(grandfa!=l)grandfa->up();
}
void spl(no*n){
    if(!n->ir()){
        for(;!n->ir();rtt(n)){
            if(!n->pr->ir())n->ju()==n->pr->ju()?rtt(n->pr):rtt(n);
        }
    }
}
no*ac(no*n){
    no*la=l;
    for(;n!=l;la=n,n=n->pr)spl(n),n->ss(la,1);
    return la;
}
void chr(no*n){
    ac(n)->re^=1,spl(n);
}
void con(no*x,no*y){
    chr(x),x->pr=y,ac(x);
}
void cu(no*x,no*y){
    chr(x),ac(y),spl(x),x->pd(),x->so[1]=y->pr=l,x->up();
}
int q(no*x,no*y){
    chr(x);no*n=ac(y);
    return n->su;
}
int main(){
    cin>>a>>b;
    no*A=gn(a),*B=gn(b);
    con(A,B),cu(A,B),con(A,B);
    cout<<q(A,B);
    return 0;
}

Link Cut Tree

上一页 | 下一页