洛谷比赛 「EZEC」 Round 4
T1 zrmpaul Loves Array
题目描述
小 Z 有一个下标从 \(1\) 开始并且长度为 \(n\) 的序列，初始时下标为 \(i\) 位置的数字为 \(i\)。有 \(m\) 个操作，每个操作会是以下四种之一。
1 对序列从小到大进行排序。
2 对序列从小到大进行排序后将其翻转，(译者注：就是从大到小排序）。
3 x y 将下标为 \(x,y\) 的数交换位置。保证 \(x\neq y\) 且 \(1\le x,y\le n\)。
4 将序列翻转。
你要输出在 \(m\) 次操作后的序列。
输入格式
第一行两个整数 \(n,m\) ，表示序列的长度以及操作的数量。
接下来 \(m\) 行，每行一个操作。保证操作合法。
输出格式
一行包含 \(n\) 个整数，表示操作后的序列。
输入输出样例
输入 #1
5 5
1
2
3 2 4
4
3 1 5
输出 #1
5 4 3 2 1
说明/提示
【数据范围】
【本题采用捆绑测试】
subtask 1（24pts）: \(1\leq n,m\leq 2 \times 10^3\) 。
subtask 2（13pts）: 没有操作三。
subtask 3（63pts）: \(1\leq n,m\leq 10^6\) 。
【样例解释】
序列经过的操作为：
1,2,3,4,5
1,2,3,4,5
5,4,3,2,1
5,2,3,4,1
1,4,3,2,5
5,4,3,2,1
签到题还是有点思维难度的，但也比至于那么难，不过需要注意的点比较多。
自己在一个点上卡了一个小时（太菜了，该退役了）。
现讲一下思路吧。观察一下这四个操作，你就会发现一个神奇的规律。
在排序操作之前的操作是对答案没有任何影响的。
所以，我们只需要找到最后的一个操作\(1\) 或者操作 \(2\) ，如果最后一次是操作 \(1\) 原序列就正着排，反之倒着排序。
之后，我们就可以模拟操作三和操作四了。
操作三直接暴力 \(swap\) ，操作四的话可以打个标记，奇数的把这个序列暴力翻转。
一个比较坑的点就是一开始要把原序列赋为从 \(1-n\) 的排列,(因为他可能只有操作 \(4\))
随机数据的话还是跑的比较快的。
具体实现看代码把：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,type,maxn,res,cnt,a[1000010];
struct node
{
int opt,x,y;
}q[1000010];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s =s * 10+ch - '0'; ch = getchar();}
return s * w;
}
int main()
{
n = read(); m = read();
for(int i = 1; i <= n; i++) a[i] = i;//一开始序列为1-n 的排列
for(int i = 1; i <= m; i++)
{
q[i].opt = read();
if(q[i].opt == 3)
{
cnt++;
q[i].x = read(); q[i].y = read();
}
if(q[i].opt == 1 || q[i].opt == 2)//找最后一次排序操作
{
type = q[i].opt; maxn = i;
}
}
if(type == 1)//如果是 1 就升序排列
{
for(int i = 1; i <= n; i++) a[i] = i;
}
if(type == 2)//反之降序排列
{
for(int i = n; i >= 1; i--) a[i] = n-i+1;
}
for(int i = maxn+1; i <= m; i++)
{
if(q[i].opt == 3)
{
if(res & 1)//如果前面序列反转了偶数次，就对序列暴力翻转
{
for(int j = 1; j <= n/2; j++) swap(a[j],a[n-j+1]);
}
swap(a[q[i].x],a[q[i].y]);//暴力交换
res = 0;
}
else if(q[i].opt == 4) res += 1;//统计有多少个操作 4
}
if(res & 1) for(int i = 1; i <= n/2; i++) swap(a[i],a[n-i+1]);
for(int i = 1; i <= n; i++) printf("%d ",a[i]);
return 0;
}
T2「EZEC-4」可乐
题目背景
很久以前，有一个 pigstd，非常迷恋美味的可乐。为了得到美味的可乐，他几乎用尽了所有的钱，他甚至对自己的 npy 也漠不关心其实是因为他没有npy，更不爱好看戏。除非买了新可乐，才会坐上马车出门炫耀一番。每一天，每个钟头他都要喝上一瓶新可乐。
pigstd 最近又买了许多箱新可乐——当然，这些可乐只有聪明的人才能喝到。
题目描述
pigstd 现在有 \(n\) 箱可乐，第 \(i\) 箱可乐上标着一个正整数 \(a_{i}\)。
若 pigstd 的聪明值为一个非负整数 \(x\)，对于第 \(i\) 箱可乐，如果 \((a_{i} \oplus x )\le k\) 那么 pigstd 就能喝到这箱可乐。
现在 pigstd 告诉了你 \(k\) 与序列 \(a\)，你可以决定 pigstd 的聪明值 \(x\)，使得他能喝到的可乐的箱数最大。求出这个最大值。
输入格式
第一行两个由空格分隔开的整数 \(n,k\)。
接下来 \(n\) 行，每行一个整数 \(a_i\)，表示第 \(i\) 箱可乐上标的数。
输出格式
一行一个正整数，表示 pigstd 最多能喝到的可乐的箱数。
输入输出样例
输入 #1
3 5
2
3
4
输出 #1
3
输入 #2
4 625
879
480
671
853
输出 #2
4
说明/提示
提示
pigstd 的聪明值 \(x\) 可以为 \(0\)。
样例解释
样例 1 解释：容易构造当 \(x=0\) 时，可以喝到所有可乐。
样例 2 解释：容易构造 \(x=913\)，可以喝到所有可乐。
样例解释未必是唯一的方法。
数据范围
本题采用捆绑测试。
Subtask 1（29 points）：\(1 \le n,k,a_{i} \le 1000\)。
Subtask 2（1 point）：\(a_{i} \le k\)。
Subtask 3（70 points）：无特殊限制。
对于所有数据，保证 \(1 \le n,k,a_{i} \le 10^6\)。
一开始看错题了，连交了几发全是 WA，差点把我心态搞崩了。
这道题我和 STd 的解法不太一样。
这道题看到异或，我们会想到什么。 没错，就是 \(01tire\)
我们可以对每个 \(a_i\) 都插入 \(tire\) 树中，然后暴力枚举 \(x\) ，
找在异或起来不小于 \(k\) 的情况下，能喝到的可乐最多。
主要是分情况讨论比较难写，但其他的还算可以。
Code:
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,k,tot = 1,siz[20000100],x,tr[20000100][2];
int ans,kk,maxn;
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s =s * 10+ch - '0'; ch = getchar();}
return s * w;
}
void insert(int x)//建 tire 树
{
int p = 1;
for(int i = 20; ~i; i--)
{
int c = (x>>i)&1;
if(!tr[p][c]) tr[p][c] = ++tot;
p = tr[p][c];
siz[p]++;
}
}
int query(int x)
{
int p = 1, res = 0;
for(int i = 20; i; i--)
{
int a = (k>>i)&1, b = (x>>i)&1;
if(a == 0)//如果说 k的这一位为0，那么tire树上的节点只能和 b 相同
{
if(b == 1) p = tr[p][1];
if(b == 0) p = tr[p][0];
}
if(a == 1)
{
if(b == 0)
{
res += siz[tr[p][0]];//节点为 0 的话，异或起来小于 1可以直接记录答案
p = tr[p][1];
}
else
{
res += siz[tr[p][1]];//同理
p = tr[p][0];
}
}
}
int a =k & 1, b =x & 1;//最后一位的情况
if(a == 0)
{
if(b == 1) p = tr[p][1];
if(b == 0) p = tr[p][0];
}
if(a == 1)
{
if(b == 0)
{
res += siz[tr[p][0]];
p = tr[p][1];
}
else
{
res += siz[tr[p][1]];
p = tr[p][0];
}
}
return res;
}
int main()
{
n = read(); k = read(); maxn = k;
for(int i = 1; i <= n; i++)
{
x = read();
maxn = max(maxn,x);//上限设为 a[i] 和 k 的最大值
insert(x);
}
for(int i = 0; i <= maxn<<1; i++)
{
ans=max(ans,query(i));//暴力枚举 x
}
printf("%d\n",ans);
}
后面的几道题就比较仙了。
T3 Excalibur
题目描述
已知有 \(n\) 个血量均为 \(k\) 的敌人，编号\(1\sim n\).
给你一柄圣剑，选择一个敌人，砍向他并对其造成 \(p\) 点伤害。
这柄圣剑还附有 \(m\) 条属性，第 \(i\) 条属性可表示为：
1、若 \(x_i\) 号敌人受到了伤害，记此伤害为 \(r_{x_i}\) 那么 \(y_i\) 号敌人就会相应受到 \(q\times r_{x_i}\)点伤害。
2、若 \(y_i\) 号敌人受到了伤害，记此伤害为\(r_{y_i}\)，那么 \(x_i\) 号敌人就会相应受到 \(q\times r_{y_i}\) 点伤害。
3、上述两点若有任意一点被触发，该属性立即失效。
现规定，当某个敌人血量 \(\le 0\) 时，即视为你击杀了这个敌人。击杀与否不影响伤害大小。
求你最多能击杀几个敌人。
数据保证：
1、每条属性中 \(x_i\neq y_i\)。
2、所有属性本质上不重复。
3 砍向任一敌人后，每个敌人最多受到一次伤害。
输入格式
第一行五个整数 \(n,m,k,p\),。
后 \(m\) 行每行两个整数 \(x,y\)。
输出格式
一行一个整数表示答案。
输入输出样例
输入 #1
3 2 2 3 1
1 2
2 3
输出 #1
3
输入 #2
3 2 2 1 1
1 2
2 3
输出 #2
0
输入 #3
3 2 4 1 2
1 2
2 3
输出 #3
1
说明/提示
【样例 1 说明】
砍向 1 号敌人，对其造成 3 点伤害；22号敌人随之受到 3 点伤害；3 号敌人随之受到 3 点伤害。共击杀 3 个敌人。
【样例 2 说明】
无法击杀任何敌人。
【样例 3 说明】
砍向 1 号敌人，对其造成 1 点伤害；2 号敌人随之受到 2 点伤害；3 号敌人随之受到 4 点伤害。共击杀 1个敌人。
【数据规模与约定】
对于 100% 的数据，\(1\le n\le 10^5\)，\(0\le m\le 10^5\)，\(1\le k,p,q\le 10^9\)，\(1\le x,y\le n\)。
本题采用捆绑测试。
| 子任务 | 分值 | n | q | 特殊性质 |
|---|---|---|---|---|
| 1 | 10 | \(≤10\) | 无 | 无 |
| 2 | 5 | 无 | =1 | 无 |
| 3 | 5 | 无 | 无 | 对于每条属性都有 \(xi=yi−1\) |
| 4 | 20 | 无 | 无 | 保证数据随机生成 |
| 5 | 60 | 无 | 无 | 无 |
这道题我开始以为是道图论题。
但，当我得知正解是树形 \(dp\) 时，我的表情是这样的：
算了，贴正解吧：
简化问题
给你若干棵树，选一颗树上的一个点作为根，根节点深度为 1，问树上有多少节点深度 \(h\)
\[h \leq
\begin{cases}
log_q{k \over p} + 1& \text{q > 1}\\
\infin & \text{q = 1, p <k}\\
1 & \text{q = 1, $p\le k$}
\end{cases}
\]
观察数据范围，注意到 \(q>1\) 时 \(\log_q(\frac{k}{p})<30\)，故可以从这个切入点解决问题。
考虑 \(\text{DP}\)。
令 \(sz[i][j]\) 为以节点 \(i\) 为根，深度等于 \(j\) 的节点数。
令 \(f[i][j]\) 为以节点 \(i\) 为根，深度小于等于 \(j\) 的节点数。（最后求答案时用个容斥即可）
易求得 \(sz\) 数组的递推式为 \(sz[u][j]= \displaystyle \sum sz[v][j−1]\)，其中 \(u\) 和 \(v\) 为父子关系，下同。
当由父节点为根转为由子节点为根时，粗略观察到 \(f[v][j]\) 和 \(f[u][j−1]\) 很相似，进一步观察可得 \(f[v][j]=f[u][j−1]+sz[v][j]+sz[v][j−1]\)。
在每棵树中任选一个节点为根，先求出这个节点的 \(sz\) 和 $ f$ 数组后，再换根 \(\text{DP}\) 即可。
别忘了特判 \(q=1\) 的情况哦！
时间复杂度为 \(O(n\log_q(\frac{k}{p}))\)。
Code(正解代码):
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,k,p,q,x,y,l,max_,vis[100009],trsz[100009],sz[100009][39],f[100009][39];
vector <ll> root,to[100009];
inline ll read(){
ll s = 0,w = 1;
char ch = getchar();
while (ch < '0'|| ch > '9'){ if (ch == '-') w = -1; ch = getchar();}
while (ch >= '0'&& ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
return s * w;
}
void dfs1(ll u,ll fa,ll pos){
trsz[pos] += 1,sz[u][1] = vis[u] = 1;
for (ll i = 0;i < to[u].size();i += 1){
ll v = to[u][i];
if (v ^ fa){
dfs1(v,u,pos);
for (ll j = 2;j <= l;j += 1) sz[u][j] += sz[v][j - 1];
}
}
}
void dfs2(ll u,ll fa,ll pos){
for (ll i = 0;i < to[u].size();i += 1){
ll v = to[u][i];
if (v ^ fa){
f[v][1] = 1;
for (ll j = 2;j <= l;j += 1) f[v][j] = f[u][j - 1] + sz[v][j] + sz[v][j - 1];
max_ = max(max_,trsz[pos] - f[v][l]);
dfs2(v,u,pos);
}
}
}
int main(){
n = read(),m = read(),k = read(),p = read(),q = read();
for (ll i = 0;i < m;i += 1) x = read(),y = read(),to[x].push_back(y),to[y].push_back(x);
if (q == 1 && p < k){cout<<0; return 0;}
while (p * pow(q,l) < k) l += 1;
for (ll i = 1;i <= n;i += 1) if (!vis[i]) root.push_back(i),dfs1(i,0,i);
for (ll i = 0;i < root.size();i += 1) for (ll j = 1;j <= l;j += 1)
f[root[i]][j] = f[root[i]][j - 1] + sz[root[i]][j];
for (ll i = 0;i < root.size();i += 1) max_ = max(max_,trsz[root[i]] - f[root[i]][l]);
for (ll i = 0;i < root.size();i += 1) dfs2(root[i],0,root[i]);
cout<<max_;
return 0;
}
T4「EZEC-4」求和
一句话题意:
T组询问，每次询问输出
$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{n} gcd(i,j)^{i+j} \bmod p $ 的结果。
看完题直接弃疗了，打了 \(10pts\) 就滚粗了
直接甩个 \(std\) 的链接吧 link
这么复杂的柿子谁推的出来啊。
T5 「EZEC-4」月下轻花舞
std
一句话题意： \(T\) 组询问，每次给定三个整数 \(l,r,n\)，求出下式的值：
\(\displaystyle \sum_{i=l}^{r} (i-1) \times \sum_{j=1}^{n} ceil(log_i^{j}) \bmod 998244353\)
看到这个柿子，我直接大呼毒瘤。
这考的时候，一点思路都没有。并且考到的还是一些自己没学过的东西（比如什么拉格朗日差值）。果然还是自己太菜了。
T6 括号
不会写，没看。
好像正解是分块（毒瘤lxl逃）
总结
这次打的还是很不错的，切了两道题。
总分 100 + 100 + 0 + 10 + 0 + 0 = 210;
混了个你谷 Rnk 17 。以后还要继续努力呀。
