首页 > 其他分享 >2022NOIPA层联测27

2022NOIPA层联测27

时间：2022-11-14 07:55:05浏览次数：82  
标签：ch 2022NOIPA int long 27 maxn 联测 ans getchar

感觉再这么成天咕下去不太好……

 

A. 天平

没有观察到只需要使得选出的砝码质量的gcd与所有砝码的fcd相等即可，但是发现应该让选出的砝码的gcd取到最小值。

我想找到最小的gcd选组成它们的两个数作为起点，以为最小值一定是其中之一，就这么省了个循环但是这个结论是错的所以WA 了，剩下的由【放进去】的假贪心想到每一轮找出一个能使gcd变到最小的选上。

code 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 54, inf = 0x3f3f3f3f;

int n, a[maxn], step, mi=inf, id;
bool vis[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

bool check()
{
    for(int i=1; i<=n; i++)
    {
        if(a[i] % mi) return false;
    }
    return true;
}

inline int gcd(int a, int b)
{
    while(b^=a^=b^=a%=b);
    return a;
}

int main()
{
    freopen("weights.in", "r", stdin);
    freopen("weights.out", "w", stdout);
    
    n = read(); 
    for(int i=1; i<=n; i++) 
    {
        a[i] = read();
        if(a[i] < mi) mi = a[i], id = i;
    }
    if(check()) {printf("1\n"); exit(0);}
    int las = mi;
    /*vis[id] = 1; id = 0;
    int las = mi;
    for(int i=1; i<=n; i++)
    {
        if(vis[id]) continue;
        int gd = gcd(a[i], las);
        if(gd < mi) {mi = gd; id = i;}
    }*/
    int m1 = 0, m2 = 0;
    for(int i=1; i<=n; i++)
    {
        for(int j=i+1; j<=n; j++)
        {
            int gd = gcd(a[i], a[j]);
            if(gd < mi) {mi = gd, m1 = i, m2 = j;}
        }
    }
    step = 2; vis[m1] = 1, vis[m2] = 1; id = 0;
    if(check()) {printf("2\n"); exit(0);}
    while(step <= n)
    {
        las = mi;
        for(int i=1; i<=n; i++)
        {
            if(vis[i]) continue;
            int gd = gcd(a[i], las);
            if(gd < mi) {mi = gd; id = i;}
        }
        if(!id) {printf("%d\n", step); break;}
        step++; vis[id] = 1; id = 0;
    }

    return 0;
}

 

B. 支配数据

把序列分成k段让每个序列相互独立线段树及时清空，一开始想把问题拆分：

code 
 #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 2, inf = 0x3f3f3f3f;
const int maxQ = 1e7 + 4;

int n, a[maxn], k, Q, ans[maxn], cnt;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct seg 
{
	struct node 
	{
		int v, tag;
	}t[maxn<<2];
	void pushup(int x)
	{
		t[x].v = min(t[x<<1].v, t[x<<1|1].v);
	}
	void build(int x, int l, int r)
	{
		t[x].tag = 0;
		if(l == r)
		{
			t[x].v = a[l]; return;
		}
		int mid = (l + r) >> 1;
		build(x<<1, l, mid);
		build(x<<1|1, mid+1, r);
		pushup(x);
	}
	void pushdown(int x)
	{
		int ls = x<<1, rs = x<<1|1;
		t[ls].v = t[rs].v = t[x].tag;
		t[ls].tag = t[rs].tag = t[x].tag;
		t[x].tag = 0;
	}
	void update(int x, int l, int r, int L, int R, int v)
	{
		if(L <= l && r <= R)
		{
			t[x].v = v; t[x].tag = v;
			return;
		}
		if(t[x].tag) pushdown(x);
		int mid = (l + r) >> 1;
		if(L <= mid) update(x<<1, l, mid, L, R, v);
		if(R > mid) update(x<<1|1, mid+1, r, L, R, v);
		pushup(x);
	}
	int query(int x, int l, int r, int L, int R)
	{
		if(L <= l && r <= R) return t[x].v;
		if(t[x].tag) pushdown(x);
		int mid = (l + r) >> 1, ans = inf;
		if(L <= mid) ans = min(ans, query(x<<1, l, mid, L, R));
		if(R > mid) ans = min(ans, query(x<<1|1, mid+1, r, L, R));
		return ans;
	}
}t;

void solve1()
{
	int N = n * k;
	for(int i=n+1; i<=N; i++) a[i] = a[i-n];
	t.build(1, 1, N);
	Q = read();
	while(Q--)
	{
		int opt = read();
		if(opt == 1)
		{
			int l = read(), r = read(), v = read();
			t.update(1, 1, N, l, r, v);
		}
		else 
		{
			int l = read(), r = read();
			printf("%d\n", t.query(1, 1, N, l, r));
		}
	}
	exit(0);
}

struct ask 
{
	int id, opt, l, r, v, bel;
	bool operator < (const ask &T) const 
	{
		if(bel == T.bel) return id < T.id;
		return bel < T.bel;
	}
}q[maxQ<<2];//依然有可能RE

void split(int now)
{
	int zl = (q[now].l-1)/n+1, zr = (q[now].r-1)/n+1;
	if(zl == zr)
	{
		q[now].l = (q[now].l-1)%n+1, q[now].r = (q[now].r-1)%n+1;
		q[now].bel = zl; return;
	}
	ask res = q[now];
	q[now].r = n; q[now].bel = zl; q[now].l = (res.l-1) % n + 1;
	cnt++; q[cnt] = res;
	q[cnt].l = 1; q[cnt].bel = zr; q[cnt].r = (res.r-1) % n + 1;
	if(zl + 1 == zr) return;
	for(int i=zl+1; i<zr; i++)
	{
		cnt++; q[cnt] = res; 
		q[cnt].l = 1, q[cnt].r = n;
		q[cnt].bel = i;
	}
}

int main()
{
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
    
    n = read(); k = read();
	for(int i=1; i<=n; i++) a[i] = read();
	if(n * k <= 1e5) solve1();
	Q = read(); cnt = Q;
	for(int i=1; i<=Q; i++)
	{
		q[i].opt = read(); q[i].id = i;
		q[i].l = read(), q[i].r = read();
		if(q[i].opt == 1) q[i].v = read();
		split(i);
	}
	for(int i=1; i<=Q; i++) 
	{
		if(q[i].opt == 2) ans[i] = inf;
	}
	sort(q+1, q+1+cnt);
	t.build(1, 1, n);
	if(q[1].opt == 1) t.update(1, 1, n, q[1].l, q[1].r, q[1].v);
	else ans[q[1].id] = t.query(1, 1, n, q[1].l, q[1].r);
	for(int i=2; i<=cnt; i++)
	{
		if(q[i].bel != q[i-1].bel) t.build(1, 1, n);
		if(q[i].opt == 1) t.update(1, 1, n, q[i].l, q[i].r, q[i].v);
		else ans[q[i].id] = min(ans[q[i].id], t.query(1, 1, n, q[i].l, q[i].r));
	}
	for(int i=1; i<=Q; i++) 
	{
		if(ans[i]) printf("%d\n", ans[i]);
	}

    return 0;
}

有没有由于数组来不下RE我不知道但是MLE了是真的。后来打算放弃记录问题直接划分：

愉快地T掉了。。。

code 
 #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 2, inf = 0x3f3f3f3f;

int n, a[maxn], k, Q, ans[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct seg 
{
	struct node 
	{
		int v, tag;
	}t[maxn<<2];
	void pushup(int x)
	{
		t[x].v = min(t[x<<1].v, t[x<<1|1].v);
	}
	void build(int x, int l, int r)
	{
		t[x].tag = 0;
		if(l == r)
		{
			t[x].v = a[l]; return;
		}
		int mid = (l + r) >> 1;
		build(x<<1, l, mid);
		build(x<<1|1, mid+1, r);
		pushup(x);
	}
	void pushdown(int x)
	{
		int ls = x<<1, rs = x<<1|1;
		t[ls].v = t[rs].v = t[x].tag;
		t[ls].tag = t[rs].tag = t[x].tag;
		t[x].tag = 0;
	}
	void update(int x, int l, int r, int L, int R, int v)
	{
		if(L <= l && r <= R)
		{
			t[x].v = v; t[x].tag = v;
			return;
		}
		if(t[x].tag) pushdown(x);
		int mid = (l + r) >> 1;
		if(L <= mid) update(x<<1, l, mid, L, R, v);
		if(R > mid) update(x<<1|1, mid+1, r, L, R, v);
		pushup(x);
	}
	int query(int x, int l, int r, int L, int R)
	{
		if(L <= l && r <= R) return t[x].v;
		if(t[x].tag) pushdown(x);
		int mid = (l + r) >> 1, ans = inf;
		if(L <= mid) ans = min(ans, query(x<<1, l, mid, L, R));
		if(R > mid) ans = min(ans, query(x<<1|1, mid+1, r, L, R));
		return ans;
	}
}t;

void solve1()
{
	int N = n * k;
	for(int i=n+1; i<=N; i++) a[i] = a[i-n];
	t.build(1, 1, N);
	Q = read();
	while(Q--)
	{
		int opt = read();
		if(opt == 1)
		{
			int l = read(), r = read(), v = read();
			t.update(1, 1, N, l, r, v);
		}
		else 
		{
			int l = read(), r = read();
			printf("%d\n", t.query(1, 1, N, l, r));
		}
	}
	exit(0);
}

struct ask 
{
	int opt, l, r, v;
}q[maxn];

int main()
{
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
    
    n = read(); k = read();
	for(int i=1; i<=n; i++) a[i] = read();
	if(n * k <= 1e5) solve1();
	Q = read(); 
	for(int i=1; i<=Q; i++)
	{
		q[i].opt = read(); 
		q[i].l = read(), q[i].r = read();
		if(q[i].opt == 1) q[i].v = read();
	}
	for(int i=1; i<=Q; i++) 
	{
		if(q[i].opt == 2) ans[i] = inf;
	}
	for(int i=1; i<=k; i++)
	{
		t.build(1, 1, n);
		for(int j=1; j<=Q; j++)
		{
			int zl = (q[j].l-1)/n+1, zr = (q[j].r-1)/n+1;
			if(zl > i || zr < i) continue;
			int l = zl == i ? (q[j].l-1)%n+1 : 1, r = zr == i ? (q[j].r-1)%n+1 : n;
			if(q[j].opt == 1) t.update(1, 1, n, l, r, q[j].v);
			else ans[j] = min(ans[j], t.query(1, 1, n, l, r));
		}
	}
	for(int i=1; i<=Q; i++) 
	{
		if(ans[i]) printf("%d\n", ans[i]);
	}

    return 0;
}

比赛结束后就鹤了一下：

建立一棵庞大的动态开点线段树，被覆盖过的在线段树上查，剩下的单独搞个ST表查。

code 
 #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e7 + 2, inf = 0x3f3f3f3f;

int n, a[maxn], k, Q, N, rt;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct Table 
{
	int d[maxn][18];
	void init()
	{
		for(int i=1; i<=n; i++) d[i][0] = a[i];
		for(int j=1; (1<<j)<=n; j++)
		{
			for(int i=1; i+(1<<j)-1<=n; i++)
			{
				d[i][j] = min(d[i][j-1], d[i+(1<<j-1)][j-1]);
			}
		}
	}
	int query(int l, int r)
	{
		int k = 0;
		while((1<<k+1) <= r-l+1) k++;
		return min(d[l][k], d[r-(1<<k)+1][k]);
	}
}st;

struct seg 
{
	struct node 
	{
		int v, tag, mv;
	}t[maxn<<2];
	int lc[maxn<<2], rc[maxn<<2];
	int tot;
	void pushup(int x)
	{
		int ans = inf;
		if(lc[x]) ans = t[lc[x]].v;
		if(rc[x]) ans = min(ans, t[rc[x]].v);
		t[x].v = ans;
	}
	void pushdown(int x)
	{
		if(!lc[x]) lc[x] = ++tot;
		if(!rc[x]) rc[x] = ++tot;
		t[lc[x]].tag = t[rc[x]].tag = t[x].tag;
		t[lc[x]].v = t[rc[x]].v = t[x].tag;
		t[lc[x]].mv = t[rc[x]].mv = 1;
		t[x].tag = 0;
	}
	void update(int &x, int l, int r, int L, int R, int v)
	{
		if(!x) x = ++tot;
		if(!rt) rt = x;
		if(L <= l && r <= R)
		{
			t[x].v = v; t[x].tag = v; t[x].mv = 1;
			return;
		}
		if(t[x].tag) pushdown(x);
		int mid = (l + r) >> 1;
		if(L <= mid) update(lc[x], l, mid, L, R, v);
		if(R > mid) update(rc[x], mid+1, r, L, R, v);
		pushup(x);
	}
	int query(int x, int l, int r, int L, int R)
	{
		if(!x && L <= l && r <= R)
		{
			int ll = (l-1)%n+1, rr = (r-1)%n+1;
			int zl = (l-1)/n+1, zr = (r-1)/n+1;
			if(zl == zr) return st.query(ll, rr);
			else return min(st.query(ll, n), st.query(1, rr));
		}
		if(L <= l && r <= R && t[x].mv) return t[x].v;
		if(t[x].tag) pushdown(x);
		int mid = (l + r) >> 1, ans = inf;
		if(L <= mid) ans = min(ans, query(lc[x], l, mid, L, R));
		if(R > mid) ans = min(ans, query(rc[x], mid+1, r, L, R));
		return ans;
	}
}t;

int main()
{
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
    
    n = read(); k = read(); N = n * k;
	for(int i=1; i<=n; i++) a[i] = read();
	st.init();
	Q = read();
	while(Q--)
	{
		int opt = read();
		if(opt == 1)
		{
			int l = read(), r = read(), v = read();
			t.update(rt, 1, N, l, r, v);
		}
		else if(opt == 2)
		{
			int l = read(), r = read();
			printf("%d\n", t.query(rt, 1, N, l, r));
		}
	}

    return 0;
}

 

C. 信息学的尽头

我也不知道我就跑了个最短路怎么还MLE 0了！？

然而就假设最短路有分：

要不是盲猜CR不会我怎么可能想到了基环树和换根dp之后打算写个暴力不做了

然而她切了

%%%CR

不过好像我好好想的话依然想不到具体该怎么办

怎么就连个找环都不会了

怎么就算个贡献都不知道加谁了

%%%CR

无奈至极地去鹤了她的两版code除了函数名之外没什么区别了

同时心情真的很糟糕

code 
 #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 2e5 + 2, inf = 0x3f3f3f3f;

int n, dfn[maxn], num, h[maxn], ccf, fa[maxn], siz[maxn];
ll pdh[maxn], dh[maxn], dep[maxn], sdep[maxn], ans[maxn];
bool inc[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct edge 
{
    int nxt, to, w;
}e[maxn<<1];
int head[maxn], len;

void add(int x, int y, int w)
{
    e[++len].to = y; e[len].nxt = head[x]; e[len].w = w;
    head[x] = len;
}

void Attend_NOI(int x, int ff)
{
    fa[x] = ff;
    dfn[x] = ++num;
    for(int i=head[x]; i; i=e[i].nxt)
    {
        int v = e[i].to;
        if(v == ff) continue;
        if(!dfn[v]) pdh[v] = e[i].w, Attend_NOI(v, x);
        else 
        {
            if(dfn[v] < dfn[x])
            {
                int st = x;
                while(st != v)
                {
                    h[++ccf] = st;
                    dh[ccf] = pdh[st];
                    st = fa[st];
                }
                h[++ccf] = v;
                dh[ccf] = e[i].w;
            }
        }
    }
}

void IwantAg(int x, int ff)
{
    sdep[x] = dep[x];
    siz[x] = 1;
    for(int i=head[x]; i; i=e[i].nxt)
    {
        int v = e[i].to;
        if(v == ff || inc[v]) continue;
        dep[v] = dep[x] + e[i].w;
        IwantAg(v, x);
        siz[x] += siz[v];
        sdep[x] += sdep[v];
    }
}

ll AuIsBest(int pos)
{
    ll ret = 0;
    for(int i=1; i<=ccf; i++)
    {
        if(i == pos) continue;
        ll dev = 0;
        if(i < pos) dev = min(dh[i+ccf]-dh[pos], dh[pos]-dh[i]);
        else dev = min(dh[i+ccf]-dh[pos+ccf], dh[pos+ccf]-dh[i]);
        ret += dev * siz[h[i]];
    }
    return ret;
}

void CTSC(int x, int ff, ll val)
{
    ans[x] = val;
    for(int i=head[x]; i; i=e[i].nxt)
    {
        int v = e[i].to;
        if(v == ff || inc[v]) continue;
        CTSC(v, x, val+(n-siz[v]*2)*e[i].w);
    }
}

int main()
{
    freopen("end.in", "r", stdin);
    freopen("end.out", "w", stdout);
    
    n = read();
    for(int i=1; i<=n; i++)
    {
        int u = read(), v = read(), w = read();
        add(u, v, w); add(v, u, w);
    }
    Attend_NOI(1, 0);
    for(int i=ccf+1; i>=1; i--) dh[i] = dh[i-1];
    int rp = ccf + 1;
    for(int i=ccf+2; i<=ccf*2; i++)
    {
        rp++; dh[rp] = dh[rp-ccf];
    }
    for(int i=2; i<=ccf*2; i++) dh[i] = dh[i-1] + dh[i];
    for(int i=ccf+1; i<=ccf*2; i++) h[i] = h[i-ccf];
    for(int i=1; i<=ccf*2; i++) inc[h[i]] = 1;
    ll Sum_ep = 0;
    for(int i=1; i<=ccf; i++) IwantAg(h[i], 0), Sum_ep += sdep[h[i]];
    for(int i=1; i<=ccf; i++)
    {
        ll sum_ep = AuIsBest(i);
        sum_ep += Sum_ep;
        CTSC(h[i], 0, sum_ep);
    }
    for(int i=1; i<=n; i++) printf("%lld ", ans[i]);
    
    return 0;
}
code 
 #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 2e5 + 2, inf = 0x3f3f3f3f;

int n, dfn[maxn], num, h[maxn], ccf, fa[maxn], siz[maxn];
ll pdh[maxn], dh[maxn], dep[maxn], sdep[maxn], ans[maxn];
bool inc[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct edge 
{
    int nxt, to, w;
}e[maxn<<1];
int head[maxn], len;

void add(int x, int y, int w)
{
    e[++len].to = y; e[len].nxt = head[x]; e[len].w = w;
    head[x] = len;
}

void Attend_NOI(int x, int ff)
{
    fa[x] = ff;
    dfn[x] = ++num;
    for(int i=head[x]; i; i=e[i].nxt)
    {
        int v = e[i].to;
        if(v == ff) continue;
        if(!dfn[v]) pdh[v] = e[i].w, Attend_NOI(v, x);
        else 
        {
            if(dfn[v] < dfn[x])
            {
                int st = x;
                while(st != v)
                {
                    h[++ccf] = st;
                    dh[ccf] = pdh[st];
                    st = fa[st];
                }
                h[++ccf] = v;
                dh[ccf] = e[i].w;
            }
        }
    }
}

void IwantAg(int x, int ff)
{
    sdep[x] = dep[x];
    siz[x] = 1;
    for(int i=head[x]; i; i=e[i].nxt)
    {
        int v = e[i].to;
        if(v == ff || inc[v]) continue;
        dep[v] = dep[x] + e[i].w;
        IwantAg(v, x);
        siz[x] += siz[v];
        sdep[x] += sdep[v];
    }
}

ll ssiz[maxn], sdis[maxn];
ll AuIsBest(int pos)
{
    ll ret = 0;
    /*for(int i=1; i<=ccf; i++)
    {
        if(i == pos) continue;
        ll dev = 0;
        if(i < pos) dev = min(dh[i+ccf]-dh[pos], dh[pos]-dh[i]);
        else dev = min(dh[i+ccf]-dh[pos+ccf], dh[pos+ccf]-dh[i]);
        ret += dev * siz[h[i]];
    }*/
    //又鹤了，，，，，，然而又鹤错了，，，
    int Pos = pos + ccf;
    int l = pos, r = Pos - 1;
    while(l < r)
    {
        int mid = (l + r + 1) >> 1;
        if(dh[mid]-dh[pos] <= dh[Pos]-dh[mid]) l = mid;
        else r = mid - 1;
    }
    if(l > pos) ret = sdis[l]-sdis[pos]-dh[pos]*(ssiz[l]-ssiz[pos]);
    if(l < Pos-1) ret += dh[Pos]*(ssiz[Pos-1]-ssiz[l])-sdis[Pos-1]+sdis[l];
    return ret;
}

void CTSC(int x, int ff, ll val)
{
    ans[x] = val;
    for(int i=head[x]; i; i=e[i].nxt)
    {
        int v = e[i].to;
        if(v == ff || inc[v]) continue;
        CTSC(v, x, val+(n-siz[v]*2)*e[i].w);
    }
}

int main()
{
    freopen("end.in", "r", stdin);
    freopen("end.out", "w", stdout);
    
    n = read();
    for(int i=1; i<=n; i++)
    {
        int u = read(), v = read(), w = read();
        add(u, v, w); add(v, u, w);
    }
    Attend_NOI(1, 0);
    for(int i=ccf+1; i>=1; i--) dh[i] = dh[i-1];
    int rp = ccf + 1;
    for(int i=ccf+2; i<=ccf*2; i++)
    {
        rp++; dh[rp] = dh[rp-ccf];
    }
    for(int i=2; i<=ccf*2; i++) dh[i] = dh[i-1] + dh[i];
    for(int i=ccf+1; i<=ccf*2; i++) h[i] = h[i-ccf];
    for(int i=1; i<=ccf*2; i++) inc[h[i]] = 1;
    ll Sum_ep = 0;
    for(int i=1; i<=ccf; i++) IwantAg(h[i], 0), Sum_ep += sdep[h[i]];
    for(int i=1; i<=ccf*2; i++)
    {
        ssiz[i] = ssiz[i-1] + siz[h[i]];
        sdis[i] = sdis[i-1] + dh[i] * siz[h[i]];
    }
    for(int i=1; i<=ccf; i++)
    {
        ll sum_ep = AuIsBest(i);
        sum_ep += Sum_ep;
        CTSC(h[i], 0, sum_ep);
    }
    for(int i=1; i<=n; i++) printf("%lld ", ans[i]);
    
    return 0;
}

同时依然不服她，%了也不服，输很多次也不服，你就当我是个死鸭子吧，就是化成灰变成烟随风散了也要嘴硬的……

 

D. 球对称薛定谔方程

组织了一下语言发现还是想不出什么和这篇题解不一样的说法，那就……

这种堆的方案数的求法让我想到了多叉堆，公式的差别在于有没有枚举接在一起的另一棵树根节点的权值。关于为什么转移时非要枚举1号点的权值与子树大小，我感觉和有一种二进制拆开的转移让其中一部分减掉lowbit差不多，就是怎么拆都行选一个最好拆的，只是需要枚举了其中一棵子树的信息具体哪棵树并不重要，但是标号最小的儿子权值可以从j+1开始比较方便枚举……

code 
 #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 305, inf = 0x3f3f3f3f;

int n, k, P, C[maxn][maxn], f[maxn][maxn], s[maxn][maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

int main()
{
    freopen("seq.in", "r", stdin);
    freopen("seq.out", "w", stdout);
    
    n = read(); k = read(); P = read();
	for(int i=0; i<=n; i++)
	{
		C[i][0] = 1;
		for(int j=1; j<=i; j++)
		{
			C[i][j] = ((ll)C[i-1][j] + C[i-1][j-1]) % P;
		}
	}
	for(int i=0; i<=k; i++) f[1][i] = 1, s[1][i] = k-i+1;
	for(int i=2; i<=n+1; i++)
	{
		for(int j=0; j<=k; j++) for(int l=1; l<i; l++) f[i][j] = (f[i][j]+1ll*f[i-l][j]*s[l][j+1]%P*C[i-2][l-1]%P)%P;
		for(int j=k; j; j--) s[i][j] = ((ll)s[i][j+1]+f[i][j])%P;
	}
	printf("%d\n", f[n+1][0]);

    return 0;
}

 

标签：ch,2022NOIPA,int,long,27,maxn,联测,ans,getchar
From： https://www.cnblogs.com/Catherine2006/p/16887902.html

相关文章

  • P2827 NOIP2016 提高组 蚯蚓
    P2827NOIP2016提高组蚯蚓-洛谷|计算机科学教育新生态(luogu.com.cn)事实上，本题疑似所有题解和lyd蓝书上的证明均有误，本篇题解将给出一个严谨的单调性正确性证明......
  • 【比赛】2022NOIP A层联测27
    A.天平点击查看代码#include<cstdio>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<iostream>#include<vector>#defineint......
  • (AtCoder Beginner Contest 277)E(分层图+最短路 or bfs搜两种状态）
    E-CrystalSwitches题目大意：给你n个点,m条边，连接成一个无向图，每个边最初有一个状态（0or1）表示是否能够通过，同时给k个开关位于k的顶点上，每次点击开关会使得所有路的状......
  • CF1027E Inverse Coloring
    考场上没敲出来（其实想到就挺好写的捏组数据手动模拟一下：\(\begin{bmatrix}1&0&1&1&1&0&1\\1&0&1&1&1&0&1\\0&1&0&0&0&1&0\\1&0&1&1&1&0&1\\0&1&0&0&0&1&0\\0......
  • ABC277E 题解
    前言题目传送门！更好的阅读体验？非常套路的分层图，纪念赛时切掉了。思路我们以样例来解释。首先，这是最基础的图。我们把图分成两层：第一层是原本\(w=1\)的路可以通......
  • ABC277D 题解
    前言题目传送门！或许更好的阅读体验？比较简单的模拟。思路首先把\(a_i\)排序。每次往后一直跑，如果不能再取了，就停下。但是这样做是\(O(n^2)\)的。我们需要优化。......
  • 2022NOIP A层联测26 乘筛积 放进去 最长路径 生成树的传说
    T1[转化枚举角度]给出长度是n的a序列，和长度是m的b序列，给出Q组询问\([p,q]\),求\(\sum_{p*i+q*j=C}^{}ai*bj\)。（n,m,C,q<=3e5）考场上来想枚举，对于\(max(p,q)>=\sqrt{C}\),......
  • AtCoder Beginner Contest 277 D Takahashi's Solitaire
    Takahashi'sSolitaire双指针&&尺取先排个序，然后把数组扩展到\(2\timesn\)，为了处理循环的情况然后双指针跑一下，限定\(r\)扩展的条件为：当前数字等于前一个或者......
  • AtCoder Beginner Contest 277 F Sorting a Matrix
    SortingaMatrix拓扑序首先可以明确无论怎么交换行列，原本在同一行或者同一列的元素，还是会处于同一行或者同一列条件一每行每行地看，如果能满足从小到大的条件，说明第......
  • AtCoder Beginner Contest 277 E Crystal Switches
    CrystalSwitches分层图+\(01bfs\)按钮的操作就是走分层图的边因此就构建两张图，然后将特殊点加一个双向边\(01bfs\)跑一下就行#include<iostream>#include<cstd......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99