2019牛客暑期多校训练营 第七场

题目链接：https://ac.nowcoder.com/acm/contest/887#question

---

A：

一开始还讨论了很多种情况，后来直接敲了暴力A了。

/* Nowcoder Contest 887
 * Problem A
 * Au: SJoshua
 */
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

bool isPerfect(string str) {
    // cout << "judge " << str << endl;
    string mk = str + str;
    vector <string> strs;
    strs.push_back(str);
    for (int i = 1; i < str.length(); i++) {
        string s = mk.substr(i, str.length());
        strs.push_back(s);
        if (s == str) {
            break;
        }
    }
    sort(strs.begin(), strs.end());
    return *strs.begin() == str;
}

string concat(vector <string> list, string con) {
    string ret = list[0];
    for (auto i = 1; i < list.size(); i++) {
        ret += con;
        ret += list[i];
    }
    return ret;
}

int main(void) {
    int T;
    cin >> T;
    while (T--) {
        string input, cur, str, head, tail, tmp;
        vector <string> ans;
        cin >> input;
        int left = 0, right = 0;
        for (left = 0; left < input.length() && input[left] == '1'; left++);
        for (right = input.length() - 1; right >= 0 && input[right] == '0'; right--);
        for (int i = 0; i < left; i++) head += input[i];
        for (int i = left; i <= right; i++) str += input[i];
        for (int i = right + 1; i < input.length(); i++) tail += input[i];
        int readingOne = false;
        if (!head.empty()) {
            ans.push_back(head);
        }

        vector <string> bits;
        for (auto ch : str) {
            if (ch == '0') {
                if (readingOne) {
                    bits.push_back(tmp);
                    tmp.clear();
                    readingOne = false;
                }
            } else if (ch == '1') {
                if (!readingOne) {
                    readingOne = true;
                }
            }
            tmp += ch;
        }
        bits.push_back(tmp);

        int cnt = 0;
        while (cnt < bits.size()) {
            for (int i = bits.size() - 1; i >= cnt; i--) {
                string tst;
                for (int j = cnt; j <= i; j++) {
                    tst += bits[j];
                }
                if (isPerfect(tst)) {
                    if (!tst.empty()) ans.push_back(tst);
                    cnt = i + 1;
                }
            }
        }

        if (!tail.empty()) {
            ans.push_back(tail);
        }
        cout << concat(ans, " ") << endl;
    }
    return 0;
}

B：

题目只对系数作出了约束。本质就是判函数有没有根，虚根也算。显然n>=3 no。n==2时判delta即可。

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;
const int maxn = 2000;
long long  A[maxn];
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        for (int i = 0; i <= n; i++) {
            cin >> A[i];
        }
        if (n >= 3) {
            printf("No
");
        } else {
            if (n == 2) {
                long long dx = A[1] * A[1] - 4 * A[0] * A[2];
                if (dx < 0) {
                    printf("Yes
");
                } else {
                    printf("No
");
                }
            } else {
                printf("Yes
");
            }
        }
    }
    return 0;
}

C：

枚举每种树，线段树维护每种树的总花费即可。

/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

const int maxn = 1e5 + 10;
struct Tree {
    int height, cost, number, index;
    void input() {
        scanf("%d%d%d", &height, &cost, &number);
    }
} tree[maxn];

bool cmp1(Tree n1, Tree n2) {
    return n1.cost < n2.cost;
}

bool cmp2(Tree n1, Tree n2) {
    return n1.height < n2.height;
}

struct Node {
    int l, r;
    ll num, sum = 0;
} segt[maxn * 3];

void maintain(int curpos) {
    if (segt[curpos].l == segt[curpos].r) return;
    segt[curpos].num = segt[curpos << 1].num + segt[curpos << 1 | 1].num;
    segt[curpos].sum = segt[curpos << 1].sum + segt[curpos << 1 | 1].sum;
}

void build(int curpos, int curl, int curr) {
    segt[curpos].l = curl; segt[curpos].r = curr;
    segt[curpos].num = segt[curpos].sum = 0;
    if (curl == curr) return;
    int mid = curl + curr >> 1;
    build(curpos << 1, curl, mid); build(curpos << 1 | 1, mid + 1, curr);
}

void add(int curpos, int index, int cost, int number) {
    if (segt[curpos].l == index && segt[curpos].r == index) {
        segt[curpos].num += number;
        segt[curpos].sum += (ll)cost * number;
        return;
    }
    int mid = segt[curpos].l + segt[curpos].r >> 1;
    if (index <= mid) add(curpos << 1, index, cost, number);
    else add(curpos << 1 | 1, index, cost, number);
    maintain(curpos);
}

ll query(int curpos, ll num) {
    if (num <= 0) return 0;
    if (num >= segt[curpos].num)
        return segt[curpos].sum;
    if (segt[curpos].l == segt[curpos].r)
        return segt[curpos].sum / segt[curpos].num * num;
    return query(curpos << 1, num) + query(curpos << 1 | 1, num - segt[curpos << 1].num);
}

int main() {
    int n;
    while (~scanf("%d", &n)) {
        ll ans = 0;
        rep0(i, 0, n) {
            tree[i].input();
            ans += (ll)tree[i].cost * tree[i].number; // calculate total cost
        }
        sort(tree, tree + n, cmp1); // sort by cost
        rep0(i, 0, n) tree[i].index = i + 1;
        build(1, 1, n); // build an empty tree
        sort(tree, tree + n, cmp2); // sort by height
        ll totNum = 0, numOfTallestTree = tree[0].number, res = ans - (ll)tree[0].number * tree[0].cost; // re num of tree
        int j = 0;
        rep1(i, 1, n) { // enum every tree as the tallest one
            if (i == n || tree[i].height != tree[i - 1].height) { // if the height is not equal
                ll tmp = query(1, totNum - numOfTallestTree + 1) + res;
                ans = min(ans, tmp);
                numOfTallestTree = tree[i].number;
                if (i < n)
                    while (j < i) {
                        add(1, tree[j].index, tree[j].cost, tree[j].number);
                        totNum += tree[j++].number;
                    }
            } else numOfTallestTree += tree[i].number;
            if (i < n) res -= (ll)tree[i].cost * tree[i].number;
        }
        printf("%lld
", ans);
    }
    return 0;
}

D：

比较p和n的长度，不足补0即可。

/* Nowcoder Contest 887
 * Problem D
 * Au: SJoshua
 */
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
    int n;
    string p;
    cin >> n >> p;
    if (p.length() > n) {
        cout << "T_T" << endl;
        return 0;
    }
    cout << p;
    for (int i = p.length(); i < n; i++) {
        cout << 0;
    }
    cout << endl;
    return 0;
}

J：

模拟题。

/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

ll f(ll x) {
    vector<int>v; v.clear();
    while (x) {
        v.pb(x % 10); x /= 10;
    }
    int _size = v.size();
    ll ret = 0;
    for (int i = 0; i < _size; i++) ret = ret * 10 + v[i];
    return ret;
}

int main() {
    int t; scanf("%d", &t);
    while (t--) {
        ll a, b; scanf("%lld%lld", &a, &b);
        printf("%lld
", f(f(a) + f(b)));
    }
    return 0;
}