2020 Multi-University Training Contest 10

1003 Mine Sweeper

• 思路：随机数生成

• AC代码

---

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

const int d[8][2] = {1, 0, 0, 1, -1, 0, 0, -1, -1, -1, -1, 1, 1, -1, 1, 1};

int t, s;
map<int, vector<vector<char> >> mp;

void init(){
    srand(time(NULL));
    for (int k = 1; k <= 50000; k ++ ){
        int r = (rand() % 25) + 1, c = (rand() % 25) + 1;
        vector<vector<char> > ans(r, vector<char>(c));
        for (int i = 0; i < r; i ++ )
            for (int j = 0; j < c; j ++ )
                ans[i][j] = (rand() % 2) ? 'X' : '.';
        int sum = 0;
        for (int i = 0; i < r; i ++ ){
            for (int j = 0; j < c; j ++ ){
                if (ans[i][j] == '.'){
                    int cnt = 0;
                    for (int l = 0; l < 8; l ++ ){
                        int dx = i + d[l][0], dy = j + d[l][1];
                        if ((dx >= 0 && dx <= r - 1) && (dy >= 0 && dy <= c - 1) && ans[dx][dy] == 'X')
                            cnt ++ ;
                    }
                    sum += cnt;
                }
            }
        }
        mp[sum] = ans;
    }
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    init();
    cin >> t;
    while (t -- ){
        cin >> s;
        vector<vector<char> > ans = mp[s];
        int r = ans.size(), c = ans[0].size();
        cout << r << " " << c << "\n";
        for (int i = 0; i < r; i ++ ){
            for (int j = 0; j < c; j ++ )
                cout << ans[i][j];
            cout << "\n";
        }
    }
    return 0;
}

1004 Permutation Counting

• 思路：

\[b = 0 \\ dp[i][j] = \sum_{k=1}^{j-1}dp[i-1][k] \\ b = 1 \\ dp[i][j] = \sum_{k=j+1}^{k=i}dp[i-1][k] \\ \]

再将复杂度降成\(O(n^2)即可\)

• AC代码

---

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

const int N = 5010;
const int mod = 1e9 + 7;

int t, n, b, ans;
ll dp[N][N];

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t -- ){
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        ans = 0;
        cin >> n;
        for (int i = 1; i < n; i ++ ){
            cin >> b;
            if (b == 0)
                for (int j = 1; j <= i; j ++ )
                    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 1]) % mod;
            else
                for (int j = i - 1; j >= 0; j -- )
                    dp[i][j] = (dp[i][j + 1] + dp[i - 1][j]) % mod;
        }
        for (int i = 0; i < n; i ++ )
            ans = (1ll * ans + dp[n - 1][i]) % mod;
        cout << ans << "\n";
    }
    return 0;
}

1011 Task Scheduler

• 思路：若\(k\)不为0，按t降序排列后输出原次序，若 \(k\)为0，输出\(1-n\)

• AC代码

---

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

const int N = 110;

int T, n, m, k;

struct node{
    int t, id;
}a[N];

inline bool cmp(node p, node q){
    if (p.t != q.t)
        return p.t > q.t;
    return p.id < q.id;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while (T -- ){
        cin >> n >> m >> k;
        for (int i = 1; i <= n; i ++ ){
            cin >> a[i].t;
            a[i].id = i;
        }
        if (k)
            sort(a + 1, a + n + 1, cmp);
        for (int i = 1; i < n; i ++ )
            cout << a[i].id << " ";
        cout << a[n].id << "\n";
    }
    return 0;
}