世界上最难c++题(A+B Problem)我真的废了吗?
连(a+b Problem)也看不懂,大家我是不是废了!好了,我在发几份题解,大家一定要为我解答疑惑,我真的废了吗?我做完了那道题,却也让我感受到,我简直是一个蒟蒻!我从此恨上了这道题,更恨上了的这里的题解!大家可以试一试,我亲测有效,当我看到这篇题解。饶了我吧,你们猜题解是怎么写的,呜呜呜!这一个个题解,如阳光过心,让我的心如火烧着。有没有人安慰我,是我学习的进度太慢了吗?我为这道题奋战,痛哭流
·
没错,这道题的确是最难的题:
我为这道题奋战,痛哭流涕,简直泣不成声
我从此恨上了这道题,更恨上了的这里的题解!!!
我做完了那道题,却也让我感受到,我简直是一个蒟蒻!
啊啊啊啊啊!!!
我写的:
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b;
cin>>a>>b;
cout<<a+b;
return 0;
}
饶了我吧,你们猜题解是怎么写的,呜呜呜!!
第一个:
#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||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);
//连边 Link
connect(A,B);
//断边 Cut
cut(A,B);
//再连边orz Link again
connect(A,B);
printf("%d\n",query(A,B));
return 0;
}
没错,你没有看错,这就是(A+B Problem)
大家可以试一试,我亲测有效,当我看到这篇题解
我不禁怀疑到我已经:
呜呜呜,有没有人救一下我,我真的要哭了
我连题解也看不懂
连(a+b Problem)也看不懂,大家我是不是废了!!!
但是接下来我更加的崩溃了!
第二份题解:
#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[1]+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;
}
天要亡我!!!
我要逆向而生,加油!!!
我坚持看完这片题解,
啊哈,还是
算了
有没有人帮我解释与一下他们在干什么?
我真的废掉了吗!
有没有人安慰我,是我学习的进度太慢了吗?
人类的进步没有带上我
好了,我在发几份题解,大家一定要为我解答疑惑,我真的废了吗?
//一颗资瓷区间加、区间翻转、区间求和的Splay
#include <bits/stdc++.h>
#define ll long long
#define N 100000
using 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]; 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;
}
#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;
}
#include<cstdio> //头文件
#define NI 2
//从来不喜欢算log所以一般用常数 不知道算不算坏习惯 因为3个节点 所以log3(当然以2为底)上取整得2
struct 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的距离和并输出
}
duan
#include <cstdio>
#include <algorithm>
#define INF 2140000000
using 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);
}
注意,这个是Java
import java.util.Scanner;
public class Main {
private static Scanner sc;
public static void main(String[] args) {
Scanner(0);
}
public static void Scanner(int sum){
sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
int c;
c = a + b;
System.out.println(c);
}
}
#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));
}
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.
#include<cstdio>
#define reg register
inline 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);
}
这一个个题解,如阳光过心,让我的心如火烧着
你看他们对我的关心多么的不切实际:
忘了吧,不学了!
更多推荐
已为社区贡献1条内容
所有评论(0)