A. Vova and Train

Description:

Vova plans to go to the conference by train. Initially, the train is at the point $1$1 and the destination point of the path is the point $L$L. The speed of the train is $1$1 length unit per minute (i.e. at the first minute the train is at the point $1$1, at the second minute — at the point $2$2 and so on).
There are lanterns on the path. They are placed at the points with coordinates divisible by $v$v (i.e. the first lantern is at the point $v$v, the second is at the point $2v$2v and so on).
There is also exactly one standing train which occupies all the points from $l$l to $r$r inclusive.
Vova can see the lantern at the point $p$p if $p$p is divisible by $v$v and there is no standing train at this position ( $p̸\in [l;r]$p̸​∈[l;r]). Thus, if the point with the lantern is one of the points covered by the standing train, Vova can’t see this lantern.
Your problem is to say the number of lanterns Vova will see during the path. Vova plans to go to $t$t different conferences, so you should answer $t$t independent queries.

Input:

The first line of the input contains one integer $t$t ( $1\le t\le 10^4$1≤t≤104) — the number of queries.
Then $t$t lines follow. The $i$i-th line contains four integers $L_i,v_i,l_i,r_i$Li​,vi​,li​,ri​ ( $1\le L,v\le 10^9$1≤L,v≤109, $1\le l\le r\le L$1≤l≤r≤L) — destination point of the $i$i-th path, the period of the lantern appearance and the segment occupied by the standing train.

Output

Print $t$t lines. The $i$i-th line should contain one integer — the answer for the $i$i-th query.

Sample Input:

4
10 2 3 7
100 51 51 51
1234 1 100 199
1000000000 1 1 1000000000

Sample Output:

3
0
1134
0

题目链接

1~L中没v个位置有一个灯笼，给出区间l~r，求区间外有多少个灯笼。

$\frac{L}{v}$vL​是1~L的灯笼总数，那么显然 $\frac{l}{v}$vl​是1~l的灯笼总数， $\frac{r}{v}$vr​是1~r的灯笼总数，所以用1~r区间灯笼数减去1~l区间灯笼数即为l~r区间灯笼数(注意特判l点为灯笼点的情况)，最后总数相减即为结果。

推了20min才推出来公式，真是僵硬……

AC代码:

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char *argv[]) {
    int T;
    scanf("%d", &T);
    for (int Case = 1, L, v, l, r; Case <= T; ++Case) {
        scanf("%d%d%d%d", &L, &v, &l, &r);
        int Ans = L / v;
        Ans -= r / v - l / v + (l % v == 0);
        printf("%d\n", Ans);
    }
    return 0;
}

B. Heaters

Description:

Vova’s house is an array consisting of $n$n elements (yeah, this is the first problem, I think, where someone lives in the array). There are heaters in some positions of the array. The $i$i-th element of the array is $1$1 if there is a heater in the position $i$i, otherwise the $i$i-th element of the array is $0$0.
Each heater has a value $r$r ( $r$r is the same for all heaters). This value means that the heater at the position $pos$pos can warm up all the elements in range $[pos-r+1;pos+r-1]$[pos−r+1;pos+r−1].
Vova likes to walk through his house while he thinks, and he hates cold positions of his house. Vova wants to switch some of his heaters on in such a way that each element of his house will be warmed up by at least one heater.
Vova’s target is to warm up the whole house (all the elements of the array), i.e. if $n=6$n=6, $r=2$r=2 and heaters are at positions $2$2 and $5$5, then Vova can warm up the whole house if he switches all the heaters in the house on (then the first $3$3 elements will be warmed up by the first heater and the last $3$3 elements will be warmed up by the second heater).
Initially, all the heaters are off.
But from the other hand, Vova didn’t like to pay much for the electricity. So he wants to switch the minimum number of heaters on in such a way that each element of his house is warmed up by at least one heater.
Your task is to find this number of heaters or say that it is impossible to warm up the whole house.

Input:

