要不是杰哥抬了一手这场又要掉分……菜是原罪

A. Got Any Grapes?

Description:

The Duck songFor simplicity, we’ll assume that there are only three types of grapes: green grapes, purple grapes and black grapes.
Andrew, Dmitry and Michal are all grapes’ lovers, however their preferences of grapes are different. To make all of them happy, the following should happen:
Andrew, Dmitry and Michal should eat at least $x$x, $y$y and $z$z grapes, respectively. Andrew has an extreme affinity for green grapes, thus he will eat green grapes and green grapes only. On the other hand, Dmitry is not a fan of black grapes — any types of grapes except black would do for him. In other words, Dmitry can eat green and purple grapes. Michal has a common taste — he enjoys grapes in general and will be pleased with any types of grapes, as long as the quantity is sufficient.Knowing that his friends are so fond of grapes, Aki decided to host a grape party with them. He has prepared a box with $a$a green grapes, $b$b purple grapes and $c$c black grapes.
However, Aki isn’t sure if the box he prepared contains enough grapes to make everyone happy. Can you please find out whether it’s possible to distribute grapes so that everyone is happy or Aki has to buy some more grapes?
It is not required to distribute all the grapes, so it’s possible that some of them will remain unused.

Input:

uck song

Output

he first line contains three integers $x$x, $y$y and $z$z ( $1\le x,y,z\le 10^5$1≤x,y,z≤105) — the number of grapes Andrew, Dmitry and Michal want to eat.
The second line contains three integers $a$a, $b$b, $c$c ( $1\le a,b,c\le 10^5$1≤a,b,c≤105) — the number of green, purple and black grapes in the box.

Sample Input:

1 6 2
4 3 3

Sample Output:

YES

Sample Input:

5 1 1
4 3 2

Sample Output:

NO

题目链接

三个人三种颜色的物品，其中一个人只要一种颜色的物品，一个人可以要两种颜色的物品，一个人可以要任意种颜色的物品，三种物品分别有 $a,b,c$a,b,c 个，三个人分别需要 $x,y,z$x,y,z 个，问能否满足分配需求

模拟即可

AC代码:

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

int X, Y, Z;
int A, B, C;

int main(int argc, char *argv[]) {
    scanf("%d%d%d", &X, &Y, &Z);
    scanf("%d%d%d", &A, &B, &C);
    if (A < X) {
        printf("NO\n");
        return 0;
    }
    A -= X;
    if (A + B < Y) {
        printf("NO\n");
        return 0;
    }
    if (A >= Y) A -= Y;
    else {
        Y -= A;
        A = 0;
        B -= Y;
    }
    Y = 0;
    if (A + B + C < Z) {
        printf("NO\n");
        return 0;
    }
    printf("YES\n");
    return 0;
}

B. Yet Another Array Partitioning Task

Description:

An array $b$b is called to be a subarray of $a$a if it forms a continuous subsequence of $a$a, that is, if it is equal to $a_l$al​, $a_{l+1}$al+1​, $\dots$…, $a_r$ar​ for some $l,r$l,r.
Suppose $m$m is some known constant. For any array, having $m$m or more elements, let’s define it’s beauty as the sum of $m$m largest elements of that array. For example:

• For array $x=[4,3,1,5,2]$x=[4,3,1,5,2] and $m=3$m=3, the $3$3 largest elements of $x$x are $5$5, $4$4 and $3$3, so the beauty of $x$x is $5+4+3=12$5+4+3=12.
• For array $x=[10,10,10]$x=[10,10,10] and $m=2$m=2, the beauty of $x$x is $10+10=20$10+10=20.

You are given an array $a_1,a_2,\dots ,a_n$a1​,a2​,…,an​, the value of the said constant $m$m and an integer $k$k. Your need to split the array $a$a into exactly $k$k subarrays such that:

• Each element from $a$a belongs to exactly one subarray.
• Each subarray has at least $m$m elements.
• The sum of all beauties of $k$k subarrays is maximum possible.

Input:

The first line contains three integers $n$n, $m$m and $k$k ( $2\le n\le 2\cdot 10^5$2≤n≤2⋅105, $1\le m$1≤m, $2\le k$2≤k, $m\cdot k\le n$m⋅k≤n) — the number of elements in $a$a, the constant $m$m in the definition of beauty and the number of subarrays to split to.
The second line contains $n$n integers $a_1,a_2,\dots ,a_n$a1​,a2​,…,an​ ( $-10^9\le a_i\le 10^9$−109≤ai​≤109).

