CF 1367D Task On The Board

傳送門

題目：

Polycarp wrote on the board a string s containing only lowercase Latin letters ('a'-'z'). This string is known for you and given in the input.

After that, he erased some letters from the string s, and he rewrote the remaining letters in any order. As a result, he got some new string t. You have to find it with some additional information.

Suppose that the string t has length m and the characters are numbered from left to right from 1 to m. You are given a sequence of m integers: b1,b2,…,bm, where bi is the sum of the distances |i−j| from the index i to all such indices jj that tj>ti (consider that 'a'<'b'<...<'z'). In other words, to calculate bi, Polycarp finds all such indices j that the index j contains a letter that is later in the alphabet than ti and sums all the values |i−j|.

For example, if t = "abzb", then:

• since t1='a', all other indices contain letters which are later in the alphabet, that is: b1=|1−2|+|1−3|+|1−4|=1+2+3=6;
• since t2='b', only the index j=3 contains the letter, which is later in the alphabet, that is: b2=|2−3|=1;
• since t3='z', then there are no indexes j such that tj>ti, thus b3=0;
• since t4='b', only the index j=3 contains the letter, which is later in the alphabet, that is: b4=|4−3|=1.

Thus, if t = "abzb", then b=[6,1,0,1].

Given the string s and the array b, find any possible string t for which the following two requirements are fulfilled simultaneously:

• t is obtained from ss by erasing some letters (possibly zero) and then writing the rest in any order;
• the array, constructed from the string tt according to the rules above, equals to the array b specified in the input data.

思路：

我們可以確定的是位置上權值是0的字符，我們貪心的用第一個符合“0個數”的最大的字符去填充，然后我們把其他每一位減去這些最大字符提供的權值，這樣我們又會找到第二大的字符，因為第二大的字符的權值是由第一大的字符提供的，按照這樣執行，直到所有位置都被填充即可，

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <queue>
 5 #include <string>
 6 #include <vector>
 7 #include <cmath>
 8 #include <stack>
 9 #include <map>
10  
11 using namespace std;
12   
13 #define ll long long
14 #define pb push_back
15 #define fi first
16 #define se second
17   
18 const int N = 2e6 + 10;
19 int cnt[N];
20 int v[N];
21 int vis[N];
22 char t[N];
23 
24 void solve()
25 {
26     int T;
27     cin >> T;
28     while(T--){
29 
30         //個數清空
31         for(int i = 0; i <= 28; ++i) cnt[i] = 0;
32 
33         string s;
34         cin >> s;
35         //統計每個字符的個數
36         for(auto ch : s){
37             cnt[ch - 'a']++;
38         }
39 
40         
41         int n;
42         cin >> n;
43         //權值
44         for(int i = 1; i <= n; ++i) cin >> v[i];
45         //已經填過
46         for(int i = 1; i <= n; ++i) vis[i] = false;
47 
48         vector<int > zero_inx;
49         int len = 0;
50         //使用到哪個字符
51         int cnt_inx = 26;
52 
53         while(len != n){
54             zero_inx.clear();
55             for(int i = 1; i <= n; ++i){
56                 if(vis[i] || v[i]) continue;
57                 zero_inx.pb(i);
58                 vis[i] = true;
59             }
60             int _size = zero_inx.size(); 
61             len += _size;
62             char ch;
63             for(int i = cnt_inx; i >= 0; --i){
64                 if(cnt[i] < _size) continue;
65                 ch = 'a' + i;
66                 cnt[i] = 0;
67                 cnt_inx = i;
68                 break;
69             }
70 
71             //減去貢獻的權值，填充字符
72             for(int i = 0; i < _size; ++i){
73                 t[zero_inx[i]] = ch;
74                 int d = 0;
75                 for(int j = zero_inx[i] + 1; j <= n; ++j) v[j] -= ++d;
76                 d = 0;
77                 for(int j = zero_inx[i] - 1; j >= 1; --j) v[j] -= ++d;
78             }
79         }
80         //cout << "====================" << endl;
81         for(int i = 1; i <= n; ++i) cout << t[i];
82         cout << endl;
83         //cout << "====================" << endl;
84     }
85 
86 }
87   
88 int main()
89 {
90     ios::sync_with_stdio(false);
91     cin.tie(0);
92     cout.tie(0);
93 
94     solve();
95  
96     return 0;
97 }

標籤：其他

上一篇：CF 1368B Codeforces Subsequences

下一篇：0621. Task Scheduler (M)