标签：钉耙 CI return int 编程 2024 query end now

Preface

最后一场 HDU 多校了，前期一直犯病但也堪堪签了前六题，但后期又是酣畅淋漓的后期三开三卡

我写 04，祁神写 09，徐神写 10，最后一个没调出来，赛后祁神和徐神都发现了很多修改点但因为题目还没公开、数据和题解也没法，就先坑着之后再来补了

树异或价值

首先不难发现 \(k\) 位这个限制其实没啥用，我们只要求出一位的情况最后做 \(k\) 次幂即可

这个式子很显然可以看成在某个点 \(x\) 的不同子树内选两个 \(a_i\) 不同的点，并产生 \(dep_x\) 的贡献

不难发现我们需要让子树内 \(0/1\) 的个数尽可能接近才能最大化贡献，因此不妨进行 DP

令 \(f_{x,-1/0/1}\) 表示在 \(x\) 的子树内，\(0\) 的个数减去 \(1\) 的个数为 \(-1/0/1\) 时的方案数，转移就类似于树上背包

但要注意虽然后面一维的范围很小，但遇到菊花图之类的可能会变得很大，因此要套个分治 NTT 优化下

#include <bits/stdc++.h>

// using std::bit_ceil; // C++20
// using std::countr_zero; // C++20

inline int bit_ceil(int a) {
    int i;
    for(i = 1; i < a; i <<= 1);
    return i;
}

inline int countr_zero(int a) {
    return __builtin_ctz(a);
}

using llsi = long long signed int;
constexpr int mod = 998244353;

template<
    typename I,
    typename LL,
    I mod,
    I g
> struct ntpoly_ns {
    using poly = std::vector<I>;
    
    static constexpr I ksm(I a, I b) {
        I c(1);
        while(b) {
            if(b & I(1)) c = LL(c) * a % mod;
            a = LL(a) * a % mod;
            b >>= 1;
        }
        return c;
    }

    static constexpr I gi = ksm(g, mod - 2);

    std::vector<int> rev;
    uint32_t n;

    void prep(int len) {
        n = bit_ceil(uint32_t(len));
        rev.resize(n); rev[0] = 0;
        int t = countr_zero(n) - 1;
        for(int i = 1; i < n; ++i) rev[i] = rev[i >> 1] >> 1 | (i & 1) << t;
    }

    void ext_zero(poly &a, int nlen) {
        uint32_t c = a.size(); if(c >= nlen) return ;
        a.resize(nlen);
        std::fill(a.begin() + c, a.end(), I(0));
    }

    void NTT(I *a, int on) {
        for(int i = 1; i < n; ++i) if(rev[i] > i) std::swap(a[i], a[rev[i]]);

        for(int d = 1; d < n; d <<= 1) {
            I wi = ksm(on > 0 ? g : gi, (mod - 1) / (2 * d));
            for(int j = 0; j < n; j += 2 * d) {
                I w(1);
                for(int k = j; k < j + d; ++k, w = LL(wi) * w % mod) {
                    I x = a[k], y = LL(w) * a[k + d] % mod;
                    a[k]     = (x + y) % mod;
                    a[k + d] = (x + mod - y) % mod;
                }
            }
        }

        if(on < 0) {
            LL inv(ksm(n, mod - 2));
            for(int i = 0; i < n; ++i) a[i] = LL(a[i]) * inv % mod;
        }
    }

    void NTT(poly &a, int on) {
        ext_zero(a, n);
        NTT(a.data(), on);
    }

    poly& mult(poly &a, poly &b) {
        if(a.size() + b.size() < 30) {
            poly c(a.size() + b.size() - 1, 0);
            for(int i = 0; i < a.size(); ++i)
                for(int j = 0; j < b.size(); ++j)
                    c[i + j] = (c[i + j] + LL(a[i]) * b[j]) % mod;
            return a = c;
        }
        prep(a.size() + b.size());
        NTT(a, 1);
        NTT(b, 1);
        for(int i = 0; i < n; ++i) a[i] = LL(a[i]) * b[i] % mod;
        NTT(a, -1);
        return a;
    }

    poly& div_mult(poly *begin, poly *end) {
        if(begin + 1 == end) return *begin;
        poly *mid = begin + (end - begin) / 2;
        poly &left = div_mult(begin, mid);
        poly &right = div_mult(mid, end);
        return mult(left, right);
    }

    poly& div_mult(std::vector<poly> &polys) {
        return div_mult(polys.data(), polys.data() + polys.size());
    }
};

ntpoly_ns<int, llsi, mod, 3> ntpoly;
using poly = ntpoly_ns<int, llsi, mod, 3>::poly;

constexpr int $n = 200005;
std::vector<int> ch[$n];
int siz[$n], fa[$n], dp[$n][3];

