头像

solego


访客:5737

离线:13小时前



solego
1个月前
//f[u][0]表示u不存在
//f[u][1]表示u存在

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int N = 6010;
int n, happy[N];
int f[N][2];
int bo[N];

int h[N], e[N], ne[N], idx;
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u) {
    f[u][0] = 0;
    f[u][1] = max(happy[u], 0);

    for(int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        dfs(v);
        f[u][0] += max(f[v][0], f[v][1]);
        f[u][1] += f[v][0];
    }
}

int main()
{
    scanf("%d", &n);
    memset(h, -1, (n + 1) * sizeof(int));
    for(int i = 1; i <= n; i++) 
        scanf("%d", &happy[i]), bo[i] = i;

    for(int i = 1; i < n; i++) {
        int a, b; scanf("%d%d", &a, &b);
        add(b, a);
        bo[a] = b;
    }
    int bbb = 0;
    for(int i = 1; i <= n; i++) 
        if(bo[i] == i) bbb = i;
    dfs(bbb);

    printf("%d\n", max(f[bbb][0], f[bbb][1]));

    return 0;
}


活动打卡代码 AcWing 1171. 距离

solego
2个月前
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 10010;
const int M = 40010;
const int Mdep = 20;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int lg[N];
void init() {
    for(int i = 1; i < N; i++)
        lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);

    memset(h, -1, sizeof h);
}

int dep[N], dist[N], f[N][Mdep+1];
void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    f[u][0] = fa;

    for(int i = 1; i <= lg[dep[u]]; i++)
        f[u][i] = f[f[u][i - 1]][i - 1];

    for(int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if(v == fa) continue;
        dist[v] = dist[u] + w[i];   
        dfs(v, u);
    }
}

int lca(int a, int b) {
    if(dep[a] < dep[b]) swap(a, b);
    for(int k = Mdep; k >= 0; k--) 
        if(dep[f[a][k]] >= dep[b]) a = f[a][k];
    if(a == b) return a;
    for(int k = Mdep; k >= 0; k--)
        if(f[a][k] != f[b][k]) a = f[a][k], b = f[b][k];
    return f[a][0];
}

int main()
{
    init();
    scanf("%d%d", &n, &m);
    for(int i = 1; i < n; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    dfs(1, 0);

    while(m--) {
        int a, b; scanf("%d%d", &a, &b);
        printf("%d\n", dist[a] + dist[b] - 2 * dist[lca(a, b)]);
    }

    return 0;
}


活动打卡代码 AcWing 1172. 祖孙询问

solego
2个月前
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 4e4 + 10, M = 8e4 + 10;
const int Mdep = 21;
int n, m, root;
int dep[N], lg[N], f[N][Mdep + 1];
int h[N], e[M], ne[M], idx;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void init_lg() {
    for(int i = 1; i <= n; i++) 
        lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
}

void dfs(int u, int fa) {
    f[u][0] = fa;
    dep[u] = dep[fa] + 1;
    for(int i = 1; i <= lg[dep[u]]; i++) 
        f[u][i] = f[f[u][i - 1]][i - 1];

    for(int i = h[u]; i != -1; i = ne[i]) 
        if(e[i] != fa) dfs(e[i], u);
}

int lca(int a, int b) {
    if(dep[a] < dep[b]) swap(a, b);
    for(int k = Mdep; k >= 0; k--)
        if(dep[f[a][k]] >= dep[b]) a = f[a][k];

    if(a == b) return a;

    for(int k = Mdep; k >= 0; k--)
        if(f[a][k] != f[b][k]) a = f[a][k], b = f[b][k];
    return f[a][0];
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        if(b == -1) root = a;
        else add(a, b), add(b, a);
    }

    init_lg();
    dfs(root, 0);

    scanf("%d", &m);
    while(m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        int t = lca(a, b);
        if(t == a) puts("1");
        else if(t == b) puts("2");
        else puts("0");
    }
    return 0;
}



solego
2个月前

题意: 稍加修改的线段树模板题。
题解: 由于乘法和加法两种修改,$lazy$标记不能确定的指出当前待修改的操作是乘法在前还是加法在前,亦或是两者混合存在,所以我们标记两个 $lazy:add$ 和 $mul$。更新的时候$add$更新为$add \times mul’+add’$,$mul$更新为$mul \times mul’+add’$,$sum$更新为$sum \times mul + add*(u.len)$


#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long ll;

const int N = 1e5 + 10;
int n, m, q[N];
ll mod;

struct Node {
    int l, r;
    ll sum, add, mul;
}tr[N << 2];

void pushup(int u) {
    tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % mod;
}

void eval(Node &t, ll add, ll mul) {
    t.sum = (t.sum * mul + (t.r - t.l + 1) * add) % mod;
    t.mul = t.mul * mul % mod;
    t.add = (t.add * mul + add) % mod;
}

