# A. Polycarp’s Pockets

## 题目:

Polycarp has $n$ coins, the value of the $i$-th coin is ${a}_{i}$. Polycarp wants to distribute all the coins between his pockets, but he cannot put two coins with the same value into the same pocket.
For example, if Polycarp has got six coins represented as an array $a=\left[1,2,4,3,3,2\right]$, he can distribute the coins into two pockets as follows: $\left[1,2,3\right],\left[2,3,4\right]$.
Polycarp wants to distribute all the coins with the minimum number of used pockets. Help him to do that.

## Input:

The first line of the input contains one integer $n$ ($1\le n\le 100$) — the number of coins.
The second line of the input contains $n$ integers ${a}_{1},{a}_{2},\dots ,{a}_{n}$ ($1\le {a}_{i}\le 100$) — values of coins.

## Output

Print only one integer — the minimum number of pockets Polycarp needs to distribute all the coins so no two coins with the same value are put into the same pocket.

6
1 2 4 3 3 2

2

1
100

1

## AC代码:

#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
map<int, int> m;
int n;
int x;
int ans = -INF;
for (int i = 0; i < n; ++i) {
m[x]++;
if (m[x] > ans) {
ans = m[x];
}
}
printf("%d\n", ans);
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("gedit out.txt");
#endif
return 0;
}

# B. Binary String Constructing

## 题目:

You are given three integers $a$, $b$ and $x$. Your task is to construct a binary string $s$ of length $n=a+b$ such that there are exactly $a$ zeroes, exactly $b$ ones and exactly $x$ indices $i$ (where $1\le i) such that ${s}_{i}\ne {s}_{i+1}$. It is guaranteed that the answer always exists.
For example, for the string “01010” there are four indices $i$ such that $1\le i and ${s}_{i}\ne {s}_{i+1}$ ($i=1,2,3,4$). For the string “111001” there are two such indices $i$ ($i=3,5$).
Recall that binary string is a non-empty sequence of characters where each character is either 0 or 1.

## Input:

The first line of the input contains three integers $a$, $b$ and $x$ ($1\le a,b\le 100,1\le x.

## Output

Print only one string $s$, where $s$ is any binary string satisfying conditions described above. It is guaranteed that the answer always exists.

2 2 1

1100

3 3 3

101100

5 3 6

01010100

## AC代码:

#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int a, b, x;
if (x % 2) {
if (a > b) {
for (int i = 0; i < x / 2; ++i) {
cout << "01";
}
cout << string(a - x / 2, '0');
cout << string(b - x / 2, '1');
}
else {
for (int i = 0; i < x / 2; ++i) {
cout << "10";
}
cout << string(b - x / 2, '1');
cout << string(a - x / 2, '0');
}
}
else {
if (a > b) {
for (int i = 0; i < x / 2; ++i) {
cout << "01";
}
cout << string(b - x / 2, '1');
cout << string(a - x / 2, '0');
}
else {
for (int i = 0; i < x / 2; ++i) {
cout << "10";
}
cout << string(a - x / 2, '0');
cout << string(b - x / 2, '1');
}
}
printf("\n");
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("gedit out.txt");
#endif
return 0;
}

# C. Intense Heat

## 题目:

The heat during the last few days has been really intense. Scientists from all over the Berland study how the temperatures and weather change, and they claim that this summer is abnormally hot. But any scientific claim sounds a lot more reasonable if there are some numbers involved, so they have decided to actually calculate some value which would represent how high the temperatures are.
Mathematicians of Berland State University came up with a special heat intensity value. This value is calculated as follows:
Suppose we want to analyze the segment of $n$ consecutive days. We have measured the temperatures during these $n$ days; the temperature during $i$-th day equals ${a}_{i}$.
We denote the average temperature of a segment of some consecutive days as the arithmetic mean of the temperature measures during this segment of days. So, if we want to analyze the average temperature from day $x$ to day $y$, we calculate it as $\frac{\sum _{i=x}^{y}{a}_{i}}{y-x+1}$ (note that division is performed without any rounding). The heat intensity value is the maximum of average temperatures over all segments of not less than $k$ consecutive days. For example, if analyzing the measures $\left[3,4,1,2\right]$ and $k=3$, we are interested in segments $\left[3,4,1\right]$, $\left[4,1,2\right]$ and $\left[3,4,1,2\right]$ (we want to find the maximum value of average temperature over these segments).
You have been hired by Berland State University to write a program that would compute the heat intensity value of a given period of days. Are you up to this task?

