关于mt19937行为
  • 板块P11069 劫掠
  • 楼主steambird
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/10/11 15:43
  • 上次更新2024/10/11 19:30:34
查看原帖
关于mt19937行为
589961
steambird楼主2024/10/11 15:43

在Dev-C++(mingw编译器)和洛谷(GCC/G++)下同样的 read 函数似乎会生成不同的序列?

下面是 5050 分代码:

#include <bits/stdc++.h>
using namespace std;

#define int long long
//这个做法的复杂度是错的,只是测试一下
constexpr int T = 30, N = 2e7+4, STSZ = (1<<24)+100;
int n,m,k,s;

int a[N],b[N],c[N];

const int M=1e9,C=1e5+5;
void read(){
    cin>>n>>m>>k>>s;
    mt19937 random(s);
    for(int i=1;i<=n;i++)  a[i]=random()%M+1,b[i]=random()%C+1;
    for(int i=1;i<=k;i++)  c[i]=random()%n+1;
}
bool exist[T];
// Experience gotten but HP insufficient
int reach[STSZ];
// curhp is non-positive
long long expval[STSZ], curhp[STSZ];
bool vis[STSZ];

struct ret {
	int c_reach;
	long long c_exp, c_hp;
	ret() {
		
	}
	ret(int c_reach, long long c_exp, long long c_hp) : c_reach(c_reach),
		c_exp(c_exp), c_hp(c_hp) {
			
		}
};

ret search(int state) {
	if (vis[state]) return ret(reach[state], expval[state], curhp[state]);
	// Consider one state to remove:
	ret final;
	for (int i = 0; i < n; i++) {
		int it = i+1;
		if (state&(1<<i)) {
			ret origin = search(state^(1<<i));
			// Directly have processors on it
			if (exist[it]) {
				// Consider further to obtain
				origin.c_exp -= a[it];
				origin.c_hp += b[it];
				if (origin.c_hp > 0) {
					origin.c_reach++;
					for (; origin.c_reach <= k; origin.c_reach++) {
						origin.c_exp += a[c[origin.c_reach]];
						origin.c_hp -= b[c[origin.c_reach]];
						if (origin.c_hp <= 0) break;
					}
//					if (origin.c_reach > k) origin.c_reach = k;
				}
			}
			if (origin.c_exp > final.c_exp) {
				final = origin;
			} else if (origin.c_exp == final.c_exp && origin.c_hp > final.c_hp) {
				final = origin;
			}
		}
	}
	reach[state] = final.c_reach;
	expval[state] = final.c_exp;
	curhp[state] = final.c_hp;
	vis[state] = true;
	return final;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	read();
	// Have initial evaluation
	int hp = m, final = k;
	for (int i = 1; i <= k; i++) {
		exist[c[i]] = true;
		expval[0] += a[c[i]];
		hp -= b[c[i]];
		if (hp <= 0) {
			curhp[0] = hp;
			final = i;
			break;
		}
	}
	reach[0] = final;
	vis[0] = true;
	long long ans = 0;
	for (int i = 0; i < (1<<n); i++) {
		long long my = search(i).c_exp;
		if (my > ans) ans = my;
	}
	cout<<ans<<endl;
	return 0;
}
2024/10/11 15:43
加载中...