题解报告（CDUT暑期集训——第二场）

题解报告（CDUT暑期集训——第二场）

---

D - Game

HDU - 6312

• 思路：水题 Alice一直是必胜态

• AC代码

---

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<algorithm>
#include<string>
#include<string.h>
#include<vector>
#include<stack>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll Pow(ll a, ll b, ll c){
    ll ans = 1;
    a %= c;
    while (b){
        if (b & 1) ans = (ans * a) % c;
        a = (a * a) % c;
        b >>= 1;
    }
    return (ans % c);
}

bool cmp(const int &a, const int &b){
    return a < b;
}

ll gcd(ll x, ll y){
    return x % y == 0 ? y : gcd(y, x % y);
}

ll lcm(ll x, ll y){
    return x / gcd(x, y) * y;
}

int n;

int main(){
    while (scanf("%d", &n) != EOF){
        printf("Yes
");
    }
    return 0;
}

E - Hack It

HDU - 6313

• 思路：构造矩阵 可构造一个n * n的每行1的个数为(sqrt{n}) 则总的1的个数为n * (sqrt{n}) 题目要求1的总个数不少于85000 n * (sqrt{n}) >= 85000 (Rightarrow) n >= 1933 对n * n的矩阵分块成n个(sqrt{n}) * (sqrt{n})的矩阵 令p = (sqrt{n}) 从n = (2 ^ 2), (3 ^ 2), ... （在草稿纸上瞎构造矩阵画出来 发现每一个p * p的小矩阵构成了一个模p循环加群 但是当p为合数时 一定会有重复的 即不满足题意 所有p为素数 由n >= 1933可得p = 47 然后按着递推公式构造矩阵就行了

• AC代码

---

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<algorithm>
#include<string>
#include<string.h>
#include<vector>
#include<stack>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

const int N = 5010;

int g[N][N];

int main(){
    int p = 47, n = 2000;
    int gx, gy;
    for (int i = 0; i < p; i ++ ){
        for (int j = 0; j < p; j ++ ){
            for (int k = 0; k < p; k ++ ){
                gx = i * p + j;
                gy = k * p + (j * k + i) % p;
                g[gx][gy] = 1;
            }
        }
    }
    printf("%d
", n);
    for (int i = 0; i < n; i ++ ){
        for (int j = 0; j < n; j ++ )
            printf("%d", g[i][j]);
        printf("
");
    }
    return 0;
}

G - Naive Operations

HDU - 6315

• 思路：去洛谷上看的线段树然后套的板子 照着板子改 维护区间内a的最大值和b的最小值就行了 注意区间内a的最大值小于b的最小值时跳出（因为这种情况下 ∀i ∈( l, r) ai / bi = 0 对结果无影响

• AC代码

---

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<algorithm>
#include<string>
#include<string.h>
#include<vector>
#include<stack>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

const int N = 100010;

int n, m, l, r;
char op[10];
int b[N], sum[N << 2], tag[N << 2], maxa[N << 2], minb[N << 2];

inline int lson(int x){
    return x << 1;
}

inline int rson(int x){
    return x << 1 | 1;
}

inline void push_up(int p){
    sum[p] = sum[lson(p)] + sum[rson(p)];
    maxa[p] = max(maxa[lson(p)], maxa[rson(p)]);
    minb[p] = min(minb[lson(p)], minb[rson(p)]);
}

inline void push_down(int p){
    if (tag[p]){
        maxa[lson(p)] += tag[p];
        maxa[rson(p)] += tag[p];
        tag[lson(p)] += tag[p];
        tag[rson(p)] += tag[p];
        tag[p] = 0;
    }
}

void build(int p, int l, int r){
    tag[p] = 0;
    if (l == r){
        sum[p] = 0;
        maxa[p] = 0;
        minb[p] = b[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(lson(p), l, mid);
    build(rson(p), mid + 1, r);
    push_up(p);
}

inline void update(int L, int R, int l, int r, int p){
    if (L <= l && R >= r){
        maxa[p] ++;
        if (maxa[p] < minb[p]){
            tag[p] ++;
            return ;
        }
        if (l == r && maxa[p] >= minb[p]){
            sum[p] ++;
            minb[p] += b[l];
            return ;
        }
    }
    push_down(p);
    int mid = (l + r) >> 1;
    if (L <= mid) update(L, R, l, mid, lson(p));
    if (R > mid) update(L, R, mid + 1, r, rson(p));
    push_up(p);
}

int query(int L, int R, int l, int r, int p){
    int ans = 0;
    if (L <= l && R >= r)
        return sum[p];
    int mid = (l + r) >> 1;
    push_down(p);
    if (L <= mid) ans += query(L, R, l, mid, lson(p));
    if (R > mid) ans += query(L, R, mid + 1, r, rson(p));
    return ans;
}

int main(){
    while (scanf("%d%d", &n, &m) != EOF){
        for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);
        build(1, 1, n);
        while (m -- ){
            scanf("%s%d%d", op, &l, &r);
            switch(op[0]){
                case 'a':
                    update(l, r, 1, n, 1);
                    break;
                case 'q':
                    printf("%d
", query(l, r, 1, n, 1));
            }
        }
    }
    return 0;
}

J - Swaps and Inversions

HDU - 6318

• 思路：就是求逆序数cnt 然后cnt * min(x, y)就行了（最开始写的merge一直TLE 把l写成了1（该打 然后重写了一遍merge竟然过了

• AC代码

---

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<algorithm>
#include<string>
#include<string.h>
#include<vector>
#include<stack>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

const int N = 100010;

int a[N], b[N];
ll n, x, y, cnt;

void merge_(ll l, ll r){
    if (r - l < 1) return ;
    ll mid = (l + r) >> 1;
    merge_(l, mid);
    merge_(mid + 1, r);
    ll i = l, j = mid + 1;
    ll pos = 0;
/*    for (int k = 1; k <= r; k ++ ){
        if (j > r || i <= mid && a[i] < a[j]) b[k] = a[i ++];
        else{
            b[k] = a[j ++];
            cnt += mid - i + 1;
        }
    }
    for (int k = l; k <= r; k ++ ) a[k] = b[k];*/
    while (i <= mid && j <= r){
        if (a[i] > a[j]){
            b[++ pos] = a[j ++];
            cnt += mid - i + 1;
        }
        else b[++ pos] = a[i ++];
    }
    while (i <= mid) b[++ pos] = a[i ++];
    while (j <= r) b[++ pos] = a[j ++];
    pos = 0;
    for (ll k = l; k <= r; k ++) a[k] = b[++ pos];
}

int main(){
    while (scanf("%lld%lld%lld", &n, &x, &y) != EOF){
        cnt = 0;
        for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
        merge_(1, n);
        printf("%lld
", cnt * min(x, y));
    }
    return 0;
}