A simple Blog for wyx I've been down the bottle hoping.
CF 2016~2017 泛做
发表于: | 分类: Oi | 评论:0 | 阅读:89

不行了 老园丁与小司机写不动啊 开始写CF了

预计要完成10道,现在完成了8/10

404D Anton and School

给你一个括号序列,问有多少子串满足前一半全都是 ( ,后一半都是 ) ,且是一个合法的括号序列

大力枚举一下最后一个左括号的位置,考虑包括他他左面有$n$个 (, 右面有$m$个 ) ,那么显然这个位置的贡献是

$$\sum_{i=1}^{min(n,m)}{C_{n-1}^{i-1} C_{m}^i}$$

这个复杂度是$O(n^2)$的,我们进行一定的优化

注意到$C_n^i = C_n^{n-i}$, 两个$C$上面的数字之和是定值

可以抽象成这样一个模型,一共有两坨球,左面随便取$i$个,右面取$k-i$个,最后把两个方案乘在一起求和。

这东西显然和在两坨球里面一起取$k$个是一样的

所以上面的式子最后化简出来等于$C_{n+m-1}^{m-1}$

然后就是组合数水水,$O(n)$

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5+5;
const int mod = 1e9+7;
typedef long long LL;
LL fac[N], ifac[N];
inline int pow(int a,int b) {
    LL res = 1;
    for(;b;b>>=1,a=(LL)a*a%mod)
        if(b&1)
            res = res * a % mod;
    return res;
}

inline void init() {
    const int Max = 2e5;
    fac[0] = 1;
    for(int i=1;i<=Max;++i) fac[i] = fac[i-1] * i %mod;
    ifac[Max] = pow(fac[Max], mod-2);
    for(int i=Max-1;~i;--i) ifac[i] = ifac[i+1] * (i+1) % mod;
}

inline int C(int n,int m) {
    if(n < m || m < 0) return 0;
    return fac[n] * ifac[m] % mod * ifac[n-m] % mod;
}

char str[N];
int sum1[N], sum2[N];

int main() {
//  freopen("tt.in","r",stdin);
    init();
    scanf("%s", str+1);
    int len = strlen(str+1);
    for(int i=1;i<=len;++i) sum1[i] = sum1[i-1] + (str[i] == '(');
    for(int i=len;i>=1;--i) sum2[i] = sum2[i+1] + (str[i] == ')');
    LL ans = 0;
    for(int i=1;i<len;++i) 
        if(str[i] == '(')
            (ans += C(sum1[i] + sum2[i] - 1, sum2[i]-1)) %= mod;
    cout << ans << endl;
}

404E. Anton and Permutation

当时我读完题之后我的表情是这样的
还有这种操作?

这尼玛不是BZ原题

原来现在CF也出不出来什么题了…已经在BZ买了权限然后上BZ找题出比赛了……

说一下怎么做吧,我写的是线段树套权值线段树,直接大力数点就行了

当时我还写了一个$CDQ$分治,想了想,还不如直接树套树呢……那个还得回退

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 2e5+5;
const int Maxm = 195 * N;
using namespace std;
typedef long long LL;

int n, q;

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int root[N<<2], tr[Maxm], ls[Maxm], rs[Maxm], sz, a[N];

inline void insert(int &x,int l,int r,int pos,int val) {
    if(!x) x = ++sz;
    tr[x] += val;
    if(l==r) return;
    int mid = (l+r) >> 1;
    if(pos <= mid) insert(ls[x], l, mid, pos, val);
    else insert(rs[x], mid+1, r, pos, val);
} 

inline int ask(int k,int l,int r,int x,int y) {
    if(!k) return 0;
    if(l==x && r==y) return tr[k];
    int mid = (l+r) >> 1;
    if(y <= mid) return ask(ls[k], l, mid, x, y);
    else if(x > mid) return ask(rs[k], mid+1, r, x, y);
    else return ask(ls[k], l, mid, x, mid) + ask(rs[k], mid+1, r, mid+1, y);
}

inline int ask(int k,int l,int r,int x1,int x2,int y1,int y2) {
    if(l == x1 && r == x2) return ask(root[k], 1, n, y1, y2);
    int mid = (l+r) >> 1;
    if(x2 <= mid) return ask(k<<1, l, mid, x1, x2, y1, y2);
    else if(x1 > mid) return ask(k<<1|1, mid+1, r, x1, x2, y1, y2);
    else return ask(k<<1, l, mid, x1, mid, y1, y2) + ask(k<<1|1, mid+1, r, mid+1, x2, y1, y2);
}