void pushdown(int u) {
    eval(tr[u << 1], tr[u].add, tr[u].mul);
    eval(tr[u << 1 | 1], tr[u].add, tr[u].mul);
    tr[u].add = 0, tr[u].mul = 1;
}

void build(int u, int l, int r) {
    tr[u] = {l, r, 0, 0, 1};
    if(l == r) {
        tr[u].sum = q[l];
        return ;
    }

    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int l, int r, ll add, ll mul) {
    if(tr[u].l >= l && tr[u].r <= r) {
        eval(tr[u], add, mul);
        return ;
    }

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if(l <= mid) modify(u << 1, l, r, add, mul);
    if(r > mid) modify(u << 1 | 1, l, r, add, mul);
    pushup(u);
}

ll query(int u, int l, int r) {
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    ll res = 0;

    if(l <= mid) res += query(u << 1, l, r);
    if(r > mid) res += query(u << 1 | 1, l, r);
    return res % mod;
}

int main()
{
    scanf("%d%lld", &n, &mod);
    for(int i = 1; i <= n; i++) scanf("%d", &q[i]);
    build(1, 1, n);

    scanf("%d", &m);
    while(m--) {
        int op, l, r;
        ll c;
        scanf("%d%d%d", &op, &l, &r);
        if(op == 1) {
            scanf("%lld", &c);
            c %= mod;
            modify(1, l, r, 0, c);
        }
        else if(op == 2) {
            scanf("%lld", &c);
            c %= mod;
            modify(1, l, r, c, 1);
        }

        else printf("%lld\n", query(1, l, r));
    }

    return 0;
}



solego
3个月前

思路证明:

注意这里:
$f$是一个非严格递减子序列,每次枚举到一个新的$q[i]$时,
会先遇到最大的小于$q[i]$的$f[k]$,然后更新$f[k] = q[i]$,
那么更新后的结果仍然是一个非严格递减序列

证明:
开始f为
$f[1] >= f[2] >= f[3] >= f[4] >= … >= f[cnt - 1] >= f[cnt] $
枚举到一个新的$q[i]$时,遍历$f$,假设$f[j]$是小于$q[i]$的最大的数,更新后$f[j] = q[i]$
对于前面,由于$f[j]$是小于$q[i]$最大的数,则$f[1~j-1]$都小于等于$f[j]$,则$f[1~j-1]$小于$q[i]$
对于后面,由于$f[j]$是小于$q[i]$最大的数,则$f[j+1~cnt]$都大于等于$q[i]$,
故更新后仍满足$f$是一个非严格递减序列

#include<cstdio>
#include<algorithm>

using namespace std;
const int N = 1010;
int q[N], n = 1;
int b[N], gb;
int f[N];

int b_s(int l, int r, int x) {
    while(l < r) {
        int mid = l + r >> 1;
        if(b[mid] < x) l = mid + 1;
        else r = mid;
    }
    return l;
}

int main()
{
    while(~scanf("%d", &q[n])) n++; 

    b[++gb] = q[n - 1];
    for(int i = n - 2; i >= 1; i--) {
        if(q[i] >= b[gb]) b[++gb] = q[i];
        else {
            int t = b_s(1, gb, q[i]);
            b[t] = q[i];
        }
    }

    int cnt = 0;
    for(int i = 1; i <= n; i++) {
        int k = 1;
        while(k <= cnt && f[k] < q[i]) k++;
        if(k > cnt) f[++cnt] = q[i];
        else f[k] = q[i];
    }

    printf("%d\n%d", gb, cnt);

    return 0;
}



solego
4个月前

民间解法

手动去重

#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 1e5 + 10;
typedef long long ll;
typedef pair<int, ll> PII;
#define x first
#define y second

PII q[N]; int n, m, l, r;
ll all[N];

int b_sl(int l, int r, int p){
    while(l < r){
        int mid = l + r + 1 >> 1;
        if(q[mid].x >= p) r = mid - 1;
        else l = mid;
    }
    return l;
}

int b_sr(int l, int r, int p){
    while(l < r){
        int mid = l + r + 1 >> 1;
        if(q[mid].x <= p) l = mid;
        else r = mid - 1;
    }
    return l;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d%lld", &q[i].x, &q[i].y);

    sort(q + 1, q + 1 + n);

    int k = 0;
    for(int i = 1; i <= n; ){
        k++;
        int j = i + 1;
        while(j <= n && q[i].x == q[j].x) {
            q[i].y += q[j].y;
            q[j].x = 1e9 + 10;
            j++;
        }
        i = j;
    }

    sort(q + 1, q + 1 + n);

    for(int i = 1; i <= k; i++) all[i] = all[i - 1] + q[i].y;

    while(m--){
        scanf("%d%d", &l, &r);
        int bl = b_sl(1, k, l), br = b_sr(1, k, r);

        ll res = all[br] - all[bl];
        if(q[br].x > r) res -= q[br].y;
        if(q[bl].x >= l) res += q[bl].y;

        printf("%lld\n", res);
    }

    return 0;
}



