Hello, everyone, what I bring to you today is Codeforces Round #734 (Div. 3) Explain the whole topic.
Link to this article: https://www.lanqiao.cn/questions/204012
Thank Lqyk students of blue bridge cloud class for their solutions.
A. Polycarp and Coins
Title Link
https://codeforces.com/contest/1551/problem/A
General idea of the topic
A man paid only one yuan and two yuan for shopping. Now he has to pay n n n yuan. The difference between the amount of one yuan and the amount of two yuan should be the smallest. Ask him to pay n n How much did n yuan use, one yuan and two yuan?
Problem solving ideas
If the difference is the smallest, the quantity ratio of one yuan to two yuan should be close 1 : 1 1 : 1 1: 1. Then it's three yuan in total, and each one will be used n / 3 n / 3 n/3, finally, just judge what the rest of the money is 0 , 1 , 2 0, 1, 2 0,1,2 yuan is enough.
AC_Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
std::ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--){
ll n;
cin >> n;
ll a = n / 3;
ll b = n / 3;
if(n % 3 == 2) b++;
else if(n % 3 == 1) a++;
cout << a << " " << b << endl;
}
return 0;
}
B1. Wonderful Coloring - 1
Title Link
https://codeforces.com/contest/1551/problem/B1
General idea of the topic
-
n n n# characters are either dyed red and green or not.
-
Two characters of the same color are different.
-
Red and green have the same number of characters.
If the above three conditions are met, what is the number of characters dyed in each color?
Problem solving ideas
Each color of the same character can be dyed at most one, so just discuss the characters that appear $\ geq 2 $and the characters that appear once respectively.
- The number of occurrences of $\ geq 2 $characters, each color can be divided into one, and the answer is added with the number of types of these characters.
- If it appears once, red one and green one, add the number of these character types to the answer divided by two (rounded down).
AC_Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
std::ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--){
string s;
cin >> s;
map<char, int> mp;
int ans = 0;
for(int i = 0;i < s.size();i++) mp[s[i]]++;
int cnt = 0;
for(auto i : mp){
if(i.second >= 2) ans++;
else cnt++;
}
cout << ans + cnt / 2 << endl;
}
return 0;
}
B2. Wonderful Coloring - 2
Title Link
https://codeforces.com/contest/1551/problem/B2
General idea of the topic
-
n n n numbers, dyed k k k) colors, or no dyeing.
-
Numbers of the same color have different values.
-
be-all k k The number of numbers for the k colors should be the same.
-
The number of dyed numbers is the largest.
use 0 − k 0 - k 0 − k indicates the color type of dyeing( 0 0 0 means no dyeing), find the dyeing scheme that meets the above conditions.
Problem solving ideas
and B 1 B1 In the same way as B1, consider the number of occurrences $\ geq k $and the number of occurrences < k < k < K are discussed separately.
- Each color can be divided into one character with occurrence times $\ geq k $, so the position can be stored and dyed directly.
- Number of occurrences < k < k < K ， are gathered together. In order to prevent the same numbers from dyeing the same color, the subscripts are dyed in order.
AC_Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 50;
struct node{
int id, val;
bool operator < (const node &p) const{
return val < p.val;
}
};
vector<int> num[maxn]; //Count the number of times a number appears
vector<node> q; //Numbers < K in the set
int main()
{
std::ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--){
int n, k;
cin >> n >> k;
vector<int> ans(n + 1, 0), vis(n + 1, 0), a(n + 1);
for(int i = 1;i <= n;i++) num[i].clear(); q.clear();
for(int i = 1;i <= n;i++){
cin >> a[i];
num[a[i]].push_back(i);
}
for(int i = 1;i <= n;i++){
if(num[i].size() >= k){
for(int j = 0;j < num[i].size();j++){
ans[num[i][j]] = j + 1;
}
vis[i] = 1;//Flag > = k
}
}
for(int i = 1;i <= n;i++){
if(!vis[a[i]]){
q.push_back({i, a[i]});
}
}
sort(q.begin(), q.end());
int sum = q.size() / k * k, v = 1;//Round and dye from 1
for(int i = 0;i < sum;i++){
ans[q[i].id] = v++;
if(v == k + 1) v = 1;
}
for(int i = 1;i <= n;i++){
if(ans[i] > k) cout << 0 << " ";//More than K is more, and it is not stained
else cout << ans[i] << " ";
}
cout << endl;
}
return 0;
}
C. Interesting Story
Title Link
https://codeforces.com/contest/1551/problem/C
General idea of the topic
from n n n contains only a , b , c , d , e a,b,c,d,e a. Select several strings from b, c, d and e, so that the number of occurrences of a single character is greater than the sum of the other four. Ask how many strings can be selected at most.
Problem solving ideas
We can record each string a , b , c , d , e a,b,c,d,e a. The number of occurrences of b, c, d and e, and then enumerate a , b , c , d , e a,b,c,d,e a. b, c, d and e are regarded as the cases that are greater than the sum of the other four characters.
Assume current enumeration a a a section i i i strings a a a the number of occurrences is s u m sum Sum, the sum of the other four is n o w now now, then their difference s u m − n o w sum - now When sum − now is positive, we can choose. In order to choose more, we will be greedy s u m − n o w sum - now The value of sum − now is sorted from large to small, and the string is continuously added to keep the total $\ geq 0 $.
AC code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 50;
int a[maxn], b[maxn], c[maxn], d[maxn], e[maxn];
int n;
int get_a(){
vector<ll> ans;
for(int i = 0;i < n;i++){
ll sum = a[i];
ll now = b[i] + c[i] + d[i] + e[i];
ans.push_back(sum - now);
}
sort(ans.rbegin(), ans.rend());
ll k = 0;
int cnt = 0;
for(int i = 0;i < n;i++){
if(k + ans[i] > 0LL) {
cnt++;
k += ans[i];
}
else break;
}
return cnt;
}
int get_b(){
vector<ll> ans;
for(int i = 0;i < n;i++){
ll sum = b[i];
ll now = a[i] + c[i] + d[i] + e[i];
ans.push_back(sum - now);
}
sort(ans.rbegin(), ans.rend());
ll k = 0;
int cnt = 0;
for(int i = 0;i < n;i++){
if(k + ans[i] > 0LL) {
cnt++;
k += ans[i];
}
else break;
}
return cnt;
}
int get_c(){
vector<ll> ans;
for(int i = 0;i < n;i++){
ll sum = c[i];
ll now = a[i] + b[i] + d[i] + e[i];
ans.push_back(sum - now);
}
sort(ans.rbegin(), ans.rend());
ll k = 0;
int cnt = 0;
for(int i = 0;i < n;i++){
if(k + ans[i] > 0LL) {
cnt++;
k += ans[i];
}
else break;
}
return cnt;
}
int get_d(){
vector<ll> ans;
for(int i = 0;i < n;i++){
ll sum = d[i];
ll now = a[i] + b[i] + c[i] + e[i];
ans.push_back(sum - now);
}
sort(ans.rbegin(), ans.rend());
ll k = 0;
int cnt = 0;
for(int i = 0;i < n;i++){
if(k + ans[i] > 0LL) {
cnt++;
k += ans[i];
}
else break;
}
return cnt;
}
int get_e(){
vector<ll> ans;
for(int i = 0;i < n;i++){
ll sum = e[i];
ll now = a[i] + b[i] + c[i] + d[i];
ans.push_back(sum - now);
}
sort(ans.rbegin(), ans.rend());
ll k = 0;
int cnt = 0;
for(int i = 0;i < n;i++){
if(k + ans[i] > 0LL) {
cnt++;
k += ans[i];
}
else break;
}
return cnt;
}
int main()
{
std::ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--){
cin >> n;
for(int i = 0;i <= n;i++) a[i] = b[i] = c[i] = d[i]= e[i] = 0;
for(int i = 0;i < n;i++){
string s;
cin >> s;
for(int j = 0; j < s.size();j++){
if(s[j] == 'a') a[i]++;
else if(s[j] == 'b') b[i]++;
else if(s[j] == 'c') c[i]++;
else if(s[j] == 'd') d[i]++;
else if(s[j] == 'e') e[i]++;
}
}
int ans = 0;
ans = max(ans, get_a());
ans = max(ans, get_b());
ans = max(ans, get_c());
ans = max(ans, get_d());
ans = max(ans, get_e());
cout << ans << endl;
}
return 0;
}
D1. Domino (easy version)
Title Link
https://codeforces.com/contest/1551/problem/D1
General idea of the topic
Place in the grid of $n * m $ 1 × 2 1\times2 one × 2 (horizontal) or 2 × 1 2\times1 two × 1 (vertical) dominoes, in n ∗ m n * m If n * m is an even number, can it be placed exactly k k k horizontal dominoes.
Problem solving ideas
Consider why the meaning of the question is n ∗ m n*m n * m are even numbers, not n , m n,m n. m is even.
When n , m n,m n. When m ， are even, 2 × 2 2\times2 two × You can put $2 $in any square of 2 $ 1 × 2 1\times2 one × 2 transverse or 2 × 1 2 \times 1 two × 1 ￠ vertical, and they all appear in even pairs, so we can divide the surface into several 2 × 2 2\times2 two × 2 grid, at this time k k k is an even number to satisfy the condition.
Suppose if n n n is an odd number. It is not difficult to find it when drawing. It must be put m / 2 m/2 m/2 horizontal, similarly, if m m m is an odd number and must be placed n / 2 n / 2 n/2 vertical rows and columns are covered with horizontal or vertical rows and columns, which will be transformed into even numbers.
So as long as you judge whether you always have to subtract what must be put can be put down k k k ， and k k k ， it shall be greater than the quantity that must be laid horizontally.
AC_Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
std::ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--){
int n, m, k;
cin >> n >> m >> k;
int tot = n * m / 2;
if(n % 2){
k -= m / 2;
tot -= m / 2;
}
if(m % 2) tot -= n / 2;
if(k < 0 || k % 2 || k > tot){
cout << "NO\n";
continue;
}
cout << "YES\n";
}
return 0;
}
D2. Domino (hard version)
Title Link
https://codeforces.com/contest/1551/problem/D2
General idea of the topic
Place in the grid of $n \times m $ 1 × 2 1\times2 one × 2 (horizontal) or 2 × 1 2\times1 two × 1 (vertical) dominoes, in n × m n \times m n × If m is an even number, can it be placed exactly k k k horizontal dominoes, with character output placement patterns.
Problem solving ideas
D 1 D1 After the idea of D1 can be discussed, it can be constructed separately according to the discussion.
First, judge whether there are odd rows and columns a − z a - z a − z - fill in any two characters.
Then delete these rows and columns temporarily and fill them as $n and M $are even numbers.
Fill first k k k ， horizontal, the rest 2 × 2 2\times2 two × The only problem is that adjacent characters will repeat. We can alternately fill different characters according to the parity relationship of subscripts. Of course, the characters from a − z a - z a − z choose by yourself.
AC_Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 200;
char ans[maxn][maxn];
int main()
{
std::ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--){
int n, m, k;
cin >> n >> m >> k;
int tot = n * m / 2;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
ans[i][j] = '#';
}
}
int nn = n, mm = m;
if(n % 2){
k -= m / 2;
tot -= m / 2;
int cnt = 1;
for(int j = 1;j <= m;j += 2){//The last line is full of horizontal
if(cnt % 2) ans[n][j] = ans[n][j + 1] = 'o';
else ans[n][j] = ans[n][j + 1] = 'p';
cnt++;
}
n--;
}
if(m % 2){
tot -= n / 2;
int cnt = 1;
for(int i = 1;i <= n;i += 2){
if(cnt % 2) ans[i][m] = ans[i + 1][m] = 'x';
else ans[i][m] = ans[i + 1][m] = 'y';
cnt++;
}
m--;
}
if(k < 0 || k % 2 || k > tot){
cout << "NO\n";
continue;
}
int cnt = 1;
for(int j = 1;j <= m;j += 2){
cnt ++;
for(int i = 1;i <= n;i++){
if(k != 0){
if((i + cnt) & 1) ans[i][j] = ans[i][j + 1] = 'a';
else ans[i][j] = ans[i][j + 1] = 'b';
k--;
}
if(!k) break;
}
if(!k) break;
}
for(int i = 1;i <= n;i += 2){
cnt++;
for(int j = 1;j <= m;j++){
if(ans[i][j] == '#'){
if((j + cnt) & 1) ans[i][j] = ans[i + 1][j] = 'k';
else ans[i][j] = ans[i + 1][j] = 'v';
}
}
}
cout << "YES\n";
for(int i = 1;i <= nn;i++){
for(int j = 1;j <= mm;j++){
cout << ans[i][j];
}
cout << endl;
}
}
return 0;
}
E. Fixed Points
Title Link
https://codeforces.com/contest/1551/problem/E
General idea of the topic
Given a length of n n Array of n a a A and a constant k k k.
There is an existing operation. The operation content is to select an array a a Any number in a a i a_i ai # and delete it, after deletion a i a_i ai ， all the numbers on the right will move one bit to the right, i.e a i − 1 , a i ， a i + 1 , a i + 2 , . . . , a n → a i − 1 , a i + 1 , a i + 2 , a i + 3 , . . . , a n a_{i-1},a_i，a_{i+1},a_{i+2},...,a_n\rightarrow a_{i-1},a_{i+1},a_{i+2},a_{i+3},...,a_{n} ai−1,ai，ai+1,ai+2,...,an→ai−1,ai+1,ai+2,ai+3,...,an.
definition b 1 , b 2 , . . . , b m b_1,b_2,...,b_m b1,b2,..., bm is a a a for the array after several operations, ask how many operations should be performed at least, so that b i = i b_i=i The number of bi = i is greater than or equal to k k k.
Problem solving ideas
Because the data range of this question is not large 1 ≤ k ≤ n ≤ 2 × 1 0 3 1\leq k\leq n\leq 2\times10^3 1≤k≤n≤2 × 103, so it's not hard to think of using it d p dp dp to solve.
definition f i , j f_{i,j} fi,j ， denotes an array a a Front of a i i i number, deleted j j After j months, b h = h ( 1 ≤ h ≤ i ) b_h=h(1\leq h\leq i) bh = maximum number of h(1 ≤ h ≤ i).
So the current number a i a_i ai, there are two kinds of decisions:
- delete a i a_i ai: delete a i a_i After ai a i a_i ai brings any contribution, i.e f i , j = f i − 1 , j − 1 f_{i,j} = f_{i-1,j-1} fi,j=fi−1,j−1.
- Do not delete a i a_i ai: it has been deleted at this time j j j number, then a i a_i The location of ai # is i − j i-j i − j, so f i , j = f i − 1 , j + [ a i = = i − j ] f_{i,j} = f_{i-1,j} + [a_i == i-j] fi,j=fi−1,j+[ai==i−j]
Finally, the number of deleted items is enumerated from small to large j j j. If f n , j ≥ k f_{n,j} \geq k fn,j ≥ k, then the j j j is the answer.
AC_Code
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
int n , k , a[N], f[N][N];
signed main()
{
int T = 1;
cin >> T;
while(T --)
{
cin >> n >> k;
memset(f , 0 , sizeof(int) * n * n);
for(int i = 1 ; i <= n ; i ++) cin >> a[i];
for(int i = 1 ; i <= n ; i ++)
{
for(int j = 0 ; j <= i ; j ++)
{
if(!j) f[i][j] = f[i - 1][j] + (a[i] == i - j);
else f[i][j] = max(f[i - 1][j - 1], f[i - 1][j] + (a[i] == i - j));
}
}
bool flag = 0;
for(int j = 0 ; j <= n ; j ++) if(f[n][j] >= k)
{
cout << j << '\n';
flag = 1;
break ;
}
if(!flag) cout << -1 << '\n';
}
return 0;
}
F. Equidistant Vertices
Title Link
https://codeforces.com/contest/1551/problem/F
General idea of the topic
Given a containing n n n-node tree and a constant K K K. Ask you to choose from the tree K K K nodes are put into the set so that the distance between any two points in the set is equal. How many different selection methods are there.
Problem solving ideas
- When K = 2 K = 2 When K=2, no matter how selected, there is only one distance in the set, which meets the conditions, so the answer is C n 2 C_{n}^{2} Cn2.
- When K > 2 K > 2 K> 2, there must be a point u u u. So that the points in the set are located in u u On different branches of u, and to u u The distance of u is equal (the proof is omitted). We define this u u u is the center of the collection
We take u u u as the center of the set, enumerate the points in the set to u u u, set the distance of the current enumeration as d d d.
So in order to u u u is the root of the tree, if more than K K And exist in K branches u u The distance of u is greater than or equal to d d d, we can choose to select from these branches K K K as schemes. Define these branches as valid branches, and the number of valid branches is c n t cnt cnt, then the number of schemes that can be brought is C c n t K C_{cnt}^{K} CcntK？ No, because there may be more than one and in some valid branches u u u distance is greater than or equal to d d d nodes, the number of schemes they can bring can not be ignored, and it is not easy to calculate directly, so it is considered d p dp dp!
- Let's define it first f [ u ] [ j ] f[u][j] f[u][j] indicates in v v v is the root of the subtree, and v v v distance is j j The number of nodes of j, then:
-
When v v v is u u When u is a child node, f [ u ] [ j ] = f [ v , j − 1 ] f[u][j] = f[v,j-1] f[u][j]=f[v,j−1]
-
When v v v is u u When u parent node:
-
f [ u ] [ j ] + = f [ v ] [ j − 1 ] , ( j = 1 ) f[u][j] += f[v][j-1] ,(j=1) f[u][j]+=f[v][j−1],(j=1)
-
f [ u ] [ j ] + = f [ v ] [ j − 1 ] − f [ u ] [ j − 2 ] ( j ≥ 2 ) f[u][j] += f[v][j - 1] - f[u][j - 2] (j\geq2) f[u][j]+=f[v][j−1]−f[u][j−2](j≥2)
-
- Let's redefine it d p [ u ] [ j ] [ k ] dp[u][j][k] dp[u][j][k] indicates in u u u is the root, from u u Front of u j j Of the j valid branches, select k k The number of schemes of k valid branches, then for the j j j valid branches (set to v v v) , there are two kinds of decisions:
-
Select No j j j valid branches: d p [ u ] [ j ] [ k ] = d p [ u ] [ j − 1 ] [ k − 1 ] × C f [ v ] [ d − 1 ] 1 = d p [ u ] [ j − 1 ] [ k − 1 ] × f [ v ] [ d − 1 ] dp[u][j][k] = dp[u][j - 1][k - 1] \times C_{f[v][d-1]}^{1} = dp[u][j - 1][k - 1] \times f[v][d-1] dp[u][j][k]=dp[u][j−1][k−1]×Cf[v][d−1]1=dp[u][j−1][k−1]×f[v][d−1].
f [ v ] [ d − 1 ] f[v][d-1] f[v][d − 1] indicates v v And in the subtree of v v v v distance greater than d − 1 d-1 Number of nodes of d − 1, i.e. and u u u distance is greater than or equal to d d d number of nodes
C f [ v ] [ d ] 1 C_{f[v][d]}^1 Cf[v][d]1 ， means to select any one of these nodes -
Do not select No j j j valid branches: d p [ u ] [ j ] [ k ] = d p [ u ] [ j − 1 ] [ k ] dp[u][j][k] = dp[u][j - 1][k] dp[u][j][k]=dp[u][j−1][k]
Distance for each enumeration d d d ， u u u's contribution to the answer is d p [ u ] [ c n t ] [ K ] dp[u][cnt][K] dp[u][cnt][K]
AC_Code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10, mod = 1e9 + 7;
struct Edge
{
int nex, to;
} edge[N << 1];
int head[N] , TOT;
int n , K , f[N][N];
long long res , dp[N][N][N];
void add_edge(int u, int v)
{
edge[++ TOT].nex = head[u];
edge[TOT].to = v;
head[u] = TOT;
}
void init()
{
for(int i = 0 ; i <= n + 1 ; i ++) head[i] = 0;
TOT = 0;
}
void dfs(int u, int far)
{
for(int i = head[u] ; i ; i = edge[i].nex)
{
int v = edge[i].to;
if(v == far) continue ;
dfs(v, u);
for(int j = 1 ; j <= n ; j ++) f[u][j] += f[v][j - 1];
}
f[u][0] = 1;
}
void dfs1(int u , int far)
{
memset(dp , 0 , sizeof(int) * n * n * n);
for(int j = 1 ; j <= n ; j ++)
{
dp[u][0][0] = 1;
int cnt = 0;
for(int i = head[u] ; i ; i = edge[i].nex)
{
int v = edge[i].to;
if(v == far)
{
if(j == 1)
{
dp[u][++ cnt][0] = 1;
for(int k = cnt ; k >= 1 ; k --) dp[u][cnt][k] = (dp[u][cnt - 1][k] + dp[u][cnt - 1][k - 1]) % mod;
}
else
{
if(f[far][j - 1] - f[u][j - 2] > 0)
{
dp[u][++ cnt][0] = 1;
for(int k = cnt ; k >= 1 ; k --) dp[u][cnt][k] = (dp[u][cnt - 1][k] + dp[u][cnt - 1][k - 1] * (f[far][j - 1] - f[u][j - 2]) % mod) % mod;
}
}
}
else
{
if(f[v][j - 1])
{
dp[u][++ cnt][0] = 1;
for(int k = cnt ; k >= 1 ; k --) dp[u][cnt][k] = (dp[u][cnt - 1][k] + dp[u][cnt - 1][k - 1] * f[v][j - 1] % mod) % mod;
}
}
}
res += dp[u][cnt][K] , res %= mod;
}
if(u != 1)
{
for(int j = n ; j >= 1 ; j --)
{
if(j == 1) f[u][j] += f[far][0];
else f[u][j] += (f[far][j - 1] - f[u][j - 2]);
}
}
for(int i = head[u] ; i ; i = edge[i].nex)
{
int v = edge[i].to;
if(v == far) continue ;
dfs1(v, u);
}
}
signed main()
{
int T = 1;
cin >> T;
while(T --)
{
init();
res = 0;
cin >> n >> K ;
for(int i = 1 ; i <= n ; i ++) for(int j = 1 ; j <= n + 1; j ++) f[i][j] = 0;
for(int i = 1 ; i < n ; i ++)
{
int u, v;
cin >> u >> v;
add_edge(u, v), add_edge(v, u);
}
if(K == 2)
{
cout << n * (n - 1) / 2 << '\n';
continue ;
}
dfs(1, 0) , dfs1(1, 0);
cout << res << '\n';
}
return 0;
}
If you have any writing errors or doubts, please comment and tell me, and I will respond as soon as possible (if the code fails in the final test, please also comment and tell me, thank you!!!)
Author: Lqyk
Link to this article: https://www.lanqiao.cn/questions/204012
Copyright notice: this work is licensed by knowledge sharing signature - prohibition of deduction of the 2.5 Chinese Mainland License Agreement.