暑假篇——NOIP2017模拟赛题解

2023-10-20 12:10
文章标签 模拟 暑假 题解 noip2017

本文主要是介绍暑假篇——NOIP2017模拟赛题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一.优雅的序列

1.题目

2.题解 

3.Code

二.甲虫入侵

1.题目

2.题解 

3.Code

三.大逃亡

1.题目

2.题解 

3.Code

 

谢谢！

虽然三道题上了200，但还是有点菜

一.优雅的序列

1.题目

点击打开链接

2.题解 

这道题难就难在重复的数字上，如果没有重复的数字，直接n-1。

不难发现，越小的数越要往前面放，但是又为了尽量避免重复，我们就轮换着放，比如：

1 1 1 2 3 4 4 4 5

就应该变成：

1 2 3 4 5 1 4 1 4

这样就能保证有最多对a[i] < a[i + 1]；

具体实践如下：

step1：把每个数字排序后的起点和重复数量存在一个pair数组内；

step2：用len表示最后排好的数组长度，每次枚举每一个数字，直到枚举完每一个数字为止。

step3：统计满足条件的i的个数。

3.Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
int n, k, len;
LL a[100005], ans, a1[100005];
pair <int, int> p[100005];
int main (){//freopen ("grace.in", "r", stdin);//freopen ("grace.out", "w", stdout);scanf ("%d", &n);for (register int i = 1; i <= n; i ++)scanf ("%lld", &a[i]);sort (a + 1, a + 1 + n);for (register int i = 2; i <= n; i ++){if (a[i] == a[i - 1]){int j;for (j = i; j <= n; j ++)if (a[j] != a[j - 1])break;p[++ k].first = i - 1;p[k].second = j - i + 1;i = j;}else{p[++ k].first = i - 1;p[k].second = 1;}}if (a[n] != a[n - 1]){p[++ k].first = n;p[k].second = 1;}while (len < n){for (register int i = 1; i <= k; i ++){if (p[i].second){a1[++ len] = a[p[i].first];p[i].first ++;p[i].second --;}}}for (register int i = 1; i <= len; i ++)if (a1[i] < a1[i + 1])ans ++;printf ("%lld\n", ans);return 0;
}

二.甲虫入侵

1.题目

点击打开链接

2.题解 

这道题是整个最难的题目，要用离散化+暴力搜索。

首先输入时可以把每次移动看做一个点，起点是（0,0）例如：样例第一个就是：（8,0）

每次移动要存入两个点，这是为后面的离散化做准备的；

然后，对于我们存入的每一个点，我们要进行去重操作（里面要排序），横坐标和纵坐标分别进行。

接着就进行离散化，我存入的每一个点都对应他们自己的一个下标，就可以用这些下标表示他们的值，一共只有1000个点，离散化之后整个的空间就变成了2000。

然后再来标记农夫走过的田地，这里我们用upper_bound找到农夫每次走之后的坐标离散化之后的下标，把洒过农药的田地标为1。

接着暴力搜索一波，把甲虫能到的位置标为-1；

最后就是统计面积，我们先来看一看离散化之后农场的样子：（标黄的是我们要求的不被甲虫侵犯的面积）

相当于每一个点都被我扩散成了两个点，那么面积的求法就是1 * 4 + (x2 - x1 - 1) * (y1 - y2 + 1) + (y1 - y2 - 1) * (x2 - x1 + 1);

就这样求面积就完了。

有点懵，上代码：

