2021 ICPC Asia Taipei Regional

Problem D

Largest Remainder

Problem Description
Given a list of ???? digits and an integer ????, we consider all different ways to permute these digits into a ????-digit decimal number. The target of this problem is to find a permutation ????, such that when ???? is divided by ????, the remainder (between 0 and ???? − 1) is the largest among all other permutations. If there are more than one possible permutation, output the largest permutation.
For instance, suppose that we have ???? = 3 digits, and they are respectively 1, 2, 3.

1. If ???? = 1, then we see that every permutation will give a remainder 0 when divided by ????, and 321 is thus the desired answer, as it is the largest permutation among all.
2. If ???? = 10, then both 123 and 213 will give a remainder 3 when divided by ????, and this is the largest possible remainder in this case. Consequently, the desired output is 213 since it is a larger permutation.
3. If ???? = 100, then the largest remainder we can get is 32, when the permutation is 132.

Input Format
The first line of the input contains a positive integer ???? followed by a positive integer ????. Then, the next line contains ???? digits, each digit ???? has value 1 ≤ ???? ≤ 9 and is separated from the next one by a space.
Output Format
Output the largest permutation that gives the largest remainder in a single line.
Technical Specification
∙ 1 ≤ ???? ≤ 16
∙ 1 ≤ ???? ≤ 200
∙ 1 ≤ ???? ≤ 9

题解：

代码：

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

const int N = 7e4 + 10;
int T[N][210], dig[20];
ll wei[20];
bool vis[20];

int main()
{
    int D, K, d;
    cin >> D >> K;
    wei[1] = 1;
    for(int i = 2; i <= 17; i ++)
        wei[i] = wei[i - 1] * 10;
    
    for(int i = 0; i < D; i ++)
        cin >> dig[i];
    sort(dig, dig + D);
    T[0][0] = 1;
    for(int i = 1; i < (1 << D); i ++)
    {
        int num = __builtin_popcount(i);
        for(int j = 17; j >= 0; j --)
        {
            if((i >> j) & 1)
                for(int r = 0; r < K; r ++)
                {
                    if(T[i ^ (1 << j)][r])
                        T[i][(r + wei[num] * dig[j]) % K] = 1;
                }
        }
    }

    for(int i = K - 1; i >= 0; i --)
    {
        if(T[(1 << D) - 1][i])
        {
            int num = (1 << D) - 1, r = i;
            for(int pos = D; pos >= 1; pos --)
                for(int j = D - 1; j >= 0; j --)
                {
                    if(!vis[j] && T[num ^ (1 << j)][((r - wei[pos] * dig[j]) % K + K) % K])
                    {
                        num = num ^ (1 << j);
                        r = ((r - wei[pos] * dig[j]) % K + K) % K;
                        cout << dig[j];
                        vis[j] = 1;
                        break;
                    }
                }
            cout << "n";
            break;
        }    
    }
    return 0;
}

Problem I

Seesaw

Problem Description
There is a seesaw in a playground. On each side of the seesaw, there are ???? seats, where the seats are located at distance exactly 1, 2, . . . , ???? units from the center. When a seat at distance ???? units from the center is occupied by someone with weight ????, a torque of magnitude ???? × ???? will appear on the corresponding side of the seesaw. The seesaw is balanced when the total torque on both sides have the same magnitude.
Initially, all the seats on the seesaw are occupied with kids with positive integral weights. Furthermore, on the left side of the seesaw, all kids have odd weights, while on the right side of the seesaw, all kids have even weights. Unfortunately, the seesaw is not balanced. Someone suggests to exchange the kids around, so as to see if the seesaw can be balanced. However, kids with weight more than 2 are unwilling to move, so that they will never change their seats. Your task is to determine if it is possible to make the seesaw balanced, and if so, what the minimum number of exchanges is.
For example, suppose ???? = 3, the kids on the left side all have weight 1, and the kids on the right side all have weight 2. Then, it is possible to make 1 exchange, by exchanging the kids at distance 3 on both sides, so that the total torque of the left side becomes 1×1+1×2+2×3 = 9, and the total torque of the right side becomes 2 × 1 + 2 × 2 + 1 × 3 = 9, and the seesaw is balanced.
For another example, suppose ???? = 3, the kids on the left side all have weight 1, and the kids on the right side of the seesaw have weights 4, 2, 2, at distance 1, 2, 3 units, respectively. Then, it is possible to make 2 exchanges, first by exchanging the kids at distance 2 on both sides, and then by exchanging the kid at distance 1 on the left with the kid at distance 3 on the right, so that the total torque on the left side becomes 2 × 1 + 2 × 2 + 1 × 3 = 9, and the total torque of the right side becomes 4 × 1 + 1 × 2 + 1 × 3 = 9, and the seesaw is balanced. In contrast, we see that it is impossible to balance the seesaw with just 1 exchange, so the minimum number of exchanges in this example is 2.
Input Format
The first line of the input is a positive integer ???? denoting the number of test cases. Each test case begins with a positive integer ????, denoting the number of seats on each side of the seesaw. Then, the next line contains ???? odd integers, which are the weights of the kids on the left side of the seesaw, listed from the one with distance 1 unit to the one with distance ???? units from the center, respectively. After that will be a line containing ???? even integers, which are the weights of the kids on the right side of the seesaw, listed from the one with distance 1 unit to the one with distance ???? units from the enter, respectively.
Output Format
For each of the test cases, if the seesaw can be balanced, output the minimum number of exchanges needed; otherwise, output -1. Each output is on a single line.
Technical Specification
∙ 1 ≤ ???? ≤ 5
∙ 1 ≤ ???? ≤ 100
∙ 1 ≤ ???? ≤ 50000; ???? is an integer