The first line of the input contains two integers $n$n and $r$r ( $1\le n,r\le 1000$1≤n,r≤1000) — the number of elements in the array and the value of heaters.
The second line contains $n$n integers $a_1,a_2,\dots ,a_n$a1​,a2​,…,an​ ( $0\le a_i\le 1$0≤ai​≤1) — the Vova’s house description.

Output

Print one integer — the minimum number of heaters needed to warm up the whole house or -1 if it is impossible to do it.

Sample Input:

6 2
0 1 1 0 0 1

Sample Output:

3

Sample Input:

5 3
1 0 0 0 1

Sample Output:

2

Sample Input:

5 10
0 0 0 0 0

Sample Output:

-1

Sample Input:

10 3
0 0 1 1 0 1 0 0 0 1

Sample Output:

3

题目链接

暴力枚举，每次找最右边的点。

AC代码:

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char *argv[]) {
    int N, R;
    scanf("%d%d", &N, &R);
    vector<bool> Flag(N + 1, false);
    vector<int> Pos, Dp(N + 1, 0);
    for (int i = 1, X; i <= N; ++i) {
        scanf("%d", &X);
        if (X) {
            Pos.push_back(i);
        }
    }
    int Cur = -1, Size = int(Pos.size()), Index = 0;
    for (int i = 1; i <= N; ++i) {
        if (Flag[i]) {
            Dp[i] = Dp[i - 1];
        }
        else {
            int Temp = -1;
            for (int j = Cur + 1; j < Size; ++j) {
                if (Pos[j] - R + 1 > i) {
                    break;
                }
                else {
                    Temp = j;
                }
            }
            if (Temp != -1) {
                for (int j = Pos[Temp] - R + 1; j <= Pos[Temp] + R - 1; ++j) {
                    if (j > N) {
                        continue;
                    }
                    if (j < 1) {
                        continue;
                    }
                    Flag[j] = true;
                    if (j == Pos[Temp] - R + 1 || j == 1) {
                        Dp[j] = Dp[j - 1] + 1;
                    }
                    else {
                        Dp[j] = Dp[j - 1];
                    }
                }
                Cur = Temp;
            }
            else {
                printf("-1\n");
                return 0;
            }
        }
    }
    printf("%d\n", Dp[N]);
    return 0;
}

C. Books Queries

Description:

You have got a shelf and want to put some books on it.
You are given $q$q queries of three types:
L $id$id — put a book having index $id$id on the shelf to the left from the leftmost existing book; R $id$id — put a book having index $id$id on the shelf to the right from the rightmost existing book; ? $id$id — calculate the minimum number of books you need to pop from the left or from the right in such a way that the book with index $id$id will be leftmost or rightmost. You can assume that the first book you will put can have any position (it does not matter) and queries of type $3$3 are always valid (it is guaranteed that the book in each such query is already placed). You can also assume that you don’t put the same book on the shelf twice, so $id$ids don’t repeat in queries of first two types.
Your problem is to answer all the queries of type $3$3 in order they appear in the input.
Note that after answering the query of type $3$3 all the books remain on the shelf and the relative order of books does not change.
If you are Python programmer, consider using PyPy instead of Python when you submit your code.

Input:

The first line of the input contains one integer $q$q ( $1\le q\le 2\cdot 10^5$1≤q≤2⋅105) — the number of queries.
Then $q$q lines follow. The $i$i-th line contains the $i$i-th query in format as in the problem statement. It is guaranteed that queries are always valid (for query type $3$3, it is guaranteed that the book in each such query is already placed, and for other types, it is guaranteed that the book was not placed before).
It is guaranteed that there is at least one query of type $3$3 in the input.
In each query the constraint $1\le id\le 2\cdot 10^5$1≤id≤2⋅105 is met.

Output

Print answers to queries of the type $3$3 in order they appear in the input.

Sample Input:

8
L 1
R 2
R 3
? 2
L 4
? 1
L 5
? 1

Sample Output:

1
1
2

Sample Input:

10
L 100
R 100000
R 123
L 101
? 123
L 10
R 115
? 100
R 110
? 115

Sample Output:

