目录

• 1.鬼画符门莲台争夺战（枚举）
• • 题目
  • 题解
  • • 枚举
    • 线段树标记
    • 前缀和占领次数
  • 代码（枚举，100%）
• 2.津津的储蓄计划（模拟）
• • 题目
  • 题解
  • 代码（未知%）
• 3.多边形的面积
• • 题目
  • 题解
• 4.小桥流水人家
• • 题目
  • 题解
  • 代码（100%）

1.鬼画符门莲台争夺战（枚举）

题目

鬼画符门莲台争夺战！ 虽然鬼画符门是一个三流门派但是近期为了改善宗门弟子质量。 特意引进了进化莲台。
部分精英弟子会自己独占一块区域，或者几个精英弟子一块占领一块区域，他们占领的区域普通弟子不可以再占领，小艺作为普通弟子想知道自己还能占领哪些地方。
莲台区域以1开始，由小到大编号表示。

题解

题意相当于一排若干格，有若干矩形，各覆盖连续的若干格，问有多少格未被任何矩形覆盖。

枚举

数据范围非常小，可以直接枚举每个位置，是否被至少一段占领。
时间复杂度： O(区域数*段数)

线段树标记

建一棵线段树，维护表示是否已占领的懒标记，每次将一段标记为已占领，最后遍历每个位置是否被占领。
时间复杂度：O(段数*log(区域数) + 区域数)

前缀和占领次数

用以每个位置为末尾的前缀和，表示该位置被占领的次数。
每当占领[L, R]，在L加1，在（R+1）减1。
最后扫描一遍，每个位置的被占领次数，为0则累加到答案。
时间复杂度：O(段数+区域数)

代码（枚举，100%）

#include 
#include 
#include 
#include using namespace std;int stringToInt(string s) {int x = 0;for (int i = 0; i < (int) s.length(); i++) {x = x * 10 + s[i] - '0';}return x;
}std::vector solution(int n, int m, std::vector> &vec) {std::vector result;for (int pos = 1; pos <= m; pos++) {bool ok = true;for (int i = 0; i < n; i++) {int l = stringToInt(vec[i][0]);int r = stringToInt(vec[i][1]);if (l <= pos && pos <= r) {ok = false;break;}}if (ok) {result.push_back(pos);}}return result;
}int main() {int n;int m;std::vector> vec;std::cin >> n;std::cin >> m;std::string line, token;for (int i = 0; i < n; i++) {std::vector s;getline(std::cin >> std::ws, line);std::stringstream tokens(line);while (std::getline(tokens, token, ' ')) {s.push_back((token));}vec.push_back(s);}std::vector result = solution(n, m, vec);cout << result.size() << endl;for (auto it = result.begin(); it != result.end(); ++it) {std::cout << *it << " ";}return 0;
}

2.津津的储蓄计划（模拟）

题目

津津的零花钱一直都是自己管理。每个月的月初妈妈给津津 300 元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。 为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上 20% 还给津津。
因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100 元或恰好 100 元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。 例如 11 月初津津手中还有 83 元，
妈妈给了津津 300 元。津津预计 11 月的花销是 180 元，那么她就会在妈妈那里存 200 元，自己留下 183 元。到了 11月月末，津津手中会剩下 3 元钱。 津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。
现在请你根据2004年1月到12月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到2004年年末，妈妈将津津平常存的钱加上20％还给津津之后，津津手中会有多少钱。

题解

似乎是NOIP原题。
比赛时没给钱够花的样例，所以理解可能有问题。
津津不能通过预知之后的月份的花销，减少存钱，从而避免预算不足。
不论按全程整数算，还是按有浮点误差算，都只能得70%分……

代码（未知%）

在其他平台测试通过的代码。
https://www.luogu.com.cn/problem/P1089

#include
int main(){int mum=0,jin=0;for(int i=1,t;i<=12;i++){scanf("%d",&t);jin+=300;if(jinprintf("-%d\n",i);return 0;}jin-=t;mum+=jin/100*100;jin%=100;}printf("%d",int(jin+mum*1.2+0.5));//printf("%d %d",jin,mum);return 0;
}

3.多边形的面积

题目

给出一个简单多边形(没有缺口)，它的边要么是垂直的，要么是水平的。要求计算多边形的面积。
多边形被放置在一个 X*Y 的卡笛尔平面上，它所有的边都平行于两条坐标轴之一。然后按逆时针方向给出各顶点的坐标值。
所有的坐标值都是整数(因此多边形的面积也为整数)。

题解

简单多边形，比赛时可能理解错了，理解成了每个内角都小于180度的凸多边形。
求若干个三角形有向面积之和。
据说比赛时数据存在边不是垂直或水平的。

4.小桥流水人家

题目

在n*m的地图上，存在一个喷水点，如果相邻的位置低于有水的地方，水就能流到相邻的某位置（即该格子需要其上下左右的格子海拔都比自身高的封闭图形才可以积水）。 已知各个格子的海拔高度，求积水的最大覆盖个格子数。

题解

首先从地图外向四周相等或更高处遍历，标记所有存不住水的位置。
能存注水的位置，形成地图内部的若干个连通块。
遍历每个能存水的块，记录块数、每块高度和以及四周最低存不住水高度，可以算出可存贮的水量。

代码（100%）

#include 
#include 
#include 
#include 
#includeusing namespace std;int str2int(string s) {int x = 0;for (int i = 0; i < (int) s.length(); i++) {x = x * 10 + s[i] - '0';}return x;
}int map[1100][1100];
bool vis[1100][1100], v2[1100][1100];
int d[][2] = {{-1, 0},{0,  -1},{0,  1},{1,  0}};int solution(int n, int m, std::vector> &vec) {int result;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {map[i + 1][j + 1] = str2int(vec[i][j]);}}/*result = 0;for(int i=2;i qx, qy;qx.push(0);qy.push(0);vis[0][0] = true;while (!qx.empty()) {int x = qx.front();qx.pop();int y = qy.front();qy.pop();for (int f = 0; f < 4; f++) {int nx = x + d[f][0];int ny = y + d[f][1];if (nx < 0 || nx > n + 1 || ny < 0 || ny > m + 1) {continue;}if (vis[nx][ny]) {continue;}if (map[nx][ny] < map[x][y]) {continue;}qx.push(nx);qy.push(ny);vis[nx][ny] = true;}}result = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (vis[i][j] || v2[i][j])continue;qx.push(i);qy.push(j);v2[i][j] = true;int mn = 1100;int sum = 0;int count = 0;while (!qx.empty()) {int x = qx.front();qx.pop();int y = qy.front();qy.pop();sum += map[x][y];count++;for (int f = 0; f < 4; f++) {int nx = x + d[f][0];int ny = y + d[f][1];if (vis[nx][ny]) {if (map[nx][ny] < mn) {mn = map[nx][ny];}continue;}if (v2[nx][ny])continue;qx.push(nx);qy.push(ny);v2[nx][ny] = true;}}result += count * mn - sum;}}return result;
}int main() {int n;int m;std::vector> vec;std::cin >> n;std::cin >> m;//std::cin>>x;//std::cin>>y;std::string line, token;for (int i = 0; i < n; i++) {std::vector s;getline(std::cin >> std::ws, line);std::stringstream tokens(line);while (std::getline(tokens, token, ' ')) {s.push_back((token));}vec.push_back(s);}int result = solution(n, m, vec);std::cout << result << std::endl;return 0;
}