#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

int main()
{
    string a;
    vector<int> A;

    int B;
    cin >> a >> B;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');

    int r;
    auto C = div(A, B, r);

    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];

    cout << endl << r << endl;

    return 0;
}

#include <iostream>
#include <vector>

using namespace std;


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.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}


int main()
{
    string a;
    int b;

    cin >> a >> b;

    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');

    auto C = mul(A, b);

    for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);

    return 0;
}

我们f[i][j]数组记录的 是 每一根竹子，在操作的过程中，高度的变化过程长度

然后在这个过程中 如果有一个相邻的同高数对，那么可以少操作一次

dp的关键就在于 能够精准的求出状态表示，以及状态转移方程
dp[i][j][k] 表示现在已经经过了i个店，j朵花，现在还有k斗酒的集合的方案个数

状态转移根据 最后一次遇到的是店 还是 花来区分
所以dp[i][j][k] = dp[i-1][j][k/2] + dp[i][j-1][k+1]

图论基础题
如果 a可引爆b，那就连一条a指向b的边

然后它就是 图的遍历的裸题

因为他是2×n的格子
所有每一列都只有四种状态

f[i][j]表示 已经操作完前i-1列，且第i列的状态为j的所有方案的集合

g数组的含义：根据第i列的状态，操作完把第i列塞满后，转移后第i+1列有哪些可能状态？
0-3 (00 01 10 11)

1.求出需要补充的 左右括号个数

我们从左向右扫描，如果遇到（我们让cnt+1，如果遇到）我们-1
如果在扫描过程中，遇到了cnt<0的情况，那我们就必须在此处加上一个左括号

如果扫描结束之后，cnt>0。那我们就必须还要补充cnt个右括号

这个样子我们就能求出左括号 和 右括号需要补充的个数了

2.求出左右括号添加的所有方案 然后相乘

此项成立是基于一些条件的
1.左右括号的添加是相互独立的
2.就算左右括号加到了同一个空之中，其也是以）（的形式加入的
因为如果是（）的形式加入，那它们可抵消，无效

3.我们如何表示集合

dp[i][j] 表示 只考虑前i个括号，左括号比右括号多j个的集合

状态转移方程

if s[i]==’(‘ , dp[i][j] = dp[i-1][j-1]
如果 s[i]==’)’ dp[i][j] = dp[i-1][j+1] + dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j-2].....+dp[i-1][0]
借助多重背包问题 改为 dp[i][j] = dp[i-1][j-1]

思路： 错误思路：
因为ijk之间是没有关系的，只要找到三个数组之间递增的关系即可
我们可以给前两个数组分别用cnt计数，再对其进行前缀和，即可求解

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N], b[N], c[N];
int cnta[N], cntb[N];

int main()
{
    scanf("%d", &n);

    for(int i=0; i<n; i++) scanf("%d%d%d", &a[i], &b[i], &c[i]);

    for(int i=0; i<n; i++)
    {
        cnta[a[i]]++;
        cntb[b[i]]++;
    }
    for(int i=0; i<n; i++)
    {
        if(i) 
        {
            cnta[i] += cnta[i-1];
            cntb[i] += cntb[i-1];
        }
    }

    for(int i=0; i<n; i++)

    return 0;
}

正解一： 排序 + 二分

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10;

typedef long long LL;

int n;
int a[N], b[N], c[N];
int cnta[N], cntb[N];

int findLast(int x)
{
    int l = 0, r = n-1;
    while(l < r)
    {
        int mid = l + r + 1>> 1;
        if(a[mid] >= x) r = mid -1;
        else l = mid;
    }
    if(a[l] >= x) return -1;
    return l;
}

int findfirst(int x)
{
    int l = 0, r = n-1;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(c[mid] <= x) l = mid + 1;
        else r = mid;
    }
    if(c[l] <= x) return n;
    return l;
}

int main()
{
    scanf("%d", &n);

    for(int i=0; i<n; i++) scanf("%d", &a[i]);
    for(int i=0; i<n; i++) scanf("%d", &b[i]);
    for(int i=0; i<n; i++) scanf("%d", &c[i]);

    sort(a, a+n);
    sort(b, b+n);
    sort(c, c+n);

    LL res = 0;
    for(int i=0; i<n; i++) 
    {
        LL x = findLast(b[i]) + 1;
        LL y = n - findfirst(b[i]);
        //cout<<x<<" "<<y<<endl;
        res += x*y;
    }

    cout << res << endl;

    return 0;
}

很极限的一个过法，你既然要出一个n^2的答案，那为什么你要调10000的数据访问
5000不好吗

思路：

1.枚举所有区间的左右端点
2.因为数组中没有重复数字 ==> 当区间最大值 最小值之差 == 区间长度
那就说明这个区间“连号”

#include<iostream>

using namespace std;

const int N = 1e4 + 10;

int n;
int a[N];

int main()
{
    scanf("%d", &n);

    for(int i=0; i<n; i++) scanf("%d", &a[i]);

    long long res = 0;
    for(int i=0; i<n; i++)
    {
        int maxx = -2e9, minx = 2e9;
        for(int j=i; j<n; j++)
        {
            if(a[j] > maxx) maxx = a[j];
            if(a[j] < minx) minx = a[j];

            if(j - i == maxx - minx) res ++;
        }
    }

    cout<< res << endl;

    return 0;
}

思路：

首先进行前缀和处理 你要凑出来k倍区间，你就要保证整个区间模k为0

如果其模k为0，那么它就是k倍区间
如果不为0，那只要找到一个和它对k同余的前缀区间，减去，剩余区间即为k倍区间

代码实现：

从前往后推，遇到模k为x的区间，就让cnt[x]++，每次都看一下它前面有多少个和它同余的
对答案进行修改

因为数据大而多 前缀和数组未开ll 导致wa了几发

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

typedef long long ll;

ll n, k;
ll a[N], cnt[N];

int main()
{
    scanf("%lld%lld", &n, &k);
    for(int i=1; i<=n; i++)
    {
        scanf("%lld", &a[i]);
        a[i] += a[i-1];
    }

    long long res = 0;
    for(int i=1; i<=n; i++)
    {
        int x = a[i] % k;
        if(!x) res++;
        res += (long long)cnt[x];

        cnt[x]++;
    }

    cout<<res<<endl;

    return 0;
}