4.1省选模拟
\(T1\)
\(dis(x,y)=dep(x)+dep(y)-2\times dep(lca(x,y))\)
显然重心最优
然后做一个匹配即可
#define Eternal_Battle ZXK
#include
#define int long long
#define MAXM 200005
#define MAXN 200005
using namespace std;
int head[MAXN],nxt[MAXN],val[MAXN],siz[MAXN],to[MAXN],tot;
int Max[MAXN],Ans,rt,n;
void add(int u,int v,int w)
{
tot++;
to[tot]=v;
val[tot]=w;
nxt[tot]=head[u];
head[u]=tot;
}
void dfs_rt(int now,int fa)
{
siz[now]=1;
for(int i=head[now];i;i=nxt[i])
{
int y=to[i];
if(y==fa) continue;
dfs_rt(y,now);
siz[now]+=siz[y];
Max[now]=max(Max[now],siz[y]);
}
Max[now]=max(Max[now],n-siz[now]);
if(Max[now] In[MAXN];
set Min;
set > Set;
void dfs_vis(int now,int fa,int fg)
{
siz[fg]++;
In[fg].insert(now);
vis[now]=fg;
for(int i=head[now];i;i=nxt[i])
{
int y=to[i];
if(y==fa) continue;
dfs_vis(y,now,fg);
}
}
void Link(int x,int y)
{
// cout<<"Link: "<first==n-x+1&&Set.rbegin()->second!=vis[x])
{
res=*In[Set.rbegin()->second].begin();
}
else
{
res=vis[*Min.begin()]!=vis[x]||x==rt?*Min.begin():*next(Min.begin());
}
Link(x,res);
return res;
}
signed main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
scanf("%lld",&n);
for(int i=1,u,v,w;i \(T2\)
诚不欺我,果然有\(dp\)
\(k<=12\)可以状压,\(m<=4\)那么状态转移数目较少
那么转移易得
\(dp[i][j][S]\)表示我们目前填第\(i\)个数字,已经填了\(j\)个位置,目前大于等于\(i-m\)的位置有哪些的方案数
由于我们是递增填数,就可以实时更新,又因为每个数不同,那么记录一下哪些在原序列里就好了
#include
#define mod 1000000007
#define MAXN 205
using namespace std;
int n,k,m,Sum;
struct Mat
{
int jz[MAXN][MAXN];
Mat operator * (Mat x)
{
Mat res;
memset(res.jz,0,sizeof(res.jz));
for(int i=0;i<=Sum;i++)
{
for(int j=0;j<=Sum;j++)
{
for(int k=0;k<=Sum;k++)
{
res.jz[i][j]=(res.jz[i][j]+1ll*jz[i][k]*x.jz[k][j])%mod;
}
}
}
return res;
}
}b,St;
int main()
{
cin>>n>>k>>m;
Sum=k<>=1;
}
cout< \(T3\)
大家都会猜结论\(QAQ,\)谁能教教我怎么猜中啊
考虑交换的中心点必然\(p_i=i\)
然后把\(p_i=i\)去掉,分为若干区间,区间内部值域相等
若出现超过长度为\(3\)的下降子序列就不合法
缩进寄了dk
#include
#define MAXN 600005
using namespace std;
int n,p[MAXN],a[MAXN],Min[MAXN];
int stk[MAXN],top;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&p[i]);
}
p[n+1]=n+1,p[0]=0;
for(int i=1;i<=n;i++)
{
if(p[i-1]!=i-1&&p[i]!=i&&p[i+1]!=i+1)
{
puts("No");
return 0;
}
a[i]=(i==p[i]);
}
for(int i=1,j;i<=n;i=j+1)
{
for(j=i;j=1;k--)
{
Min[k]=min(Min[k+1],stk[k]);
}
int Max=stk[1];
for(int k=2;k