void dfs(int cur) {
    siz[cur] = 1;
    std::vector<poly> polys = {poly{1, 0, 1}}; 
    for(auto ch: ch[cur]) {
        dfs(ch);
        siz[cur] += siz[ch];
        polys.push_back(poly{dp[ch][0], dp[ch][1], dp[ch][2]});
    }
    poly &c = ntpoly.div_mult(polys);

    int center = polys.size();
    dp[cur][0] = c[center - 1];
    dp[cur][1] = c[center];
    dp[cur][2] = c[center + 1];
    return ;
}

void work() {
    int n, k; std::cin >> n >> k;
    for(int i = 1; i <= n; ++i) ch[i].clear();
    for(int i = 2; i <= n; ++i) {
        std::cin >> fa[i];
        ch[fa[i]].push_back(i);
    }
    dfs(1);
    llsi ans = llsi(dp[1][0]) + dp[1][1] + dp[1][2];
    std::cout << ntpoly.ksm(ans % mod, k) << char(10);
    return ;
}

int main() {
    std::ios::sync_with_stdio(false);
    int T; std::cin >> T; while(T--) work();
    return 0;
}

树上询问

和之前 CF做过的一个题的思路可以说是一模一样

考虑确定树上路径的两个端点，显然可以以权值为下标建立线段树，存储 DFS 序的最大值，欧拉序的最大最小值，这样可以快速确定可能的端点 \(u,v\)

考虑检验这条路径是否合法，首先是路径上的边数 \(dis(u,v)=r-l\)，这个用 LCA 可以快速计算

其次还需要满足路径上所有点权值都在 \([l,r]\) 内，树剖后用线段树维护区间最大/最小值，判断是否超出范围

总复杂度 \(O(n\log^2 n)\)

