赛后——2.10 寒假模拟6
\(\text{T1 gene}\)
题意
待补
思路
令 \(dp_{i,j}\) 表示令 \(S\) 的前 \(i\) 个字符在增加字母后后缀为 \(T\) 的前 \(j\) 个字符的最小代价，转移方程很裸（注意我们只能在当前 \(S_i\) 身后增加字符）
\[dp_{i,j}=\begin{cases} dp_{i,j-1}+c_j &[S_i\ne T_j]\\ \min(dp_{i-1,j-1},dp_{i}{j-1}+c_j &[S_i= T_j] \end{cases}\]代码
点击查看代码
int main(){
scanf("%s",s+1);
scanf("%s",t+1);
ls=strlen(s+1),lt=strlen(t+1);
cost['A']=read(),cost['C']=read(),cost['G']=read(),cost['T']=read();
for(int i=1;i<=lt;i++){
dp[1][i]=dp[1][i-1]+cost[t[i]];
}
for(int i=2;i<=ls;i++){
for(int j=1;j<=lt;j++){
if(s[i]!=t[j]){
dp[i][j]=dp[i][j-1]+cost[t[j]];
}
else{
dp[i][j]=min(dp[i-1][j-1],dp[i][j-1]+cost[t[j]]);
}
}
}
for(int i=1;i<=ls;i++){
ans=min(ans,dp[i][lt]);
}
printf("%d\n",ans);
return 0;
}
\(\text{T2 fight}\)
题意
待补
思路
定义 \(i+n\) 为 \(i\) 的敌人，那么“敌人的敌人就是朋友”，将这种关系用并查集维护，输出第一组属于同一阵营的数据。
代码
点击查看代码
inline int find(int x){
if(fa[x]==x) return fa[x];
else return fa[x]=find(fa[x]);
}
int main(){
n=read(),m=read();
for(int i=1;i<=2*n;i++){
fa[i]=i;
}
for(int i=1;i<=m;i++){
int a=read(),b=read();
if(find(a)==find(b)){
printf("%d\n",i);
break;
}
if(find(a)!=find(b+n)){
fa[find(a)]=fa[find(b+n)];
}
if(find(a+n)!=find(b)){
fa[find(a+n)]=fa[find(b)];
}
}
return 0;
}
\(\text{T3 pastry}\)
题意
待补
思路
设等分成 \(i\) 块所需的切割数为 \(cnt_i\)，若存在非互质关系，需要去重（例如 \(8\) 和 \(12\) 种有 \(3\) 次切割是可以同步完成的），发现 \(a_i\) 很小，可以把 \([2,a_{max}]\) 全部枚举。
对于一个 \(i\) 来说，如果其倍数属于要等分的集合中，答案就算上 \(cnt_i\)，同时把其所有倍数的 \(cnt\) 都减去 \(cnt_i\)，于是我们的去重方法便是把切成的形如 \(\left\lfloor\frac{d}{i}\right\rfloor\) 的部分都化到最简，把答案算到最简分母 \(i\) 的 \(cnt_i\) 上（这个 \(i\) 未必要出现）。
插句题外话，这东西也可以用 \(\varphi(i)\) 去做，因为每个 \(i\) 只处理互质的就可以了。
代码
点击查看代码
int main(){
n=read()+1;
for(int i=1;i<=n;i++){
int x=read();
vis[x]=1;
maxx=max(maxx,x);
}
for(int i=1;i<=maxx;i++){
cnt[i]+=i-1;
bool pd=0;
for(int j=1;i*j<=maxx;j++){
if(vis[i*j]) pd=1;
if(j>1){
cnt[i*j]-=cnt[i];
}
}
if(pd) ans+=cnt[i];
}
printf("%d\n",ans);
return 0;
}
\(\text{T4 conference}\)
题意
待补
思路
考虑整数分块，把对于每个 \(k\) 的 \(\left\lfloor\frac{a_i}{k}\right\rfloor\) 包含区间的左端点都预处理出来，显然左端点是比这一区间的其他答案优的。
于是去重后的答案可选个数最大为 \(2\times \sqrt{10^8}=2\times 10^4\)，其实到这里暴力复杂度已经很小了（只是空间略微大一点）。当然也可以选择算一个 \(b_i\) 表示对于当前枚举的答案 \(k\)，荷叶 \(i\) 上每个青蛙分到的单位食物大小，排序后就能找到这个 \(k\) 所能得到的“一起讨论的荷叶个数”，因为我们的枚举都是单调增的，所以第一次更新就是最终答案。
本题需要注意的是，预处理的本质是给定 \(a_i\) 对每一个 \(k\) 做区间划分，后续的处理是给定可能答案 \(k\)，对每一个 \(a_i\) 的结果做区间划分。
代码
点击查看代码
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
ans[i]=-1;
}
for(int i=1;i<=n;i++){
int l=1;
while(1){
G.push_back(l);
if(a[i]/l==0) break;
l=a[i]/(a[i]/l)+1;
}
}
sort(G.begin(),G.end());
G.erase(unique(G.begin(),G.end()),G.end());
for(int i=0;i