首页 > 其他分享 >4.14训练解题报告

4.14训练解题报告

时间：2023-04-14 17:35:27浏览次数：54  
标签：return 4.14 训练 int res scanf 解题 Maxn include

比赛传送门 \(\color{white} 20230413Tainrnig\)

A. Ice Cave

题意：考虑糖豆人的蜂窝迷图中的一层，走过一个正常格子就会变成洞。给定当前地板局面（抽象成 \(n\times m\) 矩阵），以及起点和终点，求是否能在终点位置掉到下一层。特殊地，本题不允许停留。起点终点可以相同。\(n,m\le 500\)

判断是否能到达是容易的，dfs 即可。

如果终点本来有洞，到达终点即可。如果没有洞，到达终点后要向旁边走一格再回来。这也就要求旁边某个非洞的格子不能走。枚举邻居钦定成洞，判断是否可达即可。

对于起点等于终点的情况，只要将起点设成没有洞即可，避免了特殊处理。

By KrK

#include <cstdio>
#include <algorithm>
#pragma comment(linker, "/STACK:16000000")
using namespace std;

const int Maxn = 505;
const int Maxd = 4;
const int dy[Maxd] = {-1, 0, 1, 0};
const int dx[Maxd] = {0, -1, 0, 1};

int n, m;
char B[Maxn][Maxn];
int sr, sc;
int fr, fc;
bool tk[Maxn][Maxn];

void Fill(int r, int c)
{
	if (B[r][c] == 'X' || tk[r][c]) return;
	tk[r][c] = true;
	for (int i = 0; i < Maxd; i++)
		Fill(r + dy[i], c + dx[i]);
}

bool findPath()
{
	fill((bool*)tk, (bool*)tk + Maxn * Maxn, false);
	Fill(sr, sc);
	return tk[fr][fc];
}

int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%s", B[i] + 1);
		B[i][0] = B[i][m + 1] = 'X';
	}
	for (int j = 0; j <= m + 1; j++)
		B[0][j] = B[n + 1][j] = 'X';
	scanf("%d %d", &sr, &sc); B[sr][sc] = '.';
	scanf("%d %d", &fr, &fc);
	if (B[fr][fc] == 'X') { B[fr][fc] = '.'; printf("%s\n", findPath()? "YES": "NO"); return 0; }
	for (int i = 0; i < Maxd; i++) {
		int nr = fr + dy[i], nc = fc + dx[i];
		if (B[nr][nc] == '.') {
			B[nr][nc] = 'X';
			if (findPath()) { printf("YES\n"); return 0; }
			B[nr][nc] = '.';
		}
	}
	printf("NO\n");
	return 0;
}

B. Bad Luck Island

有三个种族，分别出剪刀石头布，每一时刻随机两个人相遇，输者会被吃掉（平局则无事）。问每个种族活到最后的概率。\(n\le 100\)

显然可以 DP。设 \(f[x][y][z]\) 为一个三元组，表示在当前人数局面下，三个种族活到最后的概率。由于相同的无效，所以可钦定不同，人数一定会减少。简单算一下概率即可转移。

个人觉得此题中写记忆化搜索比较方便。

By cxm1024

#include <bits/stdc++.h>
using namespace std;
#define ld long double
array<ld, 3> f[110][110][110];
bool vis[110][110][110];
array<ld, 3> dfs(int x, int y, int z) {
	if (vis[x][y][z]) return f[x][y][z];
	vis[x][y][z] = 0;
	if (x == 0 || y == 0 || z == 0) {
		if (x && !z) return {1, 0, 0};
		else if (y && !x) return {0, 1, 0};
		else if (z && !y) return {0, 0, 1};
		else assert(0);
	}
	ld all = x * y + y * z + x * z;
	array<ld, 3> res{0, 0, 0};
	auto solve = [&](array<ld, 3> x, ld tmp) {
		for (int i = 0; i < 3; i++)
			res[i] += x[i] * tmp;
	};
	solve(dfs(x - 1, y, z), (ld)x * z / all);
	solve(dfs(x, y - 1, z), (ld)x * y / all);
	solve(dfs(x, y, z - 1), (ld)y * z / all);
	return f[x][y][z] = res;
}
signed main() {
	int x, y, z;
	scanf("%d%d%d", &x, &y, &z);
	auto res = dfs(x, y, z);
	printf("%.10Lf %.10Lf %.10Lf\n", res[0], res[1], res[2]);
	return 0;
}

C. Woodcutters

题意：数轴上有 \(n\) 棵树，坐标为 \(x_i\)，高度为 \(h_i\)。砍倒时可以选择往左还是往右，但树之间不能重叠（点重叠也不行）。问最多砍多少棵树。

显然可以贪心。从左往右考虑每一棵树。如果可以往左倒则往左，否则如果可以往右就往右，否则不倒。过程中维护当前的右端点即可。正确性显然。

By cxm1024

