ICPC Online Training IV (Div. 2)

约好了一点半和友友出去看电影，所以直接复制了做过的D题的previous submission。前面三道没什么好说的，E是一个比较tricky的思维题，只要想到思路（全靠灵光一闪），后续的implementation约等于0.

在看F的时候友友来敲我门了，有空补上！

A. Polycarp Recovers the Permutation

一种可能的生成方式是把最大值放在一边，剩下的按照由外向内被加入新的permutation。所以只需要把最大值之外的东西反序就行了。

Solution

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>
using namespace std;

#define PII pair<int, int>
#define LL long long

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &it : a)
        cin >> it;
    if (a[0] != n && a[n - 1] != n) {
        cout << -1 << endl;
        return;
    }
    for (int i = n - 1; i >= 0; i--)
        cout << a[i] << " ";
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

B. Array Elimination

// TODO

Solution

#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>
using namespace std;

#define PII pair<int, int>
#define LL long long

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    int res = 0;

    for (auto &it : a)
        cin >> it;
    for (int i = 0; i < 30; i++) {
        int cnt = 0;
        for (int j = 0; j < n; j++)
            if (a[j] & (1 << i))
                cnt++;
        res = gcd(res, cnt);
    }
    for (int i = 1; i <= n; i++)
        if (res % i == 0)
            cout << i << " ";
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

C. Ticks

// TODO

Solution

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>
using namespace std;

#define PII pair<int, int>
#define LL long long

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    bool a[101][101] = {0};
    bool b[101][101] = {0};

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            char c;
            cin >> c;
            if (c == '*')
                a[i][j] = 1;
        }
    for (int i = n - 1; i >= 0; i--)
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 1) {
                int d = 0;
                for (; i - d - 1 >= 0 && j - d - 1 >= 0 && j + d + 1 < m; d++)
                    if (!a[i - d - 1][j - d - 1] || !a[i - d - 1][j + d + 1]) {
                        break;
                    }
                if (d >= k) {
                    b[i][j] = 1;
                    for (int h = 1; h <= d; h++) {
                        b[i - h][j - h] = 1;
                        b[i - h][j + h] = 1;
                    }
                }
            }
        }
    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < m; j++) {
    //         cout << b[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (b[i][j] != a[i][j]) {
                cout << "NO" << endl;
                return;
            }
        }
    }
    cout << "YES" << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

D. Short Task

// TODO

Solution

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <numeric>
#include <algorithm>
using namespace std;
#define MAXN 10000000
int sums[MAXN + 1];
int record[MAXN + 1];
void init()
{
    for (int i = 1; i <= MAXN; i++)
        for (int j = i; j <= MAXN; j += i)
        {
            if (sums[j] < 0 || sums[j] > MAXN - i)
                sums[j] = -1;
            else
                sums[j] += i;
        }
    for (int i = 1; i <= MAXN; i++)
        if (sums[i] > 0 && record[sums[i]] == 0)
            record[sums[i]] = i;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    init();

    int t;
    cin >> t;
    while (t--)
    {
        int c;
        cin >> c;
        cout << (record[c] > 0 ? record[c] : -1) << endl;
    }

    return 0;
}

E. Multiples and Power Differences

题目里主要有两个条件：1. b[i][j] 可以被 a[i][j] 整除；2. b[i][j] 和相邻的格子的差是某个整数的4次方；注意：\(1\leq a[i][j]\leq 16\)，也就是说我们可以先给每个格子填上1到16的最小公倍数，然后间隔地加上a[i][j]的四次方就可以啦！

Solution

#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>
using namespace std;

#define PII pair<int, int>
#define LL long long

int K = 1;

void init() {
    for (int i = 2; i <= 16; i++)
        K = lcm(K, i);
}

void solve() {
    int n, m;
    cin >> n >> m;
    int b[501][501] = {0};
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            int a;
            cin >> a;
            b[i][j] = K;
            if ((i + j) % 2)
                b[i][j] += pow(a, 4);
        }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cout << b[i][j] << " ";
        cout << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    init();
    solve();
    return 0;
}