发现AT还是永远的神，但是光写不记录的话总感觉效果不大，因此从AGC024开始估计后面每一场都会有记录虽然大概率还是咕，前面一些场的记录/题解有时间就补上
题面很好搜，所以就不放了。
A:可以发现是呈指数级增长的，暴力模拟。要不以后A、B就不放上来了
B:跳了,没啥意思,非常一眼的结论
C:树状数组题(实际上可以用桶做到O(n))
在每一个位置上开一个vector，表示这个位置需要变成的数有哪些。
假设已经知道了 \(x_{i+1}\) 需要变成的数是 \(y_1,y_2...,y_n\)
那么在 \(x_i\) 需要变成的数则是 \(y_1-1,y_2-1...y_n-1,a_i\) （排过序且去过重的）。
然后统计一下每个vector的size，答案就是 \(\sum^{n}_{i=1}siz_i\)。
同时根据上面的性质也可以发现 \(a_i-a_{i-1}\leq 1\)，且 \(a_1=0\)，否则无解。
不难发现上面的过程可以打tag+树状数组优化一下，比较简单就不详细解释了。
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define ll long long
#define ui unsigned int
il ll read(){
bool f=true;ll x=0;
register char ch=getchar();
while(ch<‘0‘||ch>‘9‘) {if(ch==‘-‘) f=false;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
if(f) return x;
return ~(--x);
}
il int read(char *s){
int len=0;
register char ch=getchar();
while(ch==‘ ‘||ch==‘\n‘) ch=getchar();
while(ch!=‘ ‘&&ch!=‘\n‘&&ch!=EOF) s[++len]=ch,ch=getchar();
return len;
}
il void write(const ll &x){if(x>9) write(x/10);putchar(x%10+‘0‘);}
il void print(const ll &x) {x<0?putchar(‘-‘),write(~(x-1)):write(x);putchar(‘\n‘);}
il ll max(const ll &a,const ll &b){return a>b?a:b;}
il ll min(const ll &a,const ll &b){return a<b?a:b;}
const int MAXN=1e6+7;
ll n,x[MAXN],a[MAXN];
int t[MAXN];
#define lowbit(x) x&(-x)
void add(int k,int val){
if(!k) return;
for(;k<5e5;k+=lowbit(k)) t[k]+=val;
}
il int ask(int k){
int ans=0;
for(;k;k-=lowbit(k)) ans+=t[k];
return ans;
}
il int query(int l,int r){
if(l>r) return 0;
if(!r) return 0;
return ask(r)-ask(l-1);
}
int main(){
n=read();
a[0]=-1;
for(ri i=1;i<=n;++i){
a[i]=read();
if(a[i]-a[i-1]>1){
return !puts("-1");
}
}
if(a[1]!=0) return !puts("-1");
ll ans=0;
for(ri d=0,i=n;i;++d,--i){
if(!query(d+a[i],d+a[i]))
add(d+a[i],1);
ans+=query(d+1,5e5);
}
print(ans);
return 0;
}
D:挺不错一道题，如果想到了可以很轻松的写出来。
首先可以注意到，如果最后的树的直径为 \(L\),那么至少有 \(\lceil\frac{L}{2}\rceil\) 种本质不同的树，因为至少有 \(\lceil\frac{L}{2}\rceil\) 种树它们的最深深度不一样。
然后可以发现，这个下界非常好卡，当 \(n\) 是奇数的时候树的结构是关于一个一个顶点中心对称的，而当 \(n\) 是偶数的时候树的结构是关于一条边轴对称的。
因此可以枚举每一条边和每一个点，以它为根分别dfs一遍，每种情况的本质不同的树的数量就是整棵树的深度，叶子结点数则分别记录一下每一层儿子最多的点，然后从根往下递推。
总复杂度 \(O(n^2)\)，不知道为啥只开了 \(n\leq 100\)
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define ll long long
#define ui unsigned int
il ll read(){
bool f=true;ll x=0;
register char ch=getchar();
while(ch<‘0‘||ch>‘9‘) {if(ch==‘-‘) f=false;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
if(f) return x;
return ~(--x);
}
il int read(char *s){
int len=0;
register char ch=getchar();
while(ch==‘ ‘||ch==‘\n‘) ch=getchar();
while(ch!=‘ ‘&&ch!=‘\n‘&&ch!=EOF) s[++len]=ch,ch=getchar();
return len;
}
il void write(const ll &x){if(x>9) write(x/10);putchar(x%10+‘0‘);}
il void print(const ll &x) {x<0?putchar(‘-‘),write(~(x-1)):write(x);putchar(‘\n‘);}
il ll max(const ll &a,const ll &b){return a>b?a:b;}
il ll min(const ll &a,const ll &b){return a<b?a:b;}
#define pll pair<ll,ll>
#define fir first
#define sec second
ll mx;
pll ans=(pll){(ll)1e18,(ll)1e18};
const int MAXN=128;
int n;
struct edge
{
int u,v;
}e[MAXN];
vector<int> g[MAXN];
ll f[MAXN],pos;
void dfs(int u,int fa,int dep){
if(fa) f[dep]=max(f[dep],g[u].size()-1);
else f[dep]=max(f[dep],g[u].size());
mx=max(mx,dep);
for(ri i=0;i<g[u].size();++i){
int v=g[u][i];
if(v==fa) continue;
dfs(v,u,dep+1);
}
}
void solve_point(){
for(ri i=1;i<=n;++i){
memset(f,0,sizeof(f));
mx=0;
dfs(i,0,1);
ll c=1,tot=0;
for(ri i=1;i<mx;++i){
tot+=c;
c*=f[i];
}
pll now=(pll){mx,c};
if(now<ans){
ans=now;
pos=i;
}
}
}
void solve_edge(){
for(ri i=1;i<n;++i){
memset(f,0,sizeof(f));
mx=0;
int u=e[i].u,v=e[i].v;
dfs(u,v,1);
dfs(v,u,1);
ll c=2,tot=0;
for(ri i=1;i<mx;++i){
tot+=c;
c*=f[i];
}
pll now=(pll){mx,c};
if(now<ans){
ans=now;
pos=n+i;
}
}
}
int main(){
n=read();
for(ri i=1;i<n;++i){
int u=read(),v=read();
g[u].push_back(v),g[v].push_back(u);
e[i]=(edge){u,v};
}
solve_point();
solve_edge();
printf("%lld %lld\n",ans.fir,ans.sec);
// print(pos);
return 0;
}
原文：https://www.cnblogs.com/Guts/p/14647407.html