HG奋斗赛B[20190429]

T1

>传送门<

记忆化搜索，听说有更简单的方法(但博主比较菜)

#include <cstdio>
#include <cstdlib>
#define ll long long

ll read(){
    ll x = ; int zf = ; char ch = ' ';
    while (ch != '-' && (ch < '' || ch > '')) ch = getchar();
    if (ch == '-') zf = -, ch = getchar();
    while (ch >= '' && ch <= '') x = x *  + ch - '', ch = getchar(); return x * zf;
}

int a[], n;
int vis[];

void DFS(int pos, int floor){
    if (vis[pos])
        return ;
    vis[pos] = ;
    for (int i = ((n - pos) & ) ? (n - ) : n; i >= pos; i -= ){
        if (i == n){
            if (a[i] & ){
                if (floor & ){
                    printf("Yes");
                    exit();
                }
            }
        }
        else{
            if ((a[i] & ) && (a[i + ] & )){
                if (i +  == n){
                    if (!(floor & )){
                        printf("Yes");
                        exit();
                    }
                }
                DFS(i + , floor + );
            }
        }
    }
}

int main(){
    n = read();
    for (int i = ; i <= n; ++i)
        a[i] = read();
    if (!(a[] & ) || !(a[n] & )){
        printf("No");
        return ;
    }
    DFS(, );
    printf("No");
    return ;
}

T2

>传送门<

第1个点肯定要选的，暴力枚举第一条线段的第二个点在哪里，然后暴力模拟，注意第二个点可能为空

#include <cstdio>
#include <cmath>
#define ll long long

const double DEL = 1e-;

ll read(){
    ll x = ; int zf = ; char ch = ' ';
    while (ch != '-' && (ch < '' || ch > '')) ch = getchar();
    if (ch == '-') zf = -, ch = getchar();
    while (ch >= '' && ch <= '') x = x *  + ch - '', ch = getchar(); return x * zf;
}

double myAbs(double a){
    return (a > ) ? a : -a;
}

double equal(double a, double b){
    if (myAbs(a - b) <= DEL)
        return ;
    else
        return ;
}

double y[];

int main(){
    int n = read();
    if (n <= ){
        printf("Yes\n");
        return ;
    }
    for (int i = ; i < n; ++i)
        y[i] = read();
    double lineA, lineB;
    int b1 = -, b2 = -;
    for (int i = ; i < n; ++i){
        lineA = (y[i] - y[]) / (double)(i);
        b1 = b2 = -;
        int j;
        for (j = ; j < n; ++j){
            if (j == i)
                continue;
            if (!equal((y[j] - y[]) / (double)(j), lineA)){
                if (b1 == -){
                    b1 = j;
                }else if (b2 == -){
                    b2 = j;
                    lineB = (y[b2] - y[b1]) / (double)(b2 - b1);
                    if (!equal(lineA, lineB))
                        break;
                }else{
                    if (!equal((y[j] - y[b1]) / (double)(j - b1), lineB))
                        break;
                }
            }
        }
        if (j == n){
            if (b1 != -){
                printf("Yes\n");
                return ;
            }
        }
    }
    double line1 = y[] - y[];
    int i;
    for (i = ; i < n; ++i){
        if (!equal((y[i] - y[]) / (double)(i - ), line1))
            break;
    }
    if (i == n && (!equal((y[] - y[]), line1)))
        printf("Yes\n");
    else
        printf("No\n");
    return ;
}

T3

>传送门<

发现不管怎么合并，结果都一样，于是等差数列求和公式用一用AC

#include <cstdio>
#define ll long long

ll read(){
    ll x = ; int zf = ; char ch = ' ';
    while (ch != '-' && (ch < '' || ch > '')) ch = getchar();
    if (ch == '-') zf = -, ch = getchar();
    while (ch >= '' && ch <= '') x = x *  + ch - '', ch = getchar(); return x * zf;
}

ll getNum(ll a){
    return ((( + a) * a) >> );
}

int main(){
    int k = read();
    if (k == ){
        printf("ab");
        return ;
    }
    char ch = 'a';
    while (k > ){
        int l = , r = , mid, ans = ;
        while (l <= r){
            mid = (l + r) >> ;
            if (getNum(mid) > k){
                r = mid - ;
            }else{
                l = mid + ;
                ans = mid;
            }
        }
        k -= getNum(ans);
        for (int i = ; i <= ans; ++i)
            printf("%c", ch);
        ++ch;
    }
    return ;
}

T4

>传送门<

欧拉筛，二分AC

#include <cstdio>
#include <map>
#include <cmath>
#include <algorithm>
#define ll long long

using namespace std;

int a[], qzh[];

int primes[];
int prime_num = ;
bool is_not_primes[] = {false};

map<int, int> mp;

ll read(){
    ll x = ; int zf = ; char ch = ' ';
    while (ch != '-' && (ch < '' || ch > '')) ch = getchar();
    if (ch == '-') zf = -, ch = getchar();
    while (ch >= '' && ch <= '') x = x *  + ch - '', ch = getchar(); return x * zf;
}