#include <bits/stdc++.h>
using namespace std;
int n;
pair<int, int> a[100010];
signed main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d%d", &a[i].first, &a[i].second);
	a[n + 1].first = 2e9 + 7;
	int lst = -2e9, ans = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i].first - a[i].second > lst)
			ans++, lst = a[i].first;
		else if (a[i].first + a[i].second < a[i + 1].first)
			ans++, lst = a[i].first + a[i].second;
		else lst = a[i].first;
	}
	printf("%d\n", ans);
	return 0;
}

D. Queue

题意：有 \(n\) 个人，第 \(i\) 个人需要 \(t_i\) 时间服务，每个人希望等待时间不能超过他的服务时间。问最多能让多少人满意。\(n,t\le 10^5\)

首先贪心地找性质。

  1. 首先发现不满意的人一定可以扔到最后，不会对其他人产生影响，所以只需要考虑选一部分人满意即可。

  2. 满意的人中一定是从小往大排，因为如果前面的时间大于后面的时间，后面的人一定不满意（等待时间过长），于是先从小到大排序。

  3. 进一步地，我们可以发现，每加入一个人，当前的时间都会至少 \(\times 2\)，所以人数是 \(\log\) 级别的。

    至此，有一个显然的 DP，\(f[i][j]\) 表示考虑了前 \(i\) 个人，选了 \(j\) 个的最小时间，则 \(f[i][j]=a[i]+\min f[k][j-1]\)，其中 \(\min\) 式可以简单地维护。复杂度 \(O(n\log n)\)。

    By cxm1024

    #include <bits/stdc++.h>
using namespace std;
#define int long long
int a[100010], f[100010][35], g[35];
signed main() {
	memset(g, 0x3f, sizeof(g));
	g[0] = 0;
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++)
		for (int j = 34; j >= 1; j--) {
			if (g[j - 1] <= a[i]) {
				f[i][j] = g[j - 1] + a[i];
				g[j] = min(g[j], f[i][j]);
			}
		}
	int ans = 0;
	for (int i = 1; i <= 34; i++)
		if (g[i] < 1e18) ans = i;
	printf("%d\n", ans);
	return 0;
}

  4. 继续观察可以发现，一定是每一步的人权值越小越好。即，如果某一次选择的人值为 \(x\)，存在一个值为 \(y(<x)\) 的人也满足条件，此时换成选 \(y\) 一定更优。

    据此，我们有一个更强的贪心的做法：排序后，从左到右考虑，如果能选则直接选中即可。

    By KrK

    #include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int Maxn = 100005;

int n;
int t[Maxn];
ll cur;
int res;

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &t[i]);
	sort(t, t + n);
	for (int i = 0; i < n; i++)
		if (cur <= t[i]) { res++; cur += t[i]; }
	printf("%d\n", res);
	return 0;
}

E. Soldier and Cards

题意：有两堆牌总共组成 \(1\sim n\) 的排列，每次取顶上的比较，大的可以获取到对方的牌：先把对方的那张放到自己堆底，再把自己的那张放到堆底。没有牌的人输。问结束的步数以及输赢情况，或输出永远不会结束。\(n\le 10\)。

注意到 \(10!<4\times 10^6\)，所以可以暴力模拟，如果出现环则永远不会结束，否则一定会在 \(10!\) 步内结束。

判定环看起来需要用 set 之类的东西，而且不方便记录状态（比如我就通过一个排列和一个分界点来表示状态）。事实上，只要暴力模拟，超过了 \(10!\) 步就可以认定为环。

By KrK

#include <cstdio>
#include <deque>
using namespace std;

const int lim = 4000000;

int n;
deque <int> Q1, Q2;
int res;

int main()
{
	scanf("%d", &n);
	int n; 
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int a; scanf("%d", &a);
		Q1.push_back(a);
	}
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int a; scanf("%d", &a);
		Q2.push_back(a);
	}
	while (res <= lim && !Q1.empty() && !Q2.empty()) {
		res++;
		if (Q1.front() > Q2.front()) { Q1.push_back(Q2.front()); Q1.push_back(Q1.front()); }
		else { Q2.push_back(Q1.front()); Q2.push_back(Q2.front()); }
		Q1.pop_front(); Q2.pop_front();
	}
	if (res <= lim)
		printf("%d %d\n", res, Q1.empty()? 2: 1);
	else printf("-1\n");
	return 0;
}

F. Soldier and Number Game

题意：多次询问，每次给定一个 \(a,b\)，求 \(\frac{a!}{b!}\) 的质因数个数（\(p^c\) 算 \(c\) 次）。\(T\le 10^6,a,b\le 5e6\)。

显然可以把分子分母分别求出来相减。由于 \(n!\) 的质因子个数即为 \(1\sim n\) 的质因子个数之和，所以只需要求出每个值的质因子个数即可。可以通过线性筛/埃氏筛求出来。

