题解 星空

大佬教程收集整理的这篇文章主要介绍了题解 星空，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

传送门

这题什么神仙转化…… 24pts状压贼好打考场上脑子抽了一直想特判 如果要在状压时同时找到两个1转移，第一层可以不枚举，而用第一个1代替，因为没有第一个1的状态也会被枚举到

「LATEX待补充」 想不到……就先顺一遍题解思路吧 首先n有点大，而这里需要区间修改 套个数据结构能维护修改 但是这只是不断用区间修改尝试统一整个区间的值，考虑差分 类比蓝书差分例题增减序列 ，只不过那道是求统一差分数组的最小步数及方案数，这里是求统一差分数组的最小步数而已

然后转化成了一个处理差分序列的问题 发现这里(k)很小，差分序列里只有不超过16个1，令其为(cnt) 再看所谓「翻转」操作，在这里即为选固定间距的点进行取反 取反两个1相当于用一次操作将它们消掉 取反一个0和一个1相当于移动这个1 最后要把序列消成全0

(2*kleqslant16)这个范围适合暴力，考虑预处理通过移动消掉i，j的最少步数 这里可以用最短路 然后枚举消点的过程可以状压 注意状压的时候可以用到一开始说的优化 如果要在状压时同时找到两个1转移，第一层可以不枚举，而用第一个1代替，因为没有第一个1的状态早晚被枚举到，就与这里的转移产生了重复 状压时间复杂度可以从(O(k^2*2^{Cnt}))优化成(O(k*2^{Cnt}))

Code:

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 40010
#define ll long long 
#define ld long double
#define usd unsigned
#define ull unsigned long long
//#definE int long long 

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
char buf[1<<21], *p1=buf, *p2=buf;
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, m;

namespace force{
	int dp[1<<16], s, cnt;
	bool vis[1<<16];
	queue<int> q;
	int len[n], b[n];
	void solve() {
		memset(dp, 127, sizeof(dp));
		s=(1<<n)-1;
		for (int i=1; i<=k; ++i) s^=(1<<(read()-1));
		for (int i=1; i<=m; ++i) {len[i]=read(); b[i]=(1<<len[i])-1;}
		q.push(s); dp[s]=0;
		while (!q.empty()) {
			//++cnt;
			s=q.front(); q.pop();
			vis[s]=0;
			for (int i=1,to; i<=m; ++i) 
				for (int j=n-len[i]; j>=0; --j) {
					to = s^(b[i]<<j);
					if (dp[s]+1<dp[to]) {
						dp[to]=dp[s]+1;
						if (!vis[to]) q.push(to);
					}
				}
		}
		printf("%dn", dp[(1<<n)-1]);
		//cout<<"cnt: "<<cnt<<endl;
		//cout<<"2^n: "<<(1<<n)<<endl;
		exit(0);
	}
}

namespace task{
	int a[20], len[70], pos[20], cnt, cnt2;
	int dis[20][n], dp[1<<16];
	queue<int> q;
	bool vis[1<<16], point[n];
	void bfs(int s, int dis[]) {
		//cout<<"bfs "<<s<<endl;
		int cnt2=0;
		dis[s]=0; q.push(s);
		while (!q.empty()) {
			s=q.front(); q.pop();
			vis[s]=0;
			if (point[s] && ++cnt2>=cnt) {while (!q.empty()) {vis[q.front()]=0; q.pop();} return ;}
			for (int i=1,t; i<=m; ++i) {
				//cout<<"len: "<<len[i]<<endl;
				if ((t=s-len[i])>0 && dis[t]>dis[s]+1) {
					dis[t]=dis[s]+1;
					if (!vis[t]) q.push(t);
				}
				if ((t=s+len[i])<=n && dis[t]>dis[s]+1) {
					dis[t]=dis[s]+1;
					if (!vis[t]) q.push(t);
				}
			}
		}
		//cout<<"dis: "; for (int i=1; i<=n; ++i) cout<<dis[i]<<' '; cout<<endl;
	}
	void solve() {
		++n;
		memset(dis, 127, sizeof(dis));
		memset(dp, 127, sizeof(dp));
		for (int i=1; i<=k; ++i) a[i]=read();
		for (int i=1; i<=k; ++i) {
			if (i==1 || (i!=1&&a[i-1]!=a[i]-1)) pos[++cnt]=a[i], point[a[i]]=1;
			if (a[i+1]!=a[i]+1) pos[++cnt]=a[i]+1, point[a[i]+1]=1;
		}
		//cout<<"cnt: "<<cnt<<' '<<k*2<<endl;
		//cout<<"pos: "; for (int i=1; i<=cnt; ++i) cout<<pos[i]<<' '; cout<<endl;
		for (int i=1; i<=m; ++i) len[i]=read();
		for (int i=1; i<=cnt; ++i) bfs(pos[i], dis[i]);
		int s;
		dp[(1<<cnt)-1]=0; q.push((1<<cnt)-1);
		while (!q.empty()) {
			s=q.front(); q.pop();
			vis[s]=0;
			for (int i=0,t2,t3; i<cnt; ++i) if (s&(1<<i)) {
				for (int j=i+1; j<cnt; ++j) if (s&(1<<j)) {
					t2=s^(1<<i)^(1<<j); t3=dp[s]+dis[i+1][pos[j+1]];
					//cout<<"disk: "; for (int k=1; k<=n; ++k) cout<<dis[i+1][k]<<' '; cout<<endl; cout<<t3<<endl; cout<<pos[j+1]<<endl;
					if (dp[t2]>t3) {
						dp[t2]=t3;
						if (!vis[t2]) q.push(t2);
					}
				}
				break;
			}
		}
		printf("%dn", dp[0]);
		//cout<<cnt2<<' '<<(1<<cnt)<<endl;
		exit(0);
	}
}

signed main()
{
	#ifdef DEBUG
	freopen("1.in", "r", stdin);
	#endif
	
	n=read(); k=read(); m=read();
	task::solve();

	return 0;
}

大佬总结

以上是大佬教程为你收集整理的题解 星空全部内容，希望文章能够帮你解决题解 星空所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。