Atcoder Beginner Contest 448
该题解即将成为本博客的第一篇文章，应值得纪念。
不论是代码/算法能力的不足，或是秉持着开源的精神，我的ABC题解写作工作从现在算是正式开始了。我会尽量做到不缺席每周的ABC以及补全能力之内的题，且在周末更新题解。私以为想提高算法能力，不论是为了面试或是其他，Atcoder
Beginner
Contest会是对初学者/有些许基础的学习者一个很好的帮助。其在每场都会有套路模板题的情况下，也会出一些类“脑筋急转弯”的题锻炼思维。它既可以帮到LeetCode选手去补足练习纯面试题时练不到的思维能力，也为新手在Codeforces上练习觉得自己“学到的模板算法没有用”时，提供了一定的正反馈。在我记录/学习/巩固的过程中，若能有机会帮到和我一样在尝试进步的普通人，那再好不过。另：由于算法领域大神云云，而我水平远远未到，题解的写作难免出现纰漏，若有说的不清楚之处，还请大家感性理解qwq。
直接模拟，复杂度。
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=100002;
int n,x,ans;
int a[maxn];
signed main()
{
cin>>n>>x;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]<x) { x=a[i]; cout<<"1"<<endl; }
else cout<<"0"<<endl;
}
return 0;
}
|
统计出每种胡椒在所有菜中的用量，随后与胡椒的库存取
即可，复杂度。考虑到 ，足以通过本题。一个显然的带log的做法是以胡椒种类为关键字排序，这里就不给出代码了。
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=100002;
int n,m,ans;
struct dish{
int a,b;
}d[maxn];
int c[maxn],cc[maxn];
signed main()
{
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>c[i];
for(int i=1;i<=n;i++) { cin>>d[i].a>>d[i].b; }
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(d[j].a==i) cc[i]+=d[j].b;
}
}
for(int i=1;i<=m;i++) ans+=min(c[i],cc[i]);
cout<<ans;
return 0;
}
|
考虑暴力，复杂度
且无明显优化空间。仔细观察可发现，每次查询之间相互独立，互不影响，且最重要的一点
。故可能成为答案的只有最小的六个
。观察到这一点解法显然，查询之前对 排序，从左往右考虑
中前六小的数，直到其下标在 中没有出现过。复杂度
。
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=300002;
int n,q,k,val;
int b[maxn];
bool judge[maxn];
struct nodd{
int val,id;
}a[maxn];
bool cmd (nodd x,nodd y) { return x.val<y.val; }
signed main()
{
cin>>n>>q;
for(int i=1;i<=n;i++) { cin>>a[i].val; a[i].id=i; }
sort(a+1,a+1+n,cmd);
while(q--)
{
cin>>k; memset(judge,0,sizeof(judge));
for(int i=1;i<=k;i++)
{
cin>>val;
judge[val]=1;
}
for(int i=1;i<=k+1;i++)
{
if(judge[a[i].id]==0)
{
cout<<a[i].val<<endl;
break;
}
}
}
return 0;
}
|
先考虑最显然的暴力，复杂度 。考虑题目本身性质，我们发现一个节点的父节点若答案是No，该节点答案一定也是No，因为从根节点到该节点的简单路径一定包含根节点到该节点父节点的简单路径。考虑如何从暴力优化，与路径有关的问题往往可以使用
DFS+回溯 的方式尝试解决。该题我们在 DFS
的过程中实时维护一个map，每遍历到一个节点，其答案是No的情况只有两种：1.其父节点答案是No。2.该节点的值在map中出现过。复杂度
。
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=300002;
int n,u,v;
int a[maxn],ans[maxn];
vector<int> edge[maxn];
map<int,int> mp;
void Getans(int now,int tag,int fa)
{
if(tag==1) ans[now]=1;
int size=edge[now].size();
if(size==0) return;
for(int i=0;i<=size-1;i++)
{
if(edge[now][i]==fa) continue;
if(tag==1) { Getans(edge[now][i],1,now); continue; }
mp[a[edge[now][i]]]++;
if(mp[a[edge[now][i]]]==1) Getans(edge[now][i],0,now);
else Getans(edge[now][i],1,now);
mp[a[edge[now][i]]]--;
}
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n-1;i++)
{
cin>>u>>v;
edge[u].push_back(v);
edge[v].push_back(u);
}
mp[a[1]]++;
Getans(1,0,0);
for(int i=1;i<=n;i++) ans[i]==1?cout<<"Yes"<<endl:cout<<"No"<<endl;
return 0;
}
|
该题数学成分浓厚，赛时耗费的时长大于F。首先观察到暴力的方法完全不可取，只能往数学角度思考。题解给出的方法是基于等比数列与
binary lifting
的，下面给出一种我自己的方法，相较于题解思考难度更低，但代码更复杂。
首先，题目要求求 ，我们可以将其转化为:
接下来我们看这里面我们需要解决什么问题，其实观察可以发现问题大体分为两类：1.大数
对一个数进行取模操作. 2.
对10007进行取模操作。其中，第二个问题如果对乘法逆元有了解，基于10007是质数，我们很快可以通过快速幂解决（通过费马小定理可证）。对于第一个问题，其实就是在考虑
在模10007或者模 意义下的值，这里我们观察
的构成方式，其实在
的结尾补数的操作就是不断地执行“乘10加k”的操作，不难观察到这是线性的，用矩阵乘法的方式表示，就是：
接下来的操作很简单，观察到暴力执行这个操作的复杂度是
，这是不能接受的，所以我们需要一个
级别的算法，这时候我们使用矩阵快速幂，就能轻松将复杂度降低到
级别啦。最后复杂度 。
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
78
79
80
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=100002;
int k,m,ans1,ans2;
int n=2;
int c[maxn],l[maxn];
int a[3][3],zhuan[3][3],ans[3][3],final[3][3];
int qpow(int b,int p,int k)
{
int ans=1;
while(p>0)
{
if(p%2!=0)
ans=ans*b%k;
b=b*b%k;
p>>=1;
}
return ans;
}
void Mi1(int mod)
{
memset(zhuan,0,sizeof(zhuan));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
zhuan[i][j]=(zhuan[i][j]+ans[i][k]*a[k][j])%mod;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
ans[i][j]=zhuan[i][j];
}
void Mi2(int mod)
{
memset(zhuan,0,sizeof(zhuan));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
zhuan[i][j]=(zhuan[i][j]+a[i][k]*a[k][j])%mod;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=zhuan[i][j];
}
void MartixQmi(int mod,int k)
{
while(k)
{
if(k&1) Mi1(mod);
Mi2(mod);
k>>=1;
}
return ;
}
signed main()
{
cin>>k>>m;
for(int i=1;i<=k;i++) { cin>>c[i]>>l[i]; }
final[1][1]=0; final[2][1]=1;
for(int i=1;i<=k;i++)
{
a[1][1]=10; a[1][2]=c[i]; a[2][1]=0; a[2][2]=1;
ans[1][1]=1; ans[1][2]=0; ans[2][1]=0; ans[2][2]=1;
MartixQmi(m,l[i]);
final[1][1]=ans[1][1]*final[1][1]+ans[1][2]*final[2][1]; final[1][1]%=m;
final[2][1]=1;
}
ans1=final[1][1];
final[1][1]=0; final[2][1]=1;
for(int i=1;i<=k;i++)
{
a[1][1]=10; a[1][2]=c[i]; a[2][1]=0; a[2][2]=1;
ans[1][1]=1; ans[1][2]=0; ans[2][1]=0; ans[2][2]=1;
MartixQmi(10007,l[i]);
final[1][1]=ans[1][1]*final[1][1]+ans[1][2]*final[2][1]; final[1][1]%=10007;
final[2][1]=1;
}
ans2=final[1][1];
int finalans=(ans2-ans1+10007)*qpow(m,10005,10007)%10007;
cout<<finalans;
return 0;
}
|
代码更简单的方法见官方题解。
很有趣的思维题。显然，寻找最短路径的旅行商问题是NP-Hard的，再该题的数据范围之下则不可能给出最优解。而该题要求寻找一个大小在1e10之内的可行解。在这里我用的是一种类似根号分治的解法，把
轴分成一个个“条”，然后类似于蛇走s型，从左到右依次走过去。在奇数个块从上往下走，偶数个块从下往上走。
接下来我们证明合理性，同时求出所分的块的大小：
设 轴分块的块大小为 ， 轴的取值范围为
，则在所有块内走过的路径之和最大是：
显然当 时有最小。而最小值小于1e10，故该方法合理。
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;
#define int long long
const int maxn=100002;
int n;
int bsize=80000;
struct nodd{
int x,y,id;
}p[maxn];
bool cmp(nodd x,nodd y){
int bx=x.x/bsize;
int by=y.x/bsize;
if(bx!=by) return bx<by;
if(bx%2==0) return x.y<y.y;
else return x.y>y.y;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++) { cin>>p[i].x>>p[i].y; p[i].id=i; }
sort(p+2,p+1+n,cmp);
for(int i=1;i<=n;i++) cout<<p[i].id<<" ";
return 0;
}
|
