T1
将字母按字典序枚举，将每一个字母尽量往首位移动，若无法满足，则向下一个枚举，对于一个字母该移动多少位，答案应该是\(pos-tot-1\)，tot是前面要多少个字母被移动过，我们发现每一个字母对\(tot\)的影响是对从\(pos\)一直到末位，所以可以联想到树状数组或线段树的区间修改单点查值，用一个树状数组维护这道题就完了
#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define int long long
#define in read()
using namespace std;
inline int read()
{
int data=0,w=1; char ch=getchar();
while(ch!=‘-‘&&(ch<‘0‘||ch>‘9‘)) ch=getchar();
if(ch==‘-‘) w=-1,ch=getchar();
while(ch>=‘0‘&&ch<=‘9‘) data=(data<<3)+(data<<1)+ch-‘0‘,ch=getchar();
return data*w;
}
inline void write(int x)
{
if(x<0) putchar(‘-‘),x=-x;
if(x>9) write(x/10);
putchar(x%10+‘0‘);
}
queue<int> q[27];
int c[500010],ans[500010];
int n,k,l=1,num=0,len;
void update(int k,int val) {while(k<=len) c[k]+=val,k+=lowbit(k);}
int query(int k)
{
int ans=0;
while(k>0) ans+=c[k],k-=lowbit(k);
return ans;
}
signed main()
{
// freopen("escape.in","r",stdin);
// freopen("escape.out","w",stdout);
n=in,k=in;
string s;
cin>>s;len=s.size();
for(int i=0;i<len;i++)
{
int a=s[i]-‘a‘+1;
q[a].push(i+1);
}
while(n--)
{
for(int i=1;i<=26;i++)
{
if(q[i].empty()) continue;
int pos=q[i].front();
int sum=pos-query(pos)-1;
if(k>=sum)
{
k-=sum;
ans[l]=pos;
l++;
update(pos,1);
q[i].pop();
break;
}
}
}
for(int i=1;i<l;i++)
{
printf("%c",s[ans[i]-1]);
}
}
T2
对于这道题我们可以发现当一个点对答案的贡献其实就是以这个点为中心的所有低于它的所有路径的组合，设这些路径是\(S_1,S_2,S_3……S_i\)，总和为\(T\)，那么一个点的贡献就是
\[S_1\times(T-S_1)+S_2\times(T-S_2)+……+S_i\times(T-S_i)
\]
化简一下可以得到
\[T^2-S_1^2-S_2^2-……-S_i^2
\]
于是我们只要找到每一个点周围有多少个小于它的点即可，对于这个我们可以考虑两次\(dfs\)，第一次存下子树内的答案，第二次从根往下递推求出答案
#include<bits/stdc++.h>
#define re register
#define ll long long
#define in read()
using namespace std;
inline int read()
{
int data=0,w=1; char ch=getchar();
while(ch!=‘-‘&&(ch<‘0‘||ch>‘9‘)) ch=getchar();
if(ch==‘-‘) w=-1,ch=getchar();
while(ch>=‘0‘&&ch<=‘9‘) data=(data<<3)+(data<<1)+ch-‘0‘,ch=getchar();
return data*w;
}
inline void write(int x)
{
if(x<0) putchar(‘-‘),x=-x;
if(x>9) write(x/10);
putchar(x%10+‘0‘);
}
const int N=300030;
int n;
struct edge{
int u,v,nxt;
}e[N<<1];
int first[N],cnt=1;
ll f[N],g[N],d[N];//子树内答案，总答案，平方和
ll ans;
inline void add(int u,int v){e[++cnt]=(edge){u,v,first[u]};first[u]=cnt;}
void dfs1(re int u,re int fa)
{
for(re int i=first[u];i;i=e[i].nxt)
{
re int v=e[i].v;
if(v==fa)continue;
dfs1(v,u);
if(u>v)
{
f[u] += f[v]+1;
d[u] += 1ll*(f[v]+1)*(f[v]+1);
g[u] = f[u];
}
}
}
void dfs2(re int u,re int fa)
{
for(re int i=first[u];i;i=e[i].nxt)
{
re int v=e[i].v;
if(v==fa)continue;
// cerr<<u<<" "<<v<<"\n";
if(v>u)
{
g[v] += g[u]+1;
d[v] += (g[u]+1)*(g[u]+1);
}
dfs2(v,u);
}
}
int main()
{
// int size=100<<20;
// __asm__ ("movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
n=in;
for(re int i=1;i<n;i++){
re int u=in,v=in;
add(u,v),add(v,u);
}
dfs1(1,0);
// for(re int i=1;i<=n;i++)cout<<f[i]<<"\n";
dfs2(1,0);
// for(re int i=1;i<=n;i++)cout<<g[i]<<"\n";
for(re int i=1;i<=n;i++) ans += 1ll*g[i]*g[i]-1ll*d[i];
write(ans);
exit(0);
}
T3
由于不是见到那路径，且边权皆为\(1\)，所以对于任意一个\(d\),若\(d\)为奇数，且\(d≥\)奇数到达终点的最短路径，那么\(d\)一定可以，同理偶数亦是如此，所以我们就可以分奇偶性来讨论，即维护一个奇偶最短路径与\(d\)比较即可。
时间复杂度\(O(n^2)\)，但空间还需要优化，所以可以离线省掉起点那一维。
还有此题需要特别多的特判
#include<bits/stdc++.h>
#define N 5050
#define M 100010
#define in read()
using namespace std;
inline int read()
{
int data=0,w=1; char ch=getchar();
while(ch!=‘-‘&&(ch<‘0‘||ch>‘9‘)) ch=getchar();
if(ch==‘-‘) w=-1,ch=getchar();
while(ch>=‘0‘&&ch<=‘9‘) data=(data<<3)+(data<<1)+ch-‘0‘,ch=getchar();
return data*w;
}
inline void write(int x)
{
if(x<0) putchar(‘-‘),x=-x;
if(x>9) write(x/10);
putchar(x%10+‘0‘);
}
int n,m,q;
struct edge{
int u,v,nxt;
}e[N<<1];
struct query{
int s,t,d,ans,id;
}p[M];
int dis[N][2],vis[N];
int first[N],cnt;
inline void add(int u,int v){e[++cnt]=(edge){u,v,first[u]};first[u]=cnt;}
inline bool cmp1(query a,query b){return a.s<b.s;}
inline bool cmp2(query a,query b){return a.id<b.id;}
queue<int>que;
void spfa(int s)
{
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
que.push(s);
dis[s][0]=0;//不可能在0时为奇数边
int flag=0;//特判
while(!que.empty())
{
int u=que.front();que.pop();vis[u]=0;
for(int i=first[u];i;i=e[i].nxt)
{
flag=1;
int v=e[i].v;
if(dis[v][0]>dis[u][1]+1)
{
dis[v][0]=dis[u][1]+1;
if(!vis[v]) que.push(v),vis[v]=1;
}
if(dis[v][1]>dis[u][0]+1)
{
dis[v][1]=dis[u][0]+1;
if(!vis[v]) que.push(v),vis[v]=1;
}
}
}
if(!flag) dis[s][0]=0x3f3f3f3f;
}
int main()
{
n=in,m=in,q=in;
for(int i=1,u,v;i<=m;i++) u=in,v=in,add(u,v),add(v,u);
for(int i=1;i<=q;i++)
{
int x=in,y=in,d=in;if(x>y) swap(x,y);
p[i].s=x,p[i].t=y,p[i].d=d,p[i].id=i;
}
sort(p+1,p+q+1,cmp1);
int num=0;
while(1)
{
if(num>=q) break;
int s=p[++num].s,flag=0;
spfa(s);
while(s==p[num].s)
{
if(!p[num].d) p[num].ans=(s==p[num].t);
else p[num].ans=(dis[p[num].t][p[num].d&1]<=p[num].d);
num++;flag=1;
}
if(flag) num--;
}
sort(p+1,p+q+1,cmp2);
for(int i=1;i<=q;i++)
{
if(p[i].ans) puts("Yes");
else puts("No");
}
}
T4
不会，先咕着吧