XJTUPC 2024 题解&游记

· · 个人记录

AC 代码等赛后代码公开之后放上来。

A

弱智题，直接输出 a+b+2c+3d 即可。

B

弱智题，直接输出 2\operatorname{sin}(tv\pi)\sqrt{x^2+y^2} 即可，没卡精度。

C

弱智题，直接根据公式计算即可。

D

弱智题，容易发现一条链正着做反着做总有一个符合条件，输出即可。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,u,v;
    int res=0;
    scanf("%d %d",&n,&m);
    while(m--)
    {
        scanf("%d %d",&u,&v);
        if(u<=v) ++res;
        else --res;
    }
    if(res>=0)
    {
        for(int i=0;i<n;++i) printf("%d%c",i," \n"[i==n-1]);
    }
    else
    {
        for(int i=2;i<=n;++i) printf("%d ",i); puts("0");
    }
}

E

签到题，考虑增量构造，每次把 i 插到 a_i 后面。

接下来我们证明这么做是对的：
既然左边的房子都已经构造好了。那么右边的房子不影响左边的答案，因此可以增量构造。
考虑 i 在答案序列插入到 a_i 后面就是恰好比 a_i 高，正确性是显然的。

接下来考虑实现，可以直接链表或者并查集维护。赛时采用了并查集，但是似乎链表更简单？

#include <bits/stdc++.h>
int fa[222222];
int gf(int u){
    if(fa[u]==u){
        return u;
    }
    return fa[u]=gf(fa[u]);
}
int a[222222];
int next[222222];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",a+i);
    }
    for(int i=1;i<=n;++i){
        fa[i]=i;
    }
    for(int i=n;i;--i){
        int x=gf(a[i]);
        next[x]=i;
        fa[x]=i;
    }
    int k=n;
    while(a[k]!=0)--k;
    while(k){
        printf("%d ",k);
        k=next[k];
    }
    return 0;
}

F

弱智题。

f(x,y)=\sum_{a_i=x}i\times\sum_{a_j=y}j

用桶维护即可。

#include<bits/stdc++.h>
long long sum[2222222];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        int a;
        scanf("%d",&a);
        sum[a]+=i;
    }
    for(int i=1;i<=m;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%lld\n",sum[x]*sum[y]);
    }
    return 0;
}

G

较难题，赛时没搞出来。
首先只要求出 \operatorname{and} 的答案，就可以求出所有的三个答案。赛时没注意到这一点，没调出来，但其实一个答案是做出来了的。
具体地，注意到

\begin{cases} a⊕b=a+b-2(a\&b)\\ a\mid b=(a⊕b)+a\&b) \end{cases}

考虑拆位计算 \operatorname{and}，发现可以把 a 进行 reverse 并复制一份接在后面，与 b 进行卷积并取第 m\sim 2m-1 项。为了避免使用 FFT/NTT 使得复杂度达到两个 \log，注意到 b 的生成函数

b=x^{2^d}\dfrac {(1-x^{2^d})(1-x^m)} {(1-x^{2^{d+1}})(1-x)}

就可以直接处理卷积结果了。

inline void convovle(const int *f,int m,int d,ll *R){ // 对于序列 f 计算它和参数为 d 时的序列 b 卷积
    static ll g[N];
    memset(g,0,sizeof(g));
    for(int i=(1<<d);i<2*m;++i) g[i] = f[i-(1<<d)];

    for(int i=1;i<2*m;++i) g[i] += g[i-1];
    for(int i=2*m-1;i>=(1<<d);--i) g[i] -= g[i-(1<<d)];

    for(int i=(2<<d);i<2*m;++i) g[i] += g[i-(2<<d)];
    for(int i=2*m-1;i>=m;--i) g[i] -= g[i-m];

    for(int i=0;i<2*m;++i) R[i] = g[i];
}

详见 https://www.luogu.com.cn/article/6e3xhab7。

H

较难题，没调出来，呜呜呜。
如果没有修改权值，考虑类似 kruskal 的过程，按权值从大到小加边，出现第一次 1 到 k 可达时的权值即为 k 的答案。
考虑维护 100 张图表示边权不小于 v 的子图，删边难以维护，考虑离线下来改为加边权，这样变成加边。对于每张图进行维护，直接遍历维护，复杂度考虑每个点只会被访问出边当且仅当这个点变为可达点。因此总复杂度为 \Theta((n+m)\max d+q)。

