ABC374 E
最大最小值，想到二分，问题是怎么 check。
其实就是对两个种有价值有重量的物品，求达到规定价值的最小重量。
只有两种物品，而且数据范围很小，考虑贪心。
假设 \(a\) 的性价比较高，\(b\) 的性价比较低，那么不可能选太多 \(b\)。
也就是如果能用 \(a\) 代替的就用 \(a\) 代替。所以选 \(b\) 的总价值不能超过 \(lcm(a,b)\)。否则能用 \(a\) 替换更优。
发现 \(a\) 最大只有 \(100\)，所以 \(b\) 最多选 \(100\) 个。暴力枚举。
code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 105;
int n; LL X;
int a[N],b[N],p[N],q[N];bool check(int w)
{LL sum=0;for(int i=1;i<=n;i++){LL tmp=1e18;for(int j=0;j<=100;j++){int k=ceil((1.0*w-j*b[i])/a[i]); k=max(k,0);tmp=min(tmp,1ll*k*p[i]+1ll*j*q[i]);if(j*b[i]>w) break;}sum+=tmp;}return sum<=X;
}
int main()
{// freopen("in.in","r",stdin);// freopen("out.out","w",stdout);scanf("%d%lld",&n,&X);for(int i=1;i<=n;i++){scanf("%d%d%d%d",&a[i],&p[i],&b[i],&q[i]);if(a[i]*q[i]<b[i]*p[i]) swap(q[i],p[i]),swap(a[i],b[i]);}int l=0,r=1e9+7,ans=0;while(l<=r){int mid=(1ll*r-l>>1)+l;if(check(mid)) ans=mid,l=mid+1;else r=mid-1;}printf("%d\n",ans);return 0;
}
CF997 C2
有点难调。
容易发现是否合法只与 \(a\) 的元素在 \(b\) 中第一次出现的位置有关。
对于 \(a\) 序列来说，在 \(b\) 中的第一次出现的位置应该是单调递增的。
所以直接用 set 维护位置，每次更新就行。（不需要特殊处理第一个位置）
code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
int T;
const int N = 2e5+5;
int n,m,q;
int a[N],b[N],ys[N];
set<int> p[N];
int main()
{// freopen("in.in","r",stdin);// freopen("out.out","w",stdout);scanf("%d",&T);while(T--){scanf("%d%d%d",&n,&m,&q);for(int i=1;i<=n;i++) scanf("%d",&a[i]),p[a[i]].clear(),p[a[i]].insert(m+1),ys[a[i]]=i;for(int i=1;i<=m;i++){scanf("%d",&b[i]);}for(int i=1;i<=m;i++){p[b[i]].insert(i);}int res=0;for(int i=2;i<=n;i++) if(*p[a[i]].begin()<*p[a[i-1]].begin())res++;if(!res) printf("YA\n");else printf("TIDAK\n");while(q--){int x,y; scanf("%d%d",&x,&y);if(ys[b[x]]-1>=1&&*p[b[x]].begin()<*p[a[ys[b[x]]-1]].begin())res--;if(ys[b[x]]+1<=n&&*p[a[ys[b[x]]+1]].begin()<*p[b[x]].begin())res--;p[b[x]].erase(x);if(ys[b[x]]-1>=1&&*p[b[x]].begin()<*p[a[ys[b[x]]-1]].begin())res++;if(ys[b[x]]+1<=n&&*p[a[ys[b[x]]+1]].begin()<*p[b[x]].begin())res++;if(ys[y]-1>=1&&*p[y].begin()<*p[a[ys[y]-1]].begin())res--;if(ys[y]+1<=n&&*p[a[ys[y]+1]].begin()<*p[y].begin())res--;p[y].insert(x);if(ys[y]-1>=1&&*p[y].begin()<*p[a[ys[y]-1]].begin())res++;if(ys[y]+1<=n&&*p[a[ys[y]+1]].begin()<*p[y].begin())res++;b[x]=y;if(res==0) printf("YA\n");else printf("TIDAK\n"); }}
}
CF997 E1
出题人贴心地给出了 \(n^3\) 的范围。直接考虑 floyd。
跑完最短路后暴力枚举选的点就好，仍然是 \(n^3\) 暴力。
code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
int T;
const int N = 405;
int n,m,q;
int f[N][N],a[N],now[N],ttt[N];
LL sum;
bool vs[N];
int main()
{// freopen("in.in","r",stdin);// freopen("out.out","w",stdout);scanf("%d",&T);while(T--){sum=0;scanf("%d%d%d",&n,&m,&q);memset(vs,0,sizeof(vs));memset(f,0x3f,sizeof(f));for(int i=1;i<=q;i++) scanf("%d",&a[i]);for(int i=1;i<=m;i++){int x,y,z; scanf("%d%d%d",&x,&y,&z);f[x][y]=f[y][x]=z;}for(int i=1;i<=n;i++) f[i][i]=0;for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[i][j]=min(f[i][j],max(f[i][k],f[k][j]));int fl=0;sum=1e18;for(int i=1;i<=n;i++){LL tmp=0;for(int j=1;j<=q;j++) tmp+=f[i][a[j]];if(sum>tmp){for(int j=1;j<=q;j++) now[j]=f[i][a[j]];sum=tmp; fl=i;}}vs[fl]=1;printf("%lld ",sum);for(int i=2;i<=n;i++){if(i>=q) {printf("0 "); continue;}fl=0;for(int j=1;j<=q;j++) ttt[j]=now[j];for(int j=1;j<=n;j++) if(!vs[j]){LL tmp=0;for(int k=1;k<=q;k++) tmp+=min(f[j][a[k]],now[k]);if(tmp<sum){for(int k=1;k<=q;k++) ttt[k]=min(f[j][a[k]],now[k]);sum=tmp; fl=j;}}for(int j=1;j<=q;j++) now[j]=ttt[j];vs[fl]=1; printf("%lld ",sum);}putchar('\n');}
}
CF997 E2
要求 \(n^2\) 的复杂度，发现问题是求路径上最大边权的最小值。考虑Kruskal 生成树。
其实这个生成的是一个堆，将边权转化为点权，保证父亲的权值不小于儿子。
因此我们将问题转化为了树上问题，设计状态 \(f_{u,i}\) 表示以 \(u\) 为根的子树内有 \(i\) 个 servers。
从下向上更新，由于越往上权值越大，说明需要连接的最大边越大，所以需要连接的点一定尽量连深的点。
如果是 \(f_{son,0}\)，说明儿子这棵子树内没有 servers，那么如果以 \(u\) 根这棵子树内有servers（\(f_{u,1/2/3\dots}\)）,那么一定连这个更优。
此时最大边就是 \(va_u\)（根节点的权值），用子树内需要连接的点的个数（\(cnt_{son}\)） 乘上最大边就行。
如果以儿子为根的子树内已经有了，那直接相加更新就好。（\(f_{u,i+j}=\sum_i\sum_j f_{son_1,i}+f_{son_2,j}\)）
然后你发现重构树会使点数翻倍，空间直接炸。
小 trick，发现最终答案只关心根 \(f_{1,i}\)，所以 dp 数组用 vector，每更新完一个就返还空间，shrink_to_fit。
code
#include<bits/stdc++.h>
using namespace std;
int T;
#define LL long long
const int N = 1e4+5;
const LL inf = 1e15;
int n,m,q;
int num;
struct E {int u,v,w;} ed[N];
int fa[N],son[N][2],va[N],cnt[N];
inline int find(int x) {return x==fa[x]?(x):(fa[x]=find(fa[x]));}
vector<LL> f[N];
void dfs(int u)
{if(!son[u][0]&&!son[u][1]) return ;dfs(son[u][0]); dfs(son[u][1]);f[u].resize(cnt[u]+1,inf);for(int i=1;i<=cnt[son[u][1]];i++) f[u][i]=min(f[u][i],1ll*va[u]*cnt[son[u][0]]+f[son[u][1]][i]);for(int i=1;i<=cnt[son[u][0]];i++) f[u][i]=min(f[u][i],1ll*va[u]*cnt[son[u][1]]+f[son[u][0]][i]);for(int i=1;i<=cnt[son[u][0]];i++)for(int j=1;j<=cnt[son[u][1]];j++)f[u][i+j]=min(f[u][i+j],f[son[u][0]][i]+f[son[u][1]][j]);f[son[u][0]].clear(); f[son[u][0]].shrink_to_fit();f[son[u][1]].clear(); f[son[u][1]].shrink_to_fit();
}int main()
{// freopen("in.in","r",stdin);// freopen("out.out","w",stdout);scanf("%d",&T);while(T--){scanf("%d%d%d",&n,&m,&q);for(int i=1;i<=n<<1;i++){f[i].clear(); f[i].resize(1,inf);cnt[i]=0; fa[i]=i; son[i][0]=son[i][1]=0;}for(int i=1,x;i<=q;i++) scanf("%d",&x),cnt[x]=1,f[x].resize(2,inf),f[x][1]=0;for(int i=1;i<=m;i++)scanf("%d%d%d",&ed[i].u,&ed[i].v,&ed[i].w);num=n;sort(ed+1,ed+1+m,[&](E &x,E &y){return x.w<y.w;});for(int i=1;i<=m;i++){int fx=find(ed[i].u),fy=find(ed[i].v);if(fx==fy) continue;fa[fx]=fa[fy]=++num; va[num]=ed[i].w; son[num][0]=fx; son[num][1]=fy; cnt[num]=cnt[fx]+cnt[fy];}dfs(num);for(int i=1;i<=q-1;i++) printf("%lld ",f[num][i]);for(int i=q;i<=n;i++) printf("0 ");putchar('\n');}return 0;
}
ABC374F
思路来自 int_R
假设物品发出时间是 \(s_i\)，需求时间是 \(t_i\)，那么答案就是 \(\sum s - \sum t\)，发现后面是定值，可以直接处理。
我们要确定的就是所有物品发出时间的总和。
在能出发的时刻，要不然立即出发，要不然等下一个时刻出发，所以出发时间一定是 \(t_i+kx\)，也就是从某一个 \(t_i\) 开始后连续发送几次 \(x\)，然后等待。
设计状态 \(f_{i,j}\) 表示在 \(t_i\)，第 \(i\) 个物品的状态从即将出发到已经到达，此时还有 \(j\) 个物品没有出发（被跳过去了）。
转移即枚举这次运输会连续几个 \(x\)，注意细节。
马蜂抽象。
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 105,inf = 1e15;
int n,k,x,t[N],f[N][N],ans;main()
{freopen("in.in","r",stdin);freopen("out.out","w",stdout);scanf("%lld%lld%lld",&n,&k,&x);memset(f,0x3f,sizeof(f)); f[0][0]=0;for(int i=1;i<=n;i++) scanf("%lld",&t[i]),ans-=t[i];for(int i=1;i<=n;i++)//第 i-1 个到了，第 i 个将要发出时，还有 j 个没发出{for(int j=0;j<i;j++) f[i][j]=min(f[i-1][j],f[i][j]);for(int j=i;j>=1;j--) f[i][j]=f[i][j-1]; f[i][0]=inf;//第 i 个没发出，要加上。for(int j=1;j<=i;j++){int now=j,tm=t[i],sum=0,h=i+1;while(now){int cur=min(now,k);sum+=cur*tm; now-=cur; tm+=x;//发第 i 个。for(;h<=n&&t[h]<tm;h++) now++;f[h][now]=min(f[h][now],f[i][j]+sum);//第 i 个发完，该第 h 个了。}}}printf("%lld\n",ans+f[n+1][0]);return 0;
}
ABC375E
唐完了。。。
显然背包，发现数据范围较小，直接爆开四维 \(f_{i,j,k,h}\) 表示前 \(i\) 个物品，三组分别为 \(j,k,h\) 的最小交换次数，每个物品分讨放到哪组。
当然四维开不下，记录前缀和，把最后一维删掉，然后就做完了。
（WwW）
code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 105;
int aim,n,v[N],s[N];
int pos[N];
int f[105][1505][1505],ans;
int main()
{// freopen("in.in","r",stdin);// freopen("out.out","w",stdout);scanf("%d",&n);memset(f,0x3f,sizeof(f));for(int i=1;i<=n;i++) scanf("%d%d",&pos[i],&v[i]),s[i]=s[i-1]+v[i];if(s[n]%3) return printf("%d\n",-1),0;aim=s[n]/3;f[0][0][0]=0;for(int i=1;i<=n;i++){for(int j=0;j<=s[i];j++){for(int k=0;k<=s[i]-j;k++){if(j>=v[i]) f[i][j][k]=min(f[i-1][j-v[i]][k]+(pos[i]!=1),f[i][j][k]);if(k>=v[i]) f[i][j][k]=min(f[i-1][j][k-v[i]]+(pos[i]!=2),f[i][j][k]);if(s[i]-k-j>=v[i]) f[i][j][k]=min(f[i-1][j][k]+(pos[i]!=3),f[i][j][k]);}}}if(f[n][aim][aim]<=1e9) printf("%d\n",f[n][aim][aim]);else printf("-1\n");return 0;
}
ABC373E
有点ex。
二分，然后考虑 check。
思路很简单，代码很抽象，还是太蔡了。
code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define P pair<LL,int>
#define fi first
#define se second
const int N = 2e5+5;
int n,m;
LL k,s[N],ans[N];
P a[N];bool check(LL mid,int p)
{int ls=n-m+1-(p>=n-m+1);（要算上自己）int rs=lower_bound(a+ls,a+1+n,make_pair(a[p].fi+mid+1,0))-a-1;（小于等于的个数）return ((rs-ls+1)*(a[p].fi+mid+1)-(s[rs]-s[ls-1]))-(mid+1)*(p>=n-m+1)>k-mid;//（注意最后要减去自己的贡献）
}int main()
{// freopen("in.in","r",stdin);// freopen("out.out","w",stdout);scanf("%d%d%lld",&n,&m,&k);if(m==n){for(int i=1;i<=n;i++) printf("%d ",0); putchar('\n');return 0;}for(int i=1;i<=n;i++) scanf("%lld",&a[i].fi),a[i].se=i;sort(a+1,a+1+n);for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i].fi;k=k-s[n];for(int i=1;i<=n;i++){LL l=0,r=k+1,res=0;while(l<=r){LL mid=l+r>>1;if(check(mid,i)) res=mid,r=mid-1;else l=mid+1;}if(res==k+1) ans[a[i].se]=-1;else ans[a[i].se]=res;}for(int i=1;i<=n;i++) printf("%lld ",ans[i]); putchar('\n');return 0;
}
