题面:bzoj
题解：神奇的\(dp\)
先按长度把边排序
指定必需走前\(l\)条边，枚举\(l\)
设\(dis[i][j][k]\)暗示当前到了\(i\)节点，已走过了\(j\)条前\(l\)条边，用了\(k\)次交换次数

B 找零钱的洁癖

题面：bzoj
题解：更为神奇
首先直接bfs，到必然水平break
其次乱贪心
据\(\text{M}\)\(\color{red}{\text{_sea}}\)说正解是整数规划？
不会，告别

H 柠檬

题面：Luogu
题解：斜率优化
首先有一个显然的性质就是：一段两端肯定不异并且是这一段选定的巨细（否则可以证明功效肯定小于这种）
设\(dp[i]\)暗示前\(i\)个的答案，\(s[i]\)暗示\(i\)是\(1\sim n\)内不异巨细的第几个
\[dp[i]=max_{0<j\leq i}^{a[i]==a[j]}{\{dp[j-1]+a[i]*(s[i]-s[j]+1)^2\}}\]
于是有
只与\(i\)有关的：\(a[i]*s[i]^2+2*a[i]*s[i]+a[i]\)
只与\(j\)有关的：\(dp[j-1]+a[i]*s[j]^2-2*a[i]*s[j](a[i]==a[j])\)
既和\(i\)有关又和\(j\)有关的：\(-2a[i]s[i]s[j]\)
于是套斜率优化板子，维护上凸壳，栈顶最优决策
注意要先把本身丢进去再决策
由于空间问题用\(vector\)模拟栈

I 分特产

题面：Luogu
题解：容斥
设至少\(x\)小我私家什么都没有
也就是把\(a[i]\)个特产分给\(n-x\)小我私家
于是在\(n-x-1\)个空格里随意插\(a[i]\)块隔板
按照乘法道理，对每一种特产考虑最后再乘起来
方案数就是\(\prod_{i=1}^{m}{C_{n-x-1+a[i]}^{a[i]}}\)
反演一下（对比之下我更喜欢这个而不是容斥）
答案就是刚好0人什么都没有
\[ans=\sum_{i=0}^{n-1}{(-1)^iC_{n}^{i}\prod_{j=1}^{m}{C_{n-i-1+a[j]}^{a[j]}}}\]

J 棒棒糖

题面：Luogu
是重题
建一颗主席树，如果\([1,mid]\)内没有这么多个数字就显然没有，，再看\([mid+1,r]\)

K 任务调理

题面：bzoj
题解：可并堆
改削操纵就把这个点抠出来（合并它的摆布儿子），再塞回去
据说可以用pb_ds水过去（然而我搞了一下午没搞出来）

code A

#include<bits/stdc++.h> using namespace std; #define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout); inline void read(int& x) { x=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=x*10+c-'0',c=getchar(); } #define maxn 155 struct Edge { int fr,to,val; }eg[maxn<<1]; int head[maxn],edgenum; inline void add(int fr,int to,int val) { eg[++edgenum]=(Edge){head[fr],to,val}; head[fr]=edgenum; } struct Road { int l,r,val; inline friend bool operator < (Road a,Road b) { return a.val<b.val; } }d[maxn]; struct Node { int x,y,z,dis; inline friend bool operator < (Node a,Node b) { return a.dis>b.dis; } }; priority_queue<Node> q; int dis[52][maxn][maxn],vis[52][maxn][maxn]; int n,m,k,ans=0x7fffffff; inline void work(int l) { memset(vis,0,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); dis[1][0][0]=0; q.push((Node){1,0,0}); int x,y,z; while(!q.empty()) { x=q.top().x,y=q.top().y,z=q.top().z; q.pop(); if(vis[x][y][z]) continue; vis[x][y][z]=1; for(int i=head[x];i;i=eg[i].fr) { #define to eg[i].to if(i<=(l<<1)) { if(y<l&&dis[to][y+1][z]>dis[x][y][z]+d[y+1].val) dis[to][y+1][z]=dis[x][y][z]+d[y+1].val,q.push((Node){to,y+1,z,dis[to][y+1][z]}); } else { if(y<l&&z<k&&dis[to][y+1][z+1]>dis[x][y][z]+d[y+1].val) dis[to][y+1][z+1]=dis[x][y][z]+d[y+1].val,q.push((Node){to,y+1,z+1,dis[to][y+1][z+1]}); if(dis[to][y][z]>dis[x][y][z]+eg[i].val) dis[to][y][z]=dis[x][y][z]+eg[i].val,q.push((Node){to,y,z,dis[to][y][z]}); } #undef to } } for(int i=0;i<=k;++i) ans=min(ans,dis[n][l][i]); } int main() { read(n),read(m),read(k); for(int i=1;i<=m;++i) read(d[i].l),read(d[i].r),read(d[i].val); sort(d+1,d+m+1); for(int i=1;i<=m;++i) add(d[i].l,d[i].r,d[i].val),add(d[i].r,d[i].l,d[i].val); for(int i=0;i<=m;++i) work(i); printf("%d\n",ans); return 0; }

B code

#include<bits/stdc++.h> using namespace std; #define ll long long #define pa pair<ll,ll> #define mp make_pair #define inf 0x7fffffff queue<pa> q; //unordered_map<ll,bool> m; map<ll,bool> m; ll n,a[105],x; inline ll bfs() { q.push(mp(0,0)); ll val,step,tp; while(!q.empty()) { val=q.front().first,step=q.front().second; q.pop(); for(int i=1;i<=n;++i) { if(q.size()>=1000000) return inf; val<=x?tp=val+a[i]:tp=val-a[i]; if(tp==x) return step+1; if(m[tp]) continue; m[tp]=1; q.push(mp(tp,step+1)); } } return inf; } inline ll greedy() { ll step=0,sum=x; for(int i=n;i;--i) { if(!a[i]) continue; step+=sum/a[i]; sum-=sum/a[i]*a[i]; } return sum?inf:step; } int main() { //freopen("test.in","r",stdin); scanf("%lld",&x); if(!x) puts("0"); while(scanf("%lld",&a[++n])!=EOF); sort(a+1,a+n+1); printf("%lld\n",min(bfs(),greedy())); return 0; }

H code