inline void change(int k,int l,int r,int pos,int val,int opt) {
    insert(root[k], 1, n, val, opt);
    if(l==r) return;
    int mid = (l+r) >> 1;
    if(pos <= mid) change(k<<1, l, mid, pos, val, opt);
    else if(pos > mid) change(k<<1|1, mid+1, r, pos, val, opt);
}

int main() {
//  freopen("tt.in","r",stdin);
    LL ans = 0;
    n = read(), q = read();
    for(int i=1;i<=n;++i) a[i] = i;
    for(int i=1;i<=n;++i) {
        change(1,1,n,i,a[i],1);
        ans += ask(1,1,n,1,i,a[i],n)-1;
    }

    for(int i=1;i<=q;++i) {
        int x = read(), y = read();
        if(x > y) swap(x, y);
        if(x == y)  {
            printf("%I64d\n", ans);
            continue;
        }
        if(x+1 == y) {
            if(a[x] < a[y]) ans ++;
            else ans --;
            change(1,1,n,x,a[x],-1);
            change(1,1,n,y,a[y],-1);    
            change(1,1,n,x,a[y],1);
            change(1,1,n,y,a[x],1);
            swap(a[x], a[y]);
            printf("%I64d\n", ans);
            continue;
        }
        change(1,1,n,x,a[x],-1);
        change(1,1,n,y,a[y],-1);
        ans += ask(1,1,n,x+1,y-1,a[x],n);
        ans -= ask(1,1,n,x+1,y-1,1,a[x]);
        ans -= ask(1,1,n,x+1,y-1,a[y],n);
        ans += ask(1,1,n,x+1,y-1,1,a[y]);
        change(1,1,n,x,a[y],1);
        change(1,1,n,y,a[x],1);
        if(a[x] < a[y]) ans ++;
        else ans --;
        swap(a[x], a[y]);
        printf("%I64d\n", ans);
    }
}

C. The Great Mixing

题目大意

给你$n$个数字,任意选取,每个数字可以选取多次,问最后使得平均数等于$n$最少需要几个数字

傻题一个,大力枚举一下答案,然后用$bitset$或一下看看是否可行就行了。

#include <bitset>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6+5;
int a[N+5];

bitset <2000+5> b[2];

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int main() {
    int k = read(), n = read();
    for(int i=0;i<n;++i) a[i] = read() - k;
    sort(a,a+n);
    int top = 0;
    for(int i=1;i<n;++i) if(a[i] != a[i-1]) a[++top] = a[i];
    n = top+1;
    b[0].set(1000);
    for(int i=1;i<=1000;++i) {
        int o = i & 1, op = (i+1) & 1;
        b[o].reset();
        for(int j=0;j<n;++j) {
            if(a[j] < 0) b[o] |= b[op] << (-a[j]);
            else b[o] |= b[op] >> a[j];
        }
        if(b[o][1000]) {
            cout << i << endl;
            return 0;
        }
    }
    puts("-1");
}

407D. Finding lines

题目大意

平面内有$n$条直线,不是水平就是竖直,然后你每次与测评机交汇,你问一个点$(x,y)$,他告诉你距离这个点最近的直线的距离.

求这$n$条直线,调用次数不超过$4n\log(n)$

题解

好题!

直接在$y=x$这条直线上分治就行了,注意到如果距离为$d$,那$[l-d+1,r+d-1]$内必然不存在交点,所以直接递归$[l,mid-d],[mid+d,r]$,就能找到$n$个交点,那么确定一条直线是竖直还是水平就大力再找一个不在任意一条直线上的点,然后每次询问$(x,temp),(temp,x)$就行了,等于0说明是竖直或水平了

分治的复杂度?每次要么找到一个交点,要么区间长度缩小一半,显然复杂度不超过$n\log{n}$

#include <vector>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define pb push_back
using namespace std;

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int temp;

inline int ask(int x,int y) {
    printf("0 %d %d\n", x, y);
    fflush(stdout);
    return read();
}

vector <int> V;

inline void solve(int l,int r) {
    if(l > r) return;
    int mid = (l+r) >> 1;
    int tt = ask(mid,mid);
    if(tt == 0) {
        V.pb(mid);
        solve(l,mid-1);
        solve(mid+1,r);
    }
    else {
        solve(l,mid-tt);
        solve(mid+tt,r);
        temp = mid;
    }
}

