@AC君 关于制作菜品【NOI2020】
2026-02-07 13:25:31
发布于：广东
9阅读
0回复
0点赞
@AC君，此题测试点有误，理由如下：
平台问题：我的老师，同学，包括我的团队已经提交此题70次以上，老师做了15个不同的版本，但是最多只过了4个点，但是我们团队发现，在洛谷这个平台上提交一遍过（图片证据还在收集），希望官方能修改一下，目前通关率在0.00%，难度是NOI级别
以下是正确代码
版本1：
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
struct dish
{
int w,id;
}v[505];
bool cmp(dish x,dish y){return x.w<y.w;}
int n,m,k,d[505];
vector<pii>ans[5005];
namespace subtask1
{
void main(int n,int m)
{
for(int i=1;i<=m;i++)
{
sort(v+1,v+n+1,cmp);
ans[i].clear();
if(v[1].w>=k)ans[i].pb(mp(v[1].id,k));
else v[n].w-=k-v[1].w,ans[i].pb(mp(v[1].id,v[1].w)),ans[i].pb(mp(v[n].id,k-v[1].w));
if(v[1].w<=k)swap(v[1],v[n]),n--;
else v[1].w-=k;
}
for(int i=1;i<=m;i++)
{
for(int j=0;j<ans[i].size();j++)
printf("%d %d ",ans[i][j].first,ans[i][j].second);
puts("");
}
}
}
namespace subtask2
{
bitset<5000005>f[505];
int now;
bool visited[505];
void dfs(int x,int y)
{
if(!x)return;
if(f[x-1][y])dfs(x-1,y);
else visited[x]=1,v[++now].id=x,v[now].w=d[x],dfs(x-1,y-k+d[x]);
}
void main()
{
bool flag=0;
now=0;
f[0][2500001]=1;
memset(visited,0,sizeof(visited));
for(int i=1;i<=n;i++)
{
if(k-d[i]>=0)f[i]=((f[i-1])|(f[i-1]<<(k-d[i])));
else f[i]=((f[i-1])|(f[i-1]>>(d[i]-k)));
if(f[i][2500001+k])
{
dfs(i,2500001+k);
flag=1;
break;
}
}
if(!flag){puts("-1");return;}
subtask1::main(now,now-1);
now=0;
for(int i=1;i<=n;i++)
if(!visited[i])v[++now].id=i,v[now].w=d[i];
subtask1::main(now,now-1);
}
}
int main()
{
int _;
scanf("%d",&_);
while(_--)
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)scanf("%d",&d[i]);
if(m>=n-1)
{
for(int i=1;i<=n;i++)v[i].id=i,v[i].w=d[i];
subtask1::main(n,m);
}
else subtask2::main();
}
return 0;
}
版本2：
#include<bits/stdc++.h>
#define N 5100
#define FN 501
#define G 2000000
using namespace std;
int T, ans[N][5], k, cnt;
void work(int n, int m, int *d, int *tr) {
while(cnt < m) {
int minn = 0, mindy = 0;
for(int i = 1; i <= n; i++) if((d[i] < d[minn] || !minn) && d[i]) minn = i;
if(d[minn] >= k) {
++cnt;
ans[cnt][1] = tr[minn], ans[cnt][2] = k, d[minn] -= k;
continue;
}
for(int i = 1; i <= n; i++) if(i != minn && d[i] + d[minn] >= k && (d[i] < d[mindy] || !mindy)) mindy = i;
++cnt;
ans[cnt][1] = tr[minn], ans[cnt][2] = d[minn];
ans[cnt][3] = tr[mindy], ans[cnt][4] = k - d[minn];
d[mindy] -= k - d[minn], d[minn] = 0;
}
}
int n, m, d[N], pcnt, flag[FN], tr[N];
bitset<4000000> f[FN];
void dfs(int x, int wz) {
if(x == 0) return;
if(f[x - 1][wz] == 1) dfs(x - 1, wz);
else flag[x] = 1, dfs(x - 1, wz - d[x]);
}
int main() {
scanf("%d", &T);
while(T --> 0) {
scanf("%d%d%d", &n, &m, &k), cnt = 0;
for(int i = 1; i <= n; i++) scanf("%d", &d[i]), tr[i] = i;
if(m == n - 2) {
memset(f, 0, sizeof(f));
for(int i = 1; i <= n; i++) d[i] -= k;
f[0][G] = 1;
for(int i = 1; i <= n; i++) {
if(d[i] >= 0) f[i] = f[i - 1] | (f[i - 1] << d[i]);
else f[i] = f[i - 1] | (f[i - 1] >> -d[i]);
}
if(!f[n][G - k]) {
puts("-1");
continue;
}
else {
for(int i = 1; i <= n; i++) flag[i] = 0;
dfs(n, G - k), pcnt = 0;
for(int i = 1; i <= n; i++) d[i] += k;
for(int i = 1; i <= n; i++) if(flag[i] == 1)
++pcnt, swap(d[i], d[pcnt]), swap(tr[pcnt], tr[i]);
work(pcnt, pcnt - 1, d, tr);
work(n - pcnt, m, d + pcnt, tr + pcnt);
}
}
else work(n, m, d, tr);
for(int i = 1; i <= m; i++) {
printf("%d %d", ans[i][1], ans[i][2]);
if(ans[i][2] != k) printf(" %d %d", ans[i][3], ans[i][4]);
printf("\n");
}
}
return 0;
}
（这是我发的第2条帖子）
彩蛋
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"今天又赚了40罐头，马上又能买得起AC之神的祝福了";
return 0;
}
今日推荐歌曲：七里香
祝福
快过年了，和ACGO的网友们说声“新年快乐！！！”也祝大家代码越写越好，祝ACGO蒸蒸日上，更希望你们点个赞，求求了！
这里空空如也
有帮助，赞一个