XJOI 模拟赛题解

发表于 |
字数统计: 2.2k | 阅读时长 ≈ 11

菜鸡 Karry5307 只会做 T1~T4 呢，还是太菜了，做不出国集水平的题目呢。

T1

大胆猜想答案为 $n(n+1)-1$。

对于 $n$ 为奇数我们可以按照如下方法构造：

也就是从 $(1,1)$ 出发走到 $(1,n+1)$，然后每一次往下走一步之后反复横跳即可。

但是如果 $n$ 为偶数呢？

可以这么构造：

也就是先从 $(n,1)$ 走到 $(1,1)$，每一次往右走之后反复横跳即可。

容易证明不存在比这种解法更优的解了。

T2

注意到我们对于每个点只需要拿他与离它最远的点贡献一次就好了，别的决策都是没有用的。

所以说考虑把树的一个直径抠出来，那么离某个点最远的点一定是直径的端点（证明可以用反证法）。

T3

有一个很暴力的状压 $\texttt{dp}$，考虑枚举一下集合 $S$ 转移即可。

发现 $S$ 是个区间，状态数变成 $O(n^2)$，枚举一下进行的操作和操作完的位置即可 $O(n^4)$，使用前缀和优化可以达到 $O(n^3)$。

考虑对操作做一个完全背包，然后钦定操作完之后 $S$ 必须位于不同的区间。

这样状态数变成 $O(n)$，也即覆盖了一个前缀或是一个后缀或是一整段。

于是就可以 $O(n^2)$ 解决。

T4

首先，如果 $m$ 是奇数的话先手取 $1$ 就可以赢了。

否则双方每次只能取偶数。（如果某一方取了奇数的话剩下的行动值是奇数那么另一方就可以取 $1$）

所以我们可以把总行动值与每次操作取得除掉一个 $2$，于是就有

明显 $h_x=\operatorname{lowbit}(x)$，所以答案就是

这个可以用整除分块做，复杂度是 $O(\sqrt{n}\log n)$，可以拿到 $69\sim 100$ 分，但是这不是正解。

考虑枚举 $h_i$ 的取值并统一计算贡献，方便起见我们设 $g(n)=\sum\limits_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor$，那么答案为

时间复杂度为 $O(\sqrt{n})$。

计算单个 $g(n)$ 可以用整除分块做，尽管是 $O(\sqrt{n})$ 的，但是常数比较大，可能拿不到满分。

可以这么做：

暴力枚举即可，常数比整除分块小，可以通过。

T5

不会，留坑。

代码

$\texttt{T1}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
ll n;
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
} 
inline void calcOdd()
{
	for(register int i=1;i<=n+1;i++)
	{
		printf("1 %d\n",i);
	}
	for(register int i=2;i<=n;i+=2)
	{
		for(register int j=n+1,k=i;j>=1;j--,k^=1)
		{
			printf("%d %d\n",k,j);
		}
		for(register int j=1,k=i;j<=n+1;j++,k^=1)
		{
			printf("%d %d\n",k,j);
		}
	}
}
inline void calcEven()
{
	for(register int i=n;i>=1;i--)
	{
		printf("%d 1\n",i);
	}
	for(register int i=2;i<=(n+1);i+=2)
	{
		for(register int j=1,k=i;j<=n;j++,k^=1)
		{
			printf("%d %d\n",j,k);
		}
		for(register int j=n,k=i;j>=1;j--,k^=1)
		{
			printf("%d %d\n",j,k);
		}
	}
}
int main()
{
	n=read();
	printf("%d\n",n*(n+1)-1);
	n&1?calcOdd():calcEven();
}

$\texttt{T2}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=2e5+51;
struct Edge{
	ll to,prev;
};
Edge ed[MAXN<<1];
ll nc,tot,res,from,to,u,v;
ll last[MAXN],x[MAXN],vis[MAXN],dist[MAXN],dist2[MAXN];
queue<ll>q;
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
} 
inline void addEdge(ll from,ll to)
{
	ed[++tot].prev=last[from];
	ed[tot].to=to;
	last[from]=tot;
}
inline ll bfs(ll x)
{
	ll top;
	memset(vis,0,sizeof(vis));
	q.push(x),vis[x]=1;
	while(!q.empty())
	{
		top=q.front(),q.pop();
		for(register int i=last[top];i;i=ed[i].prev)
		{
			if(!vis[ed[i].to])
			{
				vis[ed[i].to]=1,q.push(ed[i].to);
			}
		}
	}
	return top;
}
inline void dfs(ll node,ll fa,ll *dist)
{
	dist[node]=dist[fa]+1;
	for(register int i=last[node];i;i=ed[i].prev)
	{
		if(ed[i].to!=fa)
		{
			dfs(ed[i].to,node,dist);
		}
	}
}
int main()
{
	nc=read();
	for(register int i=1;i<=nc;i++)
	{
		x[i]=read();
	}
	for(register int i=0;i<nc-1;i++)
	{
		from=read(),to=read();
		addEdge(from,to),addEdge(to,from);
	}
	u=bfs(1),v=bfs(u),dist[0]=dist2[0]=-1,dfs(u,0,dist),dfs(v,0,dist2);
	for(register int i=1;i<=nc;i++)
	{
		if(dist[i]>dist2[i])
		{
			res=max(res,dist[i]*max(x[u],x[i]));
		}
		if(dist2[i]>dist[i])
		{
			res=max(res,dist2[i]*max(x[v],x[i]));
		}
		if(dist[i]==dist2[i])
		{
			res=max(res,dist[i]*max(max(x[u],x[i]),max(x[v],x[i])));
		}
	}
	printf("%d\n",res);
}

