2022第8届中国大学生程序设计竞赛CCPC威海站， 签到题7题

E.Python Will be Faster than C++

E. Python Will be Faster than C++
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output

Little Q is learning programming languages. He often uses Python as it is one of the most used programming languages. However, when he codes in Python, he finds that the programs do not run very efficiently, especially when compared to C/C++. He wonders if the running efficiency of Python has any improvement with version updates, and conducts an experiment.

The algorithm used in the experiment is Monte Carlo, estimating π by generating a large number of random points in a square. He codes this algorithm in Python and runs it with different versions of Python, logging the running time. Formally, there are a total of n released versions of Python, namely 3.1, 3.2, …, 3.n. The running time of the algorithm on version 3.i is ai ms. Little Q is surprised to find that the running efficiency of Python does change with version iterations.

Little Q also tests the running time of this algorithm in C++, which is stably k ms. Then he comes up with a funny idea: using the experimental data to predict which future version of Python will have a higher efficiency than C++. Unfortunately, he forgets how to apply the regression model, so he uses a brute prediction method:

For a future version i that i>n, ai=max.
With this prediction method, please tell him the earliest version of Python that has a strictly higher efficiency than C++, i.e., find the minimum i such that a_i < k.

Input
The first line contains two integers n and k (2 \le n \le 10, 1 \le k \le 1000), indicating the number of released versions of Python and the running time of the algorithm in C++.

The second line contains n integers a_1,a_2,\dots,a_n (k < a_i \le 10^5), indicating the running time of the algorithm on each version of Python.

Output
Output Python 3.x will be faster than C++, where x is an integer indicating the earliest version that a_x < k. If such a version does not exist, output Python will never be faster than C++.

Examples
inputCopy
10 1
11 45 14 19 19 8 10 13 10 8
outputCopy
Python 3.14 will be faster than C++
inputCopy
10 1
2 2 2 2 2 2 2 2 2 2
outputCopy
Python will never be faster than C++
Note
The first sample can be expressed in the following picture, in which the blue line represents the efficiency of Python, and the red line represents the efficiency of C++. The dashed line indicates the prediction. As you see, Python 3.14 will be faster than C++.

For the second sample, it is easy to notice that Python always runs for 2 ms, including the prediction of future versions. Therefore, Python will never be faster than C++, which runs for 1 ms.

题意：

• 给出py共n个版本的运行时间，以及c++的运行时间。
  定义i>n版本的py运行时间为max{0, 2a{i-1} - a{i-2}}。
• 求是否存在某个py版本运行时间小于c++。

思路：

• 只有1组数据，迭代跑1e6次看看是否存在即可。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, k;  cin>>n>>k;
    int ok = 0, a, b;
    for(int i = 1; i <= n; i++){
        int x;  cin>>x;
        if(x<k){ ok = i;  break; }
        if(i==n-1)a = x;
        if(i==n)b = x;
    }
    if(ok==0){
        for(int i = n+1; i <= 1000000; i++){
            int c = max(0, 2*b-a);
            if(c<k){ ok = i;  break; }
            a = b;  b = c;
        }
    }
    if(ok == 0)cout<<"Python will never be faster than C++\n";
    else cout<<"Python 3."<<ok<<" will be faster than C++\n";
    return 0;
}

A.Dunai

A. Dunai
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output

Lope the Bear often watches game events. He has a special skill: Dunai, also known as poisoned milk. Every time he predicts the outcome of a game by wishing the team that he believes will win good luck, the outcome often turns out to be the opposite. Recently, a tournament called Daota 2 The International is about to start. It’s time for Lope to show his Dunai skill again.

In the game Daota 2, each team has five players corresponding to five positions, numbered from 1 to 5. Daota 2 The International has been held for n editions. To better Dunai, Lope looks up the champion team of each edition, including the names and positions of the five players. In addition, he inquires about the m players involved in the upcoming tournament including their names and positions, without knowing exactly how the teams will be formed. What is known is that for every player who has won a championship, his position in the team never changes.

