AtCoder Beginner Contest 248 A~F 题解

UNIQUE VISION Programming Contest 2022（AtCoder Beginner Contest 248） 题解 A - Lacked Number 题意

给你一串包含0~9的数字串，找到没出现那个

做法

直接模拟

AC代码

#include
using namespace std;
const int N = 1e6+7;
typedef long long ll;
int A[1000];
int main(){
	string s;
	cin>>s;
	for(char ch :s){
		A[ch] = 1;
	}
	for(char ch = '0';ch<='9';ch++){
		if(A[ch]==0) cout<<ch;
	}
	return 0;
}

B - Slimes 题意

问你从A增长到B，每次增长都乘K，至少需要乘多少次

思路

模拟

AC代码

在这里插入代码片

C - Dice Sum 题意

问你可以构造出多少种序列，使每个数都小于M，每个数之和小于K

思路

记忆化搜索，dp[i][j] 代表前i个数的总和是j的方案数，对于第i个数枚举从1
到M的数且当前总和小于K，往下搜就好了

AC代码

#include
using namespace std;
const int N = 1e6+7;
typedef long long ll;
int A[1000];
int dp[100][5000];ll n,m,k;
ll mod = 998244353;
ll dfs(int step,int sum){
	if(dp[step][sum]!=-1) return dp[step][sum]%mod;
	if(step==n+1) return dp[step][sum] = 1;
	ll ans = 0;
	for(int i = 1;i<=m;i++){
		if(sum+i<=k) ans += dfs(step+1,sum+i)%mod;
	}
	return dp[step][sum] = ans%mod;
}
int main(){
	cin>>n>>m>>k;
	memset(dp,-1,sizeof(dp));
	cout<<dfs(1,0)%mod;
	return 0;
}

D - Range Count Query 题意

给你一个数组，q次询问L~R之间x出现了几次

思路

分别用数组记录所有数字出现的位置，这样每个数组都是有序的，在L~R查询x的次数时只需要在对应数组中二分查找L和R的位置，位置相减就是出现的次数

AC代码

#include
using namespace std;
const int N = 1e6+7;
typedef long long ll;
vector<int> A[N];
int main(){
	int n;
	cin>>n;
	for(int i = 1;i<=n;i++){
		int t ;
		cin>>t;
		A[t].push_back(i); 
	}
	int q;
	cin>>q;
	while(q--){
		int bg,ex,x;
		cin>>bg>>ex>>x; 
		int pose = upper_bound(A[x].begin(),A[x].end(),ex)-A[x].begin()-1;
		int posb = lower_bound(A[x].begin(),A[x].end(),bg)-A[x].begin();
		int ans = pose-posb+1;
		cout<<max(0,ans)<<endl; 
	}
	return 0;
}

E - K-colinear Line 题意

给你n个点，问你有多少条不同的直线经过至少m的点

思路

我做的时候没考虑精度问题，直接算的斜率和截距丢进map去重导致错了
正确做法：
对于三个点来说判断其中一个点是否在另外两个点组成的直线上，可以用斜率判断 即 (y3-y1) / (x3-x1) == (y2-y1) / (x2-x1) , 考虑精度问题 ，转化为乘法
(y3-y1)(x2-x1) == (y2-y1)(x3-x1)
另外那对于直线怎么去重 ： 考虑有k个点在一条直线上，不去重会产生（k-1）*k /2 条直线，那么我们在最后的时候把这个k个点上产生的答案乘上不去重产生的直线的倒数，那不就是正确的吗，即乘上（2/((k-1)*k)）

AC代码

#include
using namespace std;
const int N = 1e6+7;
typedef long long ll;
int x[N],y[N],ans[N];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i = 0;i<n;i++){
		cin>>x[i]>>y[i];
	} 
	for(int i = 0;i<n;i++){
		for(int j = i+1;j<n;j++){ // 枚举边 
			int cnt = 0;
			for(int k = 0;k<n;k++){
				int y1 = (y[j]-y[i])*(x[k]-x[i]);
				int x1 = (y[k]-y[i])*(x[j]-x[i]);
				if(x1==y1) cnt++;
			}
			ans[cnt]++;
		}
	}
	if(m==1) cout<<"Infinity";
	else {
		ll res = 0;
		for(int i = m;i<=n;i++){
			res += ans[i]*2/(i*(i-1));
		}
		cout<<res;	
	}
	
	return 0;
}

F - Keep Connect 题意

给你n列这样的图
问你对于删除 1~ (n-1) 条边还联通的不同图的数量，例如n等于3时，答案为7 15
这是删除1条边

这是删除2条边

思路

参考了下dls的视频,说说我的理解
这是个连通性DP，DP[i][j][k] 代表 前 i 列已经删去j条边，并且第i列中上下两个点的连通性为k （0代表不连通，反之）
接下来考虑每个状态的对后面状态的贡献值（刷表法）
我们设p1为第i列和i+1列的上边，p2为第i列和i+1列的下边，p3为第i列的对边

1. k为1时，即第i列上下两点联通，那么这个状态对p1,p2,p3任取两条边时
   都有贡献
   2 k为0时，即第 i 列上下两点不连通，那么这个状态只对p1,p2都是联通的状态有贡献，因为其中上下一条边删去时，无论后面的联通性如何，第i列会存在无法联通的点

AC代码

#include
using namespace std;
const int N = 1e6+7;
typedef long long ll;
int dp[3100][3100][2]; // 前i个点去除j条边第i的连通性为k(0,1)
int main(){
	int n,p;
	cin>>n>>p;
	dp[0][0][1] = 1;
	dp[0][1][0] = 1;
	for(int i = 0;i<n;i++)
	for(int j = 0;j<n;j++)
	for(int k = 0;k<2;k++)       // 第i列的边 
	if(dp[i][j][k]){
		for(int p1 = 0;p1<2;p1++) // 上邻边 
		for(int p2 = 0;p2<2;p2++)// 下邻边 
		for(int p3 = 0;p3<2;p3++)// 对边 
		{
			if(k==0){
				if(p1==0||p2==0) continue;
				dp[i+1][j+(1-p3)][p3] = (dp[i+1][j+(1-p3)][p3]+dp[i][j][k])%p;
			}	
			else{
				if(p1==0&&p2==0) continue;
				dp[i+1][j+3-p1-p2-p3][(p1+p2+p3)>=2] = (dp[i+1][j+3-p1-p2-p3][(p1+p2+p3)>=2]+dp[i][j][k])%p;
			}
		}
	}
	for(int i = 1;i<n;i++){
		cout<<dp[n-1][i][1]<<" ";
	}
	return 0;
}

经验总结

E题的去重想法有点像容斥定理，都是先计算，后面再减去由此产生多余的答案，以后的话可以在处理复杂问题可以计算，再减去重复贡献，还有涉及几何要考虑精度，用分数存