首页 > 编程语言 >洛谷P1001 A+B problem最全算法

洛谷P1001 A+B problem最全算法

时间：2022-08-25 15:35:19浏览次数：74  
标签：ch 洛谷 ll long P1001 while problem getchar define

为防止大家说我误导新人，先放一个最 不 正常的代码。

#include <iostream>
using namespace std;
int main() {
    int a,b;
    cin >> a >> b;
    cout << a+b;
    return 0;
}

接下来正文开始！！！

很正常的快读：

#include<bits/stdc++.h>
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define inf 0x7fffffff
#define INF 0x3f
#define v e[i].y
using namespace std;
inline ll read(){
    char ch=getchar();ll x=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-48,ch=getchar();return w==1?x:-x;
}
inline void write(ll x){
    if(x<0)x=-x,putchar('-');
    if(x<10){putchar(48+x);return;}
    write(x/10),putchar((x+10)%10+48);
}
int a=read(),b=read();
int main(){
    write(a+b);
    return 0;
}

然后我会逐渐走向不正常，大家最想看的网络流，平衡树等算法我会在后面写，不要着急（心急的可以拉到后面看）。

普及组的算法（正文的铺垫，大佬们先吃些小菜开开胃）：

逻辑运算：

#include<bits/stdc++.h>
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define inf 0x7fffffff
#define INF 0x3f
#define v e[i].y
using namespace std;
inline ll read(){
    char ch=getchar();ll x=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-48,ch=getchar();return w==1?x:-x;
}
inline void write(ll x){
    if(x<0)x=-x,putchar('-');
    if(x<10){putchar(48+x);return;}
    write(x/10),putchar((x+10)%10+48);
}
int a=read(),b=read();
int main(){
    write((a|b)+(a&b));
    return 0;
}

高精度：

//好吧，本题因为数有正负，除了正数的高精加外，还需要写判断大小与高精减的代码，本人表示我就算写了（还有一个原因是懒得写），大佬们也不想看，还是把精彩留给后面那些高级的算法吧。

递推（或者算是前缀和，线性dp？）：

#include<bits/stdc++.h>
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define inf 0x7fffffff
#define INF 0x3f
#define v e[i].y
using namespace std;
inline ll read(){
    char ch=getchar();ll x=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-48,ch=getchar();return w==1?x:-x;
}
inline void write(ll x){
    if(x<0)x=-x,putchar('-');
    if(x<10){putchar(48+x);return;}
    write(x/10),putchar((x+10)%10+48);
}
int n,sum[10];
int main(){
    n=2;
    for(int i=1;i<=n;i++)sum[i]=read()+sum[i-1];
    write(sum[n]);
    return 0;
}

背包：

#include<bits/stdc++.h>
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define inf 0x7fffffff
#define INF 0x3f
#define v e[i].y
using namespace std;
inline ll read(){
    char ch=getchar();ll x=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-48,ch=getchar();return w==1?x:-x;
}
inline void write(ll x){
    if(x<0)x=-x,putchar('-');
    if(x<10){putchar(48+x);return;}
    write(x/10),putchar((x+10)%10+48);
}
ll n,dp[10],a[10],b[10],V;
int main(){
    n=2,V=2;
    for(int i=1;i<=V;i++)dp[i]=-linf;
    for(int i=1;i<=n;i++)a[i]=1,b[i]=read();
    for(int i=1;i<=n;i++)
        for(int j=V;j>=a[i];j--)
            dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
    write(dp[V]);
    return 0;
}

区间 dp：