Lope wants to predict how these m players will be teamed up in a way that satisfies the following conditions:

Each player is assigned to at most one team (possibly not assigned).
The team consists of five different positions, with exactly one player for each position.
Each team includes at least one player who has won a championship.
Lope wants to know the maximum number of teams that can be formed.

Input
The first line contains an integer n (1≤n≤100), indicating the number of editions that the tournament has been held for.

Each of the following n lines contains five strings separated by spaces, indicating the name of five players in the champion team, corresponding to positions 1 to 5 respectively.

The next line contains an integer m (1≤m≤1000), indicating the number of players involved in the upcoming tournament.

Each of the following m lines contains a string and an integer between 1 and 5, indicating the name and position of a player. It is guaranteed that the names of the players are all distinct, and for every player who has won a championship, his position in the team never changes.

It is guaranteed that the string representing each player’s name consists of only English letters and digital numbers, and the length of the string does not exceed 20.

Output
Output an integer indicating the maximum number of teams that can be formed.

Examples
inputCopy
1
Kanon Keke Chisato Sumire Ren
9
Kanon 1
Keke 2
Chisato 3
Sumire 4
Ren 5
Kinako 1
Mei 2
Shiki 3
Natsumi 4
outputCopy
1
inputCopy
11
skiter Nine 33 Saksa Sneyking
Yatoro TORONTOTOKYO Collapse Mira Miposhka
ana Topson Ceb JerAx N0tail
ana Topson Ceb JerAx N0tail
MATUMBAMAN Miracle MinDContRoL GH KuroKy
shadow bLink Faithbian iceice y
Fear SumaiL UNiVeRsE Aui2000 ppd
Hao Mu xiao8 Banana SanSheng
Loda s4 AdmiralBulldog EGM Akke
Zhou Ferrari430 YYF ChuaN Faith
ArtStyle Dendi XBOCT LighTofHeaveN Puppey
100
Ame 1
NothingToSay 2
Faithbian 3
XinQ 4
y 5
Yuragi 1
bzm 2
ATF 3
Taiga 4
Misha 5
Yatoro 1
TORONTOTOKYO 2
Collapse 3
Mira 4
Miposhka 5
K1 1
ChrisLuck 2
Wisper 3
Gojira 4
Stinger 5
Monet 1
Ori 2
Xxs 3
BoBoKa 4
SiameseC 5
Pakazs 1
DarkMago 2
Sacred 3
Matthew 4
Pandaboo 5
JaCkky 1
Yopaj 2
Fbz 3
TIMS 4
skem 5
Timado 1
Bryle 2
SabeRLight 3
MoonMeander 4
DuBu 5
skiter 1
Nine 2
33 3
Saksa 4
Sneyking 5
dyrachyo 1
BOOM 2
Ace 3
tOfu 4
Seleri 5
Arteezy 1
Abed 2
Nightfall 3
Cr1t 4
Fly 5
Raven 1
Armel 2
Jabz 3
DJ 4
Jaunuel 5
YawaR 1
Quinn 2
LESLAO 3
MSS 4
Fata 5
Lumiere 1
4nalog 2
Vitaly 3
Thiolicor 4
Gardick 5
Pure 1
Stormstormer 2
Tobi 3
Kataomi 4
Fishman 5
Daxak 1
Larl 2
Noticed 3
RodjER 4
SoNNeikO 5
Ghost 1
Somnus 2
Chalice 3
kaka 4
xNova 5
23savage 1
Mikoto 2
kpii 3
Q 4
Hyde 5
Crystallis 1
Nisha 2
Resolut1on 3
Zayac 4
Puppey 5
MATUMBAMAN 1
miCKe 2
zai 3
Boxi 4
iNSaNiA 5
outputCopy
14

题意：

• 现在要进行比赛组队，每个队伍满足以下条件：
  每个球员最多被分配到一个团队（可能未分配）。
  球队由五个不同的位置组成，每个位置只有一名球员。
  每支球队至少包括一名赢得冠军的球员。
  每一个获得过总冠军的球员，他在球队中的位置都不会改变。