solego
4个月前

这种日期模拟题是怎么也做不对的。
卡了N发才卡完所有test case
要考虑到日期合法,去重,排序输出

#include<cstdio>
#include<algorithm>

struct Da{
    int y, m, d;
    bool operator < (const Da &A) const 
    {
        if(y == A.y){
            if(m == A.m) return d < A.d;
            return m < A.m;
        }
        return y < A.y;

    }

    bool operator != (const Da &A) const 
    {
        if(y != A.y || m != A.m || d != A.d) return true;
        return false;
    }
}D[3];

bool judge(int y, int m, int d){

    if(m == 0 || d == 0) return false;
    if(m > 12) return false;
    if(m == 1 || m == 3 || m == 5 || m == 7 || m == 8 || m == 10 || m == 12)
        if(d > 31) return false;
    if(m == 4 || m == 6 || m == 9 || m == 11)
        if(d > 30) return false;

    if(m == 2){
        y += 1900;
        if(y % 100 < 60) y += 100;
        if((y % 4 == 0 && y % 100 != 0) || y % 400 == 0){
            if(d > 29) return false;
        }
        else {
            if(d > 28) return false;
        }
    }
    return true;
}

int main()
{
    int a, b, c, g = 0;
    scanf("%d/%d/%d", &a, &b, &c);

    //1.年月日abc
    if(judge(a, b, c)){
        D[g].y = 1900 + a; D[g].m = b; D[g].d = c;
        if(a < 60) D[g].y += 100;
        g++;
    }
    //2.月日年abc
    if(judge(c, a, b)){
        D[g].y = 1900 + c; D[g].m = a; D[g].d = b;
        if(c < 60) D[g].y += 100;
        g++;
    }
    //3.日月年abc
    if(judge(c, b, a)){
        D[g].y = 1900 + c; D[g].m = b; D[g].d = a;
        if(c < 60) D[g].y += 100;
        g++;
    }
    std::sort(D, D + g);
    printf("%d-%02d-%02d\n", D[0].y, D[0].m, D[0].d);
    for(int i = 1; i < g; i++) 
        if(D[i] != D[i - 1]) printf("%d-%02d-%02d\n", D[i].y, D[i].m, D[i].d);

    return 0;
}



solego
4个月前

将点数转换成坐标即可

#include<cstdio>
int jdz(int x) {return x < 0 ? -x : x;}
int main()
{
    int w, m, n, mx, my, nx, ny;
    scanf("%d%d%d", &w, &m, &n);
    m--; n--; //将所有点转换成0~max-1, 方便取模

    mx = m / w, nx = n / w; // 取纵坐标
    my = m % w; ny = n % w; // 先默认是从左到右从上到下的顺序
    if((mx & 1) == 0) my = w - my - 1; //偶数行逆序
    if((nx & 1) == 0) ny = w - ny - 1; 

    int ans = jdz(nx - mx) + jdz(ny - my); //求横纵坐标距离和即可
    printf("%d\n", ans);
    return 0;
}


活动打卡代码 AcWing 1027. 方格取数

solego
6个月前
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 11;
int g[N][N], f[N][N][2 * N];
int n, a, b, c, all;

int main()
{
    scanf("%d", &n);
    while(~scanf("%d%d%d", &a, &b, &c), a || b || c) g[a][b] = c;

    //i是第一次的左,j是第二次的左
    all = 2 * n; 
    for(int k = 2; k <= all; k++)
        for(int i1 = 1; i1 <= k; i1++)
            for(int i2 = 1; i2 <= k; i2++){
                if(i1 >= 1 && i1 <= n && i2 >= 1 && i2 <= n){
                    int j1 = k - i1, j2 = k - i2;
                    int t = g[i1][j1];
                    if(i1 != i2) t += g[i2][j2];

                    f[i1][i2][k] = max(f[i1][i2][k], f[i1][i2][k - 1] + t);
                    f[i1][i2][k] = max(f[i1][i2][k], f[i1 - 1][i2][k - 1] + t);
                    f[i1][i2][k] = max(f[i1][i2][k], f[i1][i2 - 1][k - 1] + t);
                    f[i1][i2][k] = max(f[i1][i2][k], f[i1 - 1][i2 - 1][k - 1] + t);
                }
            }

    printf("%d\n", f[n][n][all]);

    return 0;
}


活动打卡代码 AcWing 1018. 最低通行费

solego
6个月前
#include<cstdio>
#include<cstring>
#include<algorithm>

const int N = 110;
int q[N][N], dp[N][N];
int n;

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            scanf("%d", &q[i][j]);

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++){
            dp[i][j] = q[i][j];
            if(i == 1) dp[i][j] += dp[i][j - 1];

            else if(j == 1) dp[i][j] += dp[i - 1][j];

            else dp[i][j] += std::min(dp[i - 1][j], dp[i][j - 1]);
        }

    printf("%d\n", dp[n][n]);

    return 0;
}