Output

In the first line, print the maximum possible sum of the beauties of the subarrays in the optimal partition.
In the second line, print $k-1$k−1 integers $p_1,p_2,\dots ,p_{k-1}$p1​,p2​,…,pk−1​ ( $1\le p_1\&lt;p_2\&lt;\dots \&lt;p_{k-1}\&lt;n$1≤p1​<p2​<…<pk−1​<n) representing the partition of the array, in which:
All elements with indices from $1$1 to $p_1$p1​ belong to the first subarray. All elements with indices from $p_1+1$p1​+1 to $p_2$p2​ belong to the second subarray. $\dots$…. All elements with indices from $p_{k-1}+1$pk−1​+1 to $n$n belong to the last, $k$k-th subarray.If there are several optimal partitions, print any of them.

Sample Input:

9 2 3
5 2 5 2 4 1 1 3 2

Sample Output:

21
3 5

Sample Input:

6 1 4
4 1 3 2 2 3

Sample Output:

12
1 3 5

Sample Input:

2 1 2
-1000000000 1000000000

Sample Output:

0
1

题目链接

一个数列在 $m$m 限定下的的beauty是数列中最大的 $m$m 个数之和，现给出一个数列求此数列分为 $k$k 个连续子数列后每个子数列在限定 $m$m 下的beauty之和最大值，并输出子序列分组情况

显然最大值应该是数列中最大的 $mk$mk 个数之和，所以按照降序排序之后取前 $mk$mk 个数即为beauty之和最大值，分组就将这 $mk$mk 个数按照原数列下标升序排序后每 $m$m 个数分为一组即可

AC代码:

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

typedef long long ll;

int main(int argc, char *argv[]) {
    int N, M, K; scanf("%d%d%d", &N, &M, &K);
    vector<pair<ll, int> > A(N);
    for (int i = 0; i < N; ++i) {
        scanf("%lld", &A[i].first);
        A[i].second = i + 1;
    }
    sort(A.begin(), A.end());
    reverse(A.begin(), A.end());
    ll Ans = 0;
    for (int i = 0; i < M * K; ++i) Ans += A[i].first;
    printf("%lld\n", Ans);
    sort(A.begin(), A.begin() + M * K, [&](pair<ll, int> Key1, pair<ll, int> Key2) {return Key1.second < Key2.second;});
    for (int i = M - 1, k = 0; k < K - 1; i += M, ++k) printf("%d ", A[i].second);
    return 0;
}

C. Trailing Loves (or L’oeufs?)

Description:

The number “zero” is called “love” (or “l’oeuf” to be precise, literally means “egg” in French), for example when denoting the zero score in a game of tennis. Aki is fond of numbers, especially those with trailing zeros. For example, the number $9200$9200 has two trailing zeros. Aki thinks the more trailing zero digits a number has, the prettier it is.
However, Aki believes, that the number of trailing zeros of a number is not static, but depends on the base (radix) it is represented in. Thus, he considers a few scenarios with some numbers and bases. And now, since the numbers he used become quite bizarre, he asks you to help him to calculate the beauty of these numbers.
Given two integers $n$n and $b$b (in decimal notation), your task is to calculate the number of trailing zero digits in the $b$b-ary (in the base/radix of $b$b) representation of n! (factorial of $n$n).

Input:

number “zero” is called “love” (or “l’oeuf” to be precise, literally means “egg” in French), for example when denoting the zero score in a game of tennis.

Output

he only line of the input contains two integers $n$n and $b$b ( $1\le n\le 10^{18}$1≤n≤1018, $2\le b\le 10^{12}$2≤b≤1012).

Sample Input:

6 9

Sample Output:

1

Sample Input:

38 11

Sample Output:

3

Sample Input:

5 2

Sample Output:

3

Sample Input:

5 10

Sample Output:

1

题目链接

求 $n!$n! 在 $m$m 进制下末尾 $0$0 的个数

前一段训练赛还打过原题，但是那场没有补题就……

贴一下那道题目以及题解

末尾0的个数

首先你得知道在 $10$10 进制下 $n!$n! 有多少个零 （就是求 $5$5 出现的次数）
然后
假设 $m$m 可以分为若干个质因子相乘
$m=p_1^{k_1}\ast p_2^{k_2}\ast p_3^{k_3}\ast p_4^{k_4}$m=p1k1​​∗p2k2​​∗p3k3​​∗p4k4​​…（ $p_i$pi​ 质因子, $k_i$ki​ 质因子的次方）
那么答案就是 min(在 $n!$n! 中每个 $p_i$pi​ 出现的次数 $k_i$ki​ );