• 现在已知历年n年的冠军队每次5个球员的名字，以及今年参赛的m个人和他们的位置。
• Lope 想知道可以组建的团队的最大数量。

思路：

• 贪心的假设理想状况下，只要人数够就能组出队来（反正随便怎么排，也没有其他限制，所以一定是可以排出来的），所以并不需要真的去排列方案。
• 一共5个位置，每个位置的人数有个上界，冠军队数也有个上界。取个min即可。
  注意冠军队给出的时候可能有重复，而且每个人只能被用一次，所以开个map维护一下。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;  cin>>n;
    map<string, int>mp;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= 5; j++){
            string s;  cin>>s;
            mp[s] = 1;
        }
    }
    int m;  cin>>m;
    vector<string>vc[6];
    for(int i = 1; i <= m; i++){
        string s;  int x;  cin>>s>>x;
        vc[x].push_back(s);
    }
    int mi = m+1;
    for(int i = 1; i <= 5; i++){
        mi = min(mi, (int)vc[i].size());
    }
    int res = 0;
    for(int i = 1; i <= 5; i++){
        for(int j = 0; j < vc[i].size(); j++){
            if(mp[vc[i][j]]==1 && res<mi){
                mp[vc[i][j]] = 0;
                res++;
            }
        }
    }
    cout<<res<<"\n";
    return 0;
}

G.Grade 2

G. Grade 2
time limit per test3 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output

Kotsuki the Cat, together with FuuFuu and Pico, lives in the KFP apartment. As a teacher, Kotsuki needs to go to school every day to give lessons. One day, Kotsuki gives a math lesson to some grade 2 students in primary school, covering the following topics:

Coprime: Two integers are coprime if the only positive integer that is a divisor of both of them is 1.
Bitwise XOR (⊕): Bitwise XOR is a binary operation that takes two integers and performs the logical exclusive OR operation on each pair of corresponding bits of their binary forms. The result in each will be 1 if only one of the bits is 1, but will be 0 if both are 0 or both are 1. For example, 5⊕3=(101)2⊕(011)2=(110)2=6.
After class, Kotsuki assigns homework to the students:

Given an integer x, for different intervals [l,r], please calculate the number of integers k within the interval satisfying kx⊕x and x are coprime. Formally, please calculate
∑k=lr[gcd(kx⊕x,x)=1]
where gcd(a,b) denotes the greatest common divisor of a and b, and [ ] denotes the Iverson bracket [P]={10if P is trueotherwise. Specially, gcd(0,a)=a.
Can you solve this grade 2 homework?

Input
The first line contains two integers x (1≤x≤106) and n (1≤n≤105), where n indicates the number of intervals.

Each of the following n lines contains two integers l and r (1≤l≤r≤1012), indicating an interval [l,r].

Output
For each interval, output the answer in a single line.

Example
inputCopy
15 2
1 4
11 4514
outputCopy
2
2252
Note
When x=15,

k=1, gcd(kx⊕x,x)=gcd(15⊕15,15)=gcd(0,15)=15
k=2, gcd(kx⊕x,x)=gcd(30⊕15,15)=gcd(17,15)=1
k=3, gcd(kx⊕x,x)=gcd(45⊕15,15)=gcd(34,15)=1
k=4, gcd(kx⊕x,x)=gcd(60⊕15,15)=gcd(51,15)=3
So the answer to interval [1,4] is 2.

题意：

• 给定一个整数x，对于给定的n个不同的区间[l,r]，请计算满足kx⊕x和x互质的区间内的整数k个数。

思路：

• 通过打表找规律会发现，对于每个x的结果是不断循环的，循环节长度是大于等于x的2的倍数。
• 所以可以通过前缀和统计循环节内gcd为1的个数，然后每次对于询问，可以直接根据区间长度得到所给区间的循环节个数乘上前缀和，再处理一下两个边界的值输出即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e6+10;
LL a[maxn], s[maxn];
int main(){
    LL x, q;  cin>>x>>q;
    LL y = 1;
    while(y < x)y <<= 1;
    for(LL i = 1; i <= y; i++){
        if(__gcd(i*x^x, x) == 1)a[i] = 1;
        s[i] = s[i-1]+a[i];
    }
    while(q--){
        LL l, r;  cin>>l>>r;  l--;
        LL res1 = s[l%y]+(l/y)*s[y];
        LL res2 = s[r%y]+(r/y)*s[y];
        cout<<res2-res1<<"\n";
    }
    return 0;
}

J.Eat, Sleep, Repeat

J. Eat, Sleep, Repeat
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output

FuuFuu the Panda, together with Pico and Kotsuki, lives in the KFP apartment. As a rare species, FuuFuu is well-treated. Therefore, his daily activities are only eating and sleeping.

One afternoon, Kotsuki is still working outside, and FuuFuu has finished his lunch and intends to go to sleep. But Pico feels too bored to play alone every day and wants to play a game with FuuFuu for a while. Although not very reluctant, FuuFuu agrees.

Pico picks n integers a1,a2,…an, and sets k constraints, the i-th of which is limitxi=yi, indicating that the maximum number of occurrences of xi is yi. Then Pico and FuuFuu take turns playing the game, where each player can choose a positive integer among a1,a2,…an for each turn and reduce it by 1. A player will lose the game if he cannot perform any action on his turn, where there are two cases:

No matter which of a1,a2,…an is chosen, there exists an integer x whose number of occurrences will be strictly greater than limitx.
a1=a2=⋯=an=0.
Even though FuuFuu is sleepy, he does not want to lose the game. Please tell him who will win if Pico goes first and both of them play optimally.

Input
The first line contains an integer T (1≤T≤105), indicating the number of test cases.

The first line of each test case contains two integers n and k (1≤n≤105, 0≤k≤105), indicating the number of integers and constraints.

The second line contains n integers a1,a2,…an (0≤ai≤109), indicating the initial integers. It is guaranteed that the initial number of occurrences of each integer does not exceed the limit.

The i-th of the following k lines contains two integers xi and yi (0≤xi≤109, 0≤yi≤n), indicating that limitxi=yi. It is guaranteed that x1,x2,…xk are all distinct.

It’s guaranteed that ∑n≤105 and ∑k≤105 over all test cases.

Output
For each test case, output the name of the winner in a single line, which is either Pico or FuuFuu.

Example
inputCopy
5
2 0
1 2
2 1
1 2
0 1
3 2
3 3 4
0 2
1 1
3 2
2 3 3
1 2
0 1
5 4
6 7 8 12 17
1 1
2 1
9 0
10 1
outputCopy
Pico
FuuFuu
Pico
FuuFuu
Pico
Note
For the first test case of the sample, since there are no constraints, the game ends only if all the integers are reduced to zero. So FuuFuu will lose the game after three turns.

For the second test case of the sample, the maximum number of occurrences of 0 is 1. Obviously, there must be two zeros after Pico’s action in the third turn, so FuuFuu will win the game.

题意：

• 给你n个数，以及m个限制，每个限制有两个数x和y，表示数x最多只能同时出现y个。
• 每次两个玩家会选一个数-1，最先做不出操作的就输了。
• Pico 先手并且两人都发挥最佳，求谁会赢？

思路：

• 如果x最多出现次数为0，说明比他大的数都只能停在x+1上了，不能更小。然后剩下的数则可以贪心的能删多小删多小。
• 既然最终结果定了，不难发现其实操作次数与策略无关。
  所以直接模拟，用map统计每个数的限制，将数组排序，从前往后扫，每个数可以减小的值 = 第一个小于等于它的无限制 或 个数未达到上限的值，用一个小根堆去维护所有可行位置。
• 最后只需要统计一下所有可以进行的操作数，是奇数还是偶数即可得到答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e6+10;
int a[maxn];
int main(){
    int T;  cin>>T;
    while(T--){
        int n, k;  cin>>n>>k;
        for(int i = 1; i <= n; i++)cin>>a[i];
        map<int,int>mp;
        priority_queue<int, vector<int>, greater<int>>q;
        q.push(0);
        while(k--){
            int x, y;  cin>>x>>y;
            if(y==0)q.push(x+1); //不能出现x
            else mp[x] = y;
        }
        sort(a+1,a+n+1);
        int res = 0, t = 0;
        for(int i = 1; i <= n; i++){
            while(q.size() && q.top()<=a[i]){//第1个<=a[i]的无限制可以出现的数
                t = q.top();  q.pop();
            }
            res ^= (a[i]-t)&1;       //统计和的奇偶性
            mp[t]--;                 //剩余出现个数--
            if(mp[t]==0)q.push(t+1); //如果x限制数为0，则比他大的数都只能停在x+1上了。
        }
        if(res)cout<<"Pico\n";
        else cout<<"FuuFuu\n";
    }
    return 0;
}

C.Grass

C. Grass
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output

Charles the Rabbit likes eating grass. As the saying goes, rabbits do not eat the grass by their burrows. Therefore, Charles has to go outside his burrow every day to look for grass to eat.

One day, Charles comes to a two-dimensional plane with many distinct points. He can choose a point A and another four points B,C,D,E to connect with A to form four segments. We consider these four segments as a clump of grass if they meet the following condition:

Any two of the four segments have only a single point of intersection A between them.
For example, in the picture below, (1) is a clump of grass, but (2) is not one as the intersection of segments AC and AE is not only a single point A.

Given n points on a plane, Charles wants to know whether there exists a clump of grass. If so, help him find a certain one.

Input
The first line contains an integer T (1≤T≤120), indicating the number of test cases.

The first line of each test case contains an integer n (1≤n≤25000), indicating the number of points.

Each of the following n lines contains two integers x,y (−107≤x,y≤107), indicating that the coordinates of the point are (x,y). It is guaranteed that all points are distinct.

It is guaranteed that ∑n≤105 over all test cases.

Output
For each test case, if there does not exist a clump of grass, output NO in a single line.

Otherwise, output YES in the first line. Then output two integers separated by a space in the second line, indicating the coordinates of point A. Then output two integers separated by a space in each of the third to sixth lines, indicating the coordinates of the other four points B,C,D,E.

If there is more than one clump of grass, output any.

Example
inputCopy
3
5
0 0
1 1
1 -1
-1 1
-1 -1
3
1 1
4 5
1 4
5
1 0
2 0
3 0
4 0
5 0
outputCopy
YES
0 0
1 1
1 -1
-1 1
-1 -1
NO
NO

题意：

• T组数据（120），每次给出二维平面的n个点（2e4），求是否能找出5个点满足点 A 和另外四个点 B、C、D、E 与 A 连接形成四个线段，输出这五个点（按照ABCDE的顺序）。

思路：

• 不难发现结论：只要BCDE四个点不是都和A共线的，就能有结果，哪怕BCDE四个点都是共线。
• 先固定4个点，O（n）寻找一个和他们不共线的点，如果找不到则必然没有可行解，如果找到，则判断一下哪一个点是中心点即可。
• 除非输入的n个点都共线（此时自然无解），否则固定4个点，必然可以找到一个点与之不是共线的情况。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PII;
const LL maxn = 2e6+10;
struct node{LL x, y; }a[maxn];

LL check(LL x){
    set<PII>se;
    for(LL i = 1; i <= 4; i++){
        LL dx = a[i].x-a[x].x, dy = a[i].y-a[x].y;
        LL dd = __gcd(dx, dy);
        dx /= dd;  dy /= dd;
        se.insert({dx, dy});
    }
    return se.size()>1;  //只要有不是五点共线就行
}
LL find(){
    for(LL i = 1; i <= 5; i++){
        set<PII>se;
        for(LL j = 1; j <= 5; j++){
            if(i==j)continue;
            LL dx = a[i].x-a[j].x, dy = a[i].y-a[j].y;
            LL dd = abs(__gcd(dx, dy));
            dx /= dd;  dy /= dd;
            se.insert({dx, dy});
        }
        if(se.size()==4)return i;
    }
}

int main(){
    LL T;  cin>>T;
    while(T--){
        LL n;  cin>>n;
        for(LL i = 1; i <= n; i++)cin>>a[i].x>>a[i].y;
        LL ok = 0;
        for(LL i = 5; i <= n; i++){
            if(check(i)){
                swap(a[i], a[5]);
                LL x = find();
                cout<<"YES\n";
                cout<<a[x].x<<" "<<a[x].y<<"\n";
                for(LL i = 1; i <= 5; i++){
                    if(i!=x)cout<<a[i].x<<" "<<a[i].y<<"\n";
                }
                ok = 1;
                break;
            }
        }
        if(ok==0)cout<<"NO\n";
    }
    return 0;
}

D.Sternhalma

D. Sternhalma
time limit per test2 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output

Pico the Puppy, together with FuuFuu and Kotsuki, lives in the KFP apartment. They often play a board game together called Sternhalma, commonly known as Chinese checkers. The objective of the game is to race all of one’s pieces across the hexagram-shaped board to the opposite side, using single-step moves or moves that jump over other pieces.

One day, Pico wants to play Sternhalma again, but Kotsuki is out at work, and FuuFuu is still sleeping. Feeling bored, Pico intends to play on his own for a while. Pico simplifies the board into the shape shown in the picture below, with a total of 19 grids, and he assigns a score to each grid.

Initially, he places a number of pieces on the board. Then, he moves the pieces according to the rule set by himself, selecting either of the following two types of moves for each turn:

Remove any piece directly from the board, getting no scores.

Remove a piece by jumping over it. Formally, for two adjacent pieces A and B, if the symmetric position of A with respect to B is not out of bounds and no piece is placed there, then A can jump over B, and B is removed from the board. The total score will be increased by the score assigned to the grid where B is located before being removed. (We consider two pieces adjacent if and only if the grids where the two pieces are located share an edge.)

The initial score is 0. Pico will keep removing the pieces until there are no pieces left on the board. For different initial placements of pieces, he wants to know the maximum score he can get.

Input
The first five lines contain 19 integers, indicating the scores assigned to the grids. The first line contains 3 integers indicating the first row of the board, the second line contains 4 integers indicating the second row of the board, and so on. Each score ranges between −106 and 106.

The next line contains an integer n (1≤n≤104), indicating the number of initial placements of pieces.

Each of the n initial placements occupies five lines. Each line contains a string consisting of only . or #. The first line contains 3 characters indicating the first row of the board, the second line contains 4 characters indicating the second row of the board, and so on. # denotes that there is a piece at this position, while . denotes that there is none.

Output
For each initial placement of pieces, output the maximum score in a single line.

Example
inputCopy
9 2 2
3 3 7 2
0 3 6 8 5
4 7 7 5
8 0 7
3
…
…#.
…##.
…
…
…
…
.##…
…#.
…

outputCopy
8
14
105
Note
The first initial placement of the sample is shown in the picture below. Obviously, only one piece can be removed by jumping over it.

For the second initial placement of the sample, the moves to obtain the maximum score are shown in the following picture.

题意：

• 跳棋游戏，给出一个跳棋棋盘，使用单步动作或跳过其他棋子的动作，将自己的所有棋子穿过六角形棋盘跑到对面。
• 共有 19 个网格，他为每个网格分配一个分数。每次又两种操作：
  1、直接从板上删除任何一块，没有得分。
  2、通过跳过它来移除一块。A 可以跳过 B，并且 B 被移出棋盘。总分会增加被移除前分配给B所在网格的分数。
• 一个整数 n (1≤n≤104)，表示初始放置棋子的次数。n 个初始位置中的每一个都占用 5 行。
  每行包含一个仅由 . 组成的字符串。或者 ＃。第一行包含 3 个字符，表示棋盘的第一行，第二行包含 4 个字符，表示棋盘的第二行，以此类推。 # 表示该位置有一块，而 .表示没有。
• 对于每个初始放置的棋子，在一行中输出最高分数。

思路：

• 因为格子的数量只有19，因此棋盘的状态最多只有2^19种。可以状态压缩并令一个数x表示当前棋盘的状态（每个位置有没有格子）。
• 因为每进行一次操作一定会少一颗棋子，所以状态的转移一定是无后效性的，且每种状态的答案是固定的，因此可以使用动态规划求出每种状态的答案。令f[x]表示到x为止能获得的最大权值和。
• 操作1：有转移f[x] = max{f[x], f[x-2^i]}
  操作2：有转移f[x] = max{f[x], f[x-2^i-2^a+2^b]}

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

int w[19], f[1<<19], vis[1<<19];
vector<pair<int,int> >v[19];     //格子i作为跳板时，合法的跳跃前后格子
void add(int mid, int a, int b){ //跳板格子，以及跳跃前后的两个格子
    v[mid].push_back({a,b});
    v[mid].push_back({b,a});
}

int dfs(int now){
    if(vis[now])return f[now];
    //op1, remove i
    for(int i = 0; i < 19; i++){
        if(!(now>>i&1))continue; 
        f[now] = max(f[now], dfs(now-(1<<i)));
    }
    //op2, jumping and remove i
    for(int i = 0; i < 19; i++){
        if(!(now>>i&1))continue;
        for(auto p : v[i]){
            int x = p.first, y = p.second;
            if(!(now>>x&1) || (now>>y&1))continue;
            //x to y (by i), +w[i]
            f[now] = max(f[now], dfs(now-(1<<i)-(1<<x)+(1<<y))+w[i]);
        }
    }
    vis[now] = 1;
    return f[now];
}

int main(){
    //输入和建图
    memset(f, 0xc0, sizeof(f));
    f[0] = 0;  vis[0] = 1;
    add(1, 0, 2);
    add(3, 0, 7);
    add(4, 0, 9), add(4, 1, 8), add(4, 3, 5);
    add(5, 1, 10), add(5, 2, 9), add(5, 4, 6);
    add(6, 2, 11);
    add(8, 3, 13), add(8, 4, 12), add(8, 7, 9);
    add(9, 4, 14), add(9, 5, 13), add(9, 8, 10);
    add(10, 5, 15), add(10, 6, 14), add(10, 9, 11);
    add(12, 7, 16);
    add(13, 8, 17), add(13, 9, 16), add(13, 12, 14);
    add(14, 9, 18), add(14, 10, 17), add(14, 13, 15);
    add(15, 11, 18);
    add(17, 16, 18);

    //solve
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    for(int i = 0; i < 19; i++)cin>>w[i];
    int T;  cin>>T;
    while(T--){
        string s, t;
        for(int i = 0; i < 5; i++)cin>>t, s += t;
        int st = 0;
        for(int i = 0; i < 19; i++){
            if(s[i]=='#')st += 1<<i;
        }
        cout<<dfs(st)<<"\n";
    }
    return 0;
}

I.Dragon Bloodline

I. Dragon Bloodline
time limit per test3 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output

Adonis the Dragon is a great leader of the dragon kingdom. It is an important mission for the dragons to pass on the dragon bloodline. Therefore, Adonis decides to choose a special day each year for egg production. Today is the day!

It is not easy to produce a dragon egg, which needs to collect various kinds of essences such as earth, water, wind, fire, etc. Specifically, the production of a dragon egg requires n kinds of essences, the amount for the i-th of which is ai.

To improve efficiency, Adonis employs many worker dragons to collect different kinds of essences for him. There are k different levels of worker dragons, from level 1 to level k. The amount of essence that a worker dragon of level i can obtain in one day is 2i−1, but each worker dragon can collect only one kind of essence. Adonis can assign which kind of essence each worker dragon should collect at the beginning, but it cannot be changed once assigned.

Knowing that the number of dragons of level i is bi, Adonis wants to know the maximum number of dragon eggs that can be produced today with the best assignment.

Input
The first line contains an integer T (1≤T≤103), denoting the number of test cases.

The first line of each test case contains two integers n and k (1≤n≤5×104, 1≤k≤20), denoting the number of kinds of essences and the maximum level of worker dragons.

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤109), denoting the amount of each kind of essence required to produce a dragon egg.

