bupt summer training for 16 #3 ——構造

https://vjudge.net/contest/172464

后來補題發現這場做的可真他媽傻逼

?

A.簽到傻逼題，自己分情況

#include <cstdio>
#include <vector>
#include <algorithm>

using std::vector;
using std::sort;

typedef long long ll;

int n, m;

ll a[2100], b[2100];

ll sa, sb, dis, tmp, qaq;

int t1 = -1, t2 = -1;

int a1, a2, a3, a4;

struct node {
    ll x, y, z;
    bool operator < (const node &a) const {
        return x < a.x;
    }
};

vector <node> e;

ll abs(ll x) {
    return x < 0 ? -x : x;
}

node find1(ll x) {
    node ret = {0, -1, -1};
    int l = 0, r = e.size() - 1, mid;
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(e[mid].x * 2 <= x) ret = e[mid], l = mid + 1;
        else r = mid - 1;
    }
    return ret;
}

node find2(ll x) {
    node ret = {0, -1, -1};
    int l = 0, r = e.size() - 1, mid;
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(e[mid].x * 2 > x) ret = e[mid], r = mid - 1;
        else l = mid + 1;
    }
    return ret;
}

int main() {
    scanf("%d", &n);
    for(int i = 1;i <= n;i ++)
        scanf("%lld", &a[i]), sa += a[i];
    scanf("%d", &m);
    for(int i = 1;i <= m;i ++)
        scanf("%lld", &b[i]), sb += b[i];
    if(abs(sa - sb) <= 1) {
        printf("%lld\n0\n", abs(sa - sb));
        return 0;
    }
    qaq = tmp = dis = sa - sb;
    for(int i = 1;i <= n;i ++) 
        for(int j = 1;j <= m;j ++)
            if(abs(qaq - (a[i] - b[j]) * 2) < abs(dis))
                dis = qaq - (a[i] - b[j]) * 2, t1 = i, t2 = j;
    for(int i = 1;i <= n;i ++)
        for(int j = i + 1;j <= n;j ++)
            e.push_back((node){a[i] + a[j], i, j});
    sort(e.begin(), e.end());
    for(int i = 1;i <= m;i ++)
        for(int j = i + 1;j <= m;j ++) {
            ll k = b[i] + b[j];
            node tt = find1(qaq + k * 2);
            if(tt.y != -1 && abs(qaq + k * 2 - tt.x * 2) < abs(tmp)) tmp = qaq + k * 2 - tt.x * 2, a1 = tt.y, a2 = i, a3 = tt.z, a4 = j;
            tt = find2(qaq + k * 2);
            if(tt.y != -1 && abs(qaq + k *  2 - tt.x * 2) < abs(tmp)) tmp = qaq + k * 2 - tt.x * 2, a1 = tt.y, a2 = i, a3 = tt.z, a4 = j;
        }
    if(abs(qaq) <= abs(dis) && abs(qaq) <= abs(tmp)) printf("%lld\n0\n", abs(qaq));
    else if(abs(dis) <= abs(tmp)) printf("%lld\n1\n%d %d", abs(dis), t1, t2);
    else printf("%lld\n2\n%d %d\n%d %d", abs(tmp), a1, a2, a3, a4);
    return 0;
 }

想寫if-else結果寫完if忘記else了

?

B.我是暴力的O(n^2logn)

首先如果只交換一個數，那O(n^2)都會算吧

那交換兩個數呢，我把n個數兩兩結合并求和，再對他們排序

再枚舉另一數組的數對，二分一下嘗試更新答案

#include <cstdio>
#include <vector>
#include <algorithm>

using std::vector;
using std::sort;

typedef long long ll;

int n, m;

ll a[2100], b[2100];

ll sa, sb, dis, tmp, qaq;

int t1 = -1, t2 = -1;

int a1, a2, a3, a4;

struct node {
    ll x, y, z;
    bool operator < (const node &a) const {
        return x < a.x;
    }
};

vector <node> e;

ll abs(ll x) {
    return x < 0 ? -x : x;
}

node find1(ll x) {
    node ret = {0, -1, -1};
    int l = 0, r = e.size() - 1, mid;
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(e[mid].x * 2 <= x) ret = e[mid], l = mid + 1;
        else r = mid - 1;
    }
    return ret;
}

node find2(ll x) {
    node ret = {0, -1, -1};
    int l = 0, r = e.size() - 1, mid;
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(e[mid].x * 2 > x) ret = e[mid], r = mid - 1;
        else l = mid + 1;
    }
    return ret;
}

