前面的碎碎念：
这次比赛A了前三题，后面的题基本上都是因为没学过而做不出，所以算是把能做的题都做出来了。赛后学习了D,E题解法，写这篇博客也算是希望能加深记忆吧。
题解部分：
A-大吉大利
经典按位考虑算贡献，若ai第j+1位为0，这位贡献自然是0，若ai第j+1位为1，这位的贡献=整个序列第j+1位1的个数(1<<j)。所以我们先预处理出整个序列各位1的个数，再遍历一遍数组统计即可。
时间复杂度：O(nlog(ai))。
代码部分：
#include<bits/stdc++.h>
using namespace std;
long long one=1,sum[30]={0},a[100005];
int main()
{
long long i,j,n,ans=0;
scanf("%lld",&n);
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
for(j=0;j<30;j++)sum[j]+=(((one<<j)&a[i])?1:0);
}
for(i=1;i<=n;i++)
{
for(j=0;j<30;j++)
{
if(((one<<j)&a[i])==0)continue;
ans+=(one<<j)*sum[j];
}
}
printf("%lld\n",ans);
return 0;
}B-三角形周长和
这题又是算贡献的思想，对于空间中的n个点，我们先任取2点形成一条边，那么剩下n-2个点，都可以和这两点形成一个三角形，所以每条边对答案的贡献是边长(n-2)。我们跑个双重循环暴力算出所有边的边长之和，因为计算的时候，实际上每条边都被算了两次，所以要除个2。最后再乘上n-2，即是最终答案。这里我使用快速幂求逆元来进行除二取模操作。
时间复杂度：O(n^2)
代码部分：
#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long fastpow(long long a,long long b)
{
long long s=1;
for(;b;b>>=1,a=a*a%mod)if(b&1)s=s*a%mod;
return s;
}
int main()
{
int i,j,n;
long long x[1005],y[1005],ans=0;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%lld%lld",&x[i],&y[i]);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)ans=(ans+abs(x[i]-x[j])+abs(y[i]-y[j]))%mod;
printf("%lld\n",ans*(n-2)%mod*fastpow(2,mod-2)%mod);
return 0;
}C-操作集锦
看到子序列自然要想到DP，设状态为DP[i][j][k]，表示前i个字母，长度为j且最后一位是k+'a'的子序列有多少种。字符串我们用R数组保存，那么有状态转移方程：
for(k=0;k<26;k++)if(k!=R[i]-'a')DP[i][j][k]+=DP[i-1][j][k]
for(k=0;k<26;k++)DP[i][j][R[i]-'a']+=DP[i-1][j-1][k]
最后我们用i跑一遍0到25的循环，统计DP[n][k][i]之和即可。
此题还有另外一种更优的做法，可以优化掉时间复杂度前面26的常数，可以去比赛评论区查看他人的题解学习。
时间复杂度：O(26n
k)
代码部分：
#include<bits/stdc++.h>
using namespace std;
int DP[1005][1005][26]={0},mod=1e9+7;
int main()
{
int i,j,a,n,k,ans=0;
char R[1005];
scanf("%d%d%s",&n,&k,R+1);
if(!k){printf("1\n");return 0;}
for(i=1;i<=n;i++)
{
DP[i][1][R[i]-'a']=1;
for(j=1;j<=min(i,k);j++)
{
for(a=0;a<26;a++)if(a!=R[i]-'a')DP[i][j][a]=(DP[i][j][a]+DP[i-1][j][a])%mod;
for(a=0;a<26;a++)DP[i][j][R[i]-'a']=(DP[i][j][R[i]-'a']+DP[i-1][j-1][a])%mod;
}
}
for(i=0;i<26;i++)ans=(ans+DP[n][k][i])%mod;
printf("%d\n",ans);
return 0;
}D-斩杀线计算大师
刚刚又浏览了一遍比赛评论区，发现exgcd做法是假的，正解是同余最短路，出题人锅了...
E-旗鼓相当的对手
此题可以用长链剖分或者树上启发式合并，但是我都没学过(我是five)。赛后请教了大佬，学习了一下树上启发式的做法。
我们可以知道，树上两点间的距离=dep[u]+dep[v]-2dep[lca(u,v)]。那么题目也就是要我们找到，所有满足k=dep[u]+dep[v]-2
dep[lca(u,v)]的点对(u,v)，把他们的答案统计到lca(u,v)上即可。
我们对每个结点开一个set，set里保存的是以该节点为根节点的子树，里面所有节点有多少种深度dep。然后对每个结点开一个map，map的键值是深度dep，对应的东西是一个结构体。结构体里一个是num，表示该深度的节点个数，一个是w_sum，表示该深度的所有结点权值之和。
那么我们进行DFS的时候，每次就把父节点当lca，把子节点当u，然后枚举父节点set里的深度，利用公式k=dep[u]+dep[v]-2dep[lca(u,v)]，算出另一个子孙节点的深度，再把这个深度作为键值，利用map统计父节点答案。
记得每次都要把子节点set和map的信息合并到父节点上，自底向上合并更新每个结点的set与map信息。
时间复杂度:O(nlog(n)
log(n))
代码部分：
#include<bits/stdc++.h>
using namespace std;
int n,k,a[100005];
long long ans[100005];
struct node
{
long long w_sum,num;
};
map<int,node>V[100005];
vector<int>R[100005];
set<int>Dep[100005];
void comb(int x,int y,int dep)
{
int d;
for(set<int>:: iterator it=Dep[y].begin();it!=Dep[y].end();it++)
{
d=k+2*dep-(*it);
if(V[x].find(d)==V[x].end())continue;
ans[x]+=V[x][d].w_sum*V[y][*it].num+V[x][d].num*V[y][*it].w_sum;
}
for(set<int>:: iterator it=Dep[y].begin();it!=Dep[y].end();it++)
{
V[x][*it].w_sum+=V[y][*it].w_sum;
V[x][*it].num+=V[y][*it].num;
}
}
void DFS(int x,int fa,int dep)
{
int i,j;
for(i=0;i<R[x].size();i++)
{
j=R[x][i];
if(j==fa)continue;
DFS(j,x,dep+1);
for(set<int>::iterator it=Dep[j].begin();it!=Dep[j].end();it++)Dep[x].insert(*it);
comb(x,j,dep);
}
Dep[x].insert(dep);
V[x][dep].w_sum+=a[x],V[x][dep].num++;
}
int main()
{
int i,u,v;
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=0;i<n-1;i++)
{
scanf("%d%d",&u,&v);
R[u].push_back(v),R[v].push_back(u);
}
DFS(1,0,1);
for(i=1;i<=n;i++)printf("%lld ",ans[i]);
return 0;
}F-几何带师
完全不会，放弃治疗。
若题解出现了部分错误，还望大佬轻喷，完结撒花。
京公网安备 11010502036488号