AC代码:

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

typedef long long ll;

ll Cal(ll X, ll N) {
    ll Ans = 0;
    while(N) {
        Ans += N / X;
        N /= X;
    }
    return Ans;
}

int main() {
    ll Ans = 1e18 + 10;
    ll N, M;
    scanf("%lld %lld", &N, &M);
    for(ll i = 2; i * i <= M; i++) {
        if(M % i == 0) {
            ll Cnt = 0;
            while(M % i == 0) M /= i, Cnt++;
            Ans = min(Ans, Cal(i, N) / Cnt);
        }
    }
    if(M > 1) Ans = min(Ans, Cal(M, N));
    printf("%lld\n", Ans);
    return 0;
}

D. Flood Fill

Description:

You are given a line of $n$n colored squares in a row, numbered from $1$1 to $n$n from left to right. The $i$i-th square initially has the color $c_i$ci​.
Let’s say, that two squares $i$i and $j$j belong to the same connected component if $c_i=c_j$ci​=cj​, and $c_i=c_k$ci​=ck​ for all $k$k satisfying $i\&lt;k\&lt;j$i<k<j. In other words, all squares on the segment from $i$i to $j$j should have the same color.
For example, the line $[3,3,3]$[3,3,3] has $1$1 connected component, while the line $[5,2,4,4]$[5,2,4,4] has $3$3 connected components.
The game “flood fill” is played on the given line as follows:
At the start of the game you pick any starting square (this is not counted as a turn). Then, in each game turn, change the color of the connected component containing the starting square to any other color. Find the minimum number of turns needed for the entire line to be changed into a single color.

Input:

The first line contains a single integer $n$n ( $1\le n\le 5000$1≤n≤5000) — the number of squares.
The second line contains integers $c_1,c_2,\dots ,c_n$c1​,c2​,…,cn​ ( $1\le c_i\le 5000$1≤ci​≤5000) — the initial colors of the squares.

Output

Print a single integer — the minimum number of the turns needed.

Sample Input:

4
5 2 2 1

Sample Output:

2

Sample Input:

8
4 5 2 2 1 3 5 5

Sample Output:

4

Sample Input:

1
4

Sample Output:

0

题目链接

一个数列中每次可以选择数字相同的连续子序列变为任意数字，求将数列中所有数字都变相同的最少操作次数

很显然的区间dp问题，但是赛时没时间写了……真的菜

显然原数列中数字相同的连续子序列不用变化，所以去重一下

