【题解】2023 NOI 春季测试 3 of 4

A. 涂色游戏

Problem

题意：\(n\times m\) 的网格，\(q\) 次询问，每次涂一行或一列，新颜色会覆盖旧颜色，输出最终形态。

\(1\le \sum nm\)，\(\sum q\le 10^6\)。

考虑倒序执行这 \(q\) 个操作。

对每一行和每一列用 std::unordered_map 存当前还有哪一些方格未被涂色。

因为反着执行涂色时旧颜色一定不会被覆盖，故对于一个操作遍历该行/列对应的容器，未涂色的涂色，再将该方格编号从容器中删掉即可。

时间复杂度 \(O(mn)\)。

std::unordered_map 插值和删值的均摊时间复杂度是 \(O(1)\) 的。

Code

#include <bits/stdc++.h>
using namespace std;
#define fre(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
#define int long long
#define double long double
#define PI acos(-1)
#define inf 0x3fffffffffffffff
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return f==1?x:-x;
}
inline void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int modp = 998244353;


void solve()
{
	int n=read(),m=read(),q=read();
	vector<array<int,3>> query(q);
	for(int i=0;i<q;++i) {
		int opt=read(),x=read(),c=read();
		query[i]={opt,x,c};
	}
	vector<unordered_map<int,int>> line(n+1),col(m+1);
	vector<vector<int>> ans(n+1,vector<int>(m+1,0));
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			line[i][j]=j;
			col[j][i]=i;
		}
	}
	for(int i=q-1;i>=0;--i) {
		auto [opt,x,c]=query[i];
		if(!opt) {
			vector<int> id;
			for(auto [fir,sec]:line[x]) {
				id.push_back(sec);
				col[sec].erase(x);
				ans[x][sec]=c;
			}
			for(auto k:id) {
				line[x].erase(k);
			}
		} else {
			vector<int> id;
			for(auto [fir,sec]:col[x]) {
				id.push_back(sec);
				line[sec].erase(x);
				ans[sec][x]=c;
			}
			for(auto k:id) {
				col[x].erase(k);
			}
		}
	}
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			printf("%lld ",ans[i][j]);
		}
		puts("");
	}
}


signed main()
{
	fre(test);
	int T=read();
	while(T--) {
		solve();
		//fflush(stdout);
	}
	return 0;
}

B. 幂次

Problem

题意：给定正整数 \(n,k\)，求 \(1\sim n\) 中有多少正整数 \(x\) 可以表示为 \(x=a^b\) 的形式，其中 \(a,b\in \mathbb N^+\) 且 \(b\ge k\) 。

\(1\le n \le 10^{18}\)，\(1\le k \le 100\)。

按照 \(k\) 范围分治。

首先，当 \(k=1\) 时，\(ans=n\)。因为所有 \(x\) 都能表示为 \(x^1\)。

其次，当 \(k\ge 3\) 时，可以暴力枚举底数 \(a\)，因为 \((10^6)^3=10^{18}\)，底数十分有限。

最后，\(k=2\) 时，一个结论是小于等于 \(x\) 的完全平方数有 \(sqrt(x)\) 个，但其中有一些和指数大于 \(2\) 时的计算结果重复，考虑容斥。在统计 \(k\ge 3\) 的过程中顺便记录哪些计入答案的数属于完全平方数，令 \(k\ge 3\) 时的答案为 \(cnt\)，有 \(num\) 个完全平方数，则 \(ans=cnt+sqrt(x)-num\)。

容易爆 long long ，可以开 __int128 。

小心精度问题，用 std::sqrtl() 而不是 std::sqrt() 。

Code

#include <bits/stdc++.h>
using namespace std;
#define fre(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
#define int __int128
#define double long double
#define PI acos(-1)
#define inf 0x3fffffffffffffff
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return f==1?x:-x;
}
inline void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int modp = 998244353;

