AcWing算法基础课----基础算法(二) 习题题解_彡倾灬染|的博客-程序员宅基地

技术标签： 算法学习笔记  c++  c语言  题解  AcWing  

基础算法二 习题

基础知识讲解链接

传送门

791. 高精度加法

题目链接

答案

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define eb emplace_back
#define x first
#define y second
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 111;
int dx[]={
    -1, 0, 1, 0};
int dy[]={
    0, 1, 0, -1};
using namespace std;

vector<int>A,B;

vector<int> ADD(vector<int>&A,vector<int>&B){
    
    vector<int>C;
    int t=0;
    for(int i=0;i<A.size()||i<B.size();i++){
    
        if(i<A.size()) t+=A[i];
        if(i<B.size()) t+=B[i];
        C.eb(t%10);
        t/=10;
    }
    if(t) C.eb(1);
    return C;
}

void solve(){
    
    string a,b;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--) A.eb(a[i]-'0');
    for(int i=b.size()-1;i>=0;i--) B.eb(b[i]-'0');
    vector<int>C=ADD(A,B);
    for(int i=C.size()-1;i>=0;i--) cout<<C[i];
}

int main() {
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

792. 高精度减法

题目链接

答案

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define eb emplace_back
#define x first
#define y second
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 111;
int dx[]={
    -1, 0, 1, 0};
int dy[]={
    0, 1, 0, -1};
using namespace std;

vector<int>A,B;

bool judge(vector<int>&A,vector<int>&B){
    
    if(A.size()!=B.size()) return A.size()>B.size();
    for(int i=A.size()-1;i>=0;i--){
    
        if(A[i]!=B[i]) return A[i]>B[i];
    }
    return 1;
}

vector<int> SUB(vector<int>&A,vector<int>&B){
    
    vector<int>C;
    int t=0;
    for(int i=0;i<A.size();i++){
    
        t=A[i]-t;
        if(i<B.size()) t-=B[i];
        C.eb((t+10)%10);
        if(t<0) t=1;
        else t=0;
    }
    while(C.size()>1&&!C.back()) C.pop_back();
    return C;
}

void solve(){
    
    string a,b;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--) A.eb(a[i]-'0');
    for(int i=b.size()-1;i>=0;i--) B.eb(b[i]-'0');
    vector<int>C;
    if(judge(A,B)) C=SUB(A,B);
    else{
    
        cout<<"-";
        C=SUB(B,A);
    }
    for(int i=C.size()-1;i>=0;i--) cout<<C[i];
}

int main() {
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

793. 高精度乘法

题目链接

答案

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define eb emplace_back
#define x first
#define y second
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 111;
int dx[]={
    -1, 0, 1, 0};
int dy[]={
    0, 1, 0, -1};
using namespace std;

vector<int>A;

vector<int> MUL(vector<int>&A,int b){
    
    vector<int>C;
    int t=0;
    for(int i=0;i<A.size()||t;i++){
    
        if(i<A.size()) t+=A[i]*b;
        C.eb(t%10);
        t/=10;
    }
    while(C.size()>1&&!C.back()) C.pop_back();
    return C;
}

void solve(){
    
    string a;
    int b;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--) A.eb(a[i]-'0');
    vector<int>C=MUL(A,b);
    for(int i=C.size()-1;i>=0;i--) cout<<C[i];
}

int main() {
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

794. 高精度除法

题目链接

答案

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define eb emplace_back
#define x first
#define y second
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 111;
int dx[]={
    -1, 0, 1, 0};
int dy[]={
    0, 1, 0, -1};
using namespace std;

vector<int>A;

vector<int> DIV(vector<int>&A,int b,int &t){
    
    vector<int>C;
    t=0;
    for(int i=A.size()-1;i>=0;i--){
    
        t=t*10+A[i];
        C.eb(t/b);
        t%=b;
    }
    reverse(C.begin(),C.end());
    while(C.size()>1&&!C.back()) C.pop_back();
    return C;
}

void solve(){
    
    string a;
    int b,t;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--) A.eb(a[i]-'0');
    vector<int>C=DIV(A,b,t);
    for(int i=C.size()-1;i>=0;i--) cout<<C[i];
    cout<<endl;
    cout<<t<<endl;
}