#include<cstdio>
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<utility>
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=200005;
int t,n,q,a[N],pos[N],seq[N],dfn[N],dfnr[N],opt,x,y; vector <int> v[N];
#define TN CI now=1,CI l=1,CI r=n
#define LS now<<1,l,mid
#define RS now<<1|1,mid+1,r
class Segment_Tree1
{
	private:
		pi mxdfn[N<<2],mndfnr[N<<2],mxdfnr[N<<2];
        inline void pushup(CI now)
        {
            mxdfn[now]=max(mxdfn[now<<1],mxdfn[now<<1|1]);
            mndfnr[now]=min(mndfnr[now<<1],mndfnr[now<<1|1]);
            mxdfnr[now]=max(mxdfnr[now<<1],mxdfnr[now<<1|1]);
        }
	public:
		inline void build(TN)
		{
			if (l==r)
            {
                int x=pos[l]; mxdfn[now]={dfn[x],x};
                mndfnr[now]=mxdfnr[now]={dfnr[x],x};
                return;
            }
			int mid=l+r>>1; build(LS); build(RS); pushup(now);
		}
		inline void update(CI pos,CI ndfn,CI ndfnr,CI num,TN)
		{
			if (l==r)
            {
                mndfnr[now]=mxdfnr[now]={ndfnr,num};
                mxdfn[now]={ndfn,num}; return;
            }
            int mid=l+r>>1;
			if (pos<=mid) update(pos,ndfn,ndfnr,num,LS); else update(pos,ndfn,ndfnr,num,RS);
            pushup(now);
		}
		inline pi query_maxdfn(CI beg,CI end,TN)
		{
			if (beg<=l&&r<=end) return mxdfn[now]; int mid=l+r>>1;
            if (end<=mid) return query_maxdfn(beg,end,LS);
            if (beg>mid) return query_maxdfn(beg,end,RS);
            return max(query_maxdfn(beg,end,LS),query_maxdfn(beg,end,RS));
		}
		inline pi query_mindfnr(CI beg,CI end,TN)
		{
			if (beg<=l&&r<=end) return mndfnr[now]; int mid=l+r>>1;
            if (end<=mid) return query_mindfnr(beg,end,LS);
            if (beg>mid) return query_mindfnr(beg,end,RS);
            return min(query_mindfnr(beg,end,LS),query_mindfnr(beg,end,RS));
		}
		inline pi query_maxdfnr(CI beg,CI end,TN)
		{
			if (beg<=l&&r<=end) return mxdfnr[now]; int mid=l+r>>1;
            if (end<=mid) return query_maxdfnr(beg,end,LS);
            if (beg>mid) return query_maxdfnr(beg,end,RS);
            return max(query_maxdfnr(beg,end,LS),query_maxdfnr(beg,end,RS));
		}
}SEG1;
class Segment_Tree2
{
	private:
		int mn[N<<2],mx[N<<2];
        inline void pushup(CI now)
        {
            mn[now]=min(mn[now<<1],mn[now<<1|1]);
            mx[now]=max(mx[now<<1],mx[now<<1|1]);
        }
	public:
		inline void build(TN)
		{
			if (l==r) return (void)(mn[now]=mx[now]=a[seq[l]]);
			int mid=l+r>>1; build(LS); build(RS); pushup(now);
		}
		inline void update(CI pos,CI mv,TN)
		{
			if (l==r) return (void)(mn[now]=mx[now]=mv); int mid=l+r>>1;
			if (pos<=mid) update(pos,mv,LS); else update(pos,mv,RS);
            pushup(now);
		}
		inline int query_min(CI beg,CI end,TN)
		{
			if (beg<=l&&r<=end) return mn[now]; int mid=l+r>>1;
            if (end<=mid) return query_min(beg,end,LS);
            if (beg>mid) return query_min(beg,end,RS);
            return min(query_min(beg,end,LS),query_min(beg,end,RS));
		}
		inline int query_max(CI beg,CI end,TN)
		{
			if (beg<=l&&r<=end) return mx[now]; int mid=l+r>>1;
            if (end<=mid) return query_max(beg,end,LS);
            if (beg>mid) return query_max(beg,end,RS);
            return max(query_max(beg,end,LS),query_max(beg,end,RS));
		}
}SEG2;
#undef TN
#undef LS
#undef RS
namespace Heavy_Division
{
    int idx,idxr,top[N],dep[N],sz[N],anc[N],son[N];
    inline void DFS1(CI now=1,CI fa=0)
    {
        son[now]=0; sz[now]=1; dep[now]=dep[fa]+1; anc[now]=fa;
        for (int to:v[now]) if (to!=fa)
        {
            DFS1(to,now); sz[now]+=sz[to];
            if (sz[to]>sz[son[now]]) son[now]=to;
        }
    }
    inline void DFS2(CI now=1,CI tf=1)
    {
        seq[dfn[now]=++idx]=now; top[now]=tf;
        if (son[now]) DFS2(son[now],tf);
        for (int to:v[now]) if (to!=anc[now]&&to!=son[now]) DFS2(to,to);
        dfnr[now]=++idxr;
    }
    inline bool query_path(int x,int y,CI L,CI R)
    {
    	int ret=0;
    	while (top[x]!=top[y])
    	{
    		if (dep[top[x]]<dep[top[y]]) swap(x,y);
    		if (SEG2.query_min(dfn[top[x]],dfn[x])<L) return 0;
            if (SEG2.query_max(dfn[top[x]],dfn[x])>R) return 0;
    		x=anc[top[x]];
    	}
    	if (dep[x]<dep[y]) swap(x,y);
        if (SEG2.query_min(dfn[y],dfn[x])<L) return 0;
        if (SEG2.query_max(dfn[y],dfn[x])>R) return 0;
		return 1;
    }
    inline int LCA(int x,int y)
    {
    	while (top[x]!=top[y])
    	{
    		if (dep[top[x]]<dep[top[y]]) swap(x,y);
    		x=anc[top[x]];
    	}
    	if (dep[x]<dep[y]) swap(x,y);
		return y;
    }
    inline int getdis(CI x,CI y)
    {
        return dep[x]+dep[y]-2*dep[LCA(x,y)];
    }
};
using namespace Heavy_Division;
int main()
{
    int size(256<<20); //256M
    __asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
    ios::sync_with_stdio(0); cin.tie(0);
	for (cin>>t;t;--t)
	{
		RI i; for (cin>>n,i=1;i<=n;++i) cin>>a[i],pos[a[i]]=i;
		for (i=1;i<n;++i) cin>>x>>y,v[x].push_back(y),v[y].push_back(x);
		DFS1(); DFS2(); SEG1.build(); SEG2.build();
		for (cin>>q;q;--q)
		{
            cin>>opt>>x>>y;
            if (opt==1)
            {
                int u=a[x],v=a[y];
                SEG1.update(a[x],dfn[y],dfnr[y],y);
                SEG1.update(a[y],dfn[x],dfnr[x],x);
                SEG2.update(dfn[x],a[y]);
                SEG2.update(dfn[y],a[x]);
                swap(a[x],a[y]); swap(pos[u],pos[v]);
            } else
            {
                int u=SEG1.query_maxdfn(x,y).se,v=SEG1.query_mindfnr(x,y).se;
                if (u==v) v=SEG1.query_maxdfnr(x,y).se;
                cout<<(getdis(u,v)==y-x&&query_path(u,v,x,y)?"Yes\n":"No\n");
            }
		}
		for (idx=idxr=0,i=1;i<=n;++i) v[i].clear();
	}
    exit(0);
	return 0;
}

黑洞合并

祁神手玩了半天发现最后的贡献好像和操作顺序无关，因此只要简单的模拟即可

