首页 > 其他分享 >沪越联赛 - 2024年6月月赛Div2 题解

沪越联赛 - 2024年6月月赛Div2 题解

时间：2024-07-06 19:20:06浏览次数：13  
标签：nx typedef int 题解 long 2024 ny Div2 define

问题 A: 替换

题目描述

小明每次注释的时候都写 \(n\) 个 /。小红看了小明的程序，觉得太难看了，那么多 /，所以决定把这些没用的 / 都去掉。小红定义了一个宏命令，每次可以将所有连续的 \(m\) 个 / 替换成空（注意不是空格）
小明得知了小红的企图后非常着急，因为他知道光把 / 都去掉，那么原本注释掉的语句就会被编译，最终变成编译错误。他赶快来阻止小红。时间紧迫，小红只能进行一次操作，她又想用最小的
达到目的。出于对正常程序员的尊重，\(2\) 个 / 开头的注释（不是小明写的）要不受影响，只有小明写的 \(n\) 个 / 都会被去掉。

题解

签到题，但是我没过。
我赛时题目理解错了，小红的目的是把所有没用的 / 全部去掉，而不是把所有的 / 都去掉。

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
# define int long long

int n; 
signed main ()
{
	// freopen ("replace.in", "r", stdin);  
	// freopen ("replace.out", "w", stdout); 
	scanf ("%lld", &n); 
	if (n == 2) return 0; 
	if (n == 4) { printf ("4\n"); return 0; }
	bool flag = 0; 
	for (int i = 2; i * i <= n; i ++ )
	{
		if (n % i == 0)
		{
			flag = 1; 
			break; 
		}
	}
	if (!flag)
	{
		printf ("%lld\n", n); 
		return 0; 
	}
	for (int i = 3; i * i <= n; i ++ )
	{
		if (n % i == 0 && (n + 2) % i != 0)
		{
			printf ("%lld\n", i); 
			return 0; 
		}
	}
	for (int i = 2; i * i <= n; i ++ )
	{
		if (n % i == 0)
		{
			int t = n / i; 
			if (n % t == 0 && (n + 2) % t != 0)
			{
				printf ("%lld\n", t); 
				return 0; 
			}
		}
	}
    return 0;
}

问题 B: 马跳三步

题目描述

有一个国际象棋的马在无限大的平面直角坐标系从 \((0,0)\) 开始行走，问 \(3\) 步内，能不能到达指定目标

题解

签到

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
//# define int long long

struct node { int x, y, stp; }; 
int dx[8] = {-2, -2, -1, -1, 2, 2, 1, 1}; 
int dy[8] = {-1, 1, -2, 2, -1, 1, -2, 2}; 
bool bfs (int x, int y)
{
	queue <node> q; q.push ({0, 0, 0}); 
	map <pii, bool> vis; vis[{0, 0}] = 1; 
	while (!q.empty ())
	{
		node u = q.front (); q.pop (); 
		if (u.stp > 3) continue; 
		if (u.x == x && u.y == y) return 1; 
		for (int i = 0; i < 8; i ++ )
		{
			int nx = u.x + dx[i], ny = u.y + dy[i]; 
			if (vis[{nx, ny}]) continue; 
			vis[{nx, ny}] = 1; 
			q.push ({nx, ny, u.stp + 1}); 
		}
	}
	return 0; 
}
signed main ()
{
	freopen ("knight.in", "r", stdin); 
	freopen ("knight.out", "w", stdout); 
	int T; scanf ("%d", &T); 
	while (T -- )
	{
		int ex, ey; scanf ("%d%d", &ex, &ey); 
		if (bfs (ex, ey)) printf ("YES\n"); 
		else printf ("NO\n"); 
	}
    return 0;
}

问题 C: 加减算式

题目描述

有 \(n\) 张卡片，卡片上可能是 \(0\) ~ \(9\) 的一位数，也可能是运算符 + 或 -。可以任意排列这 \(n\) 张牌，并计算此时的结果（前导 \(0\) 是被允许的）

请计算，计算结果的最大值和最小值。

题解

赛时口胡除了正解，但是缺少很多细节。

最大值求法：
构造一个最大的数，其他的数都是一位数。
在剩下的一位数中，加大的，减小的。