int main() {
    scanf("%d", &n);
    for(int i = 1;i <= n;i ++)
        scanf("%lld", &a[i]), sa += a[i];
    scanf("%d", &m);
    for(int i = 1;i <= m;i ++)
        scanf("%lld", &b[i]), sb += b[i];
    if(abs(sa - sb) <= 1) {
        printf("%lld\n0\n", abs(sa - sb));
        return 0;
    }
    qaq = tmp = dis = sa - sb;
    for(int i = 1;i <= n;i ++) 
        for(int j = 1;j <= m;j ++)
            if(abs(qaq - (a[i] - b[j]) * 2) < abs(dis))
                dis = qaq - (a[i] - b[j]) * 2, t1 = i, t2 = j;
    for(int i = 1;i <= n;i ++)
        for(int j = i + 1;j <= n;j ++)
            e.push_back((node){a[i] + a[j], i, j});
    sort(e.begin(), e.end());
    for(int i = 1;i <= m;i ++)
        for(int j = i + 1;j <= m;j ++) {
            ll k = b[i] + b[j];
            node tt = find1(qaq + k * 2);
            if(tt.y != -1 && abs(qaq + k * 2 - tt.x * 2) < abs(tmp)) tmp = qaq + k * 2 - tt.x * 2, a1 = tt.y, a2 = i, a3 = tt.z, a4 = j;
            tt = find2(qaq + k * 2);
            if(tt.y != -1 && abs(qaq + k *  2 - tt.x * 2) < abs(tmp)) tmp = qaq + k * 2 - tt.x * 2, a1 = tt.y, a2 = i, a3 = tt.z, a4 = j;
        }
    if(abs(qaq) <= abs(dis) && abs(qaq) <= abs(tmp)) printf("%lld\n0\n", abs(qaq));
    else if(abs(dis) <= abs(tmp)) printf("%lld\n1\n%d %d", abs(dis), t1, t2);
    else printf("%lld\n2\n%d %d\n%d %d", abs(tmp), a1, a2, a3, a4);
    return 0;
 }

補題的時候，就把比賽代碼三個地方的 int 改成了long long就過了

?

C.別人補題寫的DP一眼看不懂...反正數據范圍也不大，我們來xjb亂搞吧

數據范圍20，時間5s，沒有直接爆搜的思路

答案在0-1之間，滿足單調性...試試二分？那judge呢？暴力dfs枚舉?

效率玄學？并沒有關系！...就當試試咯...過了...比DP還快...

#include <cmath>
#include <cstdio>
#include <algorithm>

using namespace std;

const double eps = 1e-14;

int n, L[21], R[21];

double a[21];

bool dfs(int i, int x) {
    if(i > n)
        return 1;
    int y = L[i] / x;
    if(L[i] % x) y ++;
    for(y *= x;y <= R[i];y += x)
        if(dfs(i + 1, y))
            return 1;
    return 0;
}

bool judge(double k) {
    for(int i = 1;i <= n;i ++)
        L[i] = ceil(a[i] - a[i] * k), R[i] = floor(a[i] + a[i] * k);
    for(int i = L[1];i <= R[1];i ++)
        if(dfs(2, i))
            return 1;
    return 0;
}

int main() {
    scanf("%d", &n);
    for(int i = 1;i <= n;i ++)
        scanf("%lf", &a[i]);
    double l = 0, r = 1.0, mid, ans;
    for(int t = 66;t --;) {
        mid = (l + r) / 2;
        if(judge(mid)) ans = mid, r = mid - eps;
        else l = mid + eps;
    }
    printf("%.12f", ans);
    return 0;
}

看了別人DP代碼...看懂了...

f[i][j]代表把第 i 種貨幣變成 j 的最小答案

我們有一種無賴解是把所有貨幣都變0

所以對于第 i 種貨幣，從 0 枚舉到 a[i] * 2 就可以啦

復雜度O(nklogk)， ?k = max(a[i]) = 20W

這么來說粗略計算我的做法復雜度就是O(nklogk * log(1/eps))...實際優太多

?

D.ans = C(n，3) - 不合法的三角形

對于非法三角形枚舉最大邊 z

再求 x + y <= z 的 (x，y) 有多少對即可

預處理，O(1)回答

#include <cstdio>

typedef long long ll;

const int maxn = 1000010;

ll a[maxn], b[maxn];

ll c(ll x) {
    return x * (x - 1) * (x - 2) / 6;
}

int main() {
    for(int i = 3;i <= 1000000;i ++) a[i] = (i + 1) / 2 - 1;
    for(int i = 4, j = 0;i <= 1000000;i ++) {
        if(!(i & 1)) j ++;
        b[i] = b[i - 1] + j;
    }    
    for(int i = 3;i <= 1000000;i ++) a[i] += a[i - 1], b[i] += b[i - 1];
    int n;
    while(scanf("%d", &n), n >= 3) printf("%lld\n", c(n) - a[n] - b[n]);
    return 0;
}

?

E.