solego

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);
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;
}


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);
}

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;
}


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;
}

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个月前

#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;
}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;
}

void pushdown(int u) {
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) {
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]$时，

$f[1] >= f[2] >= f[3] >= f[4] >= … >= f[cnt - 1] >= f[cnt]$

#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个月前

#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;
}


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;
}


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;
}