数据结构与算法-一维差分

  • 条件:无
  • 题目:无
  • 原理:无
  • 代码:
    /**
    * mootable
     */
    #include <iostream>
    #include <iomanip>
    #include <algorithm>  //sort
    #include <map>
    #include <queue>
    #include <deque>  //双端队列,头可插,尾可插
    #include <string>
    #include <cstring>
    #include <stack>
    #include <cmath>
    #include <fstream>
    #include <ctime>
    #include <climits> //数值的限制范围
    //(double)clock() / CLOCKS_PER_SEC <= 0.95 限制0.95s跑完
    using namespace std;
    
    class Solver {
        //通用属性
    public:
        Solver() {
            //取消和c输出输入的同步,加快读取
            ios::sync_with_stdio(false);
            cin.tie(nullptr);
            cout.tie(nullptr);
        }
    
        //通用方法
    public:
        void SaveCpp(string name) const {
    
            fstream input;
            fstream output;
    
            input.open("moota.cpp", ios::in);
            const string file = name + ".cpp";
            output.open(file.c_str(), ios::out);
    
            char c = 'O';
            while (!input.eof()) {
                input.get(c);
                output << c;
            }
    
            input.close();
            output.close();
    
        }
    
    protected:
        //待实现方法
        virtual void BeginPlay() {
        };
    
        virtual void Playing() {
        };
    
        virtual void EndPlay() {
        };
    public:
        //外观模式
        void Play() {
            BeginPlay();
            Playing();
            EndPlay();
        }
    };
    //差分和前缀和的关系
    //差分的前缀和就是原数组
    //前缀和的差分也是原数组
    class SpecialSolver : public Solver {
    public:
        typedef long long lld;
        static const lld MAX = static_cast<lld>(1e6);
        static const lld INF = static_cast<lld>(1e18);
    private: //实例属性
        lld n, m;
    private: //实例方法
        lld sub1D[MAX];
    protected:
        virtual void BeginPlay() override {
            Solver::BeginPlay();
            cin >> n >> m;
            lld pre = 0, cur = 0;
            for (lld i = 1; i <= n; ++i) {
                cin >> cur;
                sub1D[i] = cur - pre;
                pre = cur;
            }
        };
    
        virtual void Playing() override {
            Solver::Playing();
            lld index;
            while (m--) {
                cin >> index;
                lld num = 0;
                for (lld i = 1; i <= index; ++i) {
                    num += sub1D[i];
                }
                cout << num;
            }
        };
    
        virtual void EndPlay() override {
            Solver::EndPlay();
    
        };
    };
    
    SpecialSolver specialSolver;
    
    int main() {
        //注意改名字
        //specialSolver.SaveCpp("一维差分模板");
        specialSolver.Play();
    }
    
    
上一篇:HDOJ1573X问题


下一篇:boost/function,boost/bind