题解 v

考场上只会爆搜……觉得重复状态其实有很多但不知道怎么记忆化，结果……
对于类似这样n不算太小但只有二三十，而重复状态极多的题其实也是可以跑状压/记搜的，状态可以开map存
然后就是爆搜，就没什么了……

这题\(k=n-1\)其实有特解……白优化了半天hash 考虑\(k=n-1\)其实就是有一个点可以任选

upd: 其实不用特解，移位卡常可以过
Code:
#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define N 100

#define ll long long

#define ld long double

#define usd unsigned

#define ull unsigned long long

//#define int long long

#define max(a, b) ((a)>(b)?(a):(b))

#define reg register int

inline int read() {

	int ans=0, f=1; char c=getchar();

	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}

	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}

	return ans*f;

}

int n, k;

char s[N];

namespace force{

	int v[N];

	bool vis[N];

	double dfs(int u, int sum) {

		//cout<<"dfs "<<u<<' '<<sum<<endl;

		if (u>k) return 1.0*sum;

		int lim=n-u+1, bkpa, bkpb, cnt;

		int a, b;

		double ans=0; double t1, t2;

		for (int i=1; i<=lim; ++i) {

			cnt=0; for (int j=1; j<=n; ++j) {if (!vis[j]) {if (++cnt==i) {vis[j]=1; a=v[j]; bkpa=j;}}}

			t1=dfs(u+1, sum+(a==0));

			//cout<<a<<' '<<bkpa<<endl;

			vis[bkpa]=0;

			cnt=0; for (int j=n; j; --j) {if (!vis[j]) {if (++cnt==i) {vis[j]=1; b=v[j]; bkpb=j;}}}

			t2=dfs(u+1, sum+(b==0));

			vis[bkpb]=0;

			//cout<<"u, i: "<<u<<' '<<i<<' '<<max(t1, t2)<<endl;

			ans+=max(t1, t2)/(1.0*lim);

		}

		return ans;

	}

	void solve() {

		for (int i=1; i<=n; ++i)

			if (s[i]=='W') v[i]=0;

			else v[i]=1;

		//cout<<1<<endl;

		printf("%.10lf\n", dfs(1, 0));

		exit(0);

	}

}

namespace task2{

	void solve() {

		int cnt=0;

		for (int i=1; i<=n; ++i) if (s[i]=='W') ++cnt;

		printf("%.10lf\n", double(cnt));

		exit(0);

	}

}

namespace task3{

	void solve() {

		int cntw=0;

		for (int i=1; i<=n; ++i) if (s[i]=='W') ++cntw;

		if (!cntw) {puts("0.0000000000"); exit(0);}

		if (cntw==n) {printf("%.10lf\n", double(k)); exit(0);}

		if (cntw==n-1 && n%2==0) {printf("%.10lf\n", double(k)); exit(0);}

		if (cntw==n-1 && n%2) {printf("%.10lf\n", double(k-1)/double(k)); exit(0);}

		if (k==n-1) {printf("%.10lf\n", double(min(cntw, n-1))); exit(0);}

		force::solve();

	}

}

namespace task{

	//unordered_map<pair<int, int>, double> mp;

	struct ele{int a, b; ele(){} ele(int a_, int b_):a(a_),b(b_){}};

	inline bool operator == (ele a, ele b) {return a.a==b.a&&a.b==b.b;}

	struct hush_table{

		static const int SIZE=50000100;

		int head[SIZE], size;

		//int cnt[SIZE];

		struct edge{double dat; ele p; int next;}e[5000010];

		inline bool find(ele q) {

			ll t=(998244353ll*q.a*q.b+(q.a))%SIZE;

			//cout<<"t: "<<t<<endl;

			for (int i=head[t]; i; i=e[i].next)

				if (q==e[i].p) return 1;

			return 0;

		}

		inline double operator [] (ele q) {

			ll t=(998244353ll*q.a*q.b+(q.a))%SIZE;

			//cout<<"t: "<<t<<endl;

			for (int i=head[t]; i; i=e[i].next)

				if (q==e[i].p) return e[i].dat;

		}

