8月24日测试总结
8月24日测试总结
mixtree
题目大意：
给定一个有 \(n\) 个点，\(n-1\) 条带权边的树。对于树中的两个点，其产生的 \(mix\) 值为两条边路径上的最大边权，问所有点对所产生的 \(mix\) 值。
思路：
考虑计算每条边的贡献。
首先，我们先将所有的边按照边权的大小从小到大排一遍序，当我们考虑到第 \(i\) 条边时，前第 $1 $ 至 $ i-1$ 条边不会对当前边产生任何影响（因为我们是从小到大进行排序的，而我们要考虑的是路径上的最大值，所以肯定不会有影响）。
然后我们把边加进来，发现，此时所有能到达端点 \(u\) 和 \(v\) 的点在加入这条边后都能形成一条路径，易得这些形成新路径的点对的 \(mix\) 值就是当前边的边权，且不可能有其他没有考虑到的路径的最大值是这条边的边权（从小到大的意义就是排除其他边对当前边贡献的影响，因为前面遍历到的边的边权都比当前边小）。
那我们从小到大加边，使用并查集维护即可。在合并两个并查集时，假设两端的点数分别是 \(x\) 和 \(y\) ，根据组合可知，有 \(x\times y\) 组点对，当前边的边权为 \(w\)。所以对答案的贡献为 \(x\times y\times w\)。
Code：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+11;
struct node
{
int u,v,w;
}a[maxn];
int n,ans;
int f[maxn];//记录祖先
int cnt[maxn];//点i连接的点的数量
inline bool cmp(node x,node y){return x.w<y.w;}
inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);}//并查集
signed main()
{
std::ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<n;++i)
cin>>a[i].u>>a[i].v>>a[i].w;
for(int i=1;i<=n;++i)
f[i]=i,cnt[i]=1;//初始化
sort(a+1,a+n,cmp);
for(int i=1;i<n;++i)
{
int fu=find(a[i].u),fv=find(a[i].v);
if(fu==fv)continue;//已经连在了一起，跳过
ans+=cnt[fu]*cnt[fv]*a[i].w;//ans+=两端的点数相乘*当前边的大小
f[fu]=fv;//合并
cnt[fv]+=cnt[fu];//更新点数
}
cout<<ans<<endl;
return 0;
}
salad
题目传送门
题目大意：
给定一个长度为 \(n\) 的且只由 \(\texttt{p}\) 和 \(\texttt{j}\) 构成的字符串，要你找出一个最长的子串，满足从左往右和从右往左扫时，任何时刻 \(\texttt{p}\) 的数量都大于等于 \(\texttt{j}\) 的数量。
思路：
首先，通过观察，不难发现满足条件的字串的两端一定都是 \(\texttt{p}\)，所以，我们每次都可以去除前导 \(\texttt{j}\)。然后，我们用 \(sum1\) 和 \(sum2\) ，分别记录 \(\texttt{p}\) 和 \(\texttt{j}\) 的数量（前缀），用 \(s1\) 和 \(s2\) 记录后缀。既然要记录前缀和后缀，那么是不是要正反都扫一遍呢？并不需要，如果当前位是 \(\texttt{p}\)，就 ++sum1,++s1，否则 ++sum2,++s2。然后在每次 \(s1\) 大于等于 \(s2\) 时，将 \(s1\) 和 \(s2\) 清零。为什么呢？
举个例子：\(\texttt{pppppjjjjpjjp}\)，这时，我们从前往后扫，在扫到第十位 \(\texttt{p}\) 时，如果 \(s1\) 和 \(s2\) 没有在第五位被清零（\(sum1\) 等于 \(sum2\)，所以不会 break），\(s1\) 就会大于 \(s2\)，那么，最长串就会被记为 \(\texttt{pppppjjjjp}\)。但是，我们发现这个字串并不符合要求（从右往左扫），这就是因为在第五位时没有清空 \(s1\) 和 \(s2\)，所以前面的五个 \(\texttt{p}\) 对第十位的 \(\texttt{p}\) 造成了影响，因为假设我们不是从左往右扫，而是从右往左扫，那么这五个 \(\texttt{p}\) 对于第十位的 \(\texttt{p}\) 来说是在它之后的，但却对它造成了影响，这显然是错误的。
所以，“每次 \(s1\) 大于等于 \(s2\) 时，将 \(s1\) 和 \(s2\) 清零”这个操作就是为了清除前缀对后缀的影响（不理解就结合前面的例子多想一会）。至于复杂度嘛，因为这个算法有点玄学，不太确定，应该是 \(O(n)\)。
思路提供者：巨佬（这是他的赛时思路，踩爆标算）。
Code：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+11;
int n;
int l,r,ans;
int s1,s2;//记录后缀
int sum1,sum2;//sum1记录p的数量，sum2记录j的数量（前缀）
char str[maxn];
signed main()
{
freopen("1.in","r",stdin);
std::ios::sync_with_stdio(false);
cin>>n;
cin>>str+1;
l=1,r=n;
while(str[r]=='j')--r;
while(l<=r)
{
while(str[l]=='j')++l;
int k=-1,i;
sum1=0,sum2=0;
for(int i=l;i<=r;++i)
{
if(str[i]=='p')
++sum1,++s1;
else
++sum2,++s2;
if(sum2>sum1)break;//j的数量大于p的数量，不符合要求，break
if(s1>=s2)//上面有解释
s1=0,s2=0,k=i;
}
if(~k)i=k;
ans=max(ans,i-l+1);//更新答案
s1=0,s2=0;
l=i+1;
}
cout<<ans<<endl;
return 0;
}