社区讨论

咱就是说题目很复杂吗

P1001A+B Problem参与者 5已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@lovi3cyo
此快照首次捕获于
2023/11/12 21:17
2 年前
此快照最后确认于
2023/11/12 21:26
2 年前
查看原帖
看下面的之前最好先看看这个
CPP
#include <bits/stdc++.h>
using namespace std;
long long int a, b;

int main () {
	scanf ("%d %d", &a, &b);
	printf ("%d", a + b);
	return 0;
} 
然后是这个
CPP
#include <bits/stdc++.h>
#define ___ int
#define $$$ main
#define _$_$_ return
#define _ cin
#define $ cout
#define __ using
#define $$ namespace
#define o_o std
__ $$ o_o;
___ $$$(){
    ___ _$o$_,$o_o$;
    _ >> _$o$_ >> $o_o$;
    $ << _$o$_ + $o_o$;
    _$_$_ 0;
}
异或是这个
CPP
#include<bits/stdc++.h>
#define MAXN 10010
#define MAXM 500010
#define MAX 2147483647
using namespace std;
int n, m, t, c = 1;
int head[MAXN], path[MAXN];
bool vis[MAXN];
struct node {
    int next, to, w;
}a[MAXM << 1];
inline int relax (int u, int v, int w) {
    if (path[v] > path[u] + w) {
        path[v] = path[u] + w;
        return 1;
    }
    return 0;
}
inline void add(int u, int v, int w) {
    a[c].to = v;
    a[c].w = w;
    a[c].next = head[u];
    head[u] = c++;
}
void spfa() {
    int u, v, num = 0;
    long long x = 0;
    list<int> q;
    for (int i = 1;i <= n; i++){path[i] = MAX; vis[i] = 0;}
    path[1] = 0;
    vis[1] = 1;
    q.push_back(1);
    num++;
    while (!q.empty()) {
        u = q.front();
        q.pop_front();
        num--; x -= path[u];
        while (num && path[u] > x / num){
            q.push_back(u);
            u = q.front();
            q.pop_front();
        }
        vis[u] = 0;
        for (int i = head[u]; i ; i = a[i].next) {
            v = a[i].to;
            if (relax(u, v, a[i].w) && !vis[v]) {
                vis[v] = 1;
                if(!q.empty() && path[v] < path[q.front()]) q.push_front(v);
                else q.push_back(v);
                num++; x += path[v];
            }
        }
    }
}
int main() {
    n = 3; m = 2;
    for (int i = 1;i <= m; i++) {
        int w;
        scanf("%d", &w);
        add(i, i + 1, w);
    }
    spfa();
    printf("%d\n", path[n]);
    return 0;
}
又或是这个
CPP
#include<bits/stdc++.h>
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||pre->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(; !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);
    connect(A,B);
    cut(A,B);
    connect(A,B);
    printf("%d",query(A,B));
    return 0;
}
都可以AC 想要的拿去

回复

6 条回复,欢迎继续交流。

正在加载回复...