程序员进阶之算法练习（五十八）

正文

题目1

题目链接
题目大意：
输入两个整数a和b，每次操作可以使得a=a+1；
问最少要几次操作，可以使得a可以整除b；

输入：
第一行整数t，表示样例个数； (1≤𝑡≤10000)
接下来t个样例，每个样例一行，有两个整数a、b；(1≤a，b≤10^9)

输出：
最少操作次数；

Examples
input
5
10 4
13 9
100 13
123 456
92 46

output
2
5
4
333
0

题目解析：
为了便于描述，下面用x和y来代替a和b；
如果x<=y，那么操作数就是y-x；
如果x>y，那么可以直接判断x%y==0，不满足则++x；
但是如果这样直接算，这个过程比较慢。在x%y!=0，不断x=x+1的时候，可以确定x/y的结果就是(x+y)/y取整；
那么最小操作次数就是(x + y) / y * y - x 。

int a[N];

int main(int argc, const char * argv[]) {
    // insert code here...
    
    int t;
    cin >> t;
    while (t--) {
        int x, y;
        cin >> x >> y;
        if (x <= y) {
            cout << y - x << endl;
        }
        else {
            if (x % y == 0) {
                cout << 0 << endl;
            }
            else {
                cout << (x + y) / y * y - x << endl;
            }
        }
    }
    
    return 0;
}

题目2

题目链接
题目大意：
有一个长度为n的字符串，有n-2个字符a，有2个字符b；
把这个字符串重新排列，可以若干个字符串，然后按字典序排列，比如说n=5的时候：
aaabb
aabab
aabba
abaab
ababa
abbaa
baaab
baaba
babaa
bbaaa

现在想知道长度为n的字符串重新排列后，第k个字符串是什么；

输入：
第一行整数t，表示样例个数； (1≤𝑡≤10000)
接下来t个样例，每个样例一行，有两个整数 𝑛 and 𝑘 (3≤𝑛≤10^{5,1≤𝑘≤min(2⋅10}9, 𝑛⋅(𝑛−1)/2)

输出：
最少操作次数；

Examples
input
7
5 1
5 2
5 8
5 10
3 1
3 2
20 100

output
aaabb
aabab
baaba
bbaaa
abb
bab
aaaaabaaaaabaaaaaaaa

题目解析：
从n=5样例，我们只看字符b，会从最后面开始，逐渐往前面排；
可以总结出规律，第1个b往前面挪动位置时，分别有：1、2、3、...、n-1种可能；
那么累计这个数字和sum，直到数字sum大于k，此时找到b的第1个位置；
接下来用sum和k的差值，就可以计算第2个b的位置，剩下的字符就全部是a了；

int main(int argc, const char * argv[]) {
    // insert code here...
    
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        for (int i = 1; i <= n; ++i) {
            if (k > i) {
                k -= i;
            }
            else {
                int x = n - i - 1, y = n - k;
                for (int j = 0; j < n; ++j) {
                    if (j == x || j == y) {
                        putchar('b');
                    }
                    else {
                        putchar('a');
                    }
                }
                puts("");
                
                break;
            }
        }
    }
    
    return 0;
}

题目3

题目链接
题目大意：
一个字符串，如果没有连续两个字符是相同的，则称为美丽的字符串；

给出一个字符串s，包括a/b/c/?，四种字符；
现在需要把每个?字符，分别填入a/b/c字符中的一个；

输入：
第一行 𝑡，表示样例数 (1≤𝑡≤1000)
每个样例一行，字符串𝑠 包括 'a', 'b', 'c' 和 '?'四种字符，字符串长度不超过10e5。

输出：
如果有解，则输出填充过后的字符串；
如果无解，则输出-1；

input
3
a???cb
a??bbc
a?b?c

output
ababcb
-1
acbac

题目解析：
首先是可以通过动态规划来解决，dp[i][j]=0/1表示第i个字符为a、b、c（j=0/1/2）是否有解；
当s[i]=='?'时，则可以生成d[i][0]、d[i][1]、d[i][2]三种状态，状态转移方程比较直接。

但是，题目还有另外一种解法：
对于字符串中的?字符，假如某个位置只有一个?连续，则只需考虑相邻的字符，填入一个不冲突的字符填入即可；
如果有多个?连续，因为连续?的相邻字符最多只有两种，但是?可以填入三种字符，则?必然可以填入一个字符，使得三个字符不连续相同；

