CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!)做题笔记

A. Farmer John's Challenge

Problem - A - Codeforces

题意：构造出满足条件的数组a，否则输出-1

做法：判断k和n或者1的关系；k==1则输出1就行，k==n就从1输出到n；都不满足就输出-1；
代码：

1. #include <iostream>
2. using namespace std;
3. int main() {
4. int t;
5. cin >> t;
6. while (t--) {
7. int n, k;
8. cin >> n >> k;
9. if (k == 1) {
10. for (int i = 0; i < n; i++)
11. cout << i + 1 << ' ';
12. }
13. else if (k == n) {
14. for (int i = 0; i < n; i++)
15. cout << "1 ";
16. }
17. else
18. {
19. cout << "-1";
20. }
21. cout << '\n';
22. }
23. return 0;
24. }

B. Bessie and MEX

Problem - B - Codeforces 

题意：构造出满足条件a[i]=mex{p1,....,pi}-p[i]的数组p；

做法：判断a[i]的值，大于0直接等于mex，小于0等于mex-a[i];同时用另外一个数组统计是否使用过该mex值，不断更新就行

代码：

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

#include <unordered_map>

using namespace std;

int main() {

    int t;

    cin >> t;

    while (t--) {

        int n;

        cin >> n;

        vector<int>a(n);

        vector<int> p(n);

        vector<int> pd(n + 1,0);

        for (int i = 0; i < n; i++)

            cin >> a[i];

        int mex = 0;

        for (int i = 0; i < n; i++) {

            if (a[i] >= 0) {

                p[i] = mex;

            }

            else {

                p[i] = mex - a[i];

            }

            pd[p[i]] = 1;

            while (pd[mex])

                mex++;

        }

        for (int i = 0; i < n; i++)

            cout << p[i] << ' ';

        cout << endl;

    }

    return 0;

}