The third line of each test case contains k integers b1,b2…,bk (1≤bi≤109), denoting the number of worker dragons of each level.

It is guaranteed that ∑n≤5×104 over all test cases.

Output
For each test case, output an integer in a single line denoting the maximum number of dragon eggs that can be produced.

Example
inputCopy
6
4 3
1 2 3 4
4 4 4
3 2
1 1 1
1 7
3 4
6 6 2
1 1 5 5
3 5
3 1 1
1 1 1 1 1
4 5
1 9 9 8
2 2 2 3 1
5 4
1 3 1 7 1
4 1 5 2
outputCopy
2
4
4
5
2
3
Note
Here is one possible assignment for the first case of the sample:

Assign 3 worker dragons of level 1 to the first essence, with a daily production of 3×1=3.
Assign 2 worker dragons of level 2 to the second essence, with a daily production of 2×2=4.
Assign 1 worker dragon of level 1, 2 worker dragons of level 2, and 1 worker dragon of level 3 to the third essence, with a daily production of 1×1+2×2+1×4=9.
Assign 3 worker dragons of level 3 to the fourth essence, with a daily production of 3×4=12.
The number of dragon eggs that can be produced is min(⌊31⌋,⌊42⌋,⌊93⌋,⌊124⌋)=min(3,2,3,3)=2.