题解：

代码：

dp还没写

Problem J

Transportation Network

Problem Description
A retail company owns many convenience stores and a central warehouse in a city. Commodities are transported from the central warehouse to convenience stores. In addition, convenience stores provide a service that customers can send packages from a convenience store to another. A logistics team of this company aim at redesigning their transportation network in the city. The original transportation network can be modeled by a simple, undirected, and complete graph ???? = (????, ????, ????), in which ???? = {0, 1, 2, . . . , ???? − 1} is the vertex set, ???? = {{????, ????} | ????, ???? ∈ ???? and ???? ̸= ????} is the edge set, and ???? : ???? → {1, 2} is a weight function. Vertex 0 represents the central warehouse and vertices 1, 2, . . . , ???? − 1 represent ???? − 1 convenience stores. All the edges in ???? represent the transportation links between all the pairs of vertices in ???? . The weight of each edge represents the cost to establish the corresponding transportation link.
For ease of management, ???? − {0} is partitioned into two disjoint sets, denoted by ???? and ????, in which ???? contains the convenience stores located at the main streets, and ???? contains the convenience stores located at some alleys. That is, except for vertex 0, every vertex in ???? belongs to either set ???? or set ????. Moreover, the weights of edges in ???? are defined as follows.
∙ For vertex 0
   – ????({0, ????}) = 1 if ???? ∈ ????.
   – ????({0, ????}) = 2 if ???? ∈ ????.
∙ For ???? ∈ ????
   – ????({????, ????′}) = 2 if ????′ ∈ ???? and ???? ̸= ????′.
   – ????({????, ????}) = 1 if ???? ∈ ????.
∙ For ???? ∈ ????
   – ????({????, ????′}) = 2 if ????′ ∈ ???? and ???? ̸= ????′.
A rooted tree is a tree with one specified vertex ???? chosen as the root. For each vertex ????, there is a unique path ????(????) from ???? to the root ????. The parent of ???? is its neighbor on ????(????); its childern are its other neighbors. For a non-root vertex ???? in a rooted tree ????, the depth of ???? is the number of edges in the path from ???? to the root. The depth of a rooted tree ???? is the maximum depth among all the vertices in ????. To achive the goal of efficient transportation, the logistics team members devote their effort to connect the central warehouse and all the convenience stores to form a special depth-2 spanning tree ???? such that the following coditions hold:

1. The root of ???? is vertex 0.
2. The depth of ???? is at most 2.
3. ???? contains all the vertices in the original transportation network.
4. The root (i.e., vertex 0) is adjacent to exact ???? vertices called hubs, and each of the remaining vertices is adjacent to exactly one hub.

For any two vertices ???? and ???? in a rooted tree ????, let ???????? (????, ????) denote the weight between ????
and ???? in ???? (i.e., the sum of the weight of edges in the path between ???? and ???? in ????). Define
????(????) = ∑︀????∈????∑︀????∈???? ???????? (????, ????) to be the routing cost of ????. The logistics team aims to construct
a transportation network ???? with the minimum of routing cost. For convenience, we call such
a depth-2 spanning tree with the minimum routing cost as critical transportation network.
Figure 3 illustrates a toy example of the problem.
Figure 3: An example of the problem with ???? = 4 and ???? = 1. The original transportation network ???? is shown on the left hand side, where gray vertex represents vertex 0, white vertex belongs to ????, and black vertices belong to ????. The critical transportation network is shown on the right hand side.
Given the original transportation network ???? and a positive integer ????, your task is to write a computer program for computing the minimum routing cost of the critical transportation network.
Input Format
The first line of the input file contains an integer ???? (???? ≤ 16) that indicates the number of test cases as follows. For each test case, the first line contains three integers (separated by whitespaces) representing ????, |????|, and ????. Then it is immediately followed by a single line, which contains |????| integers (separated by whitespaces) that represent the vertices belonging to the set ????, where ???? ∈ ???? and 1 ≤ ???? ≤ ???? − 1. It guarantees the sum of |????| in all testcases are at most 300, 000.
Output Format
The output contains one line for each test case. Each line contains one positive integer representing the routing cost of the critical transportation network.
Technical Specification
∙ 3 ≤ ???? ≤ 1, 000, 000 for each test case.
∙ |????| + |????| ≥ ????.
∙ 1 ≤ |????| ≤ ???? ≤ ???? − 1.

题解：

代码：

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

const int N = 1e5 + 10;
int a[N];

int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        ll n, s, p;
        cin >> n >> s >> p;
        for(int i = 1; i <= s; i ++)
            cin >> a[i];
        ll ans = (n - p) * p + (n - 1) * (s - 1) + 2 * (n - 1) * (p - s) + (n - 1) * (n - 1 - p);
        ans *= 2;
        cout << ans << "n";
    }
    return 0;
}

最后

以上就是强健蛋挞为你收集整理的2021 ICPC Asia Taipei Regional 2021 ICPC Asia Taipei Regional 的全部内容，希望文章能够帮你解决2021 ICPC Asia Taipei Regional 2021 ICPC Asia Taipei Regional 所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。