vector <int> ans1, ans2;

int main() {
    solve(-1e8,1e8);
    for(int i=0;i<V.size();++i) {
        if(ask(V[i],temp) == 0) ans1.pb(V[i]);
        if(ask(temp,V[i]) == 0) ans2.pb(V[i]);
    }
    cout << 1 << ' ' << ans1.size() << ' ' << ans2.size() << endl;
    for(int i=0;i<ans1.size();++i) printf("%d ",ans1[i]);
    puts("");
    for(int i=0;i<ans2.size();++i) printf("%d ",ans2[i]);
    return 0;
}

EDU 21E. Selling Souvenirs

题目大意:体积为123的背包

w=1的时候显然贪心

w=1或者w=2的时候把两个东西排序然后dp就行了,维护一个三元组表示当前的价值,第一个选的个数和第二个选的个数然后大力枚举第三个就行了

不知道为什么我又想起了thupc被傻逼分块背包支配的恐惧

#include <vector>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define pb push_back
typedef long long LL;
const int N = 3e6;
inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

struct data {
    LL val;int num1, num2;
    data (LL _val = 0, int _num1 = 0, int _num2 = 0)
    :val(_val), num1(_num1), num2(_num2) {}
    bool operator < (const data &z) const {
        return val < z.val;
    }

} F[N], temp1, temp2;

vector <LL> a[4];

inline bool cmp(int a,int b) {
    return a > b;
}

int main() {
    int n, m;
    cin >> n >> m;
    for(int i=1;i<=n;++i) {
        int w = read(), val = read();
        a[w].pb(val);
    }
    F[0] = data(0,-1,-1);
    for(int i=1;i<=3;++i) sort(a[i].begin(), a[i].end(), cmp);
//  cout << a[1].size() << ' ' << a[2].size() << endl;
    for(int i=1;i<=m;++i) {
        temp1 = temp2 = F[0];
        if(F[i-1].num1 + 1 < a[1].size()) temp1 = data(F[i-1].val + a[1][F[i-1].num1+1], F[i-1].num1+1, F[i-1].num2);
        if(i >= 2 && F[i-2].num2+1 < a[2].size()) temp2 = data(F[i-2].val + a[2][F[i-2].num2+1], F[i-2].num1, F[i-2].num2+1);
        F[i] = max(temp1, temp2);
        F[i] = max(F[i], F[i-1]);
    }
    for(int i=1;i<a[3].size();++i) a[3][i] += a[3][i-1];
    LL ans = 0;
    for(int i=0;i<a[3].size();++i) {
        int left = m - (i+1) * 3;
        if(left >= 0) ans = max(ans, F[left].val + a[3][i]);
    }
    ans = max(F[m].val, ans);
    cout << ans << endl;
}