#include<bits/stdc++.h>
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define inf 0x7fffffff
#define INF 0x3f
#define v e[i].y
using namespace std;
inline ll read(){
    char ch=getchar();ll x=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-48,ch=getchar();return w==1?x:-x;
}
inline void write(ll x){
    if(x<0)x=-x,putchar('-');
    if(x<10){putchar(48+x);return;}
    write(x/10),putchar((x+10)%10+48);
}
ll n,dp[10][10],a[10];
int main(){
    n=2;
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            dp[i][j]=-linf;
    for(int i=1;i<=n;i++)a[i]=read(),dp[i][i]=a[i];
    for(int i=n-1;i>=1;i--)
        for(int j=i+1;j<=n;j++)
            dp[i][j]=max(dp[i][j-1]+a[j],dp[i+1][j]+a[i]);
    write(dp[1][n]);
    return 0;
}

好，普及组的算法应该结束了吧，如果我硬套出什么二分，贪心之类的想必大佬们也会反感的吧。我之所以写上面这些基础算法，就是为了防止某些人问我：“你写这么多行干什么呢？你会动规，递推···吗”那么我就跟你们说，我会（滑稽

大菜来了：

倍增表：

#include<bits/stdc++.h>
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define inf 0x7fffffff
#define INF 0x3f
#define v e[i].y
using namespace std;
inline ll read(){
    char ch=getchar();ll x=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-48,ch=getchar();return w==1?x:-x;
}
inline void write(ll x){
    if(x<0)x=-x,putchar('-');
    if(x<10){putchar(48+x);return;}
    write(x/10),putchar((x+10)%10+48);
}
ll n,st[10][10];
int main(){
    n=2;
    for(int i=1;i<=n;i++)st[i][0]=read();
    for(int i=1;i<=1;i++)//虽说这么写没什么意义，但还是遵循平常写ST表的格式吧
        for(int j=1;j<=n-(1<<i)+1;j++)
            st[j][i]=st[j][i-1]+st[j+(1<<i-1)][i-1];
    write(st[1][1]);
    return 0;
}

树状数组：

#include<bits/stdc++.h>
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define inf 0x7fffffff
#define INF 0x3f
#define v e[i].y
using namespace std;
inline ll read(){
    char ch=getchar();ll x=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-48,ch=getchar();return w==1?x:-x;
}
inline void write(ll x){
    if(x<0)x=-x,putchar('-');
    if(x<10){putchar(48+x);return;}
    write(x/10),putchar((x+10)%10+48);
}
ll n,a[10];
struct BIT{
    ll c[10];
    ll lowbit(int x){return x&-x;}
    void add(int x,int V){for(;x<=n;x+=lowbit(x))c[x]+=V;}
    ll query(int x){ll res=0;for(;x;x-=lowbit(x))res+=c[x];return res;}
}A;
int main(){
    n=2;
    for(int i=1;i<=n;i++)a[i]=read(),A.add(i,a[i]);
    write(A.query(n)-A.query(0));
    return 0;
}

线段树：

#include<bits/stdc++.h>
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define inf 0x7fffffff
#define INF 0x3f
#define v e[i].y
using namespace std;
inline ll read(){
    char ch=getchar();ll x=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-48,ch=getchar();return w==1?x:-x;
}
inline void write(ll x){
    if(x<0)x=-x,putchar('-');
    if(x<10){putchar(48+x);return;}
    write(x/10),putchar((x+10)%10+48);
}
ll n,a[10];
struct sgt{
    //只需要pushup和build的segment tree简单爆了
    ll sum[100];
    void pushup(int o){sum[o]=sum[o<<1]+sum[o<<1|1];}
    void build(int o,int l,int r){
        if(l==r){sum[o]=a[l];return;}
        int mid=l+r>>1;
        build(o<<1,l,mid),build(o<<1|1,mid+1,r);
        pushup(o);
    }
}A;
int main(){
    n=2;
    for(int i=1;i<=n;i++)a[i]=read();
    A.build(1,1,n),write(A.sum[1]);
    return 0;
}

字典树：

