A. Sasha and His Trip

Description:

Sasha is a very happy guy, that’s why he is always on the move. There are $n$n cities in the country where Sasha lives. They are all located on one straight line, and for convenience, they are numbered from $1$1 to $n$n in increasing order. The distance between any two adjacent cities is equal to $1$1 kilometer. Since all roads in the country are directed, it’s possible to reach the city $y$y from the city $x$x only if $x\&lt;y$x<y.
Once Sasha decided to go on a trip around the country and to visit all $n$n cities. He will move with the help of his car, Cheetah-2677. The tank capacity of this model is $v$v liters, and it spends exactly $1$1 liter of fuel for $1$1 kilometer of the way. At the beginning of the journey, the tank is empty. Sasha is located in the city with the number $1$1 and wants to get to the city with the number $n$n. There is a gas station in each city. In the $i$i-th city, the price of $1$1 liter of fuel is $i$i dollars. It is obvious that at any moment of time, the tank can contain at most $v$v liters of fuel.
Sasha doesn’t like to waste money, that’s why he wants to know what is the minimum amount of money is needed to finish the trip if he can buy fuel in any city he wants. Help him to figure it out!

Input:

The first line contains two integers $n$n and $v$v ( $2\le n\le 100$2≤n≤100, $1\le v\le 100$1≤v≤100)  — the number of cities in the country and the capacity of the tank.

Output

Print one integer — the minimum amount of money that is needed to finish the trip.

Sample Input:

4 2

Sample Output:

4

Sample Input:

7 6

Sample Output:

6

题目链接

$1-n$1−n 个车站每个车站加油费用与车站编号相同，现有一辆邮箱容量为 $v$v 的车，求 $1$1 到 $n$n 的最小加油费用。

贪心地在尽量靠前的位置不断把油箱加满

AC代码:

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

int main(int argc, char *argv[]) {
    int n, v; cin >> n >> v;
    int ans = min(n - 1, v);
    if (n - 1 > v) {
        for (int i = 2, k = 0; k < n - 1 - v; ++k, ++i) ans += i;
    }
    cout << ans << endl;
    return 0;
}

B. Sasha and Magnetic Machines

Description:

One day Sasha visited the farmer 2D and his famous magnetic farm. On this farm, the crop grows due to the influence of a special magnetic field. Maintaining of the magnetic field is provided by $n$n machines, and the power of the $i$i-th machine is $a_i$ai​.
This year 2D decided to cultivate a new culture, but what exactly he didn’t say. For the successful growth of the new culture, it is necessary to slightly change the powers of the machines. 2D can at most once choose an arbitrary integer $x$x, then choose one machine and reduce the power of its machine by $x$x times, and at the same time increase the power of one another machine by $x$x times (powers of all the machines must stay positive integers). Note that he may not do that if he wants. More formally, 2D can choose two such indices $i$i and $j$j, and one integer $x$x such that $x$x is a divisor of $a_i$ai​, and change powers as following: $a_i=\frac{a_i}{x}$ai​=xai​​, $a_j=a_j\cdot x$aj​=aj​⋅x
Sasha is very curious, that’s why he wants to calculate the minimum total power the farmer can reach. There are too many machines, and Sasha can’t cope with computations, help him!

Input:

The first line contains one integer $n$n ( $2\le n\le 5\cdot 10^4$2≤n≤5⋅104) — the number of machines.
The second line contains $n$n integers $a_1,a_2,\dots ,a_n$a1​,a2​,…,an​ ( $1\le a_i\le 100$1≤ai​≤100) — the powers of the machines.

Output

Print one integer — minimum total power.

Sample Input:

5
1 2 3 4 5

Sample Output:

14

Sample Input:

4
4 2 4 4

Sample Output:

14

Sample Input:

5
2 4 2 3 7

Sample Output:

18

题目链接

$n$n 个数地数列，现令一个数乘 $k$k 并同时让另一个数（可被 $k$k 整除）除 $k$k ，求数列和的最小值

暴力枚举即可

AC代码:

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

int main(int argc, char *argv[]) {
    int n; cin >> n;
    map<int, int> cnt;
    ll sum = 0, ans = 0;
    for (int i = 0, x; i < n; ++i) {
        cin >> x;
        sum += x;
        cnt[x]++;
    }
    for (int i = 1; i <= 100; ++i)
        for (int j = i; j <= 100; ++j)
            for (int k = 2; k <= 100; ++k)
                if (((j == i && cnt[i] > 1) || (j != i && cnt[i] && cnt[j])) && j % k == 0)
                    ans = max(ans, (ll)(j - j / k) - (i * k - i));
    ans = sum - ans;
    cout << ans << endl;
    return 0;
}

C. Sasha and a Bit of Relax

Description:

Sasha likes programming. Once, during a very long contest, Sasha decided that he was a bit tired and needed to relax. So he did. But since Sasha isn’t an ordinary guy, he prefers to relax unusually. During leisure time Sasha likes to upsolve unsolved problems because upsolving is very useful.
Therefore, Sasha decided to upsolve the following problem:
You have an array $a$a with $n$n integers. You need to count the number of funny pairs $(l,r)$(l,r) $(l\le r)$(l≤r). To check if a pair $(l,r)$(l,r) is a funny pair, take $mid=\frac{l+r-1}{2}$mid=2l+r−1​, then if $r-l+1$r−l+1 is an even number and $a_l\oplus a_{l+1}\oplus \dots \oplus a_{mid}=a_{mid+1}\oplus a_{mid+2}\oplus \dots \oplus a_r$al​⊕al+1​⊕…⊕amid​=amid+1​⊕amid+2​⊕…⊕ar​, then the pair is funny. In other words, $\oplus$⊕ of elements of the left half of the subarray from $l$l to $r$r should be equal to $\oplus$⊕ of elements of the right half. Note that $\oplus$⊕ denotes the bitwise XOR operation.
It is time to continue solving the contest, so Sasha asked you to solve this task.