0
2
1

题目链接

题目每次在数列左边或者右边加入一个数，然后每次询问一个数，求其左边数的数量与右边数的数量的最小值。

直接上伸展树模板，在树中节点权值设置为插入数的下标(此下标我从1e5+2,1e5+3开始向左向右存)，之后每次询问将询问数其下标转至根节点判断左右子树大小最小值即可。

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e5 + 5;

struct SplayTree {
    // Root:Splay Tree根节点
    int Root, Tot;
    // Son[i][0]:i节点的左孩子，Son[i][0]:i节点的右孩子
    int Son[maxn][2];
    // Pre[i]:i节点的父节点
    int Pre[maxn];
    // Val[i]:i节点的权值
    int Val[maxn];
    // Size[i]:以i节点为根的Splay Tree的节点数(包含自身)
    int Size[maxn];
    // Cnt[i]:节点i的权值的出现次数
    int Cnt[maxn];

    void Init() {
        memset(Son, 0, sizeof(Son));
        memset(Size, 0, sizeof(Size));
    }

    void PushUp(int X) {
        Size[X] = Size[Son[X][0]] + Size[Son[X][1]] + Cnt[X];
    }

    // 判断X节点是其父节点的左孩子还是右孩子
    bool Self(int X) {
        return X == Son[Pre[X]][1];
    }

    void Clear(int X) {
        Son[X][0] = Son[X][1] = Pre[X] = Val[X] = Size[X] = Cnt[X] = 0;
    }

    // 旋转
    void Rotate(int X) {
        int Fa = Pre[X], FaFa = Pre[Fa], XJ = Self(X);
        Son[Fa][XJ] = Son[X][XJ ^ 1];
        Pre[Son[Fa][XJ]] = Pre[X];
        Son[X][XJ ^ 1] = Pre[X];
        Pre[Fa] = X;
        Pre[X] = FaFa;
        if (FaFa) {
            Son[FaFa][Fa == Son[FaFa][1]] = X;
        }
        PushUp(Fa);
        PushUp(X);
    }

    // 旋转X节点到根节点
    void Splay(int X) {
        for (int i = Pre[X]; i = Pre[X]; Rotate(X)) {
            if (Pre[i]) {
                Rotate(Self(X) == Self(i) ? i : X);
            }
        }
        Root = X;
    }

    // 插入数X
    void Insert(int X) {
        if (!Root) {
            Val[++Tot] = X;
            Cnt[Tot]++;
            Root = Tot;
            PushUp(Root);
            return;
        }
        int Cur = Root, F = 0;
        while (true) {
            if (Val[Cur] == X) {
                Cnt[Cur]++;
                PushUp(Cur);
                PushUp(F);
                Splay(Cur);
                break;
            }
            F = Cur;
            Cur = Son[Cur][Val[Cur] < X];
            if (!Cur) {
                Val[++Tot] = X;
                Cnt[Tot]++;
                Pre[Tot] = F;
                Son[F][Val[F] < X] = Tot;
                PushUp(Tot);
                PushUp(F);
                Splay(Tot);
                break;
            }
        }
    }

    // 查询X的排名
    int Rank(int X) {
        int Ans = 0, Cur = Root;
        while (true) {
            if (X < Val[Cur]) {
                Cur = Son[Cur][0];
            }
            else {
                Ans += Size[Son[Cur][0]];
                if (X == Val[Cur]) {
                    Splay(Cur);
                    return Ans + 1;
                }
                Ans += Cnt[Cur];
                Cur = Son[Cur][1];
            }
        }
    }

    // 查询排名为X的数
    int Kth(int X) {
        int Cur = Root;
        while (true) {
            if (Son[Cur][0] && X <= Size[Son[Cur][0]]) {
                Cur = Son[Cur][0];
            }
            else {
                X -= Cnt[Cur] + Size[Son[Cur][0]];
                if (X <= 0) {
                    return Val[Cur];
                }
                Cur = Son[Cur][1];
            }
        }
    }