3.Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define M 2005
int n, len[M], cntx, cnty, curx, cury, realx[M], realy[M], vis[M][M];
char dir[M];
int d[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
LL ans;
void unique (int *x, int &cnt){sort (x, x + cnt);int cnt1 = 1;for (int i = 1; i < cnt; i ++)if (x[i] != x[i - 1])x[cnt1 ++] = x[i];cnt = cnt1; 
}
bool pd (int tox, int toy){if (tox < 0 || tox >= cntx || toy < 0 || toy >= cnty || vis[tox][toy])return 0;return 1;
}
void DFS (int x, int y){vis[x][y] = -1;for (int i = 0; i < 4; i ++){int tox = x + d[i][0];int toy = y + d[i][1];if (pd (tox, toy))DFS (tox, toy);}
}
int main (){scanf ("%d", &n);for (int i = 1; i <= n; i ++){scanf ("\n%c %d", &dir[i], &len[i]);if (dir[i] == 'L'){realx[cntx ++] = curx + 1;realy[cnty ++] = cury;realx[cntx ++] = curx -= len[i];realy[cnty ++] = cury + 1;}if (dir[i] == 'R'){realx[cntx ++] = curx;realy[cnty ++] = cury;realx[cntx ++] = (curx += len[i]) + 1;realy[cnty ++] = cury + 1;}if (dir[i] == 'U'){realx[cntx ++] = curx;realy[cnty ++] = cury;realx[cntx ++] = curx + 1;realy[cnty ++] = (cury += len[i]) + 1;}if (dir[i] == 'D'){realx[cntx ++] = curx;realy[cnty ++] = cury + 1;realx[cntx ++] = curx + 1;realy[cnty ++] = cury -= len[i];}}unique (realx, cntx);unique (realy, cnty);int Indexx = lower_bound (realx, realx + cntx, curx = 0) - realx, Indexy = lower_bound (realy, realy + cnty, cury = 0) - realy, now;for (int i = 1; i <= n; i ++){if (dir[i] == 'L'){now = lower_bound (realx, realx + cntx, curx -= len[i]) - realx;for ( ; Indexx > now; Indexx --)vis[Indexx][Indexy] = 1;}if (dir[i] == 'R'){now = lower_bound (realx, realx + cntx, curx += len[i]) - realx;for ( ; Indexx < now; Indexx ++)vis[Indexx][Indexy] = 1;}if (dir[i] == 'U'){now = lower_bound (realy, realy + cnty, cury += len[i]) - realy;for ( ; Indexy < now; Indexy ++)vis[Indexx][Indexy] = 1;}if (dir[i] == 'D'){now = lower_bound (realy, realy + cnty, cury -= len[i]) - realy;for ( ; Indexy > now; Indexy --)vis[Indexx][Indexy] = 1;}}vis[Indexx][Indexy] = 1;for (int i = 0; i <= cntx; i ++){if (! vis[i][0]) DFS (i, 0);if (! vis[i][cnty]) DFS (i, cnty);}for (int i = 1; i < cnty; i ++){if (! vis[0][i]) DFS (0, i);if (! vis[cntx][i]) DFS (cntx, i);}for (int i = 1; i <= cntx; i ++){for (int j = 1; j <= cnty; j ++){if (~vis[i][j])ans += (LL) (realx[i] - realx[i - 1]) * (realy[j] - realy[j - 1]);}}printf ("%lld\n", ans);return 0;
}

三.大逃亡

1.题目

点击打开链接

2.题解 

很简单，因为答案具有单调性，直接二分答案，然后暴力搜索检查答案，注意有细节，特别是二分和距离有可能是0

3.Code

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
#define M 10005
struct node {int xx, yy, step;node (){};node (int XX, int YY, int STEP){xx = XX;yy = YY;step = STEP;}
};
int n, X, Y, sx, sy, tx, ty, dx[M], dy[M], ans1, ans2, dis[1005][1005];
int dir[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
bool flag[1005][1005], vis[1005][1005];
int fabs (int x){if (x < 0)return -x;return x;
}
bool pd1 (int tox, int toy){if (tox < 0 || tox >= X || toy < 0 || toy >= Y || vis[tox][toy])return 0;return 1;
}
void prepare (){queue <node> Q;for (int i = 1; i <= n; i ++)Q.push (node (dx[i], dy[i], 0));while (! Q.empty ()){node f = Q.front ();if (! dis[f.xx][f.yy])dis[f.xx][f.yy] = f.step;Q.pop ();for (int i = 0; i < 4; i ++){int tox = f.xx + dir[i][0];int toy = f.yy + dir[i][1];if (pd1 (tox, toy)){vis[tox][toy] = 1;Q.push (node (tox, toy, f.step + 1));}}}
}
bool pd (int tox, int toy, int now){if (tox < 0 || tox >= X || toy < 0 || toy >= Y || vis[tox][toy] || dis[tox][toy] < now)return 0;return 1;
}
inline int BFS (int now){memset (vis, 0, sizeof vis);queue <node> Q;vis[sx][sy] = 1;Q.push (node (sx, sy, 0));while (! Q.empty ()){node f = Q.front ();Q.pop ();if (f.xx == tx && f.yy == ty)return f.step;for (register int i = 0; i < 4; i ++){int tox = f.xx + dir[i][0];int toy = f.yy + dir[i][1];if (pd (tox, toy, now)){vis[tox][toy] = 1;Q.push (node (tox, toy, f.step + 1));}}}return -1;
}
inline int check (int now){int tmp = BFS (now);return tmp;
}
int main (){//freopen ("escape.in", "r", stdin);//freopen ("escape.out", "w", stdout);int l = 0, r = 0x3f3f3f3f, mid;scanf ("%d %d %d %d %d %d %d", &n, &X, &Y, &sx, &sy, &tx, &ty);for (register int i = 1; i <= n; i ++){scanf ("%d %d", &dx[i], &dy[i]);r = min (r, fabs (dx[i] - sx) + fabs (dy[i] - sy));r = min (r, fabs (dx[i] - tx) + fabs (dy[i] - ty));}prepare ();int tmp;while (l + 1 < r){mid = (l + r) / 2;tmp = check (mid);if (tmp != -1){l = mid;}elser = mid - 1;}ans1 = l, ans2 = tmp;int tp = check (r);if (tp != -1)ans1 = r, ans2 = tmp;printf ("%d %d\n", ans1, ans2);return 0;
}

谢谢！

这篇关于暑假篇——NOIP2017模拟赛题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/247005。

相关文章

【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
usaco 1.2 Transformations（模拟）

usaco 1.2 Transformations（模拟）

我的做法就是一个一个情况枚举出来 注意计算公式： （ 变换后的矩阵记为C） 顺时针旋转90°：C[i] [j]=A[n-j-1] [i] （旋转180°和270° 可以多转几个九十度来推） 对称：C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<
阅读更多...
hdu4431麻将模拟

hdu4431麻将模拟

给13张牌。问增加哪些牌可以胡牌。 胡牌有以下几种情况： 1、一个对子 + 4组 3个相同的牌或者顺子。 2、7个不同的对子。 3、13幺 贪心的思想： 对于某张牌>=3个，先减去3个相同，再组合顺子。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOExcepti
阅读更多...
C++ | Leetcode C++题解之第393题UTF-8编码验证

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目： 题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
C语言 | Leetcode C语言题解之第393题UTF-8编码验证

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目： 题解： static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return
阅读更多...
每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎，细嗅蔷薇。你好朋友，这里是锅巴的C\C++学习笔记，常言道，不积跬步无以至千里，希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目： 牛牛发明了一种新的四舍五入应用于整数，对个位四舍五入，规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数
阅读更多...
C - Word Ladder题解

C - Word Ladder题解

C - Word Ladder 题解 解题思路： 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数（也就是需要变换多少次） 开始替换时： tips: 字符串下标以0开始 我们定义两个变量a和b，用于记录当前遍历到的字符 首先是判断：如果这时a已经==b了，那么就跳过，不用管； 如果a大于b的话：那么我们就让s中的第i项替换成b，接着就直接输出S就行了。 这样
阅读更多...
【算法专场】模拟（下）

【算法专场】模拟（下）

目录 前言 38. 外观数列 算法分析 算法思路 算法代码 1419. 数青蛙 算法分析 算法思路 算法代码  2671. 频率跟踪器 算法分析 算法思路 算法代码 前言 在前面我们已经讲解了什么是模拟算法，这篇主要是讲解在leetcode上遇到的一些模拟题目~ 38. 外观数列 算法分析 这道题其实就是要将连续且相同的字符替换成字符重复的次数+
阅读更多...
模拟实现vector中的常见接口

模拟实现vector中的常见接口

insert void insert(iterator pos, const T& x){if (_finish == _endofstorage){int n = pos - _start;size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;reserve(newcapacity);pos = _start + n;//防止迭代
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2