		inline void add(ele q, double dat) {

			//cout<<"size: "<<size<<endl;

			ll t=(998244353ll*q.a*q.b+(q.a))%SIZE;

			//++cnt[t];

			//cout<<"t: "<<t<<endl;

			edge* k=&e[++size]; k->dat=dat; k->p=q; k->next=head[t]; head[t]=size;

			//if (size > 10000010) cout<<"error"<<endl;

		}

		void check() {

			//int maxn=0;

			//for (int i=0; i<SIZE; ++i) maxn=max(maxn, cnt[i]);

			//cout<<"maxn: "<<maxn<<endl;

			//cout<<"size: "<<size<<endl;

		}

	}mp;

	int v[N];

	double dfs(int u, int s) {

		//cout<<"dfs "<<u<<' '<<bitset<10>(s)<<endl;

		if (u>k) return 0.0;

		ele p(u, s);

		//cout<<"go to find"<<endl;

		if (mp.find(p)) return mp[p];

		//cout<<"not return "<<endl;

		int lim=n-u+1, cnt;

		int a, b, s2, s3;

		double ans=0; double t1, t2;

		for (reg i=1; i<=lim/2; ++i) {

			a=(s&(1<<(i-1)))?1:0;

			cnt=s2=0;

			#if 0

			for (reg j=0; j<lim; ++j)

				if (j!=i-1) {

					if (s&(1<<j)) s2|=(1<<cnt);

					++cnt;

				}

			#endif

			s2=((s>>i)<<(i-1));

			s2|=(s&((1<<(i-1))-1));

			//cout<<"s2, s3: "<<bitset<5>(s2)<<' '<<bitset<5>(s3)<<endl;

			//assert(s2==s3);

			t1=dfs(u+1, s2)+(a==0);

			b=(s&(1<<(lim-i)))?1:0;

			cnt=s2=0;

			#if 0

			for (reg j=0; j<lim; ++j)

				if (j!=lim-i) {

					if (s&(1<<j)) s2|=(1<<cnt); //, cout<<"1<<"<<(cnt)<<endl;

					++cnt;

				}

			#endif

			s2=((s>>(lim-i+1))<<(lim-i));

			s2|=(s&((1<<(lim-i))-1));

			//cout<<"s2, s3: "<<bitset<5>(s2)<<' '<<bitset<5>(s3)<<endl;

			//assert(s2==s3);

			t2=dfs(u+1, s2)+(b==0);

			ans+=max(t1, t2)/(0.5*lim);

		}

		if (lim&1) {

			int i=lim/2+1;

			a=(s&(1<<(i-1)))?1:0;

			cnt=s2=0;

			#if 0

			for (reg j=0; j<lim; ++j)

				if (j!=i-1) {

					if (s&(1<<j)) s2|=(1<<cnt);

					++cnt;

				}

			#endif

			s2=((s>>i)<<(i-1));

			s2|=(s&((1<<(i-1))-1));

			t1=dfs(u+1, s2)+(a==0);

			ans+=t1/(1.0*lim);

		}

		//cout<<"go to add"<<endl;

		mp.add(p, ans);

		//cout<<"return "<<endl;

		return ans;

	}

	void solve() {

		int ss=0;

		for (int i=1; i<=n; ++i)

			if (s[i]=='W') v[i-1]=0;

			else v[i-1]=1, ss|=(1<<(i-1));

		//cout<<1<<endl;

		printf("%.10lf\n", dfs(1, ss));

		mp.check();

		exit(0);

	}

}

signed main()

{

	#ifdef DEBUG

	freopen("1.in", "r", stdin);

	#endif

	n=read(); k=read();

	scanf("%s", s+1);

	if (k==0) {puts("0.0000000000"); return 0;}

	if (k==n || (0&&k==n-1)) task2::solve();

	//if (n>=10) task3::solve();

	//force::solve();

	task::solve();

	return 0;

}
巴特西

题解 v

最新文章

热门文章
