啊我去我 AK 了！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
A 清明时节雨纷纷
题目大意：输出 Lu-shang-xing-ren-yu-duan-hun。
这……这对吗？
:::success[code]
1
2
3
4
5
6
|
#include<bits/stdc++.h>
using namespace std;
int main(){
puts("Lu-shang-xing-ren-yu-duan-hun");
return 0;
}
|
:::
B 蜗蜗号码牌
:::info[题目大意]
给定一个长度为 $n$ 的正整数序列 $a$，问至少修改多少个数才可以使 $a$ 成为一个 $1 \sim n$ 的序列。
$1 \leq n \leq 5000$。
:::
开个桶，然后统计有多少个需要修改的地方。
:::success[code]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include<bits/stdc++.h>
using namespace std;
int to[5005];
void solve(){
int n;
memset(to,0,sizeof(to));
scanf("%d",&n);
for(int i=1;i<=n;i++){
int t;
scanf("%d",&t);
to[t]=1;
}
int ans=n;
for(int i=1;i<=n;i++)ans-=to[i];
printf("%d\n",ans);
}
int main(){
int T;
scanf("%d",&T);
while(T--){
solve();
}
return 0;
}
|
:::
C 守护蜗研所
:::info[题目大意]
给定一个长为 $n$ 的序列 $a$，进行 $q$ 次区间异或，求最终结果。
$n \leq 2 \times 10^5,q \leq 2 \times 10^5$。
:::
差分就可以。
:::success[code]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include<bits/stdc++.h>
using namespace std;
long long dif[200005];
int t[200005];
int n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&t[i]);
dif[i]=t[i]^t[i-1];
}
for(int i=1;i<=m;i++){
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
dif[l]^=k;
dif[r+1]^=k;
}
int p=0;
for(int i=1;i<=n;i++){
p^=dif[i];
printf("%d ",p);
}
return 0;
}
|
:::
D 序列异或
:::info[题目大意]
给定一个长为 $n$ 的序列 $a$。$q$ 次询问，每次询问给出 $L_1,R_1,L_2,R_2,k$，求满足 $L_1 \leq i \leq R_1,L_2 \leq j \leq R_2$ 且 $a_i \oplus a_j$ 的第 $k$ 位为 $1$ 的有序数对个数。
$2 \leq n \leq 10^5,1 \leq q \leq 5 \times 10^5,0 \leq a_i < 2^{60},0 \leq k < 60,1 \leq L_1 \leq R_1 < L_2 \leq R_2 \leq n$。
:::
由于两个询问区间互不重叠，因此可以直接上乘法原理：
区间一中第 $k$ 位是 $1$ 的个数 $\times$ 区间二中第 $k$ 位是 $0$ 的个数 + 区间一中第 $k$ 位是 $0$ 的个数 $\times$ 区间二中第 $k$ 位是 $1$ 的个数
然后一个前缀和解决。
:::success[code]
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
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int pre1[100005][62];
int pre2[100005][62];
void solve(){
memset(pre1,0,sizeof(pre1));
memset(pre2,0,sizeof(pre2));
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
ll ai;
scanf("%lld",&ai);
for(int j=0;j<60;j++){
pre1[i][j]=pre1[i-1][j]+((ai>>j)&1);
pre2[i][j]=pre2[i-1][j]+(((ai>>j)&1)^1);
}
}
for(int i=1;i<=q;i++){
int k,l1,r1,l2,r2;
ll ans=0;
scanf("%d%d%d%d%d",&k,&l1,&r1,&l2,&r2);
ans=(pre1[r1][k]-pre1[l1-1][k])*(pre2[r2][k]-pre2[l2-1][k])+(pre2[r1][k]-pre2[l1-1][k])*(pre1[r2][k]-pre1[l2-1][k]);
printf("%lld\n",ans);
}
}
int main(){
int T;
scanf("%d",&T);
while(T--)solve();
return 0;
}
|
:::
E 蜗蜗史莱姆幻想
:::info[题目大意]
给定一个长度为 $n$ 的序列 $a$，对于每一个位置 $i$，找到最靠右的位置 $j(j \leq i)$ 满足
$$(\sum_{k=j}^i a_k) > (\max_{k=1}^{j-1} a_k)$$输出 $j-i$。
$1 \leq n \leq 2 \times 10^5,1 \leq a_i \leq 10^9$。
:::
首先一个数从右边到左边一定变优，因此答案具有明显的单调性。考虑二分。
然后维护一个前缀和和一个前缀最小值就可以了。
:::success[code]
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
|
#include<bits/stdc++.h>
using namespace std;
long long pmax[200005],pre[200005],a[200005];
int n;
bool chk(int tarid,int id){
return (pre[id]-pre[tarid-1])>pmax[tarid-1];
}
long long bs(int id){
int lft=1,rgt=id,mid,ans=0;
while(lft<=rgt){
mid=(lft+rgt)>>1;
if(chk(mid,id))lft=mid+1,ans=mid;
else rgt=mid-1;
}
return ans;
}
void solve(){
pre[0]=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",a+i);
for(int i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];
for(int i=1;i<=n;i++)pmax[i]=max(pmax[i-1],a[i]);
for(int i=1;i<=n;i++){
printf("%lld ",i-bs(i));
}
puts("");
}
int main(){
int T;
scanf("%d",&T);
while(T--)solve();
return 0;
}
|
:::
F 魔法钱包
:::info[题目大意]
给定一个长为 $n$ 的序列 $a$。
初始时你有一个数 $x$。对于每一个 $1 \leq i \leq n$，
- 你可以重新排列 $x$ 中的每一个数位使其变为一个新的十进制数 $x’$。自动忽略前导零。
- 随后你 可以 选择让 $x$ 减去 $a_i$，并且计数器加一。
求最终计数器最大是多少。
$1 \leq n \leq 100,1 \leq x,a_i \leq 10000$。
:::
记忆化搜索。
考虑 $dp_i,j$ 表示考虑到 $i$，且此时 $x$ 的一种表示方式是 $j$。
随后枚举每一个 $j$ 可能的表示，并转移选或不选。
复杂度？额……大概是 $O(5! \times n \times x)$……剪枝可以更低但是没剪过了就不理他了。
:::success[code]
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
|
#include<bits/stdc++.h>
using namespace std;
int dp[105][100005];
int a[105];
int n;
int ton(string s){
int ans=0;
for(int i=s.length()-1;i>=0;i--){
ans*=10 ;
ans+=s[i]-'0';
}
return ans;
}
int dfs(int x,int y){
if(x==n+1)return 0;
if(dp[x][y]!=-1)return dp[x][y];
string t=to_string(y);
sort(t.begin(),t.end());
int ans=0;
do{
if(ton(t)>=a[x])ans=max(ans,dfs(x+1,ton(t)-a[x])+1);
ans=max(ans,dfs(x+1,ton(t)));
}while(next_permutation(t.begin(),t.end()));
return dp[x][y]=ans;
}
int main(){
memset(dp,0xff,sizeof(dp));
int x;
scanf("%d%d",&n,&x);
for(int i=1;i<=n;i++)scanf("%d",a+i);
printf("%d",dfs(0,x)-1);
return 0;
}
|
:::
G 蜗蜗能量
:::info[题目大意]
给定 $n$ 个 $26$ 进制数，试给出一个一一映射满足对每个数字的每一位执行映射后满足所有数字的总和最大。
$1 \leq n \leq 2 \times 10^5,1 \leq \sum |S| \leq 2 \times 10^5$。
:::
枚举每个数位在每个位置上的出现次数并进位，然后你就会发现你维护了一个高精。直接排序即可。
:::success[code]
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
|
#include<bits/stdc++.h>
using namespace std;
constexpr int mod=1000000007;
int wes[30][200005];
string s[200005];
bool e[30];
int ys[30];
int n,maxlen;
bool cmp(int x,int y){
for(int i=maxlen-1;i>=0;i--){
if(wes[x][i]!=wes[y][i])return wes[x][i]>wes[y][i];
}
return x>y;
}
void solve(){
memset(e,0,sizeof(e));
memset(wes,0,sizeof(wes));
maxlen=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i];
if(s[i].length()!=1)e[s[i][0]-'a']=true;
maxlen=max(maxlen,(int)s[i].length());
for(int j=0;j<s[i].length();j++)wes[s[i][j]-'a'][s[i].length()-1-j]++;
}
for(int i=0;i<26;i++){
for(int j=0;j<maxlen;j++){
if(wes[i][j]>=26){
wes[i][j+1]+=wes[i][j]/26;
wes[i][j]%=26;
}
}
}
maxlen++;
vector<int>t;
for(int i=0;i<26;i++)t.push_back(i);
sort(t.begin(),t.end(),cmp);
if(e[t[25]]){
for(int i=24;i>=0;i--){
if(!e[t[i]]){
int p=t[i];
t.erase(t.begin()+i);
t.insert(t.end(),p);
break;
}
}
}
for(int i=0;i<26;i++)ys[t[i]]=25-i;
long long ans=0;
for(int i=1;i<=n;i++){
long long k=1;
for(int j=s[i].length()-1;j>=0;j--){
ans+=k*ys[s[i][j]-'a'];
ans%=mod;
k*=26;
k%=mod;
}
}
cout<<ans<<'\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--)solve();
return 0;
}
|
:::
H 蜗蜗的异或游戏
:::info[题目大意]
给定一个长度为 $n$ 的序列 $a$，$q$ 次询问，每次询问给出 $l,r$，求满足 $l \leq i < j \leq r$ 的 $i \oplus j$ 的最小值。
$1 \leq n,q \leq 2 \tiems 10^5,0 \leq a_i \leq 10^9$。
部分分：$n,q \leq 2 \times 10^5,0 \leq a_i \leq 255$。
:::
部分分启发正解。本场唯一有点难度的题。但是我做过。所以放一下之前看的题解的复述版。
看到 $255=2^8-1$，立刻想到了建 Trie。
但是有亿个啸问题。例如不能很快确认哪个分支能走。
::::info[引理 1]
给定一个数 $a_i$，当前处在深度 $j$，若存在不同于即将前往的分支的分支，则取 $(i,$ 另一个分支的最大编号 $)$ 作为一对候选点。可以证明最终答案一定在这些候选点中产生。
:::success[证明]
反证法。
假设 $(i,j)$ 是区间 $[L,R]$ 内唯一的最小异或对，且 $(i, j) \notin S$。
设 $a_i$ 和 $a_j$ 的二进制表示中，从高到低第一个不同的位是第 $k$ 位。这意味着 $a_i$ 和 $a_j$ 在高于 $k$ 的所有位上都相同。
当考虑到下标 $j$ 并在 Trie 中遍历 $a_j$ 的路径时：
在高于 $k$ 的位沿路径向下走。因为 $a_i$ 的下标 $i < j$，在处理 $j$ 之前 $a_i$ 已经插入 Trie 了，所以高于 $k$ 位的路径一定存在。
到达第 $k$ 位时，由于 $a_j$ 的第 $k$ 位是 $b$（$0$ 或 $1$），而 $a_i$ 的第 $k$ 位是 $b \oplus 1$。 此时检查相反分支 trie[p].ch[b^1]。由于 $a_i$ 在这个分支里，该分支必然存在。
则取出该分支中下标最大的元素 $i’$。根据 maxi 的定义，必有 $i \le i’ < j$。
然后分讨。
$i’=i$：$(i,j)$ 会被加入 $S$。这与假设 $(i,j) \notin S$ 矛盾。
$i<i’<j$：
$a_{i’}$ 在第 $k$ 位之前与 $a_j$ 相同，且在第 $k$ 位与 $a_j$ 不同，但与 $a_i$ 相同。
此时由于 $a_i$ 和 $a_{i’}$ 在高于或等于 $k$ 的位上都相同，它们的异或结果在高 $k$ 位全为 $0$。则有 $a_i \oplus a_{i’} < 2^k$。
再考虑 $a_i \oplus a_j$： 它们在第 $k$ 位不同，且更高位相同。因此，$a_i \oplus a_j \ge 2^k$。
由此得出：$a_i \oplus a_{i’} < a_i \oplus a_j$。与假设矛盾。
因此，原结论成立。
:::
::::
然后现在我们有了若干点对 $(L_i,R_i)$。不妨改成三元组 $(L_i,R_i,a_{L_i} \oplus a_{R_i})$。
我们要找的是 $l \leq L_i < R_i \leq r$ 的第三个元素最小值。
将每个询问按 $r$ 从小到大排序。然后维护一个树状数组以方便单点改后缀最小值。由于 $r$ 现在单调，可以放心操作。
::::info[提示]
如果你还没有看出来这是什么的话，我要质疑你到底有没有学完 Y4 了。
:::info[算法]
这就是一个二维偏序的变种。两个约束条件：$l \leq L_i,r \geq R_i$。
:::
::::
:::success[code]
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
|
#include<bits/stdc++.h>
#define lb(x) (x&-x)
using namespace std;
constexpr int MAXN=200005;
constexpr int MAXM=MAXN<<5;
constexpr int inf=0x4f4f4f4f;
typedef pair<int,int> pii;
struct nd{
int ch[2];
int maxi;
}trie[MAXM];
int cnt=1;
int a[MAXN],tree[MAXN];
int n,q;
void insert(int val,int id){
int p=1;
trie[p].maxi=max(trie[p].maxi,id);
for(int k=29;k>=0;k--){
int b=(val>>k)&1;
if(!trie[p].ch[b])trie[p].ch[b]=++cnt;
p=trie[p].ch[b];
trie[p].maxi=max(trie[p].maxi,id);
}
}
void update(int id,int val){
for(;id>0;id-=lb(id))tree[id]=min(tree[id],val);
}
int query(int id){
int ans=inf;
for(;id<=n;id+=lb(id))ans=min(ans,tree[id]);
return ans;
}
vector<pii>pr[MAXN];
struct QUERY{
int l,r,id;
}que[200005];
bool cmp(QUERY a,QUERY b){
return a.r<b.r;
}
int ans[200005];
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)scanf("%d",a+i);
for(int j=1;j<=n;j++){
int p=1;
for(int k=29;k>=0;k--){
int b=(a[j]>>k)&1;
if(trie[p].ch[b^1]){
int tmp=trie[trie[p].ch[b^1]].maxi;
pr[j].push_back({tmp,a[tmp]^a[j]});
}
if(!trie[p].ch[b]){
p=0;
break;
}
p=trie[p].ch[b];
}
if(p>0&&trie[p].maxi>0)pr[j].push_back({trie[p].maxi,0});
insert(a[j],j);
}
for(int i=0;i<q;i++){
scanf("%d%d",&que[i].l,&que[i].r);
que[i].id=i;
}
sort(que,que+q,cmp);
memset(tree,0x4f,sizeof(tree));
int rgt=0;
for(int k=0;k<q;k++){
while(rgt<que[k].r){
rgt++;
for(auto i:pr[rgt])update(i.first,i.second);
}
ans[que[k].id]=query(que[k].l);
}
for(int i=0;i<q;i++)printf("%d\n",ans[i]);
return 0;
}
|
:::