在Dev-C++(mingw编译器)和洛谷(GCC/G++)下同样的 read 函数似乎会生成不同的序列?
下面是 50 分代码:
#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;
}