题意：

• 合成一个龙蛋需要 n 种精华，其中第 i 种精华需要 ai 个单位。
• 有 k 种工具龙，第 j 种工具龙总共有 bj 条，且每单位时间能产出 2^{j−1} 单位的任意一种精华。
• 你需要将每条工具龙分配去生产某种精华，并最大化每单位时间内能产生的龙蛋数量。

思路：

• 二分龙蛋的数量mid，check时判断能否在限定时间内，生产出mid*ai的精华。
• 贪心：开个最大堆维护mid*ai, 我们优先用效率高的工具龙，去生产数量大的精华，要么一次性生产完当前元素，要么一次性用完当前工具龙，浪费的越少，生的蛋就越多。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 5e5+10;
LL n, k, a[maxn], b[maxn], c[maxn];

LL check(LL mid){
    priority_queue<LL, vector<LL>, less<LL>>q;
    for(LL i = 1; i <= n; i++)q.push(a[i]*mid);
    for(LL i = 1; i <= k; i++)c[i] = b[i];
    LL cur = k, spd = (1<<(cur-1));
    while(q.size()){
        LL need = q.top();  q.pop();
        LL cnt = max(1LL, min(c[cur], need / spd));
        c[cur] -= cnt;
        need -= cnt*spd;
        if(need > 0)q.push(need);
        if(c[cur]==0){
            cur--;
            spd = (1 << (cur-1));
            if(cur == 0)return q.size()==0;
        }
    }
    return 1;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    LL T;  cin>>T;
    while(T--){
        cin>>n>>k;
        LL s1 = 0, s2 = 0;
        for(LL i = 1; i <= n; i++)cin>>a[i], s1 += a[i];
        for(LL i = 1; i <= k; i++)cin>>b[i], s2 += b[i]*(1<<(i-1));
        LL l = 0, r = s2/s1+100;
        while(l < r){
            LL mid = l+(r-l+1)/2; //向上取整, 不然3,4死循环
            if(check(mid))l = mid;
            else r = mid-1;
        }
        cout<<l<<"\n";
    }
    return 0;
}