高考集训讲课(To 高一)
主要是怕下午讲着讲着把自己讲懵了，有一定的迷糊概率
经过机房的讨论，一致认为插头\(DP\)实用性不大，所以这次不讲了，先把重要的讲一讲。
顺便吐槽一下，凭什么另外几个人都是几个相互联系的知识点，到我这跨越这么大。。。
反正都是\(trick\)直接上题，没有知识点讲
状压\(DP\)
\(P7519\)滚榜
这是上次想讲的题
费用提前\(+\)状压\(DP\)
我们最后只求情况数，那么中间每个队伍的通过题数是无需关注的
从最开始考虑，我们暴力枚举每种情况，如何判断这种情况能否满足
我们有序列\(a_1,a_2...a_n\)，我们的要求是，每次\(a_{i-1}+b_{i-1}
考虑状压，\(dp[i][j][k]\)表示我们已经确定\(i\)状态的队伍分数，最后一个确定的是\(j\)，我们已经使用的题数是\(j\)
由于我们上一个都比前一个多，我们直接把后面的都加上一个这个数的值就好了(费用提前)
转移易得
//有个东西叫费用提前
//当你枚举这个选了多少个的时候,为了保证后面的也是
//那么后面的就统一加上,然后那么这个时候差不变
//该加多少还是加多少
#include
#define int long long
using namespace std;
int dp[1<<13][15][505],a[15],Ans,n,m;
int lowbit(int x)
{
return x&(-x);
}
int Count(int num)
{
int res=0;
while(num)
{
res++;
num-=lowbit(num);
}
return res;
}
signed main()
{
cin>>n>>m;
int Max=0;
a[0]=-1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]>a[Max])
{
Max=i;
}
}
for(int i=1;i<=n;i++)
{
int tar=n*(a[Max]-a[i]+(Max>(j-1))&1)
{
for(int k=0;k<=m;k++)
{
for(int z=1;z<=n;z++)
{
if(!((i>>(z-1))&1))
{
int tar=k+(n-Num)*max(0ll,a[j]-a[z]+(j \(P6622\)信号传递
比较套路的贡献分开计算
设我们目前放的点是\(x\)
\(x
\(x>y,res+=(kx+ky)\)
那么我们可以处理每个位置时候计算一下贡献就好了
可以参考一下注释
如果直接枚举边\(30pts\)，提前统计一下的话是\(70pts\)
\(30pts:\)
//可以提前对于每个点要传递出去的点连边
//然后转移的时候,枚举这一步要新增哪个点
//貌似不太能处理位置
//考虑怎么能够每次转移一个点求贡献,不需要知道前面的位置
//考虑结论:
//xy (res+=kx+ky)
//那么这样的话,考虑我们每个点记录一下贡献
//当前点连出的点有num1没有放置的,就-num*x
//当前点连出的点有num2已经放置的,就+num*k*x
//当前点连入的点有num3没有放置的,那么就+num*k*x
//当前点连入的点有num4已经放置的,那么就+num*x
//复杂度2^m*n?
#define Eternal_Battle ZXK
#include
#define MAXN 25
using namespace std;
int dp[1<<23],S[MAXN],n,m,k;
vectorrd[MAXN],fx[MAXN];
int lowbit(int x)
{
return x&(-x);
}
int Count(int x)
{
int res=0;
while(x)
{
x-=lowbit(x);
res++;
}
return res;
}
void Make(int x)
{
for(int i=0;i>i)&1);
}
cout<<" ";
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&S[i]);
}
for(int i=1;i>(j-1))&1)==0)
{
int num1=0,num2=0,num3=0,num4=0;
for(int k=0;k>(y-1))&1)==0) num1++;
else num2++;
}
for(int k=0;k>(y-1))&1)==0) num3++;
else num4++;
}
dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]-num1*x+num2*k*x+num3*k*x+num4*x);
// Make(i|(1<<(j-1)));
}
}
}
cout< \(70pts\)
考虑预处理转移\(zy[j][i]\)
表示\(j\)点在\(i\)状态转移会有多少代价
#define Eternal_Battle ZXK
#include
#define MAXN 25
using namespace std;
int rd[MAXN][MAXN],fx[MAXN][MAXN];
int dp[1<<23],S[MAXN],n,m,k;
int zy[24][1<<23];
int lowbit(int x)
{
return x&(-x);
}
int Count(int x)
{
int res=0;
while(x)
{
x-=lowbit(x);
res++;
}
return res;
}
void Make(int x)
{
for(int i=0;i>i)&1);
}
cout<<" ";
}
int main()
{
// freopen("dp1.in","r",stdin);
// freopen("dp1.in","r",stdin);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&S[i]);
}
for(int i=1;i>(j-1))&1)!=0) continue;
int x=Count(i)+1;
int num1=0,num2=0,num3=0,num4=0;
for(int k=1;k<=m;k++)
{
if(((i>>(k-1))&1)==0) num1+=rd[j][k],num3+=fx[j][k];
else num2+=rd[j][k],num4+=fx[j][k];;
}
zy[j][i]=-num1*x+num2*k*x+num3*k*x+num4*x;
}
}
for(int i=0;i<=(1<>(j-1))&1)==0)
{
dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]+zy[j][i]);
}
}
}
cout< 我们发现预处理复杂度有点高，那就考虑递推预处理
由于我们被卡空间，考虑把中间没用的那一位抹去左右拼接即可
#define Eternal_Battle ZXK
#include
#define MAXN 25
using namespace std;
int dp[1<<23],id[1<<23],S[MAXN],n,m,k;
int cnt[MAXN][MAXN];
int zy[24][1<<23];
int lowbit(int x)
{
return x&(-x);
}
int Count(int x)
{
int res=0;
while(x)
{
x-=lowbit(x);
res++;
}
return res;
}
void Make(int x)
{
for(int i=0;i>i)&1);
}
cout<<" ";
}
int main()
{
// freopen("dp1.in","r",stdin);
// freopen("dp1.in","r",stdin);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&S[i]);
}
for(int i=1;i=i) poz++;
zy[i][j]=zy[i][j^val]+cnt[poz][i]+cnt[i][poz]*k+cnt[i][poz]-cnt[poz][i]*k;
}
}
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=0;i<=(1<>(j-1)&1)==0)
{
int pS=i%(1< 计数
常见的话有\(DP\)计数，生成函数计数(后面这个和多项式有关，就交给\(HH\)力，我就不管了)
\(CF724F\ Uniformly\ Branched\ Trees\)
无论是什么计数，最开始的出发点就是找特征点
树上计数，每棵树最特殊的位置就是重心，因为重心只有\(1/2\)个
考虑组合问题，在\(x\)方案里面选\(t\)个，可重复
答案是\(\binom{x+t-1}{t}\)
感性想一想就是，我们每次选一个，在后面加一个方案表示，下一次可以选和这个一样的，然后我们相当于加了\(t-1\)个方案，一共在这些里面选\(t\)个
\(dp[i][j][k]\)表示节点数为\(i\)，有\(j\)棵子树，子树大小都不超过\(k\)，并且根是重心的树的数目
首先考虑单重心的情况\(n\%2=1\)
我们转移的时候，最外层枚举节点数\(i\)，内层枚举子树\(j\)，再枚举不超过节点数\(k\)，再枚举节点\(k\)
转移易得
\(dp[i][j][k]+=dp[i-t\times k][j-t][k-1]\times C(dp[k][d-1][k-1]+t-1,t)\)
然后双中心会算重，减去一部分就好了
\(Ans-=C(dp[n/2][d-1][n/2-1],2)\)
#include
#define int long long
#define MAXN 1005
using namespace std;
int fac[MAXN+5],inv[MAXN+5];
int dp[MAXN][20][MAXN],n,d,mod;
void Init()
{
fac[0]=inv[0]=1;
fac[1]=inv[1]=1;
for(int i=2;i<=MAXN;i++)
{
fac[i]=fac[i-1]*i%mod;
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}
for(int i=1;i<=MAXN;i++)
{
inv[i]=(inv[i-1]*inv[i])%mod;
}
}
int C(int n,int m)
{
if(nt*k&&j-t>=0;t++)
{
if(k!=1) dp[i][j][k]=(dp[i][j][k]+dp[i-t*k][j-t][k-1]*C(dp[k][d-1][k-1]+t-1,t)%mod)%mod;
else dp[i][j][k]=(dp[i][j][k]+dp[i-t*k][j-t][k-1]*C(dp[k][0][k-1]+t-1,t)%mod)%mod;
}
}
}
}
if(n%2) cout< \(P8329[ZJOI2022]\)树
这是一道练习题
树形\(dp\)，换根\(dp\)
\(P4323 [JSOI2016]\)独特的树叶
考场上想出正解，忘加\(ull\)丢掉\(40pts\)的一道题，我和题解
考虑暴力枚举哪个点是多余的，把剩下的部分树\(hash\)一下，判断是否一样即可，复杂度\(O(n^2)\)
考虑我们对第一棵树以每个根都\(hash\)一次，换根\(dp\)转移一下
第二棵树同样，遇到叶子时候查一下有没有这个树就好了
#include
#define ull unsigned long long
#define MAXN 200005
using namespace std;
ull hasha[MAXN],hash1[MAXN],Mid[MAXN];
int head[MAXN],nxt[MAXN],to[MAXN],Ans=MAXN,tot;
int pri[MAXN],siz[MAXN],du[MAXN],cnt;
vectorrd[MAXN];
bool vis[MAXN*10];
mapmp;
void add(int u,int v)
{
tot++;
to[tot]=v;
nxt[tot]=head[u];
head[u]=tot;
}
void Init()
{
for(int i=2;i<=MAXN*10-5;i++)
{
if(!vis[i])
{
pri[++cnt]=i;
}
for(int j=1;j<=cnt&&i*pri[j]<=MAXN*10-5;j++)
{
vis[i*pri[j]]=1;
if(i%pri[j]==0) break;
}
}
}
void dfs(int now,int fa)
{
siz[now]=1;
hasha[now]=1ull;
for(int i=head[now];i;i=nxt[i])
{
int y=to[i];
if(y==fa) continue;
dfs(y,now);
siz[now]+=siz[y];
hasha[now]+=hasha[y]*pri[siz[y]];
}
}
void dfs_gen(int now,int fa)
{
int now_siz=siz[now];
ull now_hash=hasha[now];
for(int i=head[now];i;i=nxt[i])
{
int y=to[i];
if(y==fa) continue;
hasha[now]-=(1ull*hasha[y]*pri[siz[y]]);
siz[now]-=siz[y];
siz[y]+=siz[now];
hasha[y]+=hasha[now]*pri[siz[now]];
Mid[y]=hasha[y];
mp[hasha[y]]=true;
dfs_gen(y,now);
siz[now]=now_siz;
hasha[now]=now_hash;
}
}
void dfs_b(int now,int fa)
{
siz[now]=1;
hash1[now]=1ull;
for(int i=0;i \(wqs\)二分
这东西挺重要的
大部分问题就是取恰好\(k\)个的问题
使用的前提是答案函数呈凸性
考虑选\(i\)个最优代价是\(f(i)\)，我们通过二分额外代价\(k\)，让多选一次的代价\(+k\)，那么我们最后选\(i\)个代价就是\(f(i)-k\times i\)，我们关于这个找到一个最大点，保证了是选这些的最大值，因为得到的点截距最大
\(P2619\) [国家集训队]\(Tree\ I\)
模板题，直接二分\(k\)跑\(kruskal\)
#include
#define INF 100000005
#define MAXN 500005
using namespace std;
inline int re()
{
int x = 0, p = 1;
char ch = getchar();
while(ch > '9' || ch < '0') {if(ch == '-') p = -1; ch = getchar();}
while(ch <= '9' and ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
return x * p;
}
struct node
{
int u,v,w,col;
}rd[MAXN];
int n,m,num,Ans,fa[MAXN];
bool cmp(node a,node b)
{
if(a.w==b.w) return a.col=num)
{
Ans=Sum-num*mid;
return 0;
}
return -1;
}
int main()
{
scanf("%d%d%d",&n,&m,&num);
for(int i=1;i<=m;i++)
{
rd[i].u=re();
rd[i].v=re();
rd[i].w=re();
rd[i].col=re();
}
int l=-111,r=111,res,mid;
while(l<=r)
{
mid=(l+r)>>1;
res=check(mid);
if(res==0)
{
l=mid+1;
}
else r=mid-1;
}
cout< \(P4983\)忘情
式子很好推。
说人话就是：分\(m\)段，每段价值为\((1+\sum_{i=1}^na_i)^2\)
\(emm\)，突然想到，这道题需要斜率优化，貌似还没讲。。。先咕了。
同余最短路
我在苏州集训学到的神奇东西，所以说是我带到机房的
题都比较简单，就口胡吧
\(P2371\)[国家集训队]墨墨的等式
\(P3403\)跳楼机