Codeforces Round #593 (Div. 2)

A. Stones

思路：水题先取第一堆中的每一个和先取第二堆中的每一个进行比较就行了
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;
}

int t, a, b, c, cnt, ans;

int main(){
//    freopen("my_in.txt", "r", stdin);
//    freopen("my_out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t -- ){
        ans = 0, cnt = 0;
        cin >> a >> b >> c;
        int x, y, z, tmp;
        x = a, y = b, z = c;
        tmp = min(x, y / 2);
        x -= tmp, y -= tmp * 2;
        cnt += 3 * tmp;
        tmp = min(y, z / 2);
        cnt += 3 * tmp;
        ans = max(ans, cnt);
        cnt = 0;
        x = a, y = b, z = c;
        tmp = min(y, z / 2);
        y -= tmp, z -= tmp * 2;
        cnt += 3 * tmp;
        tmp = min(x, y / 2);
        cnt += 3 * tmp;
        ans = max(ans, cnt);
        cout << ans << "
";
    }
    return 0;
}

B. Alice and the List of Presents

思路：直接(left(2 ^ m - 1 ight) ^ 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 mod = 1e9 + 7;

ll n, m, ans;

int main(){
//    freopen("my_in.txt", "r", stdin);
//    freopen("my_out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    ans = Pow_mod(Pow_mod(2, m, mod) - 1, n, mod);
    cout << ans << "
";
    return 0;
}

C. Labs

思路：构造出类似于

[egin{matrix} 1 & 6 & 7\ 2 & 5 & 8\ 3 & 4 & 9\ end{matrix} ]

即可满足题意

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 = 310;

int n, cnt;
int mp[N][N];

int main(){
//    freopen("my_in.txt", "r", stdin);
//    freopen("my_out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++ ){
        if (i & 1){
            for (int j = 1; j <= n; j ++ )
                mp[j][i] = ++ cnt;
        }
        else{
            for (int j = n; j >= 1; j -- ){
                mp[j][i] = ++ cnt;
            }
        }
    }
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j < n; j ++ )
            cout << mp[i][j] << " ";
        cout << mp[i][n] << "
";
    }
    return 0;
}

D. Alice and the Doll

思路：暴力模拟即可
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 = 1e5 + 10;

ll n, m, k, ans;
set<int> X[N], Y[N];
set<int> XX, YY;

void calc(int x, int y, int d){
    int z;
    set<int>::iterator xx, yy;
    if (d == 1){
        xx = X[x].upper_bound(y), yy = XX.upper_bound(y);
        if (xx == X[x].end())
            z = (*yy) - 1;
        else
            z = min(*xx, *yy) - 1;
        if (z == y)
            return ;
        else{
            ans += z - y;
            YY.insert(x);
            calc(x, z, 2);
        }
    }
    else if (d == 2){
        xx = Y[y].upper_bound(x), yy = YY.upper_bound(x);
        if (xx == Y[y].end())
            z = (*yy) - 1;
        else
            z = min(*xx, *yy) - 1;
        if (z == x)
            return ;
        else{
            ans += z - x;
            XX.insert(y);
            calc(z, y, 3);
        }
    }
    else if (d == 3){
        xx = X[x].lower_bound(y), yy = XX.lower_bound(y);
        yy -- ;
        if (xx == X[x].begin())
            z = (*yy) + 1;
        else{
            xx -- ;
            z = max(*xx, *yy) + 1;
        }
        if (z == y)
            return ;
        else{
            ans += y - z;
            YY.insert(x);
            calc(x, z, 4);
        }
    }
    else if (d == 4){
        xx = Y[y].lower_bound(x), yy = YY.lower_bound(x);
        yy -- ;
        if (xx == Y[y].begin())
            z = (*yy) + 1;
        else{
            xx -- ;
            z = max(*xx, *yy) + 1;
        }
        if (z == x)
            return ;
        else{
            ans += x - z;
            XX.insert(y);
            calc(z, y, 1);
        }
    }
}

int main(){
//    freopen("my_in.txt", "r", stdin);
//    freopen("my_out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ans = 1;
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i ++ ){
        int x, y;
        cin >> x >> y;
        X[x].insert(y);
        Y[y].insert(x);
    }
    XX.insert(0), XX.insert(m + 1);
    YY.insert(0), YY.insert(n + 1);
    calc(1, 1, 1);
    if (ans == n * m - k){
        printf("Yes
");
        return 0;
    }
    ans = 1;
    XX.clear(), YY.clear();
    XX.insert(0), XX.insert(m + 1);
    YY.insert(0), YY.insert(n + 1);
    calc(1, 1, 2);
    if (ans == n * m - k){
        printf("Yes
");
        return 0;
    }
    printf("No
");
    return 0;
}