首页 > 其他分享 >CF225 Round #139 题解

CF225 Round #139 题解

时间：2023-01-20 10:34:28浏览次数：59  
标签：typedef return int 题解 long 139 CF225 dp define

比赛链接：https://codeforces.com/contest/225

题解：
A
题意题

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f;

signed main(){
	int n,m;scanf("%d%d",&n,&m);
	while(n--){
		int x,y;cin>>x>>y;
		if(x+y==7||x==y||x==m||y==m||x==7-m||y==7-m)return puts("NO"),0;
	}
	puts("YES");

	return 0;
}

B
斐波那契数列增长的挺快，因此暴力求就可以

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>
 
using namespace std;
 
typedef long long ll;
typedef long long LL;
 
const int inf = 1e9, INF = 0x3f3f3f3f;
 
int k,n;
map<int,ll>fib;
int s;
signed main(){
	scanf("%d%d",&s,&k);
	fib[k] = 1;
	ll sum = 1,t;
	for(int i=k+1;i<=k+100;i++){
		fib[i] = sum;
		sum = sum + fib[i] - (i-k < k ? 0 : fib[i-k]);
//		printf("%d %d\n",i,sum);
		if(sum > s){t=i;break;}
	}
//	for(auto it : fib)printf("%d %d\n",it.first,it.second);
	vector<int>vc;
	for(int i=t;i>=k;i--)
		if(s >= fib[i])s -= fib[i], vc.push_back(fib[i]);
	vc.push_back(0);
	printf("%d\n",vc.size());
	for(auto it : vc)printf("%d ",it);
 
	return 0;
}

C
线性dp，设 \(dp[i][0/1]\) 表示当前是第 \(i\) 位，当前位置是./#，且与上一个位置不同的最少步数
显然转移从 \(i=x+1\) 开始。
细节略多，注意 \(x,y\) 不一定 \(\leq m\)

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f;

int n,m,x,y;
char s[1005][1005];
int col[1005],ncol[1005];
int dp[1005][2];
// dp[i][0/1] 到第 i 位，且 (i-1,i) 不同 第 i 位为 ./# 

signed main(){
	memset(dp, 0x3f, sizeof dp);
	scanf("%d%d%d%d",&n,&m,&x,&y);
	y =min(y, m);x = min(x, m);
	for(int i=1;i<=n;i++)
		scanf("%s",s[i] + 1);
	for(int j=1;j<=m;j++){
		int r=0;
		for(int i=1;i<=n;i++)
			if(s[i][j] == '.')++r;
		col[j] = r;
		ncol[j] = n-r;
	}
	for(int j=2;j<=m;j++)col[j] += col[j-1], ncol[j] += ncol[j-1];
	int ans = 1e9;
	for(int i=x+1;i<=y+1;i++){
		// []
		dp[i][0] = col[i-1], dp[i][1] = ncol[i-1];
	}
	if(y == m)ans = min(ans, min(col[m], ncol[m]));
	for(int i=x+2;i<=m;i++){
		for(int j=i-y;j<=i-x;j++)if(j >= 1){
			if(dp[j][1]!=INF)dp[i][0] = min(dp[i][0], dp[j][1] + col[i-1] - col[j-1]);
			if(dp[j][0]!=INF)dp[i][1] = min(dp[i][1], dp[j][0] + ncol[i-1] - ncol[j-1]);
		}
	}
	for(int j=m+1-y;j<=m+1-x;j++)if(j>=1)
		ans = min(ans, dp[j][0] + ncol[m] - ncol[j-1]),
		ans = min(ans, dp[j][1] + col[m] - col[j-1]);
	cout<<ans;

	return 0;
}

D
考虑蛇的一次移动如何表示，例如：

34.
21.

考虑先把蛇的每一个位置都+1，然后去掉最末尾的一个。这一步相当于身体的移动

4..
32.

再考虑头该如何移动：

41. 4..
32. 321

两种都是可以的
（注意这样还能省去判断头和尾刚好差一格也是能移动的情况）
然后就是普通的bfs，但是还需要判断当前位置是否访问过，有两种情况：

  • 对整个地图 hash。自然溢出可能会被卡，普通hash可能常数过大（最大点需要4.4s,TLE）
  • 对蛇 hash（就是记一下 1~9 的位置然后hash），最大点只需要 ~2s
// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long ll;
typedef long long LL;
typedef unsigned long long ull;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 17;
const int p = 998244353, p2 = 990804011;

int n,m;
char s[maxn][maxn];
struct state{
	char st[maxn][maxn];
	int cnt;
	
	ull gethash(){
		ull hs = 0;
		ull hs2 = 0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				hs = hs*p + st[i][j],
				hs2 = (hs2*p2 + st[i][j]);
		return hs*127+hs2;
	}
	
	state(){cnt=0;}
}hajime;

int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
unordered_map<ull,int>vis;
queue<state>Q;
int ans = -1, len = 0;

int ind(int x,int y){return (x-1)*n+y;}
int in(int x,int y){return x>=1 && x<=n && y>=1 && y<=m;} 
ull hsh(int *pp){
	ull now=0;
	for(int i=1;i<=len;i++)now=now*p+pp[i];
	return now;
}

