Portal.
B1. Wonderful Coloring - 1
Portal.
记 c n t i cnt_i cnti 代表第 i i i 种字母在 s s s 中的出现次数，有两种情况：
- 若 c n t i > 1 cnt_i>1 cnti>1，此时对于这种字母，我们将它出现的某次染成红色，某次染成绿色，其他的出现情况不染色
- 若 c n t i = 1 cnt_i=1 cnti=1，此时需要和另一个 c n t j = 1 cnt_j=1 cntj=1 的字母配对染成一红一绿。
#include <bits/stdc++.h>
using namespace std;
int cnt[30];
void solve()
{
string s;cin>>s;
memset(cnt,0,sizeof cnt);
for(int i=0;i<s.length();i++) cnt[s[i]-'a']++;
int cnt1=0,cnt2=0;
for(int i=0;i<26;i++)
{
if(cnt[i]==1) cnt1++;
else if(cnt[i]>1) cnt2++;
}
cout<<(cnt1/2+cnt2)<<'\n';
}
int main()
{
int t;cin>>t;
while(t--) solve();
return 0;
}
B2. Wonderful Coloring - 2
Portal.
和 B1 相似的思路，统计每种字母出现的次数，出现次数大于 k k k 的填成 k k k 种颜色，否则就都可以填色。
由于需要输出方案数，按照序列中数的大小排序，保证一样的数排在一起，记录原 id 按序输出即可。
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int cnt[maxn],ans[maxn],ct[maxn];
struct node{int id,v;}a[maxn],b[maxn];
bool cmp(node a,node b)
{return a.v<b.v;}
void solve()
{
int n,k;cin>>n>>k;
for(int i=0;i<=n;i++) cnt[i]=0,ans[i]=0,ct[i]=0;
for(int i=1;i<=n;i++) cin>>a[i].v,cnt[a[i].v]++,a[i].id=i;
int tmp=0;
for(int i=1;i<=n;i++)
{
if(cnt[a[i].v]<k) b[++tmp]=a[i];
else if(cnt[a[i].v]>=k&&ct[a[i].v]<k) ct[a[i].v]++,ans[a[i].id]=ct[a[i].v];
}
sort(b+1,b+tmp+1,cmp);
int tp=1,tot=tmp/k*k;
for(int i=1;i<=tot;i++)
{
ans[b[i].id]=tp,tp++;
if(tp>k) tp=1;
}
for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
cout<<'\n';
}
int main()
{
int t;cin>>t;
while(t--) solve();
return 0;
}
C. Interesting Story
Portal.
sol.
D1. Domino (easy version)
Portal.
sol.
D2. Domino (hard version)
Portal.
sol.
E. Fixed Points
设计状态 f ( i , j ) f(i,j) f(i,j) 表示对于前 i i i 个数，删去 j j j 个数后，满足 b i = i b_i=i bi=i 的条件个数。
对于第
i
i
i 个位置，考虑删 / 不删，转移如下：
f
(
i
,
j
)
=
max
(
f
(
i
−
1
,
j
−
1
)
,
f
(
i
−
1
,
j
)
+
[
a
i
=
i
−
j
]
)
f(i,j)=\max(f(i-1,j-1),f(i-1,j)+[a_i=i-j])
f(i,j)=max(f(i−1,j−1),f(i−1,j)+[ai=i−j])
答案即为满足
f
(
n
,
i
)
≥
k
f(n,i)\geq k
f(n,i)≥k 的最小的
i
i
i。
#include <bits/stdc++.h>
using namespace std;
int a[2005],f[2005][2005];
void solve()
{
int n,k;cin>>n>>k;
for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) f[i][j]=0;
for(int i=1;i<=n;i++) cin>>a[i],f[i][0]=f[i-1][0]+(a[i]==i);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) f[i][j]=max(f[i-1][j-1],f[i-1][j]+(a[i]==i-j));
for(int i=0;i<=n;i++) if(f[n][i]>=k) return cout<<i<<'\n',void();
cout<<"-1\n";
}
int main()
{
int t;cin>>t;
while(t--) solve();
return 0;
}
F. Equidistant Vertices
Portal.
sol.