I

签到题，按题意模拟即可。

具体实现上，对于当前坐标维护当前字符串 S 在指令串构成的 trie 树上的最低祖先 p 以及 |S|-\operatorname{dep}_p，为了维护 Tab 操作我们需要记录每一个点子树内深度最小的分叉点，即有超过一个儿子或自己是某指令串的结束处的点。

然后随便维护就做完了，也没什么细节。

#include <bits/stdc++.h>
using namespace std;
constexpr int maxn=1e6+9;
struct node
{
    int ch[26],nxt,cnt=0,fa=-2,endpos=-1;
}tr[maxn];
int rt=0,ncnt=0;
void insert(char s[],int id)
{
    int u=rt;
    for(char *p=s;*p;++p)
    {
        if(!tr[u].ch[(*p)-'a']) tr[u].ch[(*p)-'a']=++ncnt;
        tr[tr[u].ch[(*p)-'a']].fa=u;
        ++tr[u].cnt;
        u=tr[u].ch[(*p)-'a'];
    }
    ++tr[u].cnt;
    tr[u].endpos=id;
}
int dfs(int u)
{
    int sc=0;
    for(int i=0;i<26;++i) sc+=!!tr[u].ch[i];
    if(!sc) return tr[u].nxt=u;
    if(sc>1 || ~tr[u].endpos)
    {
        for(int i=0;i<26;++i)
            if(tr[u].ch[i])
                dfs(tr[u].ch[i]);
        return tr[u].nxt=u;
    }
    for(int i=0;i<26;++i)
        if(tr[u].ch[i])
            return tr[u].nxt=dfs(tr[u].ch[i]);
    return 114514;
}
int npos=0,blen=0,n,m;
char s[5000009];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>s,insert(s,i);
    tr[0].nxt=dfs(0);
    cin>>s;
    for(int i=0;i<m;++i)
    {
        if(s[i]=='E')
        {
            if(blen) printf("-1 ");
            else printf("%d ",tr[npos].endpos);
            npos=blen=0;
            continue;
        }
        if(s[i]=='T')
        {
            if(!blen) npos=tr[npos].nxt;
            continue;
        }
        if(s[i]=='B')
        {
            if(blen) --blen;
            else if(npos) npos=tr[npos].fa;
            continue;
        }
        if(blen || !tr[npos].ch[s[i]-'a']) ++blen;
        else npos=tr[npos].ch[s[i]-'a'];
    }
    return 0;
}

J

简单题。

对 U 的每一子集 S，设 F(S)=|\sum_{x\in S}x-\sum_{x\in \complement_US}x|，则答案是 \min_{S\in U}F(S)。接下来我们证明对于每一可能的子集 S，均存在一种构造方案使得答案为 F(S)。

给出一种考场上想出的构造方式：维护两个集合 S,T 表示对应的子集和补集，每次任取 S,T 中的两个元素 a\in S,b\in T，把它们从集合中删去，并将他们的差值 |a-b| 加入 a 和 b 中较大的那个对应的集合中。
接下来证明这么做是对的：考虑对于 |S|\cdot|T|=0 的情况，正确性是显然的，每一步操作也不影响值 |\sum_{x\in S}x-\sum_{x\in T}x|，且由于每步必然有一个集合大小缩减 1，因此必然可以通过有限步操作到达 |S||T|=0 的边界情况。至此我们得到了一种操作方案。

接下来我们考虑如何计算最小值。用 bitset 维护当前所有值域中的值是否可以作为一种方案的答案，即 dp_{i,j}=[\exist S\subset \{a_1,a_2,\cdots,a_i\}(F(S)=j)]，边界条件为 dp_{0,i}=[i=0]。对每个物品考虑是否放入 S 中，则有 dp_{i,j}=dp_{i-1,j+a_i} \operatorname{or}dp_{i-1,|j-a_i|}。一部分可以 bitset 直接位移，另一部分不超过 \max a_i 次更新，可以每次暴力维护。

但是值域达到了 5\times 10^7，只需要构造 x-1 个 x 和 x 个 x-1 就可以使得中途达到的最大值域卡到上界，可以打乱优化。这里不对打乱优化进行证明，相关证明参考[THUPC2021] 混乱邪恶 题解区。

记得加滚动数组。

原题解供喷：