## Input:

The first line contains two integers $n$ and $k$ ($1\le k\le n\le 5000$) — the number of days in the given period, and the minimum number of days in a segment we consider when calculating heat intensity value, respectively.
The second line contains $n$ integers ${a}_{1}$, ${a}_{2}$, …, ${a}_{n}$ ($1\le {a}_{i}\le 5000$) — the temperature measures during given $n$ days.

## Output

Print one real number — the heat intensity value, i. e., the maximum of average temperatures over all segments of not less than $k$ consecutive days.
Your answer will be considered correct if the following condition holds: $|res-re{s}_{0}|<{10}^{-6}$, where $res$ is your answer, and $re{s}_{0}$ is the answer given by the jury’s solution.

4 3
3 4 1 2

## Sample Output:

2.666666666666667

## AC代码:

#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int n, k;
vector<int> sum(n + 1);
sum = 0;
int x;
for (int i = 1; i <= n; ++i) {
sum[i] = sum[i - 1] + x;
}
double ans = -INF;
for (int i = 1; i <= n; ++i) {
for (int j = i + k - 1; j <= n; ++j) {
double temp = (double)(sum[j] - sum[i -1]) / (double)(j - i + 1);
ans = temp > ans ? temp : ans;
}
}
printf("%.15lf\n", ans);
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("gedit out.txt");
#endif
return 0;
}

# D. Coins and Queries

## 题目:

Polycarp has $n$ coins, the value of the $i$-th coin is ${a}_{i}$. It is guaranteed that all the values are integer powers of $2$ (i.e. ${a}_{i}={2}^{d}$ for some non-negative integer number $d$).
Polycarp wants to know answers on $q$ queries. The $j$-th query is described as integer number ${b}_{j}$. The answer to the query is the minimum number of coins that is necessary to obtain the value ${b}_{j}$ using some subset of coins (Polycarp can use only coins he has). If Polycarp can’t obtain the value ${b}_{j}$, the answer to the $j$-th query is -1.
The queries are independent (the answer on the query doesn’t affect Polycarp’s coins).

## Input:

The first line of the input contains two integers $n$ and $q$ ($1\le n,q\le 2\cdot {10}^{5}$) — the number of coins and the number of queries.
The second line of the input contains $n$ integers ${a}_{1},{a}_{2},\dots ,{a}_{n}$ — values of coins ($1\le {a}_{i}\le 2\cdot {10}^{9}$). It is guaranteed that all ${a}_{i}$ are integer powers of $2$ (i.e. ${a}_{i}={2}^{d}$ for some non-negative integer number $d$).
The next $q$ lines contain one integer each. The $j$-th line contains one integer ${b}_{j}$ — the value of the $j$-th query ($1\le {b}_{j}\le {10}^{9}$).

## Output

Print $q$ integers $an{s}_{j}$. The $j$-th integer must be equal to the answer on the $j$-th query. If Polycarp can’t obtain the value ${b}_{j}$ the answer to the $j$-th query is -1.

5 4
2 4 8 2 4
8
5
14
10

1
-1
3
2

## AC代码:

#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1e4+5;
const int mod = 1e6;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int n, q;
int x;
map<int, int> amount;
for (int i = 0; i < n; ++i) {
amount[x]++;
}
int cnt;
for (int i = 0; i < q; ++i) {
cnt = 0;
for (int j = 29; j >= 0; --j) {
int num = (1 << j);
if (num <= x) {
int temp = x / num;
if (temp <= amount[num]) {
cnt += temp;
x -= num * temp;
}
else {
cnt += amount[num];
x -= amount[num] * num;
}
}
}
if (!x) {
printf("%d\n", cnt);
}
else {
printf("-1\n");
}
}
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("gedit out.txt");
#endif
return 0;
}

# E. Tree Constructing