void move(state now){
	int tmp[12];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(now.st[i][j] >= '1' && now.st[i][j] <= '9'){
				now.st[i][j] ++;
				if(now.st[i][j] < len + '1')tmp[now.st[i][j] - '0'] = ind(i, j);
			}
	int bx, by;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(now.st[i][j] == '2')
				bx = i, by = j;
			if(now.st[i][j] == len + '1')
				now.st[i][j] = '.';
		}
	
	now.cnt ++;
	for(int i=0;i<4;i++){
		int fx = bx + dx[i], fy = by + dy[i];
		if(!in(fx, fy))continue;
		if(now.st[fx][fy] == '@'){
			ans = now.cnt;
			return ;
		}else if(now.st[fx][fy] == '.'){
			tmp[1] = ind(fx, fy);
			now.st[fx][fy] = '1';
			ull nowhs = hsh(tmp);
			if(!vis.count(nowhs)){
				vis[nowhs] = 1;
//				vis.insert(nowhs);
				Q.push(now);
			}
			now.st[fx][fy] = '.';
		}
	}
}

signed main(){
	scanf("%d%d",&n,&m);
	
	for(int i=1;i<=n;i++)scanf("%s",hajime.st[i] + 1);
	
	int tmp[12];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(hajime.st[i][j] >= '1' && hajime.st[i][j] <= '9')
				len = max(len, hajime.st[i][j] - '0'),
				tmp[hajime.st[i][j] - '0'] = ind(i, j);
	hajime.cnt = 0;
	vis[hsh(tmp)] = 1;
//	vis.insert(hajime.gethash());
	Q.push(hajime);
	
	while(!Q.empty()){
		state now = Q.front(); Q.pop();
		
		move(now);
		if(~ans)break;
	}
	cout<<ans;

	return 0;
}

E
当 \(x=2k+1\) 时
\(z = k + 2y + 2ky\)
\(z+1 = (k+1)(2y+1)\)
注意如果 z+1 含有 >1 的奇数因子的话一定能被表示出来，所以不能含有，即 \(z = 2^r-1\)

当 \(x=2k\) 时
\(z = k + y + 2ky\)
\(2z+1 = (2k+1)(2y+1)\)
因此 \(2z+1\) 必然是奇素数，而 \(z = 2^r-1\)
代入有 \(2^{r+1}-1\) 是素数，这就是梅森素数
从oeis上拖一个1~40的梅森素数（注意oeis上对应的项就是 r+1），然后代入原式求出 \(z\) 即可。

// LUOGU_RID: 100275489
// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f,mod=1e9+7;

int pm[] = {0, 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011}; 
int pw(int x,int y){
	if(!y)return 1;
	if(y==1)return x;
	int mid=pw(x,y>>1);
	if(y&1)return 1ll*mid*mid%mod*x%mod;
	return 1ll*mid*mid%mod;
}
signed main(){
	int n;scanf("%d",&n);
	printf("%d\n",pw(2, pm[n]-1)-1);
	
	return 0;
}

标签：typedef,return,int,题解,long,139,CF225,dp,define
From： https://www.cnblogs.com/SkyRainWind/p/17062489.html

相关文章

  • 题解 ABC231D【Neighbors】
    首先，每个数不能有超过两个相邻元素，不然无法构成一条链。可以通过记录每个数出现次数（度数）来判断。其次，给的信息不能成环，不然也无法构成一条链。可以通过并查集来判断。在......
  • 题解 ARC115C【ℕ Coloring】
    显然\(A_1,A_2,A_4,A_8,\cdots\)必须互不相同，因此最大的数一定不小于\(\lfloor\log_2n\rfloor+1\)，猜想可以取到\(\lfloor\log_2n\rfloor+1\)。构造\(A_i=\lfloor\log......
  • 2023牛客寒假算法基础集训营2题解
    写在前面菜菜，哭哭，大佬救救QaQ理解大佬的代码并且整理成一篇博客真的很累...C：Tokitsukazeanda+b=n(hard)1.本蒟蒻的代码个人感觉用前缀和更方便。我最开始用的是线......
  • CF622F The Sum of the k-th Powers 题解
    观前提示本题解仅提供一个理论复杂度正确的解法，因为本题模数为\(10^9+7\)，没有优秀\(\text{MTT}\)板子的我被卡常了。正文部分不妨设\(S_{n,m}=\sum_{i=0}^{n-1}i^m......
  • CF576C 题解
    注意到\(\sum\limits_{i=2}^N|x_{p_i}-x_{p_{i-1}}|+|y_{p_i}-y_{p_{i-1}}|\)。本质上是两个点之间的曼哈顿距离。而曼哈顿最小距离生成树要\(O(n^2\logn)\)......
  • CF1768B 题解
    首先我们思考什么数是不用排序的。显然，序列中一个由\(1\)开始，每次递增\(1\)的子序列是不用排序的。为什么呢？因为我们把其他数按从大到小排好后这个子序列刚好构成排......
  • 洛谷P4983 忘情 题解报告
    题目地址题意：把正整数序列分隔为m个区间，若单个区间的元素之和为X，则其贡献为\((X+1)^2\)。求所有区间的贡献之和的最小值。分析：wqs二分+斜率优化dp。用单调队列发可......
  • abc273G题解
    \(dp[i][j]\)：考虑到前i行，有j个2的方案数。设有k个1（计算可得）。\(a_{i+1}=0\)：\(dp[i][j]\todp[i+1][j]\)\(a_{i+1}=1\)：\(dp[i][j]\times(n-j-k)\todp[......
  • win10下python3.9的代理报错问题解决（附web3的polygon爬虫源码）
    背景因为工作中经常需要代理访问，而开了代理，request就会报错SSLError，如下：requests.exceptions.SSLError:HTTPSConnectionPool(host='test-admin.xxx.cn',port=443):Ma......
  • C# 使用SQLDMO备份数据库时不显示进度的问题解决方法
    在使用SQLDMO备份数据库的过程中，参考了网上的例子，但是进度条却不显示，每次返回的都是0，解决方法是使用全局变量，每次做个累加就可以了。stringServerName="";......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99