1
贪心。在每一位(i)的之后,寻找(L=min(n-i,k))-意思是如果操作数(k)足够大,我可以在剩下的数中寻找字典序较小,否则在之后的(k)个字符中寻找较小。
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
long long n,k;
string a;
string find(string num,long long k){
if(k==0) return "";
if(num.size()*num.size()<k) {sort(num.begin(),num.end());return num;}
int cur=0,next=0;
for(int i=0;i<num.length();i++){
int index=0;
bool flag=false;
int tmp=num[i];
for(int m=i+1;m<i+1+k&&m<num.size();m++){
if(tmp>num[m]){
tmp=num[m];
index=m;
flag=true;
}
}
if(flag){
for(int j=index;j>=1;j--){
if(num[j]<num[j-1]){
swap(num[j],num[j-1]);
k--;
}
if(k==0) return num;
}
flag=false;
}
}
return num;
}
int main(){
freopen("escape.in","r",stdin);
freopen("escape.out","w",stdout);
scanf("%lld%lld",&n,&k);
cin>>a;
if(k==0){
cout<<a;
return 0;
}
cout<<find(a,k);
return 0;
}
线段树树状数组优化
将字符转为数字串,我们来看原串和答案串:
答案串[ ][ ][ ][ ][ ][ ][ ]
原来串[a][b][a][b][a][a][b]
答案串[a][ ][ ][ ][ ][ ][ ]
原来串[x][b][a][b][a][a][b]
答案串[a][a][ ][ ][ ][ ][ ]
原来串[x][b][x][b][a][a][b]
答案串[a][a][a][ ][ ][ ][ ]
原来串[x][b][x][b][x][a][b]
[若此时(k)无法使得最后一个a挪到前面,则移动第二位的b]
答案串[a][a][a][b][ ][ ][ ]
原来串[x][x][x][b][x][a][b]
最后使用树状数组维护挪到前面所需要的步数,如果有字符就为1,没有为0,求前缀和就好。
寻找最小字符貌似是枚举?
2
三个(O(n))输出
菊花图
每条路径一定是从叶节点到菊花的中心,再到另一个叶子,且只经过 3 个节点。设有 (s) 个叶节点的海拔小于菊花的中心,答案就是((_2^s))
链
枚举路径的海拔最高点。通过递推求出从该点出发往两侧的最长单调下降序列长度(L_1, L_2),那么以该点为最高点的合法路径数量为 (L_1 imes L_2)。
看作以 (n) 为根的有根树,每个点 (x) 都满足(fa_x > x)
把 (n) 作为根。注意到一条路径合法,当且仅当这条路径上深度最小的点不是路径的端点。枚举路径上深度最小的点,统计端点位于该点的两棵不同子树中的路径数量即可。
正解
先通过递推求出从每个点出发,海拔单调下降的路径数量。对于每个点 (x),设从 (x) 出发,到每棵子树中的海拔单调下降的路径数量分别为 (s_1, ..., s_k),那么以该点为海拔最高点的合法路径数量为
将所有点的贡献相加就是答案。
反思
二叉树想出来了。多叉想错了。哭。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 300005;
int n, f[N];
vector<int> e[N];
int main()
{
freopen("ride.in", "r", stdin);
freopen("ride.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
int x, y; scanf("%d%d", &x, &y);
e[x].push_back(y); e[y].push_back(x);
}
LL ans = 0;
for (int i = 1; i <= n; i++)
{
for (int x : e[i]) if (x < i) f[i] += f[x] + 1;
for (int x : e[i]) if (x < i) ans += (LL)(f[i] - f[x] - 1) * (f[x] + 1);
}
printf("%lld
", ans);
return 0;
}