容易发现每次就是对 bitset 左移右移或一下然后暴力做不超过 $5000$ 的部分，再加上打乱优化+开小 bitset 即可通过。

具体地，每次 $dp_{i,j+a_i} = dp_{i,j+a_i} \operatorname{or} dp_{i-1,j}$ 直接维护，$dp_{i,|j-a_i|} = dp_{i,|j-a_i|} \operatorname{or} dp_{i-1,j}$ 拆成 $j\ge a_i$（直接 bitset 移位维护）和 $j<a_i$（不超过 $5000$，直接暴力）。
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn=1e4+9;
int a[maxn],n;
bitset<(1<<20)> x[2]; 
int main()
{
    srand(time(0));
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",a+i);
    random_shuffle(a+1,a+n+1);
    x[0].set(0);
    for(int i=1;i<=n;++i)
    {
        x[i&1]=(x[~i&1]<<a[i])|(x[~i&1]>>a[i]);
        for(int j=a[i];j;--j)
            x[i&1][a[i]-j]=x[i&1][a[i]-j]|x[~i&1][j];
    }
    for(int i=0;i<(1<<20);++i)
        if(x[n&1][i]) printf("%d\n",i),exit(0);
    return 0;
}

K

中档题。
写出四个转移矩阵作矩阵快速幂即可。 

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define ll long long
#define p 998244353
using namespace std;

struct mat{
    int a[6][6];
    inline mat(){ memset(a,0,sizeof(a)); }  
};

inline mat operator * (const mat& lhs,const mat& rhs){
    mat res = mat();
    for(int i=0;i<6;++i)
    for(int j=0;j<6;++j)
    for(int k=0;k<6;++k)
        res.a[i][j] = (res.a[i][j] + (ll)lhs.a[i][k]*rhs.a[k][j])%p;
    return res;
}

inline mat operator + (const mat& lhs,const mat& rhs){
    mat res = mat();
    for(int i=0;i<6;++i)
    for(int j=0;j<6;++j)
        res.a[i][j] = (lhs.a[i][j]|rhs.a[i][j])%p;
    return res;
}

inline mat power(mat a,ll t){
    mat res = mat();
    for(int i=0;i<6;++i) res.a[i][i] = 1;
    while(t){
        if(t&1) res = res*a;
        a = a*a;
        t >>= 1;
    }
    return res;
}

ll n;
int k,ans;
int a[5];
mat A,B,C,base;

int main(){
    scanf("%lld%d",&n,&k);
    for(int i=1;i<=4;++i) scanf("%d",&a[i]);
    A.a[0][0] = A.a[0][1] = 1;
    for(int i=1;i<5;++i) A.a[i][i+1] = 1;
    B.a[4][5] = 1;
    for(int i=5;i;--i) B.a[i][i-1] = 1;
    C = A+B; 

    base = mat();
    for(int i=0;i<6;++i) base.a[i][i] = 1;
    for(int i=1;i<=4;++i){
        if(a[i]==1) base = A*base;
        else if(a[i]==2) base = B*base;
        else base = C*base;
    }
    base = power(base,n/4);
    for(int i=0;i<n%4;++i){
        if(a[i+1]==1) base = A*base;
        else if(a[i+1]==2) base = B*base;
        else base = C*base;
    }
    for(int i=0;i<6;++i) ans = (ans+base.a[i][5-k])%p;
    printf("%d",ans);
    return 0;
}

L

中档题。
容易看出光路折射模型，将坐标摊平，二分入射角，维护入射角的 \operatorname{sin} 值，注意特判全反射的情况。

