平时十五测-白红宇

平时十五测

阅读量：5051 次

发布时间：2019-06-12

本文共 5795 字，大约阅读时间需要 19 分钟。

题解：

第一题：

或者ＤＰ，先按ｘ排序，ｄｐ［ｉ］表示选择ｉ作为结尾的最大团size;

发现i向前连边的条件是xi - wi >= xj + wj; (这个式子我推出来，但并没有深入探究）

简单探索一番可以发现如果i可以和前面的j连边，j可以和前面p连边，则i就可以和p连边；

dp[i] = max(dp[j]) + 1, 这个可以用树状数组维护；

#include
      
       using namespace std;const int M = 200005;int c[M<<1], dis[M<<1], q;struct node{
    int u, v, x;}p[M];bool cmp(node A, node B){    return A.x < B.x;}void add(int x, int u){    for(; x <= q; x += x&(-x)) c[x] = max(c[x], u);}int query(int x){    int ret = 0;    for(; x; x -= x&(-x)) ret = max(ret, c[x]);    return ret;}int read(){    int x = 0; int f = 1; char c = getchar();    while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}    while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();}    return x*=f;}int main(){    freopen("clique.in","r",stdin);    freopen("clique.out","w",stdout);    int n = read(), tot = 0;    for(int i = 1; i <= n; i++){        int x = read(), w = read();        p[i].x = x;        p[i].u = x - w;        p[i].v = x + w;         dis[++tot] = p[i].u, dis[++tot] = p[i].v;    }    sort(dis + 1, dis + 1 + tot);    q = unique(dis + 1, dis + 1 + tot) - dis - 1;    for(int i = 1; i <= n; i++){        p[i].u = lower_bound(dis + 1, dis + 1 + q, p[i].u) - dis;        p[i].v = lower_bound(dis + 1, dis + 1 + q, p[i].v) - dis;    }    sort(p + 1, p + 1 + n, cmp);    add(p[1].v, 1);    int ans = 1;    for(int i = 2; i <= n; i++){        int t = query(p[i].u);        add(p[i].v, t+1);        ans = max(ans, t+1);        }    printf("%d\n", ans);    }

View Code

第二题：正确解法基于一个重要的结论，a % b <= a/2，这就意味着，任何一个数loga[i]次取模以内就能变为0。同时还注意到，a % b = a (a < b)。这两点便可以极大的降低时间复杂度。

#include
      
       using namespace std;#define ll long longconst int M = 1e5+5;int a[M], n, m;#define Ls nd->ls, lf, mid#define Rs nd->rs, mid+1, rgstruct Node{    int v; ll sum;    Node *ls, *rs;    void up(){        v = max(ls->v, rs->v);        sum = ls->sum + rs->sum;    }    }pool[M << 2], *root, *tail = pool; Node *build(int lf = 1, int rg = n){    Node *nd = ++tail;    if(lf == rg)nd->v = nd->sum = a[lf];    else {        int mid = (lf + rg) >> 1;        nd->ls = build(lf, mid);        nd->rs = build(mid+1, rg);        nd->up();    }    return nd;}void add(int pos, int x, Node *nd = root, int lf = 1, int rg = n){    if(lf == rg){        nd->v = nd->sum = x;    }    else {        int mid = (lf + rg) >> 1;        if(pos <= mid)add(pos, x, Ls);        else add(pos, x, Rs);        nd->up();    }}ll query(int L, int R, Node *nd = root, int lf = 1, int rg = n){    if(L <= lf && rg <= R)return nd->sum;    else {        int mid = (lf + rg) >> 1;        ll ret = 0;        if(L <= mid)ret += query(L, R, Ls);        if(R > mid) ret += query(L, R, Rs);        return ret;    }    }void modify(int L, int R, ll x, Node *nd = root, int lf = 1, int rg = n){    if(nd->v < x) return ;    if(lf == rg)nd->v %= x, nd->sum%= x;    else {        int mid = (lf + rg) >> 1;        int ret = 0;        if(L <= mid)modify(L, R, x, Ls);        if(R > mid) modify(L, R, x, Rs);        nd->up();    }}int read(){    int x = 0; int f = 1; char c = getchar();    while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}    while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();}    return x*=f;}int main(){    freopen("mod.in","r",stdin);    freopen("mod.out","w",stdout);    n = read(), m = read();    for(int i = 1; i <= n; i++) a[i] = read();    root = build();    int opt, l, r, x;    while(m--){        opt = read();        if(opt == 1){            l = read(), r = read();            printf("%lld\n", query(l, r));        }        else if(opt == 2){            l = read(), r = read(), x = read();            modify(l, r, x);        }        else {            l = read(), x = read();            add(l, x);        }    }        }

View Code

第三题：令S(i)={i+1,i+2,…,2i}，f(i,k)表示S(i)中二进制下恰好有k个1的数的个数（i>0，k>=0）。

发现f(i, k) <= f(i+1, k), 这个满足二分性质，就二分i, f可以用数位DP解决，但是是Log^2的，我们可以直接用组合数解决；

没有顶上界，有C(位数，要的1)，代替数位DP的过程，顶上界只有一次，是logN的；

#include
      
       using namespace std;#define ull unsigned long longconst ull INF = 2e18;ull C[67][67];int digit[67];ull dfs(int dep, int res, int sum){    int now = sum - res;    if(now > dep)return 0;    if(!now)return 1;    if(dep == 1) return digit[dep] == sum - res;    if(!digit[dep])return dfs(dep-1, res, sum);    ull tmp = C[dep-1][now];    if(tmp == INF) return INF + 1;    ull nw = dfs(dep-1, res+1, sum);    return min(INF + 1, tmp + nw);}ull check(ull xz, ull k){    ull up = xz<<1;    int cnt = 0;    while(xz){        digit[++cnt] = xz&1;        xz >>= 1;    }    ull ans1 = dfs(cnt, 0, k);    cnt = 0;    while(up){        digit[++cnt] = up&1;        up >>= 1;    }    ull ans2 = dfs(cnt, 0, k);    return ans2 - ans1;}int main(){    freopen("number.in","r",stdin);    freopen("number.out","w",stdout);    for(int i = 0; i <= 65; i++)        for(int j = 0; j <= i; j++)            if(j == 0 || i == j) C[i][j] = 1;            else C[i][j] = min(C[i-1][j-1] + C[i-1][j], INF);    int T;    scanf("%d", &T);    ull m, k;    while(T--){        scanf("%llu%llu", &m, &k);        if(m == 1 && k == 1){puts("1 -1");continue;}        ull lf = 1, rg = 1e18, p1 = -1, p2 = -1;        while(lf <= rg){            ull mid = (lf + rg) / 2;            ull now = check(mid, k);            if(now == m){                p1 = mid;                rg = mid - 1;            }            else if(now > m)rg = mid - 1;            else lf = mid + 1;        }                lf = 1, rg = 2e18;        while(lf <= rg){            ull mid = (lf + rg) / 2;            ull now = check(mid, k);            if(now == m){                p2 = mid;                lf = mid + 1;            }            else if(now > m)rg = mid - 1;            else lf = mid + 1;        }                printf("%llu %llu\n", p1, p2 - p1 + 1);    }}

View Code

转载于:https://www.cnblogs.com/EdSheeran/p/9853176.html

你可能感兴趣的文章

RDIFramework.NET — 基于.NET的快速信息化系统开发框架 - 5.3 数据库连接管理模块...