那么，什么情况下会出现-1的情况？
幸好题目给出了样例：原来的字符就有相同字符的情况。

char a[N];



int main(int argc, const char * argv[]) {
    // insert code here...
    int t;
    cin >> t;
    while (t--) {
        scanf("%s", a);
        int n = (int)strlen(a);
        
        for (int i = 0; i < n; ++i) {
            if (a[i] == '?') {
                bool vis[3] = {0};
                if (i - 1 >= 0) {
                    vis[a[i-1] - 'a'] = 1;
                }
                if (i + 1 < n && a[i + 1] != '?') {
                    vis[a[i+1] - 'a'] = 1;
                }
                for (int j = 0; j < 3; ++j) {
                    if (!vis[j]) {
                        a[i] = 'a' + j;
                    }
                }
            }
        }
        
        bool ok = 1;
        for (int i = 1; i < n; ++i) {
            if (a[i] == a[i - 1]) {
                ok = 0;
            }
        }
        if (ok) {
            printf("%s\n", a);
        }
        else {
            puts("-1");
        }
    }
           
    
    return 0;
}

题目4

题目链接
题目大意：
给出1~n的n个整数组成的数组，每个数字都只有一个；
我们把数字i称为beautiful，如果能够在数组中找到一段连续的数字，这个区间内的数字是1到i；
比如说对于数组[4,5,1,3,2,6]，我们能找到：
[1], [1,3,2], [4,5,1,3,2],[4,5,1,3,2,6] 这四个区间，所以数字1、3、5、6是beautiful，数字2、4不是beautiful；

现在给出一个1~n组成的数组，问数组中有哪些数字是beautiful；

输入：
第一行 𝑡 (1≤𝑡≤1000) 表示接下来有t个样例
每个样例的第一行是𝑛 (1≤𝑛≤2⋅10^5），表示数组的长度；
接下来一行是n个整数；

输出：
每一个样例输出一行长度为n的字符串，每个字符都是01组成，第i个字符为1表示第i个数字是beautiful；

input
3
6
4 5 1 3 2 6
5
5 3 1 2 4
4
1 4 3 2

output
101011
11111
1001

题目解析：

看到题目的第一想法是从小到大排序，然后从1开始枚举数字；
对于某个数字x，如果左边数字比x小，则合并到集合x；
如果右边的数字比x小，则合并到集合x；
这样不断枚举，不断合并，通过集合的元素和x是否相同，就可以判断是否存在解。（对应下面解法A）

更优解：
对于数字k是否有解，其实是看[1, k]这个区间内，所有数字的左边界和右边界的距离，是否刚好等于数字k；
比如说k=3，[1,2,3]三个数字的左边界是3（对应1的位置），右边界是5（对应2的位置），距离是 (5-3+1)=3，所以k=3有解；
比如说k=4, [1,2,3,4]四个数字的左边界是1（对应4的位置），右边界是5（对应2的位置），距离是 (5-1+1)=5≠k，所以k=4无解。（对应下面解法B）

class SolutionA {
    int a[N];
    int fat[N];
    int cnt[N];
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    
    
    int find(int x) {
        if (fat[x] == x) {
            return x;
        }
        int ret = find(fat[x]);
        if (ret != fat[x]) {
            fat[x] = ret;
            cnt[ret] += cnt[x];
            cnt[x] = 0;
        }
        
        return fat[x];
    }

    void merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx > fy) {
            fat[fx] = fy;
            cnt[fy] += cnt[fx];
            cnt[fx] = 0;
        }
        else {
            fat[fy] = fx;
            cnt[fx] += cnt[fy];
            cnt[fy] = 0;
        }
        find(x);
        find(y);
    }
    
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            scanf("%d", &n);
            
            for (int i = 0; i < n; ++i) {
                scanf("%d", &a[i]);
            }
            
            while (!q.empty()) {
                q.pop();
            }
            
            memset(fat, 0, sizeof(fat));
            memset(cnt, 0, sizeof(cnt));
            
            for (int i = 0; i < n; ++i) {
                q.push(make_pair(a[i], i));
            }
            
            while (!q.empty()) {
                pair<int, int> tmp = q.top();
                tmp = q.top();
                q.pop();
                
                fat[tmp.first] = tmp.first;
                cnt[tmp.first] = 1;
                
                int l = tmp.second - 1;
                if (l >= 0 && a[l] < tmp.first) {
                    merge(a[l], tmp.first);
                }
                int r = tmp.second + 1;
                if (r < n && a[r] < tmp.first) {
                    merge(a[r], tmp.first);
                }
                
                if (cnt[find(tmp.first)] == tmp.first) {
                    putchar('1');
                }
                else {
                    putchar('0');
                }
            }
            puts("");
        }
    }
}ac;