int main() {
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

795. 前缀和

题目链接

答案

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define eb emplace_back
#define x first
#define y second
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 111;
int dx[]={
    -1, 0, 1, 0};
int dy[]={
    0, 1, 0, -1};
using namespace std;

int a[N];
int s[N];

void solve(){
    
    int n,q;
    cin>>n>>q;
    rep(i,1,n) cin>>a[i];
    rep(i,1,n) s[i]=s[i-1]+a[i];
    while(q--){
    
        int l,r;
        cin>>l>>r;
        cout<<s[r]-s[l-1]<<endl;
    }
}

int main() {
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

796. 子矩阵的和

题目链接

答案

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define eb emplace_back
#define x first
#define y second
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 1111;
int dx[]={
    -1, 0, 1, 0};
int dy[]={
    0, 1, 0, -1};
using namespace std;

int a[M][M];
int s[M][M];

void solve(){
    
    int n,m,q;
    cin>>n>>m>>q;
    rep(i,1,n){
    
        rep(j,1,m){
    
            cin>>a[i][j];
        }
    }
    rep(i,1,n){
    
        rep(j,1,m){
    
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
        }
    }
    while(q--){
    
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        int ans=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
        cout<<ans<<endl;
    }
}

int main() {
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

797. 差分

题目链接

答案

法一：构建差分数组

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define eb emplace_back
#define x first
#define y second
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 1111;
int dx[]={
    -1, 0, 1, 0};
int dy[]={
    0, 1, 0, -1};
using namespace std;

int a[N];
int b[N];

void Insert(int l,int r,int c){
    
    b[l]+=c;
    b[r+1]-=c;
}

void solve(){
    
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) b[i]=a[i]-a[i-1];  //构建差分数组
    while(m--){
    
        int l,r,c;
        cin>>l>>r>>c;
        Insert(l,r,c);
    }
    for(int i=1;i<=n;i++) b[i]+=b[i-1];
    for(int i=1;i<=n;i++) cout<<b[i]<<" "; 
}

int main() {
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

法二：不构造差分数组

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define eb emplace_back
#define x first
#define y second
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 1111;
int dx[]={
    -1, 0, 1, 0};
int dy[]={
    0, 1, 0, -1};
using namespace std;

int a[N];
int b[N];

void Insert(int l,int r,int c){
    
    b[l]+=c;
    b[r+1]-=c;
}

void solve(){
    
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    while(m--){
    
        int l,r,c;
        cin>>l>>r>>c;
        Insert(l,r,c);
    }
    for(int i=1;i<=n;i++) b[i]+=b[i-1];
    for(int i=1;i<=n;i++) cout<<a[i]+b[i]<<" "; 
}

int main() {
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

798. 差分矩阵

题目链接

答案

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define eb emplace_back
#define x first
#define y second
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 1111;
int dx[]={
    -1, 0, 1, 0};
int dy[]={
    0, 1, 0, -1};
using namespace std;

int a[M][M];
int b[M][M];

void Insert(int x1,int y1,int x2,int y2,int c){
    
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
}

void solve(){
    
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
    
        for(int j=1;j<=m;j++){
    
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
    
        for(int j=1;j<=m;j++){
    
            b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
        }
    }
    while(q--){
    
        int x1,y1;
        int x2,y2;
        int c;
        cin>>x1>>y1>>x2>>y2>>c;
        Insert(x1,y1,x2,y2,c);
    }
    for(int i=1;i<=n;i++){
    
        for(int j=1;j<=m;j++){
    
            b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
        }
    }
    for(int i=1;i<=n;i++){
    
        for(int j=1;j<=m;j++){
    
            cout<<b[i][j]<<" ";
        }
        cout<<endl;
    }
}

int main() {
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/qq_45830025/article/details/117230229

智能推荐

TT的神秘任务2（思路）_tt下号思路-程序员宅基地

问题描述在你们的帮助下，TT 轻松地完成了上一个神秘任务。但是令人没有想到的是，几天后，TT 再次遇到了那个神秘人。而这一次，神秘人决定加大难度，并许诺 TT，如果能够完成便给他一个奖励。任务依旧只给了两个数字，分别表示 n 和 k，不过这一次是要求 TT 给出无法被 n 整除的第 k 大的正整数。例如 n = 3，k = 7，则前 7 个无法被 n 整除的正整数为 [1 2 4 5 7 8 10]，答案为 10。好奇的 TT 想要知道奖励究竟是什么，你能帮帮他吗？Input第一行一个整数 _tt下号思路

逆天的Zstack-工控机上测试_zstack ioc_USTC-lup的博客-程序员宅基地

放假前一直在服务器上折腾Zstack跑数据库，调IOC。正好手头有个32G内存，intel i7处理器的工控机，就试试装Zstack试试看，想着即使重负荷的跑不了，跑跑docker之类的也行。装成功后试着批量开了把云主机，看结果简直逆天了，开云主机秒秒钟的事情，8线程的cpu，10倍超分极限是80，最多能开80个云主机：..._zstack ioc

checkbox多项选择器_checkbox value 选择器-程序员宅基地

属性类型默认值说明valueString</checkbox标识，选中触发的change事件，并携带的valuedisableBooleanFalse是否禁用，无法点击checkedBooleanFalse当前是否选中colorColorcheckbox的颜色,同css的color,打勾的颜色<checkbox-g..._checkbox value 选择器

u3d 去除物理摩擦-程序员宅基地

在资源中新建，选择Physic Material（物理材质），然后将属性中的Dynamic Friction和Static Friction调整为0，然后再将这个材质拖放到对应模型中，这时候，该模型的摩擦力就为0，反之数值越大，摩擦力越大...

DPM(Defomable Parts Model) 源码分析-训练（三）_parts模型分析-程序员宅基地

申明：本文非笔者原创，原文转载自：http://blog.csdn.net/ttransposition/article/details/12954631DPM(Defomable Parts Model)原理首先调用格式：example:pascal('person', 2); % train and evaluate a 2 component pe_parts模型分析

MySQL5.7.24安装配置（图文超详细教程）_mysql5.7.24配置文件-程序员宅基地

1.下载MySQL 我用的是5.7.24打开下载链接：https://dev.mysql.com/downloads/windows/installer/5.7.html点击Download进行下载 弹出页面点击No thanks进行下载下载下来的文件名是 mysql-installer-community-5.7.24.0.msi双击文件名称进行安装 如果提示如下错误说明.NET4.5.2未安装 需要安装此插件 报错窗口有网址 直接安装即可安装完毕后 重新打开MySQL安装程序 这个_mysql5.7.24配置文件

随便推点

java扇区绘制,JavaFX图表-程序员宅基地

本文概述通常, 购物车可以定义为以符号形式表示数据的图形或图表。图表主要用于表示大量数据以及数据各部分之间的关​​系。我们可以创建不同种类的图表来表示不同种类的信息。在JavaFX中, 我们可以使用packagejavafx.scene.chart提供的类来创建图表。图表类型图表可以分为以下几种类型。饼图：在饼图中, 圆的扇区用于表示整个信息的不同比例。在JavaFX中, 类javafx.scen..._javafx categoryaxis

xp系统运行程序提示无法定位程序输入点GetFinalPathNameByHandleW于动态链接库kernel32.dll上_xsx_的博客-程序员宅基地

最近自己用python3.6.3写了一个程序，使用win7 32位系统打包成exe，在win7 32位和64位运行没问题，在xp系统运行提示“xp系统运行程序提示无法定位程序输入点GetFinalPathNameByHandleW于动态链接库kernel32.dll上”最后查到原因是xp系统上支持最高的python版本为3.4.4于是在官网https://www.python.org/downloads/windows/下载python3.4.4 32位安装完成后需要升级。1.升级pippip

二层、三层、四层、七层交换_七层交换机-程序员宅基地

1、二层交换机工作在数据链路层，根据MAC进行交换机端口选择，转发通过ASIC (Application specific Integrated Circuit)芯片实现，保证高吞吐量 a)主机A发送ARP，得到主机B的MAC b)主机A以目的IP和目的MAC为主机B，发送网络包 c)交换机根据目的MAC查到映射关系，找到出端口，就将数据转发到对应的端口..._七层交换机

c#Winform编程自学笔记（一）_winform 单选框_无～~畏的博客-程序员宅基地

## 单选框:*名称：RadioButton：有区域特性，需要使用其他控件进行隔离希望使用单独功能时，才选择这个控件，如果希望多个功能请使用CheckBox****对于Checked属性：True被选中否则False****对于AutoSize,则可以改变对于单选框位置的大小****对于CheckAlign，则改变单选框原点的位置GroupBox(容器)：使用Gopbox时内部的控件不会根据Gp的大小改变 作用1：当作RadioButton的选择区域 作用2：划分控件区域 作用3：美化_winform 单选框

React Hooks学习--useReducer，useMemo和useRef_usereducer usememo_元气满满鸭的博客-程序员宅基地

一.useReducerfunction ReducerDemo(){ const [count,dispatch] = useReducer((state,action) => { switch(action){ case 'add': return state + 1 case 'sub' return state - 1 default: return state } },0) return ( <> <h2>_usereducer usememo

Python基础教程：用Python怎么telnet到网络设备_python3如何telnat出入命令-程序员宅基地

ython基础教程：用Python怎么telnet到网络设备0.前言Telnet协议属于TCP/IP协议族里的一种，对于我们这些网络攻城狮来说，再熟悉不过了，常用于远程登陆到网络设备进行操作，但是，它的缺陷太明显了，就是不安全，信息明文传送，极容易被攻击窃取信息，不推荐使用，但本节我还是先从它入手哈。测试环境及关键代码解释1.1 简单测试环境使用python3环境使用内置telne..._python3如何telnat出入命令

推荐文章

热门文章

相关标签