inline int qpow(int k,int n) {
	int s=1;
	for(;n;n>>=1,k*=k) if(n&1) s*=k;
	return s;
}
map<int,bool> mp;
void solve()
{
	int n=read(),k=read();
	if(k==1) {
		write(n);
	}
	else {
		int cnt=0,sqrt_num=0;
		for(int i=2;i*i*i<=n;++i) {
			int x=1;
			for(int j=1;;++j) {
				x*=i;
				if(x>n) {
					break;
				}
				if(j>=k && !mp[x]) {
					if((int)sqrtl(x)*(int)sqrtl(x)==x) {
						sqrt_num++;
					}
					mp[x]=1;
					cnt++;
				}
			}
		}
		if(k==2) {
			write(cnt+sqrtl(n)-sqrt_num);
		} else {
			write(cnt+1);
		}
	}
}


signed main()
{
	fre(test);
	int T=1;
	while(T--) {
		solve();
		//fflush(stdout);
	}
	return 0;
}

C. 圣诞树

Problem

好题

题意：给定二维坐标系上 \(n\) 个点构成的凸多边形，求从 \(y\) 轴最高点出发的一条最短路径，要求经过 \(n\) 个点且每个点仅能经过一次，依次输出编号。

\(3\le n\le 1000\)，\(|x_i|,|y_i|\le 10^7\)。

正解是区间dp，不是很会。

只会 \(3\le n\le18\)，不过加上两个特殊性质一共能拿到 80pts。

套路题，最短哈密顿路径，考虑状压dp。

令起点为 \(s\)，则 \(dp[i][j]\) 代表从 \(s\) 到 \(j\) ，且经过 \(i\) 的二进制为 \(1\) 的位数对应编号的点的最短路径长度。

则 \(dp[i][j]=\mathop\min\limits_{k\in[1,n]}(dp[i\oplus2^j][k]+dis[k][j])\)。

答案为 \(\min\limits_{i\in[1,n]}(dp[2^n-1][i])\)。

接下来考虑如何记录路径。

令 \(pre[mask][j]=k\) 表示状态为 \(mask\)，当前点 \(j\) 从点 \(k\) 转移过来最优。

状态转移时 \(pre\) 与 \(dp\) 同步。

统计答案时，\(mask\) 对应为 \(1\) 的位异或变成 \(0\)，即可回溯到上一状态。

Code

#include <bits/stdc++.h>
using namespace std;
#define fre(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
#define int long long
#define double long double
#define PI acos(-1)
#define inf 0x3fffffffffffffff
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return f==1?x:-x;
}
inline void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int modp = 998244353;

void solve()
{
	int n=read();
	vector<vector<double>> dis(n,vector<double>(n));
	vector<double> X(n),Y(n);
	int top=0;
	double maxn=0;
	for(int i=0;i<n;++i) {
		cin>>X[i]>>Y[i];
		if(Y[i]>maxn) {
			maxn=Y[i];
			top=i;
		}
	} 
	for(int i=0;i<n;++i) {
		for(int j=0;j<n;++j) {
			dis[i][j]=sqrtl((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]));
		}
	}
	vector<vector<double>> dp(1<<n,vector<double>(n,1.0*inf));
	vector<vector<int>> pre(1<<n,vector<int>(n,-1));
	dp[1<<top][top]=0;
	for(int i=1;i<(1<<n);++i) {
		for(int j=0;j<n;++j) {
			if(i>>j&1) {
				for(int k=0;k<n;++k) {
					if(i>>k&1) {
						if(dp[i^(1<<j)][k]+dis[k][j]<dp[i][j]) {
							dp[i][j]=dp[i^(1<<j)][k]+dis[k][j];
							pre[i][j]=k;
						}
					}
				}
			}
		}
	}
	double res=1.0*inf;
	for(int i=0;i<n;++i) {
		if(i!=top) {
			res=min(res,dp[(1<<n)-1][i]);
		}
	}
	vector<int> path;
	for(int i=0;i<n;++i) {
		if(fabs(dp[(1<<n)-1][i]-res)<1e-14) {
			path.push_back(i);
			int mask=(1<<n)-1,j=i;
			while(pre[mask][j]!=-1) {
				int tmp=j;
				j=pre[mask][j];
				mask^=(1<<tmp);
				path.push_back(j);
			}
			break;
		}
	}
	reverse(path.begin(),path.end());
	for(auto i:path) {
		printf("%lld ",i+1);
	}
}


signed main()
{
	fre(test);
	int T=1;
	while(T--) {
		solve();
		//fflush(stdout);
	}
	return 0;
}