    /* * 在Insert操作时X已经Splay到根了 * 所以X的前驱就是X的左子树的最右边的节点 * 后继就是X的右子树的最左边的节点 */

    // 求前驱
    int GetPath() {
        int Cur = Son[Root][0];
        while (Son[Cur][1]) {
            Cur = Son[Cur][1];
        }
        return Cur;
    }

    // 求后继
    int GetNext() {
        int Cur = Son[Root][1];
        while (Son[Cur][0]) {
            Cur = Son[Cur][0];
        }
        return Cur;
    }

    // 删除值为X的节点
    void Delete(int X) {
        // 将X旋转到根
        Rank(X);
        if (Cnt[Root] > 1) {
            Cnt[Root]--;
            PushUp(Root);
            return;
        }
        if (!Son[Root][0] && !Son[Root][1]) {
            Clear(Root);
            Root = 0;
            return;
        }
        if (!Son[Root][0]) {
            int Temp = Root;
            Root = Son[Root][1];
            Pre[Root] = 0;
            Clear(Temp);
            return;
        }
        if (!Son[Root][1]) {
            int Temp = Root;
            Root = Son[Root][0];
            Pre[Root] = 0;
            Clear(Temp);
            return;
        }
        int Temp = GetPath(), Old = Root;
        Splay(Temp);
        Pre[Son[Old][1]] = Temp;
        Son[Temp][1] = Son[Old][1];
        Clear(Old);
        PushUp(Root);
    }
};

int main(int argc, char *argv[]) {
    int Q;
    cin >> Q;
    int Left = 1e5 + 2, Right = 1e5 + 3;
    SplayTree Tree;
    Tree.Init();
    map<int, int> Mp;
    for (int Query = 1, Id; Query <= Q; ++Query) {
        char Op;
        cin >> Op >> Id;
        if (Op == 'L') {
            Mp[Id] = Left;
            Tree.Insert(Left--);
        }
        else if (Op == 'R') {
            Mp[Id] = Right;
            Tree.Insert(Right++);
        }
        else if (Op == '?') {
            Tree.Rank(Mp[Id]);
            int _Left = Tree.Size[Tree.Son[Tree.Root][0]], _Right = Tree.Size[Tree.Son[Tree.Root][1]];
            cout << min(_Left, _Right) << endl;
        }
    }
    return 0;
}

D. Boxes Packing

Description:

Maksim has $n$n objects and $m$m boxes, each box has size exactly $k$k. Objects are numbered from $1$1 to $n$n in order from left to right, the size of the $i$i-th object is $a_i$ai​.
Maksim wants to pack his objects into the boxes and he will pack objects by the following algorithm: he takes one of the empty boxes he has, goes from left to right through the objects, and if the $i$i-th object fits in the current box (the remaining size of the box is greater than or equal to $a_i$ai​), he puts it in the box, and the remaining size of the box decreases by $a_i$ai​. Otherwise he takes the new empty box and continues the process above. If he has no empty boxes and there is at least one object not in some box then Maksim cannot pack the chosen set of objects.
Maksim wants to know the maximum number of objects he can pack by the algorithm above. To reach this target, he will throw out the leftmost object from the set until the remaining set of objects can be packed in boxes he has. Your task is to say the maximum number of objects Maksim can pack in boxes he has.
Each time when Maksim tries to pack the objects into the boxes, he will make empty all the boxes he has before do it (and the relative order of the remaining set of objects will not change).

Input:

The first line of the input contains three integers $n$n, $m$m, $k$k ( $1\le n,m\le 2\cdot 10^5$1≤n,m≤2⋅105, $1\le k\le 10^9$1≤k≤109) — the number of objects, the number of boxes and the size of each box.
The second line of the input contains $n$n integers $a_1,a_2,\dots ,a_n$a1​,a2​,…,an​ ( $1\le a_i\le k$1≤ai​≤k), where $a_i$ai​ is the size of the $i$i-th object.

Output:

Print the maximum number of objects Maksim can pack using the algorithm described in the problem statement.

Sample Input:

