Mambacrose

ride or die

Codeforces #Round 271

| Comments

Summary

很水的一场就不说了吧

D.Flowers

给定个格子,你可用染色,但是如果用了,就必须连续用,求方案数。

直接

E.Pillars

个跳板,从如果并且,那么可以跳到,询问最多可以跳多少次。

因为是要求最大值,我们用线段树维护数组

在线段树中叶子节点所代表的值表示的最大值。

那么每次时只需找出线段树中区间的最大值即可。

因为h可能达到次方,需要离散化,然后用二分求出即可。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<map>
#define N 100100
using namespace std;
typedef long long LL;
int L[N * 3], R[N * 3], Val[N * 3], Pos[N * 3], pre[N];
LL A[N], B[N];
int n, k, i, tot, Ans, maxn, site, p;
map<LL, int> C;
void Build(int x, int l, int r)
{
    L[x] = l, R[x] = r;
    if (l == r) return;
    int mid = (l + r) >> 1;
    Build(x << 1, l, mid);
    Build(x << 1 | 1, mid + 1, r);
}
void Query(int x, int l, int r)
{
    if (L[x] >= l && R[x] <= r)
    {
        if (Val[x] > maxn)    
            maxn = Val[x], p = Pos[x];
        return;
    }
    int mid = (L[x] + R[x]) >> 1;
    if (l <= mid) Query(x << 1, l , r);
    if (r > mid) Query(x << 1 | 1, l, r);
}
void Updata(int x, int p, int id, int v)
{
    if (L[x] == p && R[x] == p)
    {
        Val[x] = v, Pos[x] = id;
        return;
    }
    int mid = (L[x] + R[x]) >> 1;
    if (p <= mid) Updata(x << 1, p, id, v);
    else Updata(x << 1 | 1, p, id, v);
    if (Val[x << 1] >= Val[x << 1 | 1]) Val[x] = Val[x << 1], Pos[x] = Pos[x << 1];
    else Val[x] = Val[x << 1 | 1], Pos[x] = Pos[x << 1 | 1];
}
int find(LL x)
{
    int l = 1, r = n; 
    while (l <= r)
    {
       int mid = (l + r) >> 1;
       if (B[mid] <= x) l = mid + 1; 
       else r = mid - 1;
    }
    return l;
}
int main()
{
    freopen("E.in", "r", stdin);
    freopen("E.out", "w", stdout);
    scanf("%d%d", &n, &k);
    for (i = 1; i <= n; i++) scanf("%I64d", &A[i]), B[i] = A[i];
    sort(B + 1, B + n + 1);
    for (i = 1; i <= n; i++) 
        if (B[i] != B[i - 1]) C[B[i]] = ++tot;
    Build(1, 1, tot);
    for (i = 1; i <= n; i++)
    {
        int t = C[A[i]], l =find(A[i] - k), r = find(A[i] + k - 1);
        maxn = p = 0;
        if (l != 1) Query(1, 1, C[B[l - 1]]);
        if (r != n + 1) Query(1, C[B[r]], tot);
        pre[i] = p;
        if (maxn + 1 > Ans) Ans = maxn + 1, site = i;
        Updata(1, t, i, maxn + 1);
    }
    printf("%d\n", Ans);
    tot = 1, B[1] = site;
    while (pre[site] != 0) B[++tot] = pre[site], site = pre[site];
    for (i = tot; i >= 1; i--) printf("%I64d ", B[i]);
    return 0;
}

F.Ant colony

给定一个序列,求中不能够整除中每个数的数的个数。

只需要求出中能整除这数的个数。

考虑到能整除这个数的数必定是这个区间的

用倍增可以再求出区间 (预处理)

然后我们就只要统计中等于x的数即可

用链表将这个序列中大小相同的数串在一起,然后直接二分即可

,总复杂度

#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
int n, q, l, r, i, j, s[110000], f[110000][30], U[110000];
map<int, vector<int> >C;
int gcd(int a, int b)
{
    if (!b) return a;
    return gcd(b, a % b);
}
int Calc(int x, int l, int r)
{
    int L = lower_bound(C[x].begin(), C[x].end(), l) - C[x].begin(),
        R = upper_bound(C[x].begin(), C[x].end(), r) - C[x].begin();
    return (r - l + 1 - R + L);
}
int Rmq(int l, int r)
{
    return gcd(f[l][U[r - l + 1]], f[r + 1 - (1 << U[r - l + 1])][U[r - l + 1]]);    
}
int main()
{
    freopen("F.in", "r", stdin);
    freopen("F.out", "w", stdout);
    scanf("%d", &n);
    for (i = 1; i <= n; i++) scanf("%d", &s[i]);
    for (i = 1; i <= n; i++) 
        f[i][0] = s[i], C[s[i]].push_back(i);
    for (i = 1; 1 << i <= n; i++)
        for (j = 1; j + (1 << i) <= n + 1; j++)
            f[j][i] = gcd(f[j + (1 << (i - 1))][i - 1], f[j][i - 1]); 
    for (i = 1; 1 << i <= n; i++) U[1 << i] = i;
    for (i = 1; i <= n; i++) if (!U[i]) U[i] = U[i - 1]; 
    scanf("%d", &q);
    while (q--)
    {
        scanf("%d%d", &l, &r);
        printf("%d\n", Calc(Rmq(l, r), l, r));
    }
    return 0;
}

Comments

comments powered by Disqus