Tinkoff Challenge - Final Round (Codeforces Round #414, rated, Div. 1 + Div. 2) F

尼玛有文化衫的场真难做……我终于知道为啥DDF那天FST了

这题就是让你把一段区间$[l,r]$数位为$x$的都换成$y$

啥叫数位为$x$?举个栗子:38变成88懂没?

怎么做?非常简单的,维护10棵线段树分别表示权值为$x$的数位出现的次数然后大力转移就行了

注意修改的时候要$O(10)$要不然就乱套了,让他实现一个“路径压缩”

尼玛我A了之后发现一坨人写的是$O(100)$的转移比我$O(10)$的转移快一倍啊这是要干啥啊?

真的有这种操作

#include <vector>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+5;
const int M = N << 3;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int a[N];
int P[N];

struct seg {
    int lazy[10];
    LL cnt[10];
    seg () {
        memset(cnt, 0, sizeof cnt);
    }

    inline bool empty() {
        bool flag = false;
        for(int i=0;i<10;++i) flag |= (lazy[i] != i);
        return !flag; 
    }

    void operator += (const seg &z) {
        for(int i=0;i<10;++i) cnt[i] += z.cnt[i];
    }

    inline LL get() {
        LL ans = 0;
        for(int i=0;i<10;++i) ans += cnt[i] * i;
        return ans;
    }
} tr[M];

inline void updata(int k) {
    for(int i=0;i<10;++i) tr[k].cnt[i] = tr[k<<1].cnt[i] + tr[k<<1|1].cnt[i];
}

inline void build(int k,int l,int r) {
    for(int i=0;i<10;++i) tr[k].lazy[i] = i;
    if(l==r) {
        int cnt = 1;
        while(a[l]) {
            tr[k].cnt[a[l]%10] += P[cnt];
            cnt ++;
            a[l] /= 10;
        }
        return;
    }
    int mid = (l+r) >> 1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    updata(k);
}

#define pb push_back
inline void down(int k,int l,int r) {
//  if(l==r) return;
    if(tr[k].empty()) return;
    static vector <int> v[10];
    static LL sum[10];
    {
        for(int i=0;i<10;++i) v[i].clear();
        int ls = k<<1;
        for(int i=0;i<10;++i) v[tr[ls].lazy[i]].pb(i);
        for(int i=0;i<10;++i) sum[i] = tr[ls].cnt[i];
        for(int i=0;i<10;++i) if(tr[k].lazy[i] != i){
            for(int j=0;j<v[i].size();++j) 
                tr[ls].lazy[v[i][j]] = tr[k].lazy[i];
            sum[tr[k].lazy[i]] += tr[ls].cnt[i];
            sum[i] -= tr[ls].cnt[i];
        }
        for(int i=0;i<10;++i) tr[ls].cnt[i] = sum[i];
    }
    {
        for(int i=0;i<10;++i) v[i].clear();
        int ls = k<<1|1;
        for(int i=0;i<10;++i) v[tr[ls].lazy[i]].pb(i);
        for(int i=0;i<10;++i) sum[i] = tr[ls].cnt[i];
        for(int i=0;i<10;++i) if(tr[k].lazy[i] != i){
            for(int j=0;j<v[i].size();++j) 
                tr[ls].lazy[v[i][j]] = tr[k].lazy[i];
            sum[tr[k].lazy[i]] += tr[ls].cnt[i];
            sum[i] -= tr[ls].cnt[i];
        }
        for(int i=0;i<10;++i) tr[ls].cnt[i] = sum[i];
    }
    for(int i=0;i<10;++i) tr[k].lazy[i] = i;
}

inline void change(int k,int l,int r,int x,int y,int temp1,int temp2) {
    down(k,l,r);
    if(x <= l && r <= y){
        LL  sum = 0;
        for(int i=0;i<10;++i) if(tr[k].lazy[i] == temp1) {
            tr[k].lazy[i] = temp2;
            sum += tr[k].cnt[i];
            tr[k].cnt[i] = 0;
        }
        tr[k].cnt[temp2] += sum;
        return;
    }
    down(k,l,r);
    int mid = (l+r) >> 1;
    if(x <= mid) change(k<<1,l,mid,x,y,temp1,temp2);
    if(y >  mid) change(k<<1|1,mid+1,r,x,y,temp1,temp2);
    updata(k);
} 

inline LL ask(int k,int l,int r,int x,int y) {
    if(x <= l && r <= y) return tr[k].get();
    down(k,l,r);
    int mid = (l+r) >> 1;
    LL temp = 0;
    if(x <= mid) temp += ask(k<<1,l,mid,x,y);
    if(y > mid) temp += ask(k<<1|1,mid+1,r,x,y);
    return temp;
} 


int main() {
//  freopen("tt.in","r",stdin);
    int n = read(), q = read();
    for(int i=1;i<=n;++i) a[i] = read();
    P[1] = 1;
    for(int i=2;i<=9;++i) P[i] = P[i-1] * 10;
    build(1,1,n);
    for(int i=1;i<=q;++i) {
        int opt = read();
        if(opt == 1) {
            int l = read(), r = read(), x = read(), y = read();
            if(x == y) continue;
            change(1,1,n,l,r,x,y);
        }
        else {
            int l = read(), r = read();
            printf("%I64d\n", ask(1,1,n,l,r));
        }
    }
}

803G. Periodic RMQ Problem

题目大意,给你一个长度为$10^5$的数组,然后把它循环$10^4$次,现在有两个操作

  • $[l,r]$中的数字赋值为$x$

  • 查询$[l,r]$中的最小值

我就是作死,强行写了一个$\log 10^5$的做法

考虑一个$\log 10^9$的做法,先建立一个$10^5$的线段树,然后动态开点修改查询即可,写法类似主席树

然后我们考虑怎么把$log$压到$10^5$,我们类比分块的思想,用一个$10^4$的线段树维护一下每个相同的块的修改情况,这样就能在$\log(m)+\log(n)$的复杂度内做完所有操作

建议对代码能力没有信心的孩子去写第一个做法……

复杂度就是$n\log n$

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 1e5+5;
const int M = N << 2;
const int Maxm = N * 200;
inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int tr[M], lazy[M],n,k,a[N];

namespace seg {
    int root[N], lazy[Maxm];
    int ls[Maxm], rs[Maxm], tr[Maxm], sz;

    inline int newnode() {
        lazy[++sz] = inf;
        return sz;
    }

    inline void build(int &k,int l,int r) {
        k = newnode();
        lazy[k] = inf;
        if(l==r) {
            tr[k] = a[l];
            return;
        }
        int mid = (l+r) >> 1;
        build(ls[k], l, mid);
        build(rs[k], mid+1, r);
        tr[k] = min(tr[ls[k]], tr[rs[k]]);
    }

    inline void init() {
        build(root[1], 1, n);
        for(int i=2;i<=k;++i) root[i] = root[i-1];
    }

    inline void down(int k,int l,int r) {
        if(l==r) return;
        if(lazy[k] != inf) {
            int temp1 = newnode();
            int tt = ls[k];
            ls[temp1] = ls[tt];
            rs[temp1] = rs[tt];
            tr[temp1] = lazy[k];
            lazy[temp1] = lazy[k];
            ls[k] = temp1;
            temp1 = newnode();
            tt = rs[k];
            ls[temp1] = ls[tt];
            rs[temp1] = rs[tt];
            tr[temp1] = lazy[k];
            lazy[temp1] = lazy[k];
            rs[k] = temp1;
        } 
        lazy[k] = inf;
    }

    inline void set(int x,int val) {
        int y = newnode();
        ls[y] = ls[root[x]], rs[y] = rs[root[x]];
        tr[y] = lazy[y] = val; root[x] = y;
    }

    inline void change(int &k,int l,int r,int x,int y,int val) {
        int tmp = k;
        k = ++sz;
        ls[k] = ls[tmp];
        rs[k] = rs[tmp];
        tr[k] = tr[tmp];
        lazy[k] = lazy[tmp];
        if(l==x && r==y) {
            lazy[k] = tr[k] = val;
            return; 
        }
        down(k,l,r);
        int mid = (l+r) >> 1;
        if(y <= mid) change(ls[k], l, mid, x, y, val);
        else if(x > mid) change(rs[k], mid+1, r, x, y, val);
        else change(ls[k], l, mid, x, mid, val), change(rs[k], mid+1, r, mid+1, y, val);
        tr[k] = inf;
        if(ls[k]) tr[k] = min(tr[k], tr[ls[k]]);
        if(rs[k]) tr[k] = min(tr[k], tr[rs[k]]);
    }

    inline int ask(int k,int l,int r,int x,int y) {
        if(l==x && r==y) return tr[k];
        down(k,l,r);
        int mid = (l+r) >> 1;
        if(y <= mid) return ask(ls[k], l, mid, x, y);
        else if(x > mid) return ask(rs[k],mid+1, r, x, y);
        else return min(ask(ls[k], l, mid, x, mid), ask(rs[k], mid+1, r, mid+1, y));
    }
}

inline void down(int k,int l,int r) {
    if(lazy[k] == inf) return;
    if(l==r) {
        seg :: set(l,lazy[k]);
        lazy[k] = inf;
        return;
    }
    tr[k<<1] = tr[k<<1|1] = lazy[k];
    lazy[k<<1] = lazy[k<<1|1] = lazy[k];
    lazy[k] = inf;
}

inline void change(int k,int l,int r,int x,int y,int temp) {
    down(k,l,r);
    if(l==x && r==y) {
        tr[k] = lazy[k] = temp;
        return;
    }
    int mid = (l+r) >> 1;
    if(y <= mid) change(k<<1,l,mid,x,y,temp);
    else if(x > mid) change(k<<1|1,mid+1,r,x,y,temp);
    else change(k<<1,l,mid,x,mid,temp), change(k<<1|1,mid+1,r,mid+1,y,temp);
    tr[k] = min(tr[k<<1],tr[k<<1|1]);
}

inline int ask(int k,int l,int r,int x,int y) {
    down(k,l,r);
    if(l==x && r==y) 
        return tr[k];
    int mid = (l+r) >> 1;
    if(y <= mid) return ask(k<<1,l,mid,x,y);
    else if(x > mid) return ask(k<<1|1,mid+1,r,x,y);
    else return min(ask(k<<1,l,mid,x,mid),ask(k<<1|1,mid+1,r,mid+1,y));
}

inline void change(int k,int l,int r,int pos,int x1,int x2,int val) {
    down(k,l,r);
    if(l==r) {
        seg::change(seg::root[l],1,n,x1,x2,val);
        tr[k] = seg::tr[seg::root[l]];
        return;
    }
    int mid = (l+r) >> 1;
    if(pos <= mid) change(k<<1,l,mid,pos,x1,x2,val);
    else change(k<<1|1,mid+1,r,pos,x1,x2,val);
    tr[k] = min(tr[k<<1],tr[k<<1|1]);
}

inline int ask(int k,int l,int r,int pos,int x1,int x2) {
    down(k,l,r);
    if(l==r)  return seg::ask(seg::root[l],1,n,x1,x2);
    int mid = (l+r) >> 1;
    if(pos <= mid) return ask(k<<1,l,mid,pos,x1,x2);
    else return ask(k<<1|1,mid+1,r,pos,x1,x2);
}

inline void build(int k,int l,int r) {
    lazy[k] = inf;
    if(l==r) {
        tr[k] = seg::tr[seg::root[l]];
        return;
    }
    int mid = (l+r) >> 1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    tr[k] = min(tr[k<<1], tr[k<<1|1]);
}

inline int bel(int x) {
    return (x-1)/n+1;
}

int main() {
//  freopen("tt.in","r",stdin);
    n = read(), k = read();
    for(int i=1;i<=n;++i) a[i] = read();
    seg :: init();
    build(1,1,k);
    int q = read();
    while(q--) {
        int opt = read();
        if(opt == 1) {
            int l = read(), r = read(), val = read();
            int bl1 = bel(l), bl2 = bel(r);
            l -= (bl1-1)*n;
            r -= (bl2-1)*n;
            if(bl1 == bl2) change(1,1,k,bl1,l,r,val);
            else if(bl2 == bl1+1) {
                change(1,1,k,bl1,l,n,val);
                change(1,1,k,bl2,1,r,val);
            }
            else {
                change(1,1,k,bl1,l,n,val);
                change(1,1,k,bl1+1,bl2-1,val);
                change(1,1,k,bl2,1,r,val);
            }
        }
        else {
            int l = read(), r = read(), ans = inf;
            int bl1 = bel(l), bl2 = bel(r);
            l -= (bl1-1)*n;
            r -= (bl2-1)*n;
        
            if(bl1 == bl2) ans = ask(1,1,k,bl1,l,r);
            else if(bl2==bl1+1) {
                ans = min(ans,ask(1,1,k,bl1,l,n));
                ans = min(ans,ask(1,1,k,bl2,1,r));
            }
            else {
                ans = min(ans,ask(1,1,k,bl1,l,n));
                ans = min(ans,ask(1,1,k,bl1+1,bl2-1));
                ans = min(ans,ask(1,1,k,bl2,1,r));
            }
            printf("%d\n", ans);
        }
    }
}

CF 792E Colored Balls

题目大意

给你一坨球,第$i$坨有$a_i$个,现在问你最少分成多少堆,并要求

  • 每一堆颜色相同
  • 任意两堆个数不超过2

贪心,考虑我枚举第一个东西分成几堆,就能算出第一堆有几个,然后大力判一下就行了

注意那个不定方程$ax+by=c$有$b=a+1$所以实际上只需要判断$c/a+c% a$就行了

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int a[500+5], n;
long long ans = 0;

inline bool check(int x) {
    ans = 0;
    for(int i=1;i<=n;++i) {
        int temp1 = a[i]/x, temp2 = a[i] % x;
        if(temp2 == 0) ans += temp1;
        else if(temp1 + temp2 >= x - 1) ans += temp1 + 1;
        else return false; 
    }
    return true;
}

int main() {
    cin >> n;
    for(int i=1;i<=n;++i) cin >> a[i];
    int x = inf;
    for(int i=1;i<=n;++i) x = min(x, a[i]);
    for(int i=1;i<=x;++i) {
        if(check(x/i+1)) return 0*printf("%I64d\n", ans);
        if(check(x/i)) return 0*printf("%I64d\n", ans);
    }
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP