【补题系列】2020USST算法竞赛练习场4
题解
题意：定义MEX为一个集合中未出现的最小非负整数，现在有q次询问，每次添加一个数进入集合中，每次操作都可以让集合中任意一个值+x或-x若干次，求每次询问后的最大MEX值
算法：贪心
由于+x和-x的操作是任意次的，因此每次询问时只需存储新加的数%x的值，按照题意需要从0开始尽可能填满之后的数，因此一开始假设答案为0，之后只要ans%x存在就可以使ans++，然后每次输出答案即可
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include<bits/stdc++.h>
using namespace std;
int giao[1000005];
int main(){
int n,x;
cin>>n>>x;
int ans=0;
for(int i=1;i<=n;i++){
int y;
cin>>y;
giao[y%x]++;
while(giao[ans%x]>=1){
giao[ans%x]--;
ans++;
}
cout<<ans<<endl;
}
return 0;
}
|
题解
题意：给出n位由0或1构成数，再给出其中包含的1的个数m（其余n-m位全是0），要求求出其中包含至少一个1的子串的种类数
算法：数学 + 逆向思维
题目要求找包含至少一个1的种类数，一看就很多，所以可以逆向思维，最多可以有n*(n+1)/2种，然后再减去全是0的种类数就可以了，可以分类讨论一下
- 当全是1时：
ans=(n+1)*n/2
全是0时：ans=0
当1的个数大于0的个数时：很容易想到用1把所有0都分隔开，比如5位数有3个1，则最佳情况应该是10101，因此答案很容易想到：ans=n*(n+1)/2-(n-m)
当1的个数小于0的个数时：此时也应该尽量用1把所有0都分隔开，而且要尽量均摊，比如00100100是最佳的，m个1可以把(n-m)个0分隔成(m+1)份，每一份的0的数量是mf=(n-m)/(m+1)，此时还余下duo=(n-m)%(m+1)个0没有被分配，那么久把它丢进去继续分配，因此答案为ans=(n+1)*n/2-(m+1-duo)*mf(mf+1)/2-duo*(mf+1)*(mf+2)/2
AC代码
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 n;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
ll x,y;
cin>>x>>y;
if(y==0){
cout<<"0"<<endl;
continue;
}
if(x==y){
cout<<x*(x+1)/2<<endl;
continue;
}
if(y>=x-y){
cout<<(x+1)*x/2-(x-y)<<endl;
continue;
}
ll ling=x-y;
ll mf=ling/(y+1);
ll duo=ling%(y+1);
ll ans=(x+1)*x/2;
ans-=(y+1-duo)*mf*(mf+1)/2;
ans-=duo*(mf+1)*(mf+2)/2;
cout<<ans<<endl;
}
return 0;
}
|
题解
个人觉得比较好的矩阵加速题，记录一下
题意：给出一个n行m列矩阵的第一列2~n行的数值，该矩阵第一行从第2列到第m列分别为233、2333、23333。。。其余位置$a {i,j}=a {i-1,j}+a_{i,j-1}$，现在要求你求出第n行m列的数的值（mod 10000007）的答案
算法：矩阵加速（矩阵快速幂）
容易发现题目的矩阵长这样
由于n很小但m特别大，直接递推肯定T，所以联想到矩阵加速，我们把第一列提取出来，想办法构造一个矩阵，让第一列乘完这个矩阵之后变成第二列，然后套矩阵快速幂
但是发现这个233不好构造，考虑到左上角第一个数没用，所以我们可以令它为23，然后给这个矩阵多加一行3，就可以构造成如下的矩阵啦
出于习惯原因，我把第一列写成了行向量，总共n+2行，矩阵是(n+2)*(n+2)的方阵，接下来套矩阵快速幂即可
AC代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e7+7;
int n,m;
struct M{
ll mat[15][15];
}ans;
M operator *(M x1,M x2){
M res;
memset(res.mat,0,sizeof(res.mat));
for(int i=1;i<=n+2;i++){
for(int j=1;j<=n+2;j++){
for(int k=1;k<=n+2;k++){
res.mat[i][j]+=(x1.mat[i][k]%mod*x2.mat[k][j]%mod)%mod;
res.mat[i][j]%=mod;
}
}
}
return res;
}
inline M qpow(M a,ll k,M ans){
M base=a;
while(k>0){
if(k&1) ans=ans*base;
base=base*base;
k>>=1;
}
return ans;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
memset(ans.mat,0,sizeof(ans));
for(int i=2;i<=n+1;i++){
scanf("%lld",&ans.mat[1][i]);
}
ans.mat[1][1]=23;
ans.mat[1][n+2]=3;
M a;
memset(a.mat,0,sizeof(a.mat));
for(int i=2;i<=n+1;i++){
for(int j=i;j<=n+1;j++){
a.mat[i][j]=1;
}
}
for(int i=1;i<=n+1;i++){
a.mat[1][i]=10;
a.mat[n+2][i]=1;
}
a.mat[n+2][n+2]=1;
M anss=qpow(a,m,ans);
cout<<anss.mat[1][n+1]%mod<<endl;
}
return 0;
}
|