最小值求法：

  1. 如果没有减号，可以发现，最小值所构成的数位数尽量平均。所以对于每个数维护在最小值中对应的 \(10\) 的幂次。
  2. 跟最大值一样，构造一个最大的数做减法，加小的，减大的
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
# define int long long
# define rd(t) read <t> ()
# define mem(a, b) memset (a, b, sizeof (a))
# define fi first
# define se second
# define lc u << 1
# define rc u << 1 | 1
# define debug printf ("debug\n")
const int N = 20, M = (1 << 15) + 5; 
template <typename T> inline T read ()
{
    T s = 0; int w = 1; char c = getchar (); 
    if (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
    for (; isdigit (c); c = getchar ()) s = (s << 1) + (s << 3) + c - '0';
    return s * w;
}

int n, m; 
char a[N]; 
int b[N], tot, tmp[N], cnt; 
int quan[N]; 
signed main ()
{
	freopen ("addsub.in", "r", stdin); 
	freopen ("addsub.out", "w", stdout); 
	n = rd (int); 
	for (int i = 1; i <= n; i ++ ) cin >> a[i]; 
	int add = 0, sub = 0; 
	for (int i = 1; i <= n; i ++ )
	{
		if (isdigit (a[i]) || a[i] == '0') b[ ++ tot] = a[i] - '0'; 
		else if (a[i] == '+') add ++ ; 
		else sub ++ ; 
	}
	// cout << sub << " " << add << endl; 
	sort (b + 1, b + 1 + tot, greater <int> ()); 
	string s = "", t = ""; 
	for (int i = 1; i <= tot; i ++ ) s += (char)(b[i] + '0'); 
	// cout << s << endl; 
	for (int i = s.size () - 1; i >= 0; i -- )
	{
		t = s[i] + t; 
		if (!sub && add) t = "+" + t, add -- ; 
		if (sub) t = "-" + t, sub -- ; 
	}
	// cout << t << endl; 
	int sum = 0, op = 1, num = 0; 
	for (int i = 0; i < t.size (); i ++ )
	{
		if (isdigit (t[i])) num = num * 10 + (t[i] - '0'); 
		else if (t[i] == '+') sum += op * num, num = 0, op = 1; 
		else sum += op * num, num = 0, op = -1; 
	}
	sum += op * num; 
	printf ("%lld ", sum); 
	
	add = 0, sub = 0; 
	for (int i = 1; i <= n; i ++ )
	{
		if (a[i] == '+') add ++ ; 
		else if (a[i] == '-') sub ++ ; 
	}
	if (!sub)
	{
		sort (b + 1, b + 1 + tot); 
		int he = (n + add - 1) / add; 
		int num = add + 1; 
		for (int i = 1; i <= tot; i ++ ) tmp[i] = b[i]; 
		int cnt = 0; 
		for (int i = 1; i <= tot; i ++ )
		{
			if (tmp[i] == 0)
				cnt ++ ; 
		}
		if (cnt)
		{
			int tmptot = tot; 
			tot = 0; 
			for (int i = cnt + 1; i <= tmptot; i ++ ) b[ ++ tot] = tmp[i]; 
		}
		// for (int i = 1; i <= tot; i ++ ); 
		// 0 0 0 1 2 3 4 5 ++ 
		// 4 6
		// 1 2 3 0 0 4 5
		for (int i = tot; i >= tot - num + 1; i -- ) quan[i] = 1; 
		for (int i = 1; i <= num; i ++ ) quan[i] = (tot / num); 
		for (int i = 1; i <= tot % num; i ++ ) quan[i] ++ ; 
		int wei = 2; 
		for (int i = tot - num; i >= num + 1; i -= num)
		{
			for (int j = i; j >= i - num + 1; j -- ) quan[j] = wei; 
			wei ++ ; 
		}
		/*
		7 6 0 0 0 0 0 0 0 0  0  1  1 
		1 2 3 4 5 6 7 8 9 10 11 12 13
		7 6 6 0 5 0 4 0 3 0 2 1 1 
		*/
		// cout << endl; 
		// for (int i = 1; i <= tot; i ++ ) cout << quan[i] << " " ;
		// cout << endl; 
		// return 0; 
		int ans = 0; 
		for (int i = 1; i <= tot; i ++ ) ans += b[i] * pow (10, quan[i] - 1); 
		printf ("%lld\n", ans); 
		return 0; 
	}
	int tmptot = tot; 
	sort (b + 1, b + 1 + tot); 
	for (int i = 1; i <= tot; i ++ ) tmp[i] = b[i]; 
	tot = 0; 
	for (int i = 1; i <= sub + add; i ++ ) b[ ++ tot] = tmp[i]; 
	for (int i = tmptot; i >= sub + add + 1; i -- ) b[ ++ tot] = tmp[i]; 
	s = "", t = ""; 
	for (int i = 1; i <= tot; i ++ ) s += (char)(b[i] + '0'); 
	for (int i = 0; i < s.size (); i ++ )
	{
		t = t + s[i]; 
		if (!add && sub) t = t + "-", sub -- ; 
		if (add) t = t + "+", add -- ; 
	}
	sum = 0, op = 1, num = 0; 
	for (int i = 0; i < t.size (); i ++ )
	{
		if (isdigit (t[i])) num = num * 10 + (t[i] - '0'); 
		else if (t[i] == '+') sum += op * num, num = 0, op = 1; 
		else sum += op * num, num = 0, op = -1; 
	}
	sum += op * num; 
	printf ("%lld\n", sum); 
    return 0;
}

问题 D: 滚雪球

题目描述

在 \(H\) 行 \(W\) 列的方格中，有些地方有雪，有些地方没雪。如果一个雪球在 \((X,Y)\) 的雪球可以滚到相邻的四个格子（不能滚到边界）。如果滚到雪上了，雪球大小 \(+1\)，否则雪球大小 \(-1\)。如果在某个时刻雪球大小为 \(0\)，就不能滚了。

在 \((X_a,Y_a)\) 有一个大小为 \(A\) 的雪球，人们要把他们滚到 \((X_b,Y_b)\)，而且大小需要为 \(B\)。人们想问问你，可不可以。

题解

赛时过了。

发现对于同一个格子，大小不同的时候是不同的状态。所以 visit 数组应该多一维。

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
# define int long long
const int N = 55; 

int n, m; 
int a, xa, ya, b, xb, yb; 
char mp[N][N]; 
struct node { int x, y, stp; }; 
int dx[4] = {1, -1, 0, 0}; 
int dy[4] = {0, 0, 1, -1}; 
bool vis[N][N][4005]; 
bool bfs ()
{
	queue <node> q; q.push ({xa, ya, a}); 
	memset (vis, 0, sizeof vis); 
	vis[xa][ya][a] = 1; 
	while (!q.empty ())
	{
		node u = q.front (); q.pop (); 
		if (!u.stp) continue; 
		if (u.x == xb && u.y == yb && u.stp == b) return 1; 
		for (int i = 0; i < 4; i ++ )
		{
			int nx = u.x + dx[i], ny = u.y + dy[i]; 
			int nstp = u.stp + (mp[nx][ny] == '*' ? 1 : -1); 
			if (nx < 1 || nx > n || ny < 1 || ny > m) continue; 
			if (vis[nx][ny][nstp]) continue; 
			vis[nx][ny][nstp] = 1; 
			q.push ({nx, ny, nstp}); 
		}
	}
	return 0; 
}
signed main ()
{
	freopen ("snowball.in", "r", stdin); 
	freopen ("snowball.out", "w", stdout); 
	int T; cin >> T; 
	while (T -- )
	{
		cin >> n >> m >> a >> xa >> ya >> b >> xb >> yb; 
		for (int i = 1; i <= n; i ++ )
		{
			for (int j = 1; j <= m; j ++ )
				cin >> mp[i][j]; 
		}
		if (bfs ()) printf ("Yes\n"); 
		else printf ("No\n"); 
	}
    return 0;
}

问题 E: 数羊

题目描述

\(wxz\) 睡觉的时候喜欢按照斐波那契数列数羊（第一次 \(1\) 只，第二次 \(2\) 只，第三次 \(3\)只 \(\cdots\)）。但是他有时候会少数一只羊。比如第 \(i\) 次数错了，那么第 \(i\) 次的数量就会变成第 \(i-1\) 次的数量 \(+\) 第 \(i-2\) 次的数量 \(-1\)。（第 \(4\) 次数错了，就会变成：\(1,1,2,2,4,6,10\)。

\(wxz\) 数了 \(n\) 次，羊的数量是 \(m\)，现在 \(wxz\) 想知道，最少数错了多少次，第 \(n\) 次的羊会变成 \(m\)。

题解

这道题有点神仙，但是看完题解感觉十分简单。
经过小数据的模拟，可以发现，减少的羊数也是斐波那契数列。所以，就是要找出最少增加多少个斐波那契数列的项，使得和为错误的数量。

不妨贪心的从 \(fib[n-2]\) 开始做，每次尝试可不可以放入。

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
# define int long long

int n, m; 
int f[85]; 
signed main ()
{
	freopen ("count.in", "r", stdin); 
	freopen ("count.out", "w", stdout); 
	scanf ("%lld%lld", &n, &m); 
	f[1] = f[2] = 1; 
	for (int i = 3; i <= n; i ++ ) f[i] = f[i - 1] + f[i - 2]; 
	if (f[n] - m < 0) { printf ("-1\n"); return 0; }
	int ans = 0; 
	int t = f[n] - m; 
	for (int i = n - 2; i >= 1; i -- )
	{
		if (f[i] <= t)
		{
			t -= f[i]; 
			ans ++ ; 
		}
		if (!t) break; 
	}
	printf ("%lld\n", ans); 
	return 0;
}

## 问题 F: 波折数列

题目描述

定义一个由 \(a,b,c\) 组成的序列是波折的，当且仅当：

  1. \(a,b,c\) 互不相等
  2. \(b\) 是最小的或者是最大的

\(n\) 个整数构成的序列是波折的，当且仅任意三个连续子序列都是波折的。
问 \(1\) ~ \(n\) 的所有排列中，有多少个是波折的。

题解

赛时过了

一开始，我以为是打表。但是我太菜了，打表程序跑到 \(20\) 就没法跑了。

不能打表，那可以考虑 \(dp\)（不然这场比赛没有 \(dp\) 了）

考虑 \(dp_{i,0}\) 表示有 \(i\) 个人且 \(i\) 个人结尾的方法数，\(dp_{i,1}\) 表示有 \(i\) 个人且第 \(i\) 个人为开头方法数。

有 \(i\) 个人排列的方法数就是

\[ans_i+=dp_{j,0}*dp_{i-j-1,i}\times \binom{i-1}{j} \]

因为不确定前面 \(j\) 个人的顺序，所以要在 \(i-1\) 个人中选 \(j\) 个人出来。

容易发现，\(i\) 是结尾的个数和 \(i\) 是开头的个数相等。所以：

\[dp_{i,0}=dp_{i,1}=\frac{ans_i}{2} \]

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
# define int long long
# define debug printf ("debug\n")
const int N = 3005, p = 1e9 + 7; 

int n; 
int getinv (int a, int b = p - 2)
{
	int ans = 1; 
	while (b)
	{
		if (b & 1) ans = ans * a % p; 
		a = a * a % p; 
		b >>= 1; 
	}
	return ans; 
}
int c[N][N]; 
void init ()
{
    for (int i = 0; i < N; i ++ )
    {
        for (int j = 0; j <= i; j ++ )
        {
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % p;
        }
    }
}
int dp[N][2];
int sum[N];
signed main()
{
	freopen ("zigzag.in", "r", stdin); 
	freopen ("zigzag.out", "w", stdout); 
	scanf ("%lld", &n); 
    init (); 
    sum[1] = 1;
    sum[2] = 2;
    dp[0][0] = dp[0][1] = 1;
    dp[1][0] = dp[1][1] = 1;
    dp[2][0] = dp[2][1] = 1;
    for (int i = 3; i <= n; i ++ )
    {
        for (int j = 0; j < i; j ++ )
			sum[i] = (sum[i] + dp[j][0] * dp[i - j - 1][1] % p * c[i - 1][j] % p) % p;
        dp[i][0] = dp[i][1] = sum[i] * getinv (2) % p;
    }
    printf ("%lld\n", sum[n]); 
    return 0;
}

标签：nx,typedef,int,题解,long,2024,ny,Div2,define
From： https://www.cnblogs.com/legendcn/p/18287362

相关文章

  • C++题解(3) 信息学奥赛一本通: 1013：温度表达转化 洛谷:B2013 温度表达转化 土豆编程:M
    【题目描述】利用公式 C=5×(F−32)÷9C=5×(F−32)÷9(其中CC表示摄氏温度，FF表示华氏温度)进行计算转化,输入华氏温度FF，输出摄氏温度CC，要求精确到小数点后55位。【输入】输入一行，包含一个实数FF，表示华氏温度。（F≥−459.67）（F≥−459.67）【输出】输出一行，包含一个......
  • 前端生成二维码（N种方法选择2024最新）
    文来分享5个用于生成二维码的JavaScript工具库，助你快速生成二维码！node-qrcodenode-qrcode是一个用于生成二维码的Node.js库，它支持多种数据格式，并且可以将生成的二维码导出为各种图像格式，如PNG、JPEG、SVG和DataURI，其适用于服务端和客户端。node-qrcode的特点如下：......
  • [AGC064D] Red and Blue Chips 题解
    题目链接点击打开链接题目解法挺牛的题这种计数本质不同的结果的题，一个很不错的切入口是判断结果的合法性令B的总数为\(m\)我们把结果串先挂在第\(m\)个B上考虑从后往前枚举原串（最后一个B不枚举），相当于我们在倒序模拟操作过程枚举到B，我们相当于要把后面的一个B......
  • HT-014 Div3 扫雷 题解 [ 绿 ] [ 二维差分 ]
    分析观察到是曼哈顿距离\(\ler\)的范围可以扫到，联想到如下图形：左边是\(r=1\)可以扫到的范围，右边是\(r=2\)可以扫到的范围。于是，我们只要对这样的图形在\(1000*1000\)的格子里差分一下就好了。但这样的复杂度是\(O(nm)\)的，会死的很惨。优化不难发现这个图形是一......
  • HT-014 Div3 跳棋 题解 [ 黄 ] [ 并查集 ] [ 树型结构 ]
    分析依旧是一个连通块题。观察题面不难发现两个重要性质：一个跳棋只能以它旁边的两个跳棋为中点跳跃，且满足跳跃路线中除中点以外没有其它跳棋阻挡。只有我们的跳棋可以移动。跳棋的操作具有可逆性/对称性。第三条性质可以这么理解，就是一个跳棋跳过去之后，它还可以跳回来。......
  • 【2023-2024第二学期】助教工作学期总结——数字电路与逻辑设计助教
    一、助教工作的具体职责和任务协助教师引导大一转专业学生如何学习本门课程，收集学生问题、定期答疑、协助教师批改作业并跟踪作业完成情况，实验指导，改进课程建设。指导学生学习《数字电路与逻辑设计》。并指导学生完成《数字电路与逻辑设计实验》。二、助教工作的每周时长和具体......
  • [POI2015] WYC 题解
    [POI2015]WYC显然矩阵乘法发现点数和边权非常小，所以可以考虑拆点把每个点拆为\(u_1\),\(u_2\),\(u_3\)，初始：\(u_1\tou_2\),\(u_2\tou_3\)，每一条加边：\(u+(w-1)\timesn\tov\)因为\(k\)非常大，所以考虑倍增优化注意：答案会爆longlong，需要使用unsignedlonglong//Pro......
  • 百元蓝牙耳机推荐2024，百元蓝牙耳机排行榜盘点
    在2024年面对琳琅满目的蓝牙耳机选项，消费者往往难以抉择，特别是在预算有限的情况下，如何在众多产品中挑选出既满足质量又符合预算的耳机成为了一个不小的挑战。为了帮助大家在繁多的选择中找到真正物有所值的百元蓝牙耳机，我们经过深入的市场研究和用户反馈收集，精心准备了一份最......
  • 【2023-2024第二学期】助教工作学期总结（教务处助教）
    一、助教工作的具体职责和任务帮助老师整理试卷以及存放协助老师做会议记录表二、助教工作的每周时长和具体安排每周工作时间不定，一般情况下由老师通知，课余时间随叫随到，具体安排是做会议记录表和其他事情三、对助教工作反思第一，工作时要细心，不要贪图一时快，要细心照顾每一个......
  • 让我彻底沉迷的设计神器CorelDRAW2024中文版本发布啦！
    ......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99