赛后总结
CF Round 908(div2)
A. Secret Sport
本题读懂题以后，是秒杀的，但鉴于本人语文实在不好，还是花费了20多分钟。
本题询问全局获胜的人是A还是B，但实际上最后一局的获胜者就是赢家，所以只需输出最后一个胜利的人即可。
下面就是本题简单的代码：
#include<bits/stdc++.h>
using namespace std;
int n,t;
string s;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
cin>>n;
cin>>s;
cout<<s[n-1]<<endl;
}
return 0;
}
B. Two Out of Three
本题构造题，要满足下列条件（只满足其中$2$个）：
- 存在$1\le i,j \le n$，使得$a_i=a_j,b_i=1,b_j=2$
- 存在$1\le i,j \le n$，使得$a_i=a_j,b_i=1,b_j=3$
- 存在$1\le i,j \le n$，使得$a_i=a_j,b_i=2,b_j=3$
由此可知原数组至少有$2$组及以上的相等的值，否则输出$-1$。
那么也就可以构造其中两组等值满足只含有$1,2$和$1,3$，所以也就有了代码：
#include<bits/stdc++.h>
using namespace std;
int t;
int n;
int a[105];
int cnt[105];
int is[105];
int tot;
bool _3,_2;//判断是否已经有了1,2或1,3
int b[105];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
cin>>n;
_3=0,_2=0;
tot=0;
memset(cnt,0,sizeof cnt);
for(int i=1;i<=n;i++)
{
cin>>a[i],cnt[a[i]]++;
b[i]=1;
if(cnt[a[i]]==2)
{
tot++;
if(!_3) is[a[i]]=3,_3=1;
else if(!_2) is[a[i]]=2,_2=1;
else is[a[i]]=1;
}
if(cnt[a[i]]>=2) b[i]=is[a[i]];
}
if(tot<2) cout<<-1<<endl;
else
{
for(int i=1;i<=n;i++)
cout<<b[i]<<" ";
cout<<endl;
}
}
return 0;
}
C. Anonymous Informant
本题开始VP时就做不来了，但赛后讲完豁然开朗，总会想当初为何没想到，所以总之还是要多做题。
本题可以有不动点的移动推出每一次移动后，最后一个值就是上一次的不动点，我们也就可以得到上一次移动前的不动点，如果该点的值大于$n$，那么定是不能在移动了，此时如果移动次数小于$k$，那就不可行，否则$min(k,n)$次后仍能移动则可行（注：如果能移动$n$次那一定有循环节，后面则无需继续）。
于是就有了代码 真是后悔没想到：
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t;
int n,k;
int a[N];
int inx[N];
int p;
bool solve(int v)
{
if(v>=min(n,k)) return true;
int q=a[p];
if(q>n) return false;
p=(p-q+n)%n;
if(!p) p=n;
return solve(v+1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
cin>>n>>k;
for(int i=1;i<=n;i++) inx[i]=i,cin>>a[i];
p=n;
if(solve(0))cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
D. Neutral Tonality
做到现在发现之前甚至连算法都还没考，终于来了一道贪心，但我VP时看都没看到这道题。
这道题的贪心，就是给$b$数组从大到小排序，这样$b$数组本身是不会贡献任何最长上升子序列长度的。
接着就是考虑如何插入的问题，这也好想，只需要在$a$数组中找到第一个小于$b$数组当前值时插入，这样也不会贡献最长上升子序列长度。而寻找这个第一个小于它的值则可以用双指针即可。
所以由此就得到了AC代码:
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],b[N];
int t;
int n,m;
bool cmp(int x,int y)
{
return x>y;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
sort(b+1,b+m+1,cmp);
int q=1;
for(int i=1;i<=n;i++)
{
while(a[i]<b[q]&&q<=m) cout<<b[q++]<<" ";
cout<<a[i]<<" ";
}
while(q<=m) cout<<b[q++]<<" ";
cout<<endl;
}
return 0;
}
E. Freedom of Choice
本题实在是难以读懂题意，于是我打开了洛谷寻找本题翻译。
读完题意发现还是有点难度的，看了看题解的解释，又是豁然开朗（就是自己做不来），在此自己复述一遍。
本题可以轻易求出最后的数组长度的范围$L \le |S| \le R$，其中$L=\sum_1ml_i,R=\sum_1mr_i$我们可以发现如果$\R-L+1>\sum_1mlc_i$，那么就可以直接输出$0$，因为$a$的种类只有$\sum_1mlc_i$种。
那么就接着考虑剩余的情况，也就可以枚举$|S|$。基于贪心的思想，对于每一个可重集，我们可以从中选取$[l_i,r_i]$个值。
如果其中不等于$|S|$的值个数$|s_i|$大于$r_i$，那么就选取这其中$r_i$个数,反之，则必须要补充上$|l_i-s_i|$个$|S|$值，那么计数也要加上$|l_i-s_i|$。
所以代码如下：
#include<bits/stdc++.h>
#define mk make_pair
using namespace std;
typedef long long ll;
const int N=1e5+5;
int t;
ll m;
ll n,l[N],r[N];
ll sz,sl,sr,a[N],c[N],lc[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
cin>>m;
map<ll,vector<int> > is;
map<pair<int,ll>,ll> val;
sz=sl=sr=0;
for(int i=1;i<=m;i++)
{
cin>>n>>l[i]>>r[i];
sl+=l[i],sr+=r[i];
sz+=n;
lc[i]=0;
for(int j=1;j<=n;j++)
cin>>a[j],is[a[j]].push_back(i);
for(int j=1;j<=n;j++)
cin>>c[j],lc[i]+=c[j];
for(int j=1;j<=n;j++)
val[{i,a[j]}]=c[j];
}
if(sr-sl+1>sz)
{
cout<<0<<endl;
continue;
}
ll ans=LONG_LONG_MAX;
for(ll cnt=sl;cnt<=sr;cnt++)
{
ll tot=sr,rs=0;
vector<int> inx=is[cnt];
for(int i:inx)
{
tot-=r[i];
ll cr=lc[i]-val[{i,cnt}];
if(cr<l[i]) rs+=l[i]-cr,r=l[i];
tot+=min(cr,(ll)r[i]);
}
ans=min(ans,rs+max(0ll,cnt-tot));
}
cout<<ans<<endl;
}
return 0;
}
终于完成了！