## 题目:

You are given three integers $n$, $d$ and $k$.
Your task is to construct an undirected tree on $n$ vertices with diameter $d$ and degree of each vertex at most $k$, or say that it is impossible.
An undirected tree is a connected undirected graph with $n-1$ edges.
Diameter of a tree is the maximum length of a simple path (a path in which each vertex appears at most once) between all pairs of vertices of this tree.
Degree of a vertex is the number of edges incident to this vertex (i.e. for a vertex $u$ it is the number of edges $\left(u,v\right)$ that belong to the tree, where $v$ is any other vertex of a tree).

## Input:

The first line of the input contains three integers $n$, $d$ and $k$ ($1\le n,d,k\le 4\cdot {10}^{5}$).

## Output

If there is no tree satisfying the conditions above, print only one word “NO” (without quotes).
Otherwise in the first line print “YES” (without quotes), and then print $n-1$ lines describing edges of a tree satisfying the conditions above. Vertices of the tree must be numbered from $1$ to $n$. You can print edges and vertices connected by an edge in any order. If there are multiple answers, print any of them.1

6 3 3

YES
3 1
4 1
1 2
5 2
2 6

6 2 3

NO

10 4 3

YES
2 9
2 10
10 3
3 1
6 10
8 2
4 3
5 6
6 7

8 5 3

YES
2 5
7 2
3 7
3 1
1 6
8 7
4 3

## AC代码:

#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 4e5+5;
const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int n, d, k;
if (d >= n) {
printf("NO\n");
return 0;
}
// 度数
vector<int> deg(n);
// 连接结果
vector<PII> ans;
// 顶点和直径
set<PII> q;
for (int i = 0; i < d; ++i) {
++deg[i];
++deg[i + 1];
if (deg[i] > k || deg[i + 1] > k) {
printf("NO\n");
return 0;
}
ans.pb(mp(i, i + 1));
}
// 以此插入顶点和顶点直径
for (int i = 1; i < d; ++i) {
q.insert(mp(max(i, d - i), i));
}
for (int i = d + 1; i < n; ++i) {
// 若有顶点且不可再连，移除
while (!q.empty() && deg[q.begin() -> second] == k) {
q.erase(q.begin());
}
// 若无顶点可连或可连顶点直径为最大值，无解
if (q.empty() || q.begin() -> first == d) {
printf("NO\n");
return 0;
}
++deg[i];
++deg[q.begin() -> second];
ans.pb(mp(i, q.begin() -> second));
q.insert(mp(q.begin() -> first + 1, i));
}
printf("YES\n");
for (int i = 0; i < n - 1; ++i) {
printf("%d %d\n", ans[i].first + 1, ans[i].second + 1);
}
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("gedit out.txt");
#endif
return 0;
}

# F. Abbreviation

## 题目:

You are given a text consisting of $n$ space-separated words. There is exactly one space character between any pair of adjacent words. There are no spaces before the first word and no spaces after the last word. The length of text is the number of letters and spaces in it. ${w}_{i}$ is the $i$-th word of text. All words consist only of lowercase Latin letters.
Let’s denote a segment of words $w\left[i..j\right]$ as a sequence of words ${w}_{i},{w}_{i+1},\dots ,{w}_{j}$. Two segments of words $w\left[{i}_{1}..{j}_{1}\right]$ and $w\left[{i}_{2}..{j}_{2}\right]$ are considered equal if ${j}_{1}-{i}_{1}={j}_{2}-{i}_{2}$, ${j}_{1}\ge {i}_{1}$, ${j}_{2}\ge {i}_{2}$, and for every $t\in \left[0,{j}_{1}-{i}_{1}\right]$ ${w}_{{i}_{1}+t}={w}_{{i}_{2}+t}$. For example, for the text “to be or not to be” the segments $w\left[1..2\right]$ and $w\left[5..6\right]$ are equal, they correspond to the words “to be”.
An abbreviation is a replacement of some segments of words with their first uppercase letters. In order to perform an abbreviation, you have to choose at least two non-intersecting equal segments of words, and replace each chosen segment with the string consisting of first letters of the words in the segment (written in uppercase). For example, for the text “a ab a a b ab a a b c” you can replace segments of words $w\left[2..4\right]$ and $w\left[6..8\right]$ with an abbreviation “AAA” and obtain the text “a AAA b AAA b c”, or you can replace segments of words $w\left[2..5\right]$ and $w\left[6..9\right]$ with an abbreviation “AAAB” and obtain the text “a AAAB AAAB c”.
What is the minimum length of the text after at most one abbreviation?