class SolutionB {
    int a[N];
    
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            scanf("%d", &n);
            
            for (int i = 0; i < n; ++i) {
                int x;
                scanf("%d", &x);
                a[x-1] = i;
            }
            
            int left = n, right = 0;
            for (int i = 0; i < n; ++i) {
                left = min(left, a[i]);
                right = max(right, a[i]);
                if (right - left == i) {
                    cout << "1";
                }
                else {
                    cout << "0";
                }
            }
            cout << endl;
        }
    }
}ac_fast;

题目5

题目链接
题目大意：
举办一场比赛，有n个人参加比赛，并得到了n个分数p[i]；
现在需要分配金银铜牌的数量分别为g、s、b个，有以下要求：
金银铜的数量必须有一个；（𝑔>0 , 𝑠>0 and 𝑏>0)）
金牌人数要少于银牌和铜牌；（𝑔<𝑠 and 𝑔<𝑏）
金银铜的分数，必须严格减少，金牌分数>银牌分数>铜牌分数>没得奖的分数；
获奖人数不超过总人数的一半；( 𝑔+𝑠+𝑏≤n/2）

输入：
第一行𝑡，表示有t个样例 (1≤𝑡≤10000)
每个样例有两行
第一行 𝑛 (1≤𝑛≤4⋅1e5)
第二行 𝑝1,𝑝2,…,𝑝𝑛 (0≤𝑝𝑖≤1e6， 𝑝1≥𝑝2≥⋯≥𝑝𝑛 )

输出：
每个样例输出一行，三个整数𝑔,𝑠,𝑏；
g=s=b=0表示无法分配；
否则输出g、s、b分别表示金银铜牌的数量。

input
5
12
5 4 4 3 2 2 1 1 1 1 1 1
4
4 3 2 1
1
1000000
20
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
32
64 64 63 58 58 58 58 58 37 37 37 37 34 34 28 28 28 28 28 28 24 24 19 17 17 17 17 16 16 16 16 11

output
1 2 3
0 0 0
0 0 0
2 5 3
2 6 6

题目解析：
总结一下题目的意思：
金银铜铁，共需要4个分数（铁牌表示无得奖）；
金牌人数要少于银牌和铜牌；
金银铜加起来不超过一半；
希望获奖的人尽可能多；

将数字去重，按照数字大小排序，每个数字有一个权值，权值就是人数；
相当于把数组切分成a、b、c、d共4段，要求sum(a)<sum(b) & sum(a)<sum(b)，并且sum(a+b+c)尽可能的大，又不超过权值总和的1/2；

假设新的数组排序之后是s[1~m]，金牌只需要有最少的人数，那么就是s[1]；
从题目的要求来分析，s[1]是分给金牌，s[2~x]分给银牌，x的求法就是直接遍历，累计银牌人数大于金牌；
同理，铜牌的人数也要大于金牌，然后就可以不断遍历，只要满足s[1], s[2], s[3] 之和小于n/2；
剩下所有人分给铁牌。

map<int, int> h;
vector<int> s;

int main(int argc, const char * argv[]) {
    // insert code here...
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        
        h.clear();
        while (!s.empty()) {
            s.pop_back();
        }
        
        for (int i = 0; i < n; ++i) {
            int k;
            scanf("%d", &k);
            ++h[k];
        }
        for (map<int, int>::iterator iter = h.begin(); iter != h.end(); ++iter) {
//            cout << iter->first << " " << iter->second << endl;
            s.push_back(iter->second);
        }
        
        int ans[3] = {0};
        
        if (s.size() >= 4) {
            int x = s.back();
            s.pop_back();
            
            int y = 0;
            while (x >= y && !s.empty()) {
                y += s.back();
                s.pop_back();
            }
         
            int z = 0;
            while (x >= z && !s.empty()) {
                z += s.back();
                s.pop_back();
            }
            
            while (x + y + z <= n / 2) {
                ans[0] = x;
                ans[1] = y;
                ans[2] = z;
                
                if(s.empty()) {
                    break;
                }
                z += s.back();
                s.pop_back();
            }
        }
        
        cout << ans[0] << " " << ans[1] << " " << ans[2] << endl;
    }
           
    
    return 0;
}