2019牛客暑期多校(第七场) 写题记录

J A+B problem

签到 翻转之后相加 再翻转

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int t;
    cin >> t;
    while(t--) {
        string a, b;
        cin >> a >> b;
        ll x = 0, y = 0;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        ll z = 0;
        for(int i = 0; i < a.size(); i++) {
            x = x * 10 + a[i] - '0';
        }
        for(int i = 0; i < b.size(); i++) {
            y = y * 10 + b[i] - '0';
        }
        z = x + y;
        if(!z)
            cout << z << endl;
        else {
            while(z % 10 == 0)
                z /= 10;
            while(z) {
                cout << z % 10;
                z /= 10;
            }
            cout << endl;
        }
    }
    return 0;
}

A String

分割 01 尽快让每段最长最小
最小表示 应该更快一些 不过 只有01 和长度才200

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

string s;

bool ok(int l, int r) {
    if(r == l)
        return 1;
    string ss = "";
    for(int i = l; i <= r; i++)
        ss += s[i];
    string str = ss;
    int x = r - l;
    while(x--) {
        str += str[0];
        str.erase(0, 1);
        if(str < ss)
            return 0;
    }
    return 1;
}

int main() {
    int t;
    cin >> t;
    while(t--) {
        cin >> s;
        int lr = s.size();
        int l = 0, r = lr - 1;
        while(1) {
            for(int i = r; i >= l; i--) {
                if(ok(l, i)) {
                    for(int j = l; j <= i; j++)
                        cout << s[j];
                    cout << ' ';
                    l = i + 1;
                    r = lr - 1;
                    break;
                }
            }
            if(l >= lr)
                break;
        }
        cout << endl;
    }
    return 0;
}

B Irreducible Polynomial

基本代数定理 除了 n == 2 无解没有的拆 >= 3 拆2项压力不打

#include<cstdio>
int main() {
    int n,tp,a[25];
    int cas;
    scanf("%d", &cas);
    while(cas --) {
        scanf("%d", &n);
        for(int i=0; i<=n; scanf("%d",a+i),i++);
        if(n>2||n==2&&a[1]*a[1]>=4*a[0]*a[2])
            printf("No\n");
        else
            printf("Yes\n");
    }
    return 0;
}

C Governing sand

权值线段树
我们 排好序 从小到大枚举 每次吧最小的多余的删掉 大于高度也去掉
枚举完 找最小值

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int, int> P;

int n;
struct no {
    int h, c, p, pos;
} a[maxn];

bool cmp1(no a, no b) {
    return a.c < b.c;
}

bool cmp2(no a, no b) {
    return a.h < b.h;
}

struct node {
    ll num;
    ll sum;
} tree[maxn << 2];

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

void updata(int L, int val, int num, int l, int r, int rt) {
    if (l == r) {
        tree[rt].num += num;
        tree[rt].sum += 1ll * num * val;
        return;
    }
    int mid = l + r >> 1;
    if(L <= mid)
        updata(L, val, num, l, mid, rt << 1);
    else
        updata(L, val, num, mid + 1, r, rt << 1 | 1);
    tree[rt].num = tree[rt << 1].num + tree[(rt << 1) | 1].num;
    tree[rt].sum = tree[rt << 1].sum + tree[(rt << 1) | 1].sum;
}

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

signed main() {
    fastio;
    while (cin >> n) {
        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i].h >> a[i].c >> a[i].p;
            ans += (ll) a[i].c * a[i].p;
        }
        sort(a + 1, a + 1 + n, cmp1);
        for (int i = 0; i < n; i++)
            a[i].pos = i;
        build(1, n, 1);
        sort(a + 1, a + 1 + n, cmp2);

        int prep = 0;
        ll tot = 0;
        ll cnt = a[1].p;
        ll res = ans - 1ll * a[1].p * a[1].c;
        for (int i = 2; i <= n; i++) {
            if (i == n + 1 || a[i].h != a[i - 1].h) {
                ll tmp =  query(tot - (cnt - 1), 1, n, 1) + res;
                if (ans > tmp) ans = tmp;
                cnt = a[i].p;
                while (prep < i) {
                    updata(a[prep].pos, a[prep].c, a[prep].p, 1, n, 1);
                    tot += a[prep].p;
                    prep++;
                }
            } else cnt += a[i].p;
            
            res -= (ll)a[i].c * a[i].p;
        }
        cout << ans << endl;
    }
    return 0;
}

D Number

找个n位 p 的倍数 补0 。。。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int, int> P;

