526互联

Educational Codeforces Round 114

发布时间 2023-09-01 16:11:42作者: gan_coder

今天的D题有点惊险了，属于是，还剩9分钟搞出来。

B题开始猜到了结论，只要在最大值和最小值之间都是可以的，证明的话，可以先考虑从数量大的开始填，然后反证法一下（口胡）

C题选择attack肯定是尽量跟，dragon的defence越接近越好
如果有相等就直接选，否则就选前面的或者后面的

本来写的是bfs，最后15min灵光一现

D题开始感觉不是很好搞，后面发现可以m其实只有1e5级别，我们可以暴力扩展状态，将它们的状态看成一个点，有点类似于dij的思路，然后用hash判断一下是否能走，然后一个小优化就是如果已经走到一个能走的点，那么根据单调性，就不需要再扩展。

跑了2s，常数巨大

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<unordered_map>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define mm(x,y,z)  make_pair(make_pair((x),(y)),(z))

#define A puts("YES")
#define B puts("NO")

using namespace std;
typedef double db;
typedef long long ll;

const ll mo1=998244353;
const ll mo2=1e9+7;
const ll mo3=1e9+9;

const int N=2e5+5;
const ll inf=1ll<<60;

struct key{
	ll a,b,c;
};
struct node{
	ll v;
	ll a[12];
};
bool operator < (const node &a,const node &b){
	return a.v <b.v;
}
priority_queue<node> q;
int h,t;
map<pair<pair<ll,ll>,ll> ,bool> f,g;

ll n,c[N],a[20][N],xx[20],ans,u[N];

key C(ll *d){
	
	ll a=0,b=0,c=0;
	fo(i,1,n) {
		a=a*(ll)131+(ll)d[i]%mo1;
		b=b*(ll)13331+(ll)d[i]%mo2;
		c=c*(ll)114514+(ll)d[i]%mo3;
	}
	return (key){a,b,c};
}
void calc(ll *d){
	ll sum=0;
	fo(i,1,n) {
		sum+=a[i][d[i]];
	}
	if (ans<sum) {
		ans=sum;
		fo(i,1,n) {
			u[i]=d[i];
		}
	}
}
ll S(ll *d){
	ll s=0;
	fo(i,1,n) {
		s+=a[i][d[i]];
	}
	return s;
}
int main() {
	
	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	
	scanf("%lld",&n);
	fo(i,1,n) {
		scanf("%lld",&c[i]);
		fo(j,1,c[i]) {
			scanf("%lld",&a[i][j]);
		}
	}
	
	int m;
	key k;
	scanf("%d",&m);
	fo(i,1,m) {
		fo(j,1,n) {
			scanf("%lld",&xx[j]);
		}
		
		k=C(xx);
		f[mm(k.a, k.b, k.c)]=1;
		
//		printf("%lld %lld %lld\n",k.a,k.b, k.c);
	}
	
	node y,z;
	
	fo(i,1,n) y.a[i]=c[i]; 
	y.v=S(y.a);
	q.push(y);
	
	bool flag=0;
	
	while (!q.empty()) {
		
		z=q.top(); q.pop();
		
		k=C(z.a);
		
		if (f.find(mm(k.a, k.b, k.c)) ==f.end()) {
			calc(z.a);
			flag=1;
		}
		
		g[mm(k.a, k.b, k.c)]=1;
		
		if (flag) continue;
		
		fo(i,1,n) {
			if (z.a[i] ==1) continue;
			fo(j,1,n) y.a[j]=z.a[j];
			y.a[i]--;
			
			k=C(y.a);
			if (g.find(mm(k.a, k.b, k.c))==g.end()) {
				
				y.v=S(y.a);
				q.push(y);

				g[mm(k.a, k.b, k.c)]=1;
			}
		}
	}
	
	fo(i,1,n) printf("%lld ",u[i]);

	return 0;
}

今天又是手速场，E看起来没什么人过的样子，下班。