UPD：我们首先处理横坐标变换，改为全部向右走的形式（\Delta x_i=x_i'-x'_{i-1}=|x_i-x_{i-1}|,x_{n+1}=0），这样当前单位长度路径所耗费的代价就仅与当前横坐标位置相关。考虑代价可以转化为类似路程除以速度（速度 v_i 为当前总质量 M_i=\sum_{j=i}^n m_i+M 的倒数）的形式，根据拉格朗日乘数法证明或者利用初中物理知识可以知道，如果我们模拟类似光路折射的入射角偏转并最后到达了某个点，则经过的路径一定是到达该点的最小代价路径。同理可以证明，由于光速不断变快，入射角单调增加，在中途不发生全反射的情况下，最后到达 x=x'_{n+1} 的时候 y 坐标是入射角的单调增函数。因此可以二分入射角，在二分过程中维护当前偏转角 \theta（为了保留精度，维护 \delta=\sin\theta），在第 i 个介质内经过的路程为 S_i=\dfrac{x'_i-x'_{i-1}}{\cos\theta}=\dfrac{\Delta x_i}{\sqrt{1-\delta^2}}，代价为 \dfrac {S_i}{v_i}。光线离开介质 i 时由折射定律，\dfrac{\sin \theta}{\sin\theta'}=\dfrac{v_i}{v_{i+1}}。假设计算出的 \sin{\theta'}>1，说明发生了全反射。若最终 y>y_0 或者中途发生了全反射则说明入射角过大，否则说明入射角过小。

细节比较多。

#include <bits/stdc++.h>
using namespace std;
constexpr int maxn=10009;
using ld=long double;
#define eps 1e-12
ld m[maxn],x[maxn];
ld X[maxn];
ld v[maxn];
int main()
{
    int n;
    ld M,y;

    scanf("%d",&n);
    scanf("%Lf %Lf",&M,&y);
    for(int i=1;i<=n;++i) scanf("%Lf",m+i);
    for(int i=1;i<=n;++i) scanf("%Lf",X+i);
    int fl=1;
    for(int i=1;i<=n;++i){
        if(std::abs(X[i])>eps){
            fl=0;
        }
    }
    if(fl){
        printf("%.9Lf\n",y*M);
        return 0;
    }
    for(int i=1;i<=n;++i)
        x[i]=x[i-1]+std::abs(X[i]-X[i-1]);
    x[n+1]=x[n]+std::abs(X[n]);
    v[++n]=M;
    for(int i=n-1;i;--i)
        v[i]=v[i+1]+m[i];
    ld sum=v[1];
    long double l=0,r=std::acos(-1)/2-eps;
    long double res=-1,mid,ans=-1;
    while(r-l>eps)
    {
        mid=(l+r)/2; res=0;
        long double san=std::sin(mid),cy=0;
        int flag=0;
        for(int i=1;i<n;++i)
        {
            ld R=(x[i]-x[i-1])/std::sqrt(1-san*san);
            res+=R*v[i];
            cy=cy+R*san;
            san*=v[i]/v[i+1];
            if(san>1){
                flag=1;
                break;
            }
        }
        ld R=(x[n]-x[n-1])/std::sqrt(1-san*san);
        res+=R*v[n];
        cy=cy+R*san;
        if(flag || cy>y)
        {
            r=mid;
            if(flag!=1)ans=res;
        }
        else{
            l=mid;
            ans=res;
        }
    }
    printf("%.9Lf\n",ans);
    return 0;
}

M

签到题，按题意模拟即可。需要精细实现，如每轮只访问度数改变的点，当度数恰被减为 k 时，加入队列，每次忽略掉被减到度数小于 k 的点。
考虑证明复杂度，删点操作复杂度为度数之和 O(n)，每个点进入队列的次数 O(1)，总复杂度线性。

#include <bits/stdc++.h>
using namespace std;
struct edge{
    int to;
    int next;
}e[3333333];
int pe=1111111;
int deg[1111111];
void insert(int a,int to){
    e[pe]=(edge){to,e[a].next};
    e[a].next=pe++;
    deg[to]++;
}
std::vector<int> now,tmp;
int vis[1111111];
void dfs(int o){
    vis[o]=1;
    for(int p=e[o].next;p;p=e[p].next){
        if(!vis[e[p].to]){
            dfs(e[p].to);
        }
    }
}
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<n;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        insert(u,v);
        insert(v,u);
    }
    for(int i=1;i<=n;++i){
        if(deg[i]==k){
            now.push_back(i);
        }
    }
    while(1){
        for(int i:now){
            vis[i]=1;
            for(int p=e[i].next;p;p=e[p].next){
                deg[e[p].to]--;
                if(deg[e[p].to]==k){
                    tmp.push_back(e[p].to);
                }
            }
        }
        now.clear();
        for(int i:tmp){
            if(deg[i]==k){
                now.push_back(i);
            }
        }
        tmp.clear();
        if(now.empty())break;
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        if(!vis[i]){
            ++ans;
            dfs(i);
        }
    }
    printf("%d\n",ans);
    return 0;
}

N

中档题，考虑贪心。
自底而上每次把找到的满足至少有 k 种颜色的子树拉出来形成一个连通块然后噶了，最后判断根所在连通块是否符合要求。

