「NOI2020」制作菜品
多次随机，每次把原材料顺序打乱。
维护一个大根堆，每次将当前原材料与大根堆顶的材料配对，然后还可以自己构成一个菜品，之后将其塞到大根堆里。
目前拿到了80 pts 不太明白为什么这样正确率比较高。orz现场拿到这个分数的lyn大佬。
还有以下代码是flying2018巨佬基础上直接改的。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define N 5010
using namespace std;
struct node{
int id,x;
bool operator <(const node a)const{return x<a.x;}
};
struct q{
int x,id;
}d[N];
priority_queue<node>q;
struct answ{
int i,x,j,y;
}ans[N];
int main()
{
freopen("dish.in","r",stdin);
freopen("dish.out","w",stdout);
int t;
scanf("%d",&t);
while(t --> 0)
{
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
srand(1ll*n*m);
for(int i=1;i<=n;i++) scanf("%d",&d[i].x),d[i].id=i;
int tot=0;
for(int _=0;_<10000000/n;_++)
{
tot=0;
while(!q.empty()) q.pop();
random_shuffle(d+1,d+n+1);
// for(int i=1;i<=n;i++)
// if(d[i]<k) q.push((node){i,d[i]});
for(int i=1;i<=n;i++)
// if(d[i]>=k)
{
int r=d[i].x;
while(!q.empty() && q.top().x+r>=k)
{
ans[++tot]=(answ){q.top().id,q.top().x,d[i].id,k-q.top().x};
r-=k-q.top().x;
q.pop();
}
if(r>=k){for(;r>=k;r-=k) ans[++tot]=(answ){d[i].id,k,0,0};}
if(r) q.push((node){d[i].id,r});
}
if(q.empty()) break;
}
if(tot!=m){puts("-1");continue;}
for(int i=1;i<=m;i++)
if(ans[i].j==0) printf("%d %d
",ans[i].i,ans[i].x);
else printf("%d %d %d %d
",ans[i].i,ans[i].x,ans[i].j,ans[i].y);
}
return 0;
}
「JOISC 2020 Day1」汉堡肉
还是考虑多次随机，每次打乱矩形的顺序然后取前K个矩形然后剩余的矩形要与他们取交。
至于该每个矩形应该与哪个矩形取交，这里是比较交的面积占原矩形的比例。orz ouuan yyds！
#include<bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);(i)<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);(i)>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<':'<<x<<endl
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
void wr(int x){
if(x<0)putchar('-'),x=-x;
if(x>=10)wr(x/10);
putchar('0'+x%10);
}
const int MAXN=2e5+10;
struct node{
int x1,x2,y1,y2;
inline node operator&(const node &b){
return {max(x1,b.x1),min(x2,b.x2),max(y1,b.y1),min(y2,b.y2)};
}
inline double S(){
if(x1>x2||y1>y2)return 0;
return 1.0*(x2-x1+1)*(y2-y1+1);
}
inline bool operator<(const node &b)const{
if(x1!=b.x1)return x1<b.x1;
if(x2!=b.x2)return x2<b.x2;
if(y1!=b.y1)return y1<b.y1;
return y2<b.y2;
}
inline bool operator==(const node &b)const{
return x1==b.x1&&x2==b.x2&&y1==b.y1&&y2==b.y2;
}
}a[MAXN],b[5];
mt19937 gen(20020328);
int n,K;
inline void solve(){
shuffle(a+1,a+1+n,gen);
fp(i,1,K)b[i]=a[i];
fp(i,K+1,n){
double mx=0;int p=0;
fp(j,1,K){
double t=(b[j]&a[i]).S()/b[j].S();
if(t>mx)mx=t,p=j;
}
if(!p)return;
b[p]=b[p]&a[i];
}
fp(i,1,K)printf("%d %d
",b[i].x1,b[i].y1);
exit(0);
}
main(){
n=read();K=read();
fp(i,1,n)a[i].x1=read(),a[i].y1=read(),a[i].x2=read(),a[i].y2=read();
sort(a+1,a+1+n);n=unique(a+1,a+1+n)-a-1;
while(1)solve();
return 1;
}
上面的貌似被hack了。。https://uoj.ac/submission/437167 可以看看这个。。感觉很神奇
我理解这个代码的意思是每次把匹配失败的塞到v2里 下一次随机优先匹配这些失败的最后再塞成功的 感觉很神奇。。