5 2 6
5 2 1 4 2

Sample Output:

4

Sample Input:

5 1 4
4 2 3 4 1

Sample Output:

1

Sample Input:

5 3 3
1 2 3 1 1

Sample Output:

5

题目链接

总共n个物品，m个箱子，每个箱子的容量为k，每个物品的体积为a[i]( $i\in [1,n]$i∈[1,n])，从左至右一次向箱子内装物品，箱子装不下就换另一个新箱子装，若最后还有物品没有装进箱子内就把最左边的物品扔掉重新装。

从右至左枚举物品，能装下就装，装不下就换箱子，箱子用完为止。

AC代码:

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char *argv[]) {
    int N, M, K;
    scanf("%d%d%d", &N, &M, &K);
    vector<int> A(N, 0);
    for (int i = 0; i < N; ++i) {
        scanf("%d", &A[i]);
    }
    long long Ans = 0, Sum = 0;
    for (int i = N - 1; i >= 0; --i) {
        if (Sum + A[i] <= K) {
            Sum += A[i];
        }
        else {
            Sum = A[i];
            M--;
        }
        if (!M) {
            break;
        }
        Ans++;
    }
    printf("%lld\n", Ans);
    return 0;
}

E. Binary Numbers AND Sum

Description:

You are given two huge binary integer numbers $a$a and $b$b of lengths $n$n and $m$m respectively. You will repeat the following process: if $b\>0$b>0, then add to the answer the value $a\mathrm{\&}b$a & b and divide $b$b by $2$2 rounding down (i.e. remove the last digit of $b$b), and repeat the process again, otherwise stop the process.
The value $a\mathrm{\&}b$a & b means bitwise AND of $a$a and $b$b. Your task is to calculate the answer modulo $998244353$998244353.
Note that you should add the value $a\mathrm{\&}b$a & b to the answer in decimal notation, not in binary. So your task is to calculate the answer in decimal notation. For example, if $a=1010_2\left(10_{10}\right)$a=10102​ (1010​) and $b=1000_2\left(8_{10}\right)$b=10002​ (810​), then the value $a\mathrm{\&}b$a & b will be equal to $8$8, not to $1000$1000.

Input:

The first line of the input contains two integers $n$n and $m$m ( $1\le n,m\le 2\cdot 10^5$1≤n,m≤2⋅105) — the length of $a$a and the length of $b$b correspondingly.
The second line of the input contains one huge integer $a$a. It is guaranteed that this number consists of exactly $n$n zeroes and ones and the first digit is always $1$1.
The third line of the input contains one huge integer $b$b. It is guaranteed that this number consists of exactly $m$m zeroes and ones and the first digit is always $1$1.

Output:

Print the answer to this problem in decimal notation modulo $998244353$998244353.

Sample Input:

4 4
1010
1101

Sample Output:

12

Sample Input:

4 5
1001
10101

Sample Output:

11

题目链接

用一个数组记录b数从右至左的当前位置左边(翻转之后是右边)1总数，因为在逐次减位时每个1都会到达后面的每一位，之后枚举a数的每一位，记录1位置下的值加入结果当中。

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;
const int mod = 998244353;

int N, M;
string A, B;
long long Ans;
int Cnt[maxn];
long long Pwd[maxn];

int main(int argc, char *argv[]) {
    cin >> N >> M;
    cin >> A >> B;
    reverse(A.begin(), A.end());
    reverse(B.begin(), B.end());
    Pwd[0] = 1;
    for (int i = 1; i <= N; ++i) {
        Pwd[i] = (Pwd[i - 1] * 2) % mod;
    }
    Cnt[M] = 0;
    for (int i = M - 1; i >= 0; --i) {
        Cnt[i] = (B[i] == '1') + Cnt[i + 1];
    }
    Ans = 0;
    for (int i = 0; i < N; ++i) {
        if (A[i] == '1') {
            Ans += (Pwd[i] * Cnt[i]) % mod;
        }
        Ans %= mod;
    }
    printf("%lld\n", Ans);
    return 0;
}