考虑证明这个贪心。 假设我们现在有了一个方案，这个方案里面含有一系列的点，表示 dfs 回溯的时候这些点去掉已经选出的子树之后颜色不少于 k 种，并且其所有的子树均不满足条件。
那么考虑如何调整，向上调整则会影响到它上面一个连通块，导致答案不会更优；向下调整则由于其所有的子树均不满足条件，答案不增。

至于怎么维护，随便线段树合并一下就可以过。

#include <bits/stdc++.h>
struct st{
    int cnt;
    st* c[2];
    void MT(){
        cnt=c[0]->cnt+c[1]->cnt;
    }
}t[4444444],*nul=t+4444400,*root[222222],*pt=t+1;
st* insert(st* o,int v,int l,int r){
    ++o->cnt;
    if(l==r){
        return o;
    }
    int mid=l+r>>1;
    if(v<=mid){
        o->c[0]=pt++;
        o->c[0]->c[0]=o->c[0]->c[1]=nul;
        insert(o->c[0],v,l,mid);
    }
    else{
        o->c[1]=pt++;
        o->c[1]->c[0]=o->c[1]->c[1]=nul;
        insert(o->c[1],v,mid+1,r);
    }
    return o;
}
st* merge(st* x,st* y,int l,int r){
    if(x==nul)return y;
    if(y==nul)return x;
    if(l==r){
        x->cnt|=y->cnt;
        return x;
    }
    int mid=l+r>>1;
    x->c[0]=merge(x->c[0],y->c[0],l,mid);
    x->c[1]=merge(x->c[1],y->c[1],mid+1,r);
    x->MT();
    return x;
}
int col[222222];
struct edge{
    int to;
    int next;
}e[666666];
int pe=222222;
void insert(int a,int to){
    e[pe]=(edge){to,e[a].next};
    e[a].next=pe++;
}
int n,k;
int ans=0;
void dfs(int o,int fa){
    for(int p=e[o].next;p;p=e[p].next){
        if(e[p].to!=fa){
            dfs(e[p].to,o);
            root[o]=merge(root[o],root[e[p].to],1,n);
        }
    }
    if(root[o]->cnt>=k){
        ++ans;
        root[o]=pt++;
        root[o]->c[0]=root[o]->c[1]=nul;
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i){
        scanf("%d",col+i);
    }
    for(int i=1;i<n;++i){
        int x,y;
        scanf("%d %d",&x,&y);
        insert(x,y);
        insert(y,x);
    }
    for(int i=1;i<=n;++i){
        root[i]=pt++;
        root[i]->c[0]=root[i]->c[1]=nul;
        root[i]=insert(root[i],col[i],1,n);
    }
    dfs(1,0);
    printf("%d\n",ans);
}

O

对于注意力充沛的选手来说，就是签到题。

注意到 \forall(1\le j \le n,\gcd(i,j)=1),\lfloor\dfrac n {\max\{i,j\}}\rfloor=|\{(x,y)\in([1,n]\cap N^*)^2:\dfrac x y =\dfrac i j\}| ，且对于不同的互质 i,j，这些集合交集为空。因此在所有的这些集合中，每个 [1,n]^2 中的整点将会恰好被枚举一次。

因此答案为 n^2。

或者有

\begin{aligned} Ans&=\sum_{i=1}^n\sum_{1\le j \le n,\gcd(i,j)=1}^n\lfloor\dfrac n {\max\{i,j\}}\rfloor \\ &=n+2\sum_{i=1}^n\sum_{i<j \le n,\gcd(i,j)=1}^n\lfloor\dfrac n j \rfloor \\ &=-n+2\sum_{i=1}^n \lfloor\dfrac n i\rfloor\varphi(i) \\ &=-n+2\sum_{i=1}^n\sum_{j=1}^n\Big(\lfloor\dfrac i j\rfloor-\lfloor\dfrac {i-1} j\rfloor\Big)\varphi(j) \\ &=-n+2\sum_{i=1}^n \sum_{j=1}^n [j \mid i] \varphi(j) \\ &=-n+2\sum_{i=1}^n \sum_{d\mid i} \varphi(d)\\ &=-n+2\cdot\sum_{i=1}^n i\\ &=-n+2\cdot\dfrac{n(n+1)} 2 =n^2 \end{aligned}