$\texttt{T3}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll MAXN=2e3+51,inf=1e18;
ll test,n,m,v,g;
ll x[MAXN],prv[MAXN],nxt[MAXN],sum[MAXN],dp[MAXN][2],f[MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline ll calc(ll l,ll r)
{
    if(r<=x[1])
    {
        return 0;
    }
    ll lx=nxt[l],rx=prv[r],res;
    if(lx>rx)
    {
        return inf;
    }
    return sum[rx]-sum[lx]+dp[l][1]+dp[r][0];
}
inline ll calc2(ll l,ll r)
{
    if(r<=x[1])
    {
        return 0;
    }
    ll res=inf;
    for(register int i=1;i<l;i++)
    {
        res=min(res,calc(l-i,r-i)+f[i]*(r-l+1));
    }
    return res;
}
inline void solve()
{
    n=read(),m=read();
    memset(x,0,sizeof(x)),memset(prv,0,sizeof(prv));
    memset(nxt,0,sizeof(nxt)),memset(dp,0,sizeof(dp));
    memset(f,0,sizeof(f)),memset(sum,0,sizeof(sum));
    for(register int i=1;i<=n;i++)
    {
        x[i]=read();
    }
    for(register int i=1;i<=n;i++)
    {
        for(register int j=x[i-1]+1;j<=x[i];j++)
        {
            prv[j]=i-1,nxt[j]=i;
        }
    }
    for(register int i=1;i<=x[n];i++)
    {
        f[i]=inf;
    }
    for(register int i=1;i<=m;i++)
    {
        v=read(),g=read();
        for(register int j=g;j<=x[n];j++)
        {
            f[j]=min(f[j],f[j-g]+v);
        }
    }
    for(register int i=1;i<=n;i++)
    {
        for(register int j=x[i-1]+1;j<=x[i];j++)
        {
            dp[j][0]=calc2(x[i-1]+1,j);
        }
        for(register int j=x[i-1]+1;j<=x[i];j++)
        {
            dp[j][1]=calc2(j,x[i]);
        }
        sum[i]=sum[i-1]+dp[x[i]][0];
    }
    printf("%lld\n",sum[n]>=inf?-1:sum[n]);
}
int main()
{
    test=read();
    for(register int i=0;i<test;i++)
    {
        solve();
    }
}

$\texttt{T4} O(\sqrt n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
typedef long long int ll;
const ll MOD=998244353;
ll n,res,sqrtn;
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
} 
inline ll calc(ll l,ll r)
{
	ll res=r-l,p=1;
	while(r)
	{
		r>>=1,l>>=1,res+=p*(r-l);
		p<<=1;
	}
	return res;
}
int main()
{
	n=read(),sqrtn=sqrt(n);
	for(register int i=1;i<=sqrtn;i++)
	{
		res=(res+(n/i)*(i&-i)%MOD);
	}
	res%=MOD;
	for(register ll l=sqrtn+1,r;l<=n;l=r+1)
	{
		r=n/(n/l);
		res=(res+(n/l)*calc(l-1,r)%MOD)%MOD;
	}
	printf("%lld\n",res);
}

$\texttt{T4} O(\sqrt{n})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
typedef long long int ll;
const ll MOD=998244353;
ll n,res,cur;
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline ll calc(ll n)
{
    ll res=0,sqrtn=sqrt(n),cur=1;
    for(register int i=1;i+3<=sqrtn;i+=4)
    {
        res+=n/i,res+=n/(i+1),res+=n/(i+2),res+=n/(i+3),cur=i+4;
    }
    while(cur<=sqrtn)
    {
        res+=n/(cur++);
    }
    return (2*res-sqrtn*sqrtn)%MOD;
}
int main()
{
    n=read();
    res=calc(n),cur=1;
    for(register int i=1;i<=60;i++)
    {
        n>>=1;
        if(!n)
        {
            break;
        }
        res=(res+cur*calc(n)%MOD)%MOD,cur=(cur+cur)%MOD;
    }
    printf("%lld\n",res);
}