三屏合一网站开发,网站建设预算申请表,搜索引擎大全,wordpress文章类插件正题
题目链接:https://www.luogu.com.cn/problem/P6775 题目大意 nnn种原材料#xff0c;第iii个有did_idi个#xff0c;mmm道菜品都需要kkk个原料而且每道菜最多只能用两种材料。
要求构造方案使得满足条件。 1≤n≤500,n−2≤m≤5000,1≤k≤5000,(∑i1ndi)mk1\leq n\l…正题
题目链接:https://www.luogu.com.cn/problem/P6775 题目大意
nnn种原材料第iii个有did_idi个mmm道菜品都需要kkk个原料而且每道菜最多只能用两种材料。
要求构造方案使得满足条件。
1≤n≤500,n−2≤m≤5000,1≤k≤5000,(∑i1ndi)m×k1\leq n\leq 500,n-2\leq m\leq 5000,1\leq k\leq 5000,(\sum_{i1}^nd_i)m\times k1≤n≤500,n−2≤m≤5000,1≤k≤5000,(∑i1ndi)m×k 解题思路
额去年线上赛的时候一点想法都没有是时候轮到我来一雪前耻历虽然这题还是很难
首先我们注意到一个特殊的条件n−2≤mn-2\leq mn−2≤m看上去没什么想法但是看一下数据范围有n−1mn-1mn−1m和n−1≤mn-1\leq mn−1≤m两个部分分。
先考虑n−1mn-1mn−1m的就是原料比菜品多一个那么我们一定有dminkd_{min}kdmink而且dmindmaxk(n≠2)d_{min}d_{max}k(n\neq 2)dmindmaxk(n2)。
嗯所以我们每次拿最少的一个原料和最多的一个原料做一个菜那么依旧满足n−1mn-1mn−1m的条件。
然后考虑n≤mn\leq mn≤m的情况不难发现肯定有dmax≥kd_{max}\geq kdmax≥k所以我们直接拿最多的来做一道菜那么要不n−1,m−1n-1,m-1n−1,m−1要么m−1m-1m−1变成n−1mn-1mn−1m的情况。
之后是n−2mn-2mn−2m的做法这个是本题的核心难点。
在洛谷题解上看到过一个有趣的证明我们可以把原料看成一个点菜品所用的两个原料看成一条边那么因为mn−2mn-2mn−2所以这张图一定是不连通的那么至少会被分成两棵树。
发现对于树就是mn−1mn-1mn−1的情况所以其实是相当于我们要把mn−2mn-2mn−2的情况分成两个mn−1mn-1mn−1的情况。
而且因为mn−1mn-1mn−1一定有解所以我们只需要考虑怎么分就好了。
相当于我们要找出一个原料集合SSS使得 ∑i∈Sdi(∣S∣−1)k⇒∑i∈S(di−k)−k\sum_{i\in S}d_i(|S|-1)k\Rightarrow \sum_{i\in S}(d_i-k)-ki∈S∑di(∣S∣−1)k⇒i∈S∑(di−k)−k
然后直接dpdpdp的复杂度是O(Tn2k)O(Tn^2k)O(Tn2k)的加个bitsetbitsetbitset优化就是O(Tn2kw)O(T\frac{n^2k}{w})O(Twn2k)可以通过本题 code
#includecstdio
#includecstring
#includealgorithm
#includevector
#includebitset
using namespace std;
const int N510,S5e610,W2500000;
struct node{int w,id;
}d[N];
struct cnode{int a,A,b,B;
}v[N*10];
int T,n,m,k,tot;
bool vis[N];
bitsetSf[N];
vectornode u;
bool cmp(node x,node y)
{return x.wy.w;}
void Add(int a,int A,int b0,int B0)
{v[tot](cnode){a,A,b,B};return;}
void solve(int m,vectornode d){int nd.size();tot0;while(mmn){sort(d.begin(),d.end(),cmp);Add(d[n-1].id,k);d[n-1].w-k;m--;if(!d[n-1].w)d.pop_back(),n--;}if(mn-1){while(m){sort(d.begin(),d.end(),cmp);swap(d[0],d[n-1]);Add(d[n-1].id,d[n-1].w,d[0].id,k-d[n-1].w);d[0].w-k-d[n-1].w;d.pop_back();n--;m--;if(!d[0].w)swap(d[0],d[n-1]),d.pop_back(),n--;}}for(int i1;itot;i){if(v[i].b)printf(%d %d %d %d\n,v[i].a,v[i].A,v[i].b,v[i].B);else printf(%d %d\n,v[i].a,v[i].A);}u.clear();return;
}
int main()
{scanf(%d,T);f[0][W]1;while(T--){scanf(%d%d%d,n,m,k);for(int i1;in;i)scanf(%d,d[i].w),d[i].idi;if(mn-2){for(int i1;in;i){int tmpd[i].w-k;if(tmp0){f[i]f[i-1];f[i]|(f[i-1]tmp);}else{f[i]f[i-1];f[i]|(f[i-1](-tmp));}}if(!f[n][W-k])puts(-1);else{memset(vis,0,sizeof(vis));for(int in,zW-k;i1;i--){int tmpd[i].w-k;if(f[i-1][z-tmp])u.push_back(d[i]),vis[i]1,z-tmp;}solve(u.size()-1,u);for(int i1;in;i)if(!vis[i])u.push_back(d[i]);solve(u.size()-1,u);}}else{for(int i1;in;i)u.push_back(d[i]);solve(m,u);}}return 0;
}