int main() {
	string p;
	int n;
	cin >> n >> p; 
	int lenn = n;
	int lenp = p.size();
	
	if(lenn == lenp ) cout << p << endl;
	else if(lenn < lenp) cout << "T_T" << endl;
	else {
		cout << p ;
		for(int i = 1; i <= lenn - lenp; i ++) {
			cout << 0;
		}cout << endl;
	}
	
	return 0;
}

E Find the median

这道题
首先 我们把能想到线段树 其次 维护 这一片区间 + 1的次数
那么就是 用点代表区间
如果我们考虑用点 代表区间的话 首先我们对这个区间进行一个补长 右边加个一什么的
（5， 6） （7， 9） (9, 11) (11, 11)
我们 左端点不变 右端点 +1 进行离散化前存储
然后 离散化完 我们实际存储
第一 5， 6 区间 被我们 [1, 2)
第二 7， 9 区间 被我们 [2, 4)
第三 9， 11 区间 被我们 [ 3, 6)
第4区间 11 11 被我们 [5, 6) 代替了
这样 左开右闭区间 就能 一个不拉处理他们

如果 我们处理 5， 6 区间 我们只要 直接查 左区间 下标 （右区间 + 1）(我们离散化 + 1 就是为了能不重复的处理区间 这里要补回1)下标 - 1 相当于 第一个区间 1 这个点代表了 5 【2，4）这个区间 代表了7，9
数据差多大 都可以用这样处理的下标 不漏不重的处理

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 4e5 + 10;
int le[maxn], rig[maxn];
int n;
int a1, a2, b1, b2, x[maxn], y[maxn], c1, c2, m1, m2;
int b[maxn << 1], ls[maxn], rs[maxn];
ll sum[maxn << 3], lazy[maxn << 3];
 
void push_down(int l, int r, int root) {
    if(!lazy[root])
        return ;
    int mid = l + r >> 1;
    sum[root << 1] += (ll)(b[mid + 1] - b[l]) * lazy[root];
    sum[root << 1 | 1] += (ll)(b[r + 1] - b[mid + 1]) * lazy[root];
    lazy[root << 1] += lazy[root];
    lazy[root << 1 | 1] += lazy[root];
    lazy[root] = 0;
}
 
void updata(int L, int R, int l, int r, int rt) {
    if(L <= l && R >= r) {
        lazy[rt] += 1;
        sum[rt] += 1ll * (b[r + 1] - b[l]);
        return ;
    }
    push_down(l, r, rt);
    int mid = l + r >> 1;
    if(L <= mid)
        updata(L, R, l, mid, rt << 1);
    if(R > mid)
        updata(L, R, mid + 1, r, rt << 1 | 1);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
 
int query(int l, int r, int rt, ll k) {
    if(l == r)
        return b[l] + (k - 1) / (lazy[rt]); // sum 和 lazy 最后不一样 sum 是这一段所有的和 lazy 只是次数
    int mid = l + r >> 1;
    push_down(l, r, rt);
    if(sum[rt << 1] < k)
        return query(mid + 1, r, rt << 1 | 1, k - sum[rt << 1]);
    else
        return query(l, mid, rt << 1, k);
}
 
signed main() {
    fastio;
    cin >> n;
    cin >> x[1] >> x[2] >> a1 >> b1 >> c1 >> m1;
    cin >> y[1] >> y[2] >> a2 >> b2 >> c2 >> m2;
 
    int len = 0;
    for(int i = 3; i <= n; i ++) {
        x[i] = (1ll * a1 * x[i - 1] + b1 * x[i - 2] + c1) % m1;
        y[i] = (1ll * a2 * y[i - 1] + b2 * y[i - 2] + c2) % m2;
    }
 
    for(int i = 1; i <= n; i ++) {
        ls[i] = min(x[i], y[i]) + 1;
        b[++ len] = ls[i];
        rs[i] = max(x[i], y[i]) + 1;
        b[++ len] = rs[i] + 1;
    }
    sort(b + 1, b + 1 + len);
    len = unique(b + 1, b + 1 + len) - b - 1;
    ll tot = 0;
    for(int i = 1; i <= n; i ++) {
        tot += (rs[i] - ls[i] + 1);
        int ul = lower_bound(b + 1, b + 1 + len, ls[i]) - b;
        int ur = lower_bound(b + 1, b + 1 + len, rs[i] + 1) - b;
        updata(ul, ur - 1, 1, len, 1);
        cout << query(1, len, 1, (tot + 1) / 2) << endl;
    }
    return 0;
}