void getPrime(int n){
    is_not_primes[] = true;
    is_not_primes[] = true;
    for (int i = ; i <= n; i++){
        if (is_not_primes[i] == false)
            primes[prime_num++] = i;
        for (int j = ; (j < prime_num) && (primes[j] * i <= n); j++){
            is_not_primes[primes[j] * i] = true;
            if ((i % primes[j]) == )
                break;
        }
    }
}

int main(){
    getPrime();
    int n = read();
    for(int i = ; i <= n; ++i){
        int x = read();
        ++a[x];
    }
    for(int i = ; i < prime_num; ++i)
        for(int j = primes[i]; j <= ; j += primes[i])
            qzh[i] += a[j];
    for(int i = ; i < prime_num; ++i)
            qzh[i] += qzh[i - ];
    int m = read(), l, r;
    for(int i = ; i <= m; ++i){
        l = read(), r = read();
        ll ans_r = qzh[lower_bound(primes + , primes + prime_num, r + ) - primes - ];
        ll ans_l = qzh[lower_bound(primes + , primes + prime_num, l) - primes - ];
        printf("%lld\n", ans_r - ans_l);
    }
}

T5

>传送门<

真正难的题目(目测实测洛谷黑题)，因为我比较菜，不会分块cdq分治，差分乱搞的算法，只能打一发树套树，

如何使用树套树呢？

　　我们把一维问题转换成二维问题，一个点的横坐标就是这个点的位置，纵坐标是这个点前一个与它颜色相同的点的位置，权值是横坐标减纵坐标。
　　这里查询[l,r]区间的答案，就是二维平面上(l,l)点和(r,r)点组成的矩阵内的权值之和。

　　原理？占坑代填

然后预处理再上树套树板子就行了

#include <cstdio>
#include <vector>
#include <set>
#define ll long long

using namespace std;

ll read(){
    ll x = ; int zf = ; char ch = ' ';
    while (ch != '-' && (ch < '' || ch > '')) ch = getchar();
    if (ch == '-') zf = -, ch = getchar();
    while (ch >= '' && ch <= '') x = x *  + ch - '', ch = getchar(); return x * zf;
}

//SegmentTree
long long s[];
int lc[], rc[];
int node_cnt = ;
void Add(int &pos, int l, int r, int k, ll val){
    if (!pos)
        pos = ++node_cnt;
    s[pos] += val;
    if (l == r)
        return;
    int mid = (l + r) >> ;
    if (k <= mid)
        Add(lc[pos], l, mid, k, val);
    else
        Add(rc[pos], mid + , r, k, val);
}
long long Query(int pos, int l, int r, int k){
    if (!pos)
        return ;
    if (l == r)
        return s[pos];
    int mid = (l + r) >> ;
    if (k <= mid)
        return Query(lc[pos], l, mid, k) + s[rc[pos]];
    else
        return Query(rc[pos], mid + , r, k);
}

int rt[], fst[];

//fentree
struct fenTree{
    #define lowbit(x) (x & -x)
    void add(int k, int pos, ll val, int n){
        for (int i = k; i <= n; i += lowbit(i))
            Add(rt[i], , n, pos, val);
    }
    ll qry(int k, int pos, int n) {
        ll res = ;
        for (int i = pos; i; i -= lowbit(i))
            res += Query(rt[i], , n, k);
        return res;
    }
    #undef lowbit
} bit;

void update(int x, int y, int n){
    if(fst[x])
        bit.add(x, fst[x], fst[x] - x, n);
    if(y)
        bit.add(x, y, x - y, n);
    fst[x] = y;
}

int aa[];
set<int> st[];

inline set<int>::iterator nxt_it(set<int>::iterator it){
    return (++it);
}

inline set<int>::iterator pre_it(set<int>::iterator it){
    return (--it);
}

int main(){
    int n = read(), m = read();
    for (int i = ; i <= n; ++i)
        aa[i] = read();
    for (int i = ; i <= n; i ++) {
        if (!st[aa[i]].empty()){
            fst[i] = *st[aa[i]].rbegin();
            bit.add(i, fst[i], i - fst[i], n);
        }
        st[aa[i]].insert(i);
    }
    int op, x, y;
    for (int I = ; I < m; ++I){
        op = read(), x = read(), y = read();
        if (op == ){
            set<int>::iterator it = st[aa[x]].find(x);
            if (nxt_it(it) != st[aa[x]].end())
                update(*nxt_it(it), (it == st[aa[x]].begin() ?  : *pre_it(it)), n);
            st[aa[x]].erase(x);
            aa[x] = y;
            it = st[y].insert(x).first;
            update(x, (it == st[y].begin() ?  : *pre_it(it)), n);
            if(nxt_it(it) != st[y].end())
                update(*nxt_it(it), x, n);
        }
        else
            printf("%lld\n", bit.qry(x, y, n));
    }
    return ;
}