具体原理我也不清楚，总之牛逼就对了

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int MOD = 998244353;
void add(int &x, int a){if ((x+=a)>=MOD) x-=MOD;}

void solve(){
    int n; cin >> n;
    vector<int> vec(n);
    for (int i=0; i<n; ++i) cin >> vec[i];
    int ans=0;
    for (int j=n-1; j>0; --j){
        add(ans, vec[0]*vec[j]%MOD*((vec[0]+vec[j])%MOD)%MOD);
        add(vec[0], vec[j]);
    }
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t; while (t--) solve();
    return 0;
}

亡语

总感觉是我没搞懂题目要干嘛，写完一直 WA 也不知道咋回事，等数据和题解出来再看下吧

怪物猎人

算出可能进行的轮数的上下界，如果这个界内含有两个及以上的整数则两个人都有解，否则按奇偶性输出一个人即可

#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
int t,k,x,y;
signed main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    for (cin>>t;t;--t)
    {
        cin>>k>>x>>y;
        int L=(k+x-1)/x,R=(k+y-1)/y;
        if (L!=R) cout<<"Yes\nYes\n"; else
        {
            if (L%2==1) cout<<"Yes\nNo\n";
            else cout<<"No\nYes\n";
        }
    }
    return 0;
}

融合矿石

跑两遍完全背包，先求出 \(f_x\) 表示体积为 \(x\) 的石头最多能有多少“金辉石”，然后就能顺便算出对应的贡献

再求出 \(g_x\) 表示体积为 \(x\) 的石头最大总价值，总复杂度 \(O(nm)\)

#include<bits/stdc++.h>
using namespace std;
// #define int long long

using pii = pair<int, int>;
#define ft first
#define sd second

const int N = 3005;
const int INF = (int)1e9+5;
int f[N], g[N];

void solve(){
    vector<int> v(10);
    for (int i=0; i<10; ++i) cin >> v[i];
    int n, m; cin >> n >> m;
    vector<pii> vec(n+1);
    for (int i=1; i<=n; ++i){
        int a, b; cin >> a >> b;
        vec[i] = {a, b};
    }

    f[0] = 0;
    for (int j=1; j<=m; ++j) f[j] = -INF;
    for (int i=1; i<=n; ++i){
        for (int j=vec[i].ft; j<=m; ++j){
            f[j] = max(f[j], f[j-vec[i].ft]+vec[i].sd);
        }
    }

    // printf("f:"); for (int j=0; j<=m; ++j) printf("%d ", f[j]); puts("");

    auto calc = [&](int a, int b){
        for (int i=9; i>=0; --i){
            if (10*b > a*i) return v[i];
        }
        return 0;
    };

    g[0] = 0;
    for (int j=1; j<=m; ++j) g[j] = -INF;
    for (int i=1; i<=m; ++i){
        for (int j=i; j<=m; ++j){
            g[j] = max(g[j], g[j-i]+i*calc(i, f[i]));
        }
    }
    // printf("g:"); for (int j=0; j<=m; ++j) printf("%d ", g[j]); puts("");

    cout << g[m] << '\n';
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t; while (t--) solve();
    return 0;
}

小猫钓鱼

简单手玩发现两个人初始时的 pair 数是相同的，不妨记为 \(c\)

手玩一下发现当且仅当 \(c=0\) 时后手胜，否则总是先手胜

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,a[N],b[N],c[N];
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    for (cin>>t;t;--t)
    {
        cin>>n; int cnt=0;
        for (RI i=1;i<=n;++i) cin>>a[i];
        for (RI i=1;i<=n;++i) cin>>b[i];
        for (RI i=1;i<=n;++i) c[i]=0;
        for (RI i=1;i<=n;++i) if (++c[a[i]]==2) ++cnt;
        // if (cnt>=2) puts("Tie"); else
        // if (cnt==1) puts("shuishui"); else
        // puts("sha7dow");
        puts(cnt>0?"shuishui":"sha7dow");
    }
    return 0;
}

长期素食

比赛的时候以为只要求出每天的最大/次大直线即可 DP 求解，后面得知好像要求出前三大

这类找次大/次次大最优直线的问题可以用随机化分组转化为求最大直线的经典问题从而求凸壳求解，但祁神赛后才把赛时的求前二大改为求前三大，现在数据没出也测不了

收集签名

徐神赛时写了 DP 的做法但一直 WA，赛后发现有特判写错了，也是因为还没数据测不了先坑着

Postscript

由于今天要整理东西准备明天出发北京了，因此这场以及之前欠下的一些博客都留着回来后再补吧

标签：钉耙,CI,return,int,编程,2024,query,end,now
From： https://www.cnblogs.com/cjjsb/p/18363504

2024“钉耙编程”中国大学生算法设计超级联赛（9）