这场在3月26日举行的div3，恰好我当时掉青，正好恰波低保。
A. Divisibility Problem
题意
给你两个正数$a$与$b$，求出$a$最少增加多少才能被$b$整除
思路
显然$\frac a b$的余数为$a % b$，那么将这部分补足即可
$$ ans=b-a% b$$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
int main()
{
ll t,a,b;
cin>>t;
while(t--)
{
cin>>a>>b;
ll ans=(b-(a%b))%b;
cout<<ans<<endl;
}
return 0;
}
|
给出整数$n,k$，考虑所有由$n-2$个$a$和$2$个$b$构成的字符串，输出其中字典序第$k$小的。
思路
在草纸上可以看出第一个$b$的下标与这个$b$所对应的串的个数是一个等差数列的关系。
所以我们可以在数组中预处理出等差数列前$n$项和，并且通过二分在这个数组查找$k$对应的第一个$b$的位置，再计算字典序小于第一个$b$的字符串的个数，可以推得第二个$b$的位置。
暴力也可，注意这题爆$int$
代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
int frac[maxn];
signed main()
{
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#ifdef DEBUG
freopen("input.in", "r", stdin);
#endif
int t,n,k;
for(int i=1;i<maxn;i++)
frac[i]=frac[i-1]+i;
cin>>t;
while(t--)
{
cin>>n>>k;
int st=lower_bound(frac+1,frac+maxn,k)-frac;
int a=n-st,b=n-(k-frac[st-1])+1;
for(int i=1;i<=n;i++)
cout<<(i==a||i==b?'b':'a');
cout<<endl;
}
return 0;
}
|
C. Ternary XOR
题意戳这
思路
贪心……应该挺容易想的
代码
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>
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
char s[maxn];
int ans1[maxn],ans2[maxn];
int main()
{
int t,n;
cin>>t;
while(t--)
{
cin>>n>>s+1;
ans1[1]=ans2[1]=1;
bool flag=0;
for(int i=2;i<=n;i++)
{
if(s[i]=='2')
{
if(flag)
{
ans2[i]=2;
ans1[i]=0;
}
else
ans1[i]=ans2[i]=1;
}
else if(s[i]=='0')
ans1[i]=ans2[i]=0;
else{
if(!flag)
{
ans1[i]=1;
ans2[i]=0;
flag=1;
}
else{
ans1[i]=0;
ans2[i]=1;
}
}
}
for(int i=1;i<=n;i++)
cout<<ans1[i];
cout<<endl;
for(int i=1;i<=n;i++)
cout<<ans2[i];
cout<<endl;
}
return 0;
}
|
D. Carousel
题意
$n$个动物围成一个圈，要你给他们染色，要求保证相邻的不同动物颜色一定不同（相同种类动物颜色无要求），输出最少染色方案
思路
贪心，从1开始贪心地进行递增染色，遇到相同的动物则置为1。
可以看出来答案一定不会超过$3$
初步染色后若$1$号位置和$n$号位置的种类不同且颜色相同，那么就要特殊处理，如果$t[n-1],t[n],t[1],t[2]$这一段有连续相同动物，那么稍微修改下$t[n]$或者$t[1]$颜色即可。
如果这四个无连续相同动物，那么从最近连续相同种类动物开始重新染色。
代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5,inf=0x3f3f3f3f,mod=1000000007;
int t[maxn],col[maxn];
int main()
{
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#ifdef DEBUG
freopen("input.in", "r", stdin);
#endif
int n,q;
cin>>q;
while(q--)
{
cin>>n;
map<int,int> mp;
for(int i=1;i<=n;i++)
{
cin>>t[i];
}
int ans=1,tar=0;
bool flag=0;
col[1]=1;
for(int i=2,now=1;i<=n;i++)
{
if(t[i]!=t[i-1])
{
ans=2;
if(now==1)
col[i]=now=2;
else
col[i]=now=1;
}
else{
flag=1;
tar=i;
col[i]=now=1;
}
}
if(t[n]!=t[1]&&col[n]==col[1])
{
if(t[n-1]==t[n])
col[n]=2;
else if(t[1]==t[2])
col[1]=2;
else{
if(!flag)
{
ans=3;
col[n]=3;
}
else{
int now=col[tar];
if(now==1)
col[tar]=now=2;
else
col[tar]=now=1;
for(int i=tar+1;i<=n;i++)
{
if(now==1)
col[i]=now=2;
else
col[i]=now=1;
}
}
}
}
cout<<ans<<endl;
for(int i=1;i<=n;i++)
cout<<col[i]<<' ';
cout<<endl;
}
return 0;
}
|
E. Tree Queries
题意
一个$n$个结点的树上给定$k$个节点，问你是否存在一条一端为根节点$1$的路径，使得每个选出的节点到这条路径距离不超过$1$
思路
好题，没做出来……
首先，到一个节点距离不超过$1$的节点有该节点的父节点、该节点本身、该节点的儿子节点。
可以发现一条从上面下来的路径无论以上述哪种方式接近该节点，都会通过该节点的父节点。
于是问题转化为，给出一系列节点（即所给节点的父节点），是否存在一条从根节点开始的路径，通过这些节点。
于是我们可以将所给节点的父节点放入集合，按深度排序，如果任何后一个节点在前一个节点的子树中，则回答YES。
注意1的父节点这里仍然设为1，判断一个节点是否在另一个节点的子树中可以用树链剖分常用的$dfs$序+节点子树大小来搞
代码
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
| #include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10,inf=0x3f3f3f3f,mod=1000000007;
vector<int> G[maxn];
int tim=0,fa[maxn],siz[maxn],dfn[maxn],dep[maxn];
void dfs(int x,int f)
{
dep[x]=dep[f]+1;
fa[x]=f;
siz[x]=1;
dfn[x]=++tim;
for(auto &v:G[x])
{
if(v==f)
continue;
dfs(v,x);
siz[x]+=siz[v];
}
}
signed main()
{
int n,m,k,u,v;
cin>>n>>m;
for(int i=1;i<n;i++)
{
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,1);
while(m--)
{
vector<int>vec;
cin>>k;
for(int i=1;i<=k;i++)
{
cin>>u;
vec.push_back(fa[u]);
}
sort(vec.begin(),vec.end(),[](const int&a,const int &b){
return dep[a]<dep[b];
});
bool ok=1;
for(int i=1;i<vec.size();i++)
{
u=vec[i-1],v=vec[i];
if(dfn[u]>dfn[v]||dfn[v]>dfn[u]+siz[u]-1)
{
ok=0;
break;
}
}
cout<<(ok?"YES":"NO")<<endl;
}
return 0;
}
|
F. Make k Equal
给你$n$个元素的数组，可以选择数组中最大元素自减或者最小元素自增，求出数组中出现$k$个相等的元素最少需要操作多少次。
思路
前缀和、离散化、贪心
$a_i$范围$10^9$，必须要离散化，通过$id$函数得到$a_i$的编号。对于每个$a_i$，预处理求出将所有小于$a_i$转化为$a_i-1$的代价$pre[id(a_i)]$，和将所有大于$a_i$的元素转化为$a_i+1$的代价$suf[id(a_i)]$，同时处理出小/大于$a_i$的元素的数量。
计算时，对于每个元素$x$，需要转化的元素数量即为$res=k-cnt[x]$，有三种转化方式
- 只从最小元素转化，此时代价为$pre[id]+res$
- 只从最大元素转化，此时代价为$suf[id]+res$
- 两边都有转化，此时代价为$pre[id]+suf[id]+res$（因为每次都是对极值进行操作）
代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int maxn=2e5+10,inf=0x3f3f3f3f,mod=1000000007;
vector<ll>vec;
int id(ll x)
{
return lower_bound(vec.begin(),vec.end(),x)-vec.begin()+1;
}
ll sum[maxn],a[maxn],pre[maxn],suf[maxn],cnt[maxn],pcnt[maxn],scnt[maxn];
signed main()
{
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#ifdef DEBUG
freopen("input.in", "r", stdin);
#endif
int n,k;
cin>>n>>k;
map<ll,ll>mp;
for(int i=1;i<=n;i++)
{
cin>>a[i];
mp[a[i]]++;
if(mp[a[i]]>=k)
{
cout<<0<<endl;
exit(0);
}
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i];
vec.push_back(a[i]);
}
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(),vec.end()),vec.end());
ll rec=0;
for(int i=1;i<=n;i++)
{
rec+=a[i];
int now=id(a[i]);
cnt[now]++;
if(a[i]!=a[i+1])
{
pre[now]=(a[i]-1)*(i-cnt[now])-(rec-cnt[now]*a[i]);
pcnt[now]=pcnt[now-1]+cnt[now-1];
}
}
rec=0;
for(int i=n;i>=1;i--)
{
rec+=a[i];
if(a[i-1]!=a[i])
{
int now=id(a[i]);
suf[now]=(rec-cnt[now]*a[i])-(n-i+1-cnt[now])*(a[i]+1);
scnt[now]=scnt[now+1]+cnt[now+1];
}
}
ll ans=LLONG_MAX;
for(auto &x:vec)
{
int now=id(x);
ll res=k-cnt[now];
ans=min(ans,pre[now]+suf[now]+res);
if(pcnt[now]>=res)
ans=min(ans,pre[now]+res);
if(scnt[now]>=res)
ans=min(ans,suf[now]+res);
}
cout<<ans<<endl;
return 0;
}
|