## Input:

The first line of the input contains one integer $n$ ($1\le n\le 300$) — the number of words in the text.
The next line contains $n$ space-separated words of the text ${w}_{1},{w}_{2},\dots ,{w}_{n}$. Each word consists only of lowercase Latin letters.
It is guaranteed that the length of text does not exceed ${10}^{5}$.

## Output

Print one integer — the minimum length of the text after at most one abbreviation.

## Sample Input:

6
to be or not to be

12

## Sample Input:

10
a ab a a b ab a a b c

13

## Sample Input:

6
aa bb aa aa bb bb

## Sample Output:

11

### 题目链接 ## AC代码:

#include <bits/stdc++.h>

using namespace std;

const int N = 303;

int n;
bool eq[N][N];
int dp[N][N];
string s[N];

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif

cin >> n;
int allsum = n - 1;
for (int i = 0; i < n; ++i) {
cin >> s[i];
allsum += s[i].size();
}

for (int i = 0; i < n; ++i) {
eq[i][i] = true;
for (int j = 0; j < i; ++j) {
eq[i][j] = eq[j][i] = s[i] == s[j];
}
}

for (int i = n - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (eq[i][j]) {
if (i + 1 < n && j + 1 < n)
dp[i][j] = dp[i + 1][j + 1] + 1;
else
dp[i][j] = 1;
}
}
}

int ans = allsum;
for (int i = 0; i < n; ++i) {
int sum = 0;
for (int j = 0; i + j < n; ++j) {
sum += s[i + j].size();
int cnt = 1;
for (int pos = i + j + 1; pos < n; ++pos) {
if (dp[i][pos] > j) {
++cnt;
pos += j;
}
}
int cur = allsum - sum * cnt + (j + 1) * cnt - j * cnt;
if (cnt > 1 && ans > cur) {
ans = cur;
}
}
}

cout << ans << endl;

return 0;
}

### phpstudy的mysql版本升级至5.7

phpstudy安装的mysql版本一般都是5.5或5.4的，但是有时候做项目又必须用到mysql5.7版本，所以我们现在来看一下如何在phpstudy的环境下将mysql版本升级至5.7   温馨提醒： 先删掉所有环境变量，如果是之前有的话，不然怎么安装cmd上指向的还是原来的版本。安装完再设新的环境变量。 并且卸载掉mysqld服务mysqld remove。如果不先删除的话，可能会...

### java乐观锁和悲观锁最底层的实现

1. CAS实现的乐观锁 CAS（Compare And Swap 比较并且替换）是乐观锁的一种实现方式，是一种轻量级锁，JUC 中很多工具类的实现就是基于 CAS 的，也可以理解为自旋锁 JUC是指import java.util.concurrent下面的包， 比如：import java.util.concurrent.atomic.AtomicInteger; 最终实现是汇编指令：lock...

### 常用的伪类选择器

CSS选择器众多 CSS选择器及权重计算 最常用的莫过于类选择器，其它的相对用的就不会那么多了，当然属性选择器和为类选择器用的也会比较多，这里我们就常用的伪类选择器来讲一讲。 什么是伪类选择器？ CSS伪类是用来添加一些选择器的特殊效果。 常用的为类选择器 状态伪类 我们中最常见的为类选择器就是a标签（链接）上的为类选择器。 当我们使用它们的时候，需要遵循一定的顺序问题，否则将可能出现bug 注意...

### 1．写一个程序，提示输入两个字符串，然后进行比较，输出较小的字符串。考试复习题库1|要求：只能使用单字符比较操作。

1．写一个程序，提示输入两个字符串，然后进行比较，输出较小的字符串。 要求只能使用单字符比较操作。 参考代码： 实验结果截图：...