Input:

The first line contains one integer $n$n ( $2\le n\le 3\cdot 10^5$2≤n≤3⋅105) — the size of the array.
The second line contains $n$n integers $a_1,a_2,\dots ,a_n$a1​,a2​,…,an​ ( $0\le a_i\&lt;2^{20}$0≤ai​<220) — array itself.

Output

Print one integer — the number of funny pairs. You should consider only pairs where $r-l+1$r−l+1 is even number.

Sample Input:

5
1 2 3 4 5

Sample Output:

1

Sample Input:

6
3 2 2 3 7 6

Sample Output:

3

Sample Input:

3
42 4 2

Sample Output:

0

题目链接

在一个 $n$n 个数的数列内求 $[l,r]$[l,r] 间 $mid=\frac{l+r-1}{2}$mid=2l+r−1​ 满足 $a_l\oplus a_{l+1}\oplus \dots \oplus a_{mid}=a_{mid+1}\oplus a_{mid+2}\oplus \dots \oplus a_r$al​⊕al+1​⊕…⊕amid​=amid+1​⊕amid+2​⊕…⊕ar​ 的偶数长度区间数量。

观察易得满足要求的区间内所有数 $\oplus$⊕ 值为 $0$0 ，所以利用前缀和计数即可

AC代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = (1 << 20) + 5;

int N;
int Cur;
int Cnt[maxn][2];
ll Ans;

int main(int argc, char *argv[]) {
    scanf("%d", &N);
    Cnt[0][1] = 1;
    for (int i = 0, X; i < N; ++i) {
        scanf("%d", &X);
        Cur ^= X;
        Ans += Cnt[Cur][i & 1]++;
    }
    printf("%lld\n", Ans);
    return 0;
}

D. Sasha and One More Name

Description:

Reading books is one of Sasha’s passions. Once while he was reading one book, he became acquainted with an unusual character. The character told about himself like that: “Many are my names in many countries. Mithrandir among the Elves, Tharkûn to the Dwarves, Olórin I was in my youth in the West that is forgotten, in the South Incánus, in the North Gandalf; to the East I go not.”
And at that moment Sasha thought, how would that character be called in the East? In the East all names are palindromes. A string is a palindrome if it reads the same backward as forward. For example, such strings as “kazak”, “oo” and “r” are palindromes, but strings “abb” and “ij” are not.
Sasha believed that the hero would be named after one of the gods of the East. As long as there couldn’t be two equal names, so in the East people did the following: they wrote the original name as a string on a piece of paper, then cut the paper minimum number of times $k$k, so they got $k+1$k+1 pieces of paper with substrings of the initial string, and then unite those pieces together to get a new string. Pieces couldn’t be turned over, they could be shuffled.
In this way, it’s possible to achive a string abcdefg from the string f|de|abc|g using $3$3 cuts (by swapping papers with substrings f and abc). The string cbadefg can’t be received using the same cuts.
More formally, Sasha wants for the given palindrome $s$s find such minimum $k$k, that you can cut this string into $k+1$k+1 parts, and then unite them in such a way that the final string will be a palindrome and it won’t be equal to the initial string $s$s. It there is no answer, then print “Impossible” (without quotes).

Input:

The first line contains one string $s$s ( 1≤∣s∣≤5000) — the initial name, which consists only of lowercase Latin letters. It is guaranteed that $s$s is a palindrome.

Output

Print one integer $k$k — the minimum number of cuts needed to get a new name, or “Impossible” (without quotes).

Sample Input:

nolon

Sample Output:

2

Sample Input:

otto

Sample Output:

1

Sample Input:

qqqq

Sample Output:

Impossible

Sample Input:

kinnikkinnik

Sample Output:

1

题目链接

求一个回文串最少切断几次可以重新拼接为和原来不同的回文串

若回文串除中心位其余字符全都一样直接输出 Impossible

否则就暴力枚举切开位置暴力拼接字符串进行判断

若还无法利用一次切断找到符合要求的字符串则直接输出2即可

因为一个回文串最多被切断2次可重新拼接为和原字符串不同的回文串

AC代码:

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

int main(int argc, char *argv[]) {
    string s; cin >> s;
    bool flag = true;
    for (int i = 0; i < s.size() / 2; ++i)
        if (s[0] != s[i] || s[0] != s[s.size() - i - 1])
            flag = false;
    if (flag) {
        cout << "Impossible" << endl;
        return 0;
    }
    string t;
    for (int i = 0; i < s.size(); ++i) {
        t = s.substr(i) + s.substr(0, i);
        if (t == s) continue;
        flag = true;
        for (int j = 0; j <= t.size() / 2; ++j)
            if (t[j] != t[t.size() - j - 1])
                flag = false;
        if (flag) {
            cout << 1 << endl;
            return 0;
        }
    }
    cout << 2 << endl;
    return 0;
}