额，切掉之后才知道有个东西叫分层图？？
就是瞎鸡儿连边，然后跑最短路就行了：
#include<iostream>
#include<cstdio>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
#define in read()
#define fur(i,a,b) for(int i=a;i<=b;i++)
#define pa pair<int,int>
#define heep __gnu_pbds::priority_queue<pa,greater<pa> >
#define nm make_pair
#define int long long
const int inf=1e18;
const int xx=1e5+101;
heep q;
heep::point_iterator id[xx*10];
int dis[xx*10];
int head[xx],cnt=0,s,t,n,m,k;
struct edge{int to,val,nxt;}e[xx*10];
inline int read()
{
int x=0;
char ch=getchar();
for(;!isalnum(ch);ch=getchar());
for(;isalnum(ch);ch=getchar()) x=x*10+ch-'0';
return x;
}
inline void add(int u,int v,int w)
{
e[++cnt]=(edge){v,w,head[u]};
head[u]=cnt;
}
inline void dij()
{
fur(i,0,n*(k+1)) dis[i]=inf;
fur(i,0,k) dis[s+i*n]=0,id[s+i*n]=q.push(nm(0,s+i*n));
while(!q.empty())
{
int w=q.top().second,x=w%n,z=w/n;
q.pop();
for(int v=head[x];v;v=e[v].nxt)
{
int y=e[v].to;
if(dis[x+z*n]+e[v].val<dis[y+z*n])
{
dis[y+z*n]=dis[x+z*n]+e[v].val;
if(id[y+z*n]!=0) q.modify(id[y+z*n],nm(dis[y+z*n],y+z*n));
else id[y+z*n]=q.push(nm(dis[y+z*n],y+z*n));
}
if(z<k)
{
int i=z,j=z+1;
if(dis[x+i*n]<dis[y+j*n])
{
dis[y+j*n]=dis[x+i*n];
if(id[y+j*n]!=0) q.modify(id[y+j*n],nm(dis[y+j*n],y+j*n));
else id[y+j*n]=q.push(nm(dis[y+j*n],y+j*n));
}
}
}
}
}
signed main()
{
n=in;m=in;k=in;
s=in;t=in;
fur(i,1,m)
{
int x=in,y=in,z=in;
add(x,y,z);
add(y,x,z);
}
dij();
printf("%lld\n",dis[t+k*n]);
return 0;
}考完发现是二分，贼尴尬，感觉自己就是个\(sb\)，都忘记中位数定理的具体内容了，无奈……
但其实可以持取，枚举左端点，右端点不断右移，可以做到\(O(n)\):
#include<iostream>
#include<cstdio>
using namespace std;
#define re register
#define fur(i,a,b) for(re int i=a;i<=b;++i)
#define fdr(i,a,b) for(re int i=a;i>=b;--i)
#define in read()
#define int long long
inline int read()
{
int x=0;
char ch=getchar();
for(;!isalnum(ch);ch=getchar());
for(;isalnum(ch);ch=getchar()) x=x*10+ch-'0';
return x;
}
const int xx=1e5+10;
int x[xx],xu[xx],xd[xx];
int k,n,m;
inline bool check(int i,int j)
{
if(j>n) return false;
int mid=(i+j)>>1;
return (xu[mid]-xu[i]-(i-1)*(x[mid]-x[i]))+(xd[mid]-xd[j]-(n-j)*(x[j]-x[mid]))<=k;
}
signed main()
{
n=in;m=in;k=in;
fur(i,1,n) x[i]=in;
fur(i,2,n) xu[i]=xu[i-1]+(i-1)*(x[i]-x[i-1]);
fdr(i,n-1,1) xd[i]=xd[i+1]+(n-i)*(x[i+1]-x[i]);
int ans=0,r=1;
fur(l,1,n)
{
while(check(l,r)&&r<=n+1) ++r;
ans=max(ans,r-l);
}
cout<<ans<<endl;
return 0;
}额，傻逼贪心？
在容器里的东西肯定是挑出其中对应的下一个数最远的一个丢弃，这样肯定比丢其他的不劣，然后……题就做完了……
（可我他妈连题都没看啊！！！）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
#define in read()
#define re register
#define fur(i,a,b) for(re int i=a;i<=b;++i)
#define fdr(i,a,b) for(re int i=a;i>=b;--i)
#define cl(a,b) memset(a,b,sizeof(a))
#define jinitaimei signed
#define pa pair<int,int>
#define heep __gnu_pbds::priority_queue<pa>
#define nm make_pair
inline int read()
{
int x=0;
char ch=getchar();
for(;!isalnum(ch);ch=getchar());
for(;isalnum(ch);ch=getchar()) x=x*10+ch-'0';
return x;
}
const int xx=1e5+10;
int x[xx],y[xx];
int nxt[xx],nxit[xx];
bool choose[xx];
heep q;
heep::point_iterator id[xx];
jinitaimei main()
{
int n=in,k=in;
fur(i,1,n) y[i]=x[i]=in;
sort(y+1,y+n+1);
int all=unique(y+1,y+n+1)-y-1;
fur(i,1,n) x[i]=lower_bound(y+1,y+all+1,x[i])-y;
fur(i,0,n) nxt[i]=n+1;
nxit[n+1]=n+1;
fdr(i,n,1) nxit[i]=nxt[x[i]],nxt[x[i]]=i;
int num=0,ans=0;
fur(i,1,n)
{
if(choose[x[i]])
{
q.modify(id[x[i]],nm(nxit[i],x[i]));
continue;
}
++ans;
if(num<k) ++num;
else choose[q.top().second]=false,id[q.top().second]=0,q.pop();
id[x[i]]=q.push(nm(nxit[i],x[i]));
choose[x[i]]=true;
}
cout<<ans<<endl;
return 0;
}额，又是一道我没看的傻逼题……
一棵树根为\(i\)的树能被分成每块大小为\(T\)的充要条件是其子树有\(\frac{size_i}{T}\)个\(size\)为\(T\)倍数的子树，应该很容易证吧，就是加加减减一下就可以了……
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
#define in read()
#define re register
#define fur(i,a,b) for(re int i=a;i<=b;++i)
#define fdr(i,a,b) for(re int i=a;i>=b;--i)
#define jinitaimei signed
//#define int long long
inline int read()
{
int x=0;
char ch=getchar();
for(;!isalnum(ch);ch=getchar());
for(;isalnum(ch);ch=getchar()) x=x*10+ch-'0';
return x;
}
const int xx=1e6+10;
int sz[xx],fa[xx],cntt[xx];
vector<int>e[xx];
inline void add(int u,int v){e[u].push_back(v);}
inline void dfs(int g)
{
sz[g]=1;
fur(i,0,(int)e[g].size()-1)
{
int j=e[g][i];
if(j==fa[g]) continue;
fa[j]=g;
dfs(j);
sz[g]+=sz[j];
}
++cntt[sz[g]];
}
jinitaimei main()
{
int n=in;
fur(i,1,n-1)
{
int x=in,y=in;
add(x,y);
add(y,x);
}
dfs(1);
int ans=0;
fur(i,1,n) if(n%i==0)
{
int sum=0;
for(int j=i;j<=n;j+=i) sum+=cntt[j];
if(sum==n/i) ++ans;
}
cout<<ans<<endl;
return 0;
}看到栅栏数为\(5\)就想到状压了，可一直没想到好的转移与环的情况怎么处理，后来看了题解如茅塞顿开……
嗯……设\(f_{i,j}\)为到第\(i\)个栅栏到后\(5\)个栅栏的状态为\(j\)时能使小朋友高兴的最大方案数。
转移方程有个很好的\(f_{i,j}=max(f_{i-1,(j\&15)<<1},f_{i-1,(j\&15)<<1|1})+num_{i,j}\)，而\(num_{i,j}\)为当\(i\)个栅栏状态为\(j\)能使起点为\(i\)的小朋友开心的数量。
转移需要这些代码：
fur(i,1,N)
{
int x=in,y=in,z=in,hate=0,love=0;
fur(j,1,y)
{
int q=in;q=(q-x+n)%n;
hate|=1<<q;
}
fur(j,1,z)
{
int q=in;q=(q-x+n)%n;
love|=1<<q;
}
fur(j,0,31) if((j&hate)||(~j&love)) ++num[x][j];
} 对于环，我们可以枚举最后一个栅栏的情况，然后直接转移即可
时间复杂度\(O(2^{10}n)\):
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define in read()
#define re register
#define fur(i,a,b) for(re int i=a;i<=b;++i)
#define fdr(i,a,b) for(re int i=a;i>=b;--i)
#define cl(a,b) memset(a,b,sizeof(a))
#define jinitaimei signed
//#define int long long
inline int read()
{
int x=0;
char ch=getchar();
for(;!isalnum(ch);ch=getchar());
for(;isalnum(ch);ch=getchar()) x=x*10+ch-'0';
return x;
}
const int xx=1e5+10;
int dp[xx][33];
int num[xx][33];
jinitaimei main()
{
int n=in,N=in;
fur(i,1,N)
{
int x=in,y=in,z=in,hate=0,love=0;
fur(j,1,y)
{
int q=in;q=(q-x+n)%n;
hate|=1<<q;
}
fur(j,1,z)
{
int q=in;q=(q-x+n)%n;
love|=1<<q;
}
fur(j,0,31) if((j&hate)||(~j&love)) ++num[x][j];
}
int ans=0;
fur(i,0,31)
{
cl(dp[0],0x8f);dp[0][i]=0;
fur(j,1,n) fur(k,0,31) dp[j][k]=max(dp[j-1][(k&15)<<1],dp[j-1][(k&15)<<1|1])+num[j][k];
ans=max(ans,dp[n][i]);
}
cout<<ans<<endl;
return 0;
}
原文：https://www.cnblogs.com/ALANALLEN21LOVE28/p/11437823.html