#include<bits/stdc++.h>
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define inf 0x7fffffff
#define INF 0x3f
#define v e[i].y
using namespace std;
inline ll read(){
    char ch=getchar();ll x=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-48,ch=getchar();return w==1?x:-x;
}
inline void write(ll x){
    if(x<0)x=-x,putchar('-');
    if(x<10){putchar(48+x);return;}
    write(x/10),putchar((x+10)%10+48);
}
ll n,ans;
struct trie{
    //做法：01trie
    //结点数字*对应权值就是一个结点的数值，数值和就是答案
    int ch[100][2],val[100],a[100],num;
    void Insert(int x){
        int op=0,w=(x<0?-1:1);
        x=abs(x);
        for(int i=30;i>=0;i--){
            bool j=(x&(1<<i));
            op=(ch[op][j]?ch[op][j]:ch[op][j]=++num);
            val[op]+=w,a[op]=j*(1<<i);
        }
    }
}A;
int main(){
    n=2;
    for(int i=1;i<=n;i++)A.Insert(read());
    for(int i=1;i<=A.num;i++)ans+=A.val[i]*A.a[i];
    write(ans);
    return 0;
}

未完待续

标签：ch,洛谷,ll,long,P1001,while,problem,getchar,define
From： https://www.cnblogs.com/mcDinic/p/16624421.html

相关文章

  • 洛谷P4619 [SDOI2018]旧试题
    再做一遍，算是复健一下数论。题目链接Description\(T\)组数据，给出\(A,B,C\)，求\[\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^Cd(ijk)\]\(d\)表示正因子个数。答案对\(P=1......
  • 洛谷 P1162 填涂颜色
    题目链接：https://www.luogu.com.cn/problem/P1162试题分析：本题运用广搜，我们大体思路是这样的：首先，我们将起始位置放到队尾，然后，在队列不为空的情况下，我们要一直取队首并拓......
  • 洛谷 P1443 马的遍历
    题目链接：https://www.luogu.com.cn/problem/P1443试题分析：题目是一个比较经典的广搜题，首先我们要读入长，宽，和马起点的坐标，然后将其压入队尾；在队列不为空时，一直取队首并将其......
  • [洛谷] 日 祭
    TOT：[140]2022JULY[58]7.13注册洛谷，做出第一道入门题（用py3）[1]7.14[2]7.19开始学C++7.24学完基本语法，用C++做出第一道题（庆祝）[2]7.26[15]7.27首道黄标！(......
  • 洛谷-P2272 最大半连通子图
    最大半连通子图tarjan缩点后计算弱连通图，相当于\(DAG\)图中点最多的路径，计算最大弱连通子图的时候就检查每个子节点的最长路径数量注意该题的答案计算与边有关，要去重......
  • 洛谷 P1706 全排列问题
    题目链接：https://www.luogu.com.cn/problem/P1706试题分析：题目要求按照字典序输出自然数 1 到 n 所有不重复的排列，且每一序列中的数字也不重复，我们可以运用搜索，将搜索......
  • MathProblem 39 Zeros and ones problem
    Whatisthesmallestintegergreaterthan0thatcanbewrittenentirelywithzerosandonesandisevenlydivisibleby225?Solution将其分解：\[225=5\times......
  • 洛谷 CF442C 紫 题解
    前言说实话这道题确实不太适合作为紫题，但是它的思路很妙，在此我详细解释一下每一步操作背后的原因。大致流程从前往后读入数组\(a\)，对于一个下标\(pos\)，若其满足\(a[......
  • 洛谷P4726 【模板】多项式指数函数（多项式 exp）
    题目https://www.luogu.com.cn/problem/P4726思路（略）是个板题，但是包含了很多多项式的基础板子，适合用来练手。据说递归版的好写（好抄），但是我猜测和fft类似，迭代版的应该常......
  • 【题解】 洛谷P3694 邦邦的大合唱站队
    发现尽管\(n\)比较大，但\(m\)非常小，于是考虑状压。记\(dp_{i}\)表示满足条件的乐队集合为\(i\)时的最小出队人数，\(dp_i=\min\{dp_{i\\xor\\1<<k}\}+w_{i\\xo......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99