之后考虑区间dp，枚举区间长度，在区间长度上继续枚举区间，状态转移就是
$dp\left[l\right]\left[r\right]\{\begin{array}{cc}dp[l+1][r-1]+1& \left(c\right[l]==c[r\left]\right)\\ \min \left(dp\right[l+1\left]\right[r],dp[l\left]\right[r-1\left]\right)+1& \left(c\right[l\left]\ne c\right[r\left]\right)\end{array}$dp[l][r]{dp[l+1][r−1]+1min(dp[l+1][r],dp[l][r−1])+1​(c[l]==c[r])(c[l]̸​=c[r])​

AC代码:

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

const int maxn = 5e3 + 5;
const int INF = 0x3f3f3f3f;

int N;
int C[maxn];
int Dp[maxn][maxn];

int main(int argc, char *argv[]) {
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i) scanf("%d", &C[i]);
    N = unique(C + 1, C + N + 1) - C - 1;
    for (int k = 1; k <= N; ++k) {
        for (int l = 0; l <= N; ++l) {
            int r = l + k;
            if (C[l] == C[r]) Dp[l][r] = Dp[l + 1][r - 1] + 1;
            else Dp[l][r] = min(Dp[l][r - 1], Dp[l + 1][r]) + 1;
        }
    }
    printf("%d\n", Dp[1][N]);
    return 0;
}

E. Arithmetic Progression

Description:

This is an interactive problem!
An arithmetic progression or arithmetic sequence is a sequence of integers such that the subtraction of element with its previous element ( $x_i-x_{i-1}$xi​−xi−1​, where $i\ge 2$i≥2) is constant — such difference is called a common difference of the sequence.
That is, an arithmetic progression is a sequence of form $x_i=x_1+(i-1)d$xi​=x1​+(i−1)d, where $d$d is a common difference of the sequence.
There is a secret list of $n$n integers $a_1,a_2,\dots ,a_n$a1​,a2​,…,an​.
It is guaranteed that all elements $a_1,a_2,\dots ,a_n$a1​,a2​,…,an​ are between $0$0 and $10^9$109, inclusive.
This list is special: if sorted in increasing order, it will form an arithmetic progression with positive common difference ( $d\&gt;0$d>0). For example, the list $[14,24,9,19]$[14,24,9,19] satisfies this requirement, after sorting it makes a list $[9,14,19,24]$[9,14,19,24], which can be produced as $x_n=9+5\cdot (n-1)$xn​=9+5⋅(n−1).
Also you are also given a device, which has a quite discharged battery, thus you can only use it to perform at most $60$60 queries of following two types:

• Given a value $i$i ( $1\le i\le n$1≤i≤n), the device will show the value of the $a_i$ai​.
• Given a value $x$x ( $0\le x\le 10^9$0≤x≤109), the device will return $1$1 if an element with a value strictly greater than $x$x exists, and it will return $0$0 otherwise.

Your can use this special device for at most $60$60 queries. Could you please find out the smallest element and the common difference of the sequence? That is, values $x_1$x1​ and $d$d in the definition of the arithmetic progression. Note that the array $a$a is not sorted.

Interaction:

actionThe interaction starts with a single integer $n$n ( $2\le n\le 10^6$2≤n≤106), the size of the list of integers.
Then you can make queries of two types:

• “? i” ( $1\le i\le n$1≤i≤n) — to get the value of $a_i$ai​.
• “> x” ( $0\le x\le 10^9$0≤x≤109) — to check whether there exists an element greater than $x$x

After the query read its result $r$r as an integer.

• For the first query type, the $r$r satisfies $0\le r\le 10^9$0≤r≤109.
• For the second query type, the $r$r is either $0$0 or $1$1.
• In case you make more than $60$60 queries or violated the number range in the queries, you will get a $r=-1$r=−1.
• If you terminate after receiving the -1, you will get the “Wrong answer” verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.

When you find out what the smallest element $x_1$x1​ and common difference $d$d, print

• "! $x_1$x1​ $d$d"

And quit after that. This query is not counted towards the $60$60 queries limit.
After printing any query do not forget to output end of line and flush the output. Otherwise you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

Hacks:

For hack, use the following format:
The first line should contain an integer $n$n ( $2\le n\le 10^6$2≤n≤106) — the list’s size.
The second line contains $n$n integers $a_1,a_2,\dots ,a_n$a1​,a2​,…,an​ ( $0\le a_i\le 10^9$0≤ai​≤109) — the elements of the list.
Also, after the sorting the list must form an arithmetic progression with positive common difference.

Sample Input:

4
0
1
14
24
9
19

Sample Output:

> 25
> 15
? 1
? 2
? 3
? 4
! 9 5

题目链接

一道交互题目，有一个 $n$n 个数的无序等差数列，可以用两种询问询问至多 $60$60 次，求等差数列首项和公差，两种询问分别为：

1. ? ! 代表询问数列中第 $i$i 个数的数值
2. > x 代表询问数列中严格大于 $x$x 数字的数量

交互题目无非就是二分、随机、倍增这么几种算法的考察，所以第二种询问显然是利用它来二分查找出数列中的最大值，最大查询次数不过 $\log 10^9=30$log109=30 次，然后用剩余查询次数随机地查询 $30$30 个数，最大值与其之差必定是公差 $d$d 的倍数，所以求 $30$30 次 $\gcd$gcd （最大公约数）就是公差，错误的概率很小（具体数据请移步官方题解）。

由于 $rand$rand 函数的上界为 $32767$32767 并不能随机到 $[1,n]$[1,n] 的所有数而且有毒瘤数据来卡这种情况，所以手写随机函数或者使用随机数 $mt19937$mt19937

std::mt19937

AC代码:

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

int main(int argc, char *argv[]) {
    int n; cin >> n;
    int query = 60, last;
    int left = 0, right = 1e9;
    while (left <= right) {
        int mid = (left + right) >> 1;
        cout << "> " << mid << endl;
        cout << flush;
        query--;
        int x; cin >> x;
        if (x) left = mid + 1;
        else {
            last = mid;
            right = mid - 1;
        }
    }
    mt19937 mt(time(NULL));
    int d = 0;
    while (query--) {
        cout << "? " << mt() % n + 1 << endl;
        cout << flush;
        int x; cin >> x;
        d = __gcd(d, last - x);
    }
    cout << "! " << last - (n - 1) * d << " " << d << endl;
    cout << flush;
    return 0;
}