By cxm1024

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e6;
int prime[MAXN + 10], cnt[MAXN + 10], tot = 0;
bool isprime[MAXN + 10];
void getprime() {
	memset(isprime, 1, sizeof(isprime));
	isprime[0] = isprime[1] = 0;
	for (int i = 2; i <= MAXN; i++) {
		if (isprime[i]) {
			prime[++tot] = i;
			cnt[i] = 1;
		}
		for (int j = 1; j <= tot && i * prime[j] <= MAXN; j++) {
			isprime[i * prime[j]] = 0;
			cnt[i * prime[j]] = cnt[i] + 1;
			if (i % prime[j] == 0) break;
		}
	}
	for (int i = 2; i <= MAXN; i++)
		cnt[i] += cnt[i - 1];
}
void Solve(int test) {
	int x, y;
	scanf("%d%d", &x, &y);
	printf("%d\n", cnt[x] - cnt[y]);
}
signed main() {
	getprime();
	int T;
	scanf("%d", &T);
	for (int i = 1; i <= T; i++) Solve(i);
	return 0;
}

标签：return,4.14,训练,int,res,scanf,解题,Maxn,include
From： https://www.cnblogs.com/cxm1024/p/17318999.html

相关文章

  • 2023.4.14每日会议
    昨天做了什么：完成了对listview的item点击弹出详细信息，完成了图片识别微信支付截图录入遇到了那些问题：相机拍的照片太模糊，图片识别识别不出来今天打算做什么：根据用户消费比例给出消费建议，并且做总支付的图以及各项占比 ......
  • 「解题报告」CF1528F AmShZ Farm
    之前zzy讲题讲到的，今天在题单里看到了，就又做了下。首先发现，对于一个\(a\)数组，\(b\)数组的方案数就是\(a\)中每个数的出现次数的\(k\)次方加和。考虑如何将\(a\)数组的条件转化一下。贪心的想，对于一个\(a_i\)，我们肯定要尽可能使得它最终的数尽可能小。那么我们考虑每......
  • Codeforces Round #289 Div. 2 解题报告 A.B.C.E
    A-MaximuminTable纯递推。代码如下：#include<iostream>#include<string.h>#include<math.h>#include<queue>#include<algorithm>#include<stdlib.h>#include<map>#include<set>#include<stdio.h>usingn......
  • Codeforces Round #290 (Div. 2) 解题报告 A.B.C.D.
    A-FoxAndSnake模拟。代码如下：#include<iostream>#include<string.h>#include<math.h>#include<queue>#include<algorithm>#include<stdlib.h>#include<map>#include<set>#include<stdio.h>usingnames......
  • Codeforces Round #287 (Div. 2) 解题报告 A.B.C.D.E
    这次的CF挺水的，当时B题犯了一个很SB的错误，浪费了好多时间，所以D和E也没来得及看。sad，。。A-AmrandMusic水题，从小的开始选。代码如下：#include<iostream>#include<string.h>#include<math.h>#include<queue>#include<algorithm>#include<stdlib.h>#include<map>......
  • 如何训练个人的ChatGpt4
    如何在自己的计算机上安装类似ChatGPT的个人AI并在没有互联网的情况下运行它本文旨在为任何人安装此软件。最初它有一个视频，伴随着操作方法，但是事情变化很快，我的三次尝试只是推迟了我发表这篇文章。我以后可能会包括它。我努力创建一个简单的分步说明，为极端新手安装个人AI。......
  • Codeforces Round #305 (Div. 1) A.B.C 解题报告
    A.MikeandFrog枚举。先是找循环，然后很容易得出一个两元一次方程，然后可以发现解也是有循环节的，所以最小的那个肯定出现在一定范围内，否则就后面也不可能出现。假设两个变量为x,y,系数分别为z1,z2。很显然，两者的最小公倍数便是一个周期，所以如果枚举x的话，只需要枚举到z2就可......
  • HDU 4864Task(多校联合训练1）（贪心）
    题目地址：HDU4864这题又是一上来认为是最小费用流，但是边太多，果然，敲完交上去后不断TLE。。小优化了两次也没过。。。sad。。后来看了题解才发现是贪心。。。贪心也不好想。大体思路是很好想的，就是先都按时间从大到小排序，再遍历任务，从机器里找能匹配的，并在能匹配的里边找等级尽量小的......
  • 「解题报告」CF960G Bandit Blues
    无脑的APJ用最无脑的方法解题！！！做了两天图论脑子爆炸后的apj寻求精神慰藉首先考虑\(n\)一定是从前往后的最大值与从后往前的最大值，这样我们只需要求出长度为\(n\)，有\(k\)个前缀最大值的排列数量，记作\(f_{n,k}\)。考虑每次将当前排列中的最大值与最大值后面的排列去掉，这......
  • 使用 LoRA 和 Hugging Face 高效训练大语言模型
    在本文中，我们将展示如何使用大语言模型低秩适配(Low-RankAdaptationofLargeLanguageModels，LoRA)技术在单GPU上微调110亿参数的FLAN-T5XXL模型。在此过程中，我们会使用到HuggingFace的Transformers、Accelerate和PEFT库。通过本文，你会学到:如何搭建开发环......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99