B:
饥饿的奶牛
题目描述
有一条奶牛冲出了围栏,来到了一处圣地(对于奶牛来说),上面用牛语写着一段文字。
现用汉语翻译为:
有 $N$ 个区间,每个区间 $x,y$ 表示提供的 $x\sim y$ 共 $y-x+1$ 堆优质牧草。你可以选择任意区间但不能有重复的部分。
对于奶牛来说,自然是吃的越多越好,然而奶牛智商有限,现在请你帮助他。
输入格式
第一行一个整数 $N$。
接下来 $N$ 行,每行两个数 $x,y$,描述一个区间。
输出格式
输出最多能吃到的牧草堆数。
样例 #1
样例输入 #1
3
1 3
7 8
3 4
样例输出 #1
5
提示
$1 \leq n \leq 1.5 \times 10^5$,$0 \leq x \leq y \leq 3 \times 10^6$。
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <array>
#include <ctime>
#include <cstring>
#define endl "\n"
#define ture true;
#define flase false;
using namespace std;
int arr[3000111];
int n, sj;
int point[3000111][2];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
int x, y;
scanf("%d%d", &x, &y);
point[x][0] = 1;
point[x][1] = y - x + 1;
sj = max(sj, y);
}
sj++;
for (int i = 1; i <= sj; i++)
{
arr[i] = max(arr[i], arr[i - 1]);
if (point[i][0] == 1)
{
if (arr[i + point[i][1]] < arr[i] + point[i][1])
{
arr[i + point[i][1]] = arr[i] + point[i][1];
}
}
}
cout << arr[sj] << endl;
return 0;
}
C:
轰炸
题目描述
“我该怎么办?”飞行员klux
向你求助。
事实上,klux
面对的是一个很简单的问题,但是他实在太菜了。
klux
要想轰炸某个区域内的一些地方,它们是位于平面上的一些点,但是(显然地)klux
遇到了抵抗,所以klux
只能飞一次,而且由于飞机比较破,一点起飞就只能沿直线飞行,无法转弯。现在他想一次轰炸最多的地方。
输入格式
第一行为$n$
输入数据由$n$对整数组成$(1 \le n \le700)$,每对整数表示一个点的坐标。没有一个点会出现两次。
输出格式
一个整数,表示一条直线能覆盖的最多的点数。
样例 #1
样例输入 #1
5
1 1
2 2
3 3
9 10
10 11
样例输出 #1
3
提示
本题翻译并改编自uva270,数据及解答由uva提供。
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <array>
#include <ctime>
#include <cstring>
#define endl "\n"
#define ture true;
#define flase false;
using namespace std;
int d1[770], d2[770];
int lin = 2;
int ans = 0;
int main()
{
int a;
scanf("%d", &a);
for (int i = 1; i <= a; i++)
{
scanf("%d %d", &d1[i], &d2[i]);
}
for (int i = 1; i <= a; i++)
for (int j = 1; j <= a; j++)
{
if (i != j)
{
double z, x;
z = d1[i] - d1[j];
x = d2[i] - d2[j];
for (int k = 1; k <= a; k++)
{
if (k != i && k != j)
{
double c, v;
c = d1[i] - d1[k];
v = d2[i] - d2[k];
if (c / v == z / x)lin++;
}
}
if (lin > ans)ans = lin;
lin = 2;
}
}
printf("%d", ans);
return 0;
}
D:
增进感情
题目背景
小明和小红的感情,是慢慢发展起来的。
题目描述
他们对对方分别有一个好感值。定义两人的亲密程度为两人的好感值之和。
如果他们的亲密程度达到 $v$,则他们将走到一起。他们以后的生活将取决于两人的好感值之差的绝对值,这个值越小,他们的生活将越幸福。
现在,他们对对方的好感值都为 $0$,小明有 $n$ 件事可以干,每件事可以增加他对小红的好感 $a_i$ 点,并且增加小红对他的好感 $b_i$ 点。(可能为负数)
小明可以任选一些事做,请你帮小明求出怎样才能让他们的生活更加幸福(求出两人在一起的前提下,好感值之差的最小绝对值即可)。
输入格式
第一行,两个正整数 $n,v$。
之后 $n$ 行,每行两个空格隔开的整数 $a_i,b_i$。
输出格式
一行,一个非负整数,表示两人在一起的前提下,好感值之差的最小绝对值。如果无论如何两人也无法在一起,输出 -1
。
样例 #1
样例输入 #1
4 15
5 6
-1 8
7 2
1 0
样例输出 #1
3
提示
数据范围与约定
- 对于 $20\%$ 数据,保证 $n \le 10$。
- 对于 $100\%$ 数据,保证 $1 \le n \le 30$,$1 \le \left\vert a_i\right\vert,\left\vert b_i\right\vert \le 100$。
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <array>
#include <ctime>
#include <cstring>
#define endl "\n"
#define ture true;
#define flase false;
using namespace std;
const int maxn = 0x7fffffff, N = 35;
int n, c;
int a[N], b[N];
int ans = maxn, sum[3];
void dfs(int x) {
if (sum[1] + sum[2] > c) {
ans = min(ans, abs(sum[1] - sum[2]));
}
if (x > n || ans == 0) {
return;
}
sum[1] += a[x];
sum[2] += b[x];
dfs(x + 1);
sum[1] -= a[x];
sum[2] -= b[x];
dfs(x + 1);
}
int main() {
scanf("%d%d", &n, &c);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &a[i], &b[i]);
}
dfs(1);
if (ans != maxn)printf("%d", ans);
else puts("-1");
return 0;
}
E:
魔鬼之城
题目描述
在一个被分割为N*M个正方形房间的矩形魔鬼之城中,一个探险者必须遵循下列规则才能跳跃行动。他必须从(1, 1)进入,从(N, M)走出;在每一房间的墙壁上都写了一个魔法数字,是1~13之内的自然数;探险者可以想像出8个方向中的任何一个(水平或垂直或对角线方向),随后他就可以作一次空间跳跃穿过这一方向上的连续的X个房间,其中X是他原来所在房间的魔法数字。但如果在这一方向上的房间数小于X,则他不作任何跳跃,而必须想像另一个方向。同时,探险者不能作连续两次相同方向的跳跃。
例如在上图的5*4的魔鬼之城中,如果探险者现在所在的位置是(3, 3),那么通过依次空间跳跃他可以到达下列房间中的一个:(1, 1),(3, 1),(1, 3),(5, 1),或(5, 3)。另外,如果他要用两次跳跃从(5, 4)到达(3, 2),则他不能首先跳到(4, 3)(因为这样他第二次跳跃的方向将和第一次相同,而这是不允许的)。所以他必须先跳跃到(2, 1)。
请你写一个程序,对给定的地图,算出探险者至少需要跳跃多少步才能离开魔鬼之城。
输入格式
一行给出N,M(都不超过100);
下来有M行,每行为N个自然数,表示对应房间中的魔法数字。
输出格式
出最小步数,如果探险者无法离开魔鬼之城,请输出“NEVER”。
样例 #1
样例输入 #1
5 4
3 3 6 7 11
3 2 1 1 3
3 2 2 1 1
2 1 2 2 1
样例输出 #1
4
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <array>
#include <ctime>
#include <cstring>
#include <queue>
#define endl "\n"
#define ture true;
#define flase false;
using namespace std;
int mapa[105][105];
int v[105][105][10];
int dx[9] = { 0,0,1,1,1,0,-1,-1,-1 };
int dy[9] = { 0,-1,-1,0,1,1,1,0,-1 };
struct node {
int x, y, step, way;
};
queue<node> q;
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
scanf("%d", &mapa[i][j]);
node start;
start.x = 1, start.y = 1;
start.step = 0, start.way = 9;
q.push(start);
while (!q.empty())
{
node now = q.front();
q.pop();
if (now.x == m && now.y == n)
{
printf("%d", now.step);
return 0;
}
for (int i = 1; i <= 8; i++)
{
if (now.way != i)
{
int tx = now.x + dx[i] * mapa[now.x][now.y];
int ty = now.y + dy[i] * mapa[now.x][now.y];
int ts = now.step;
if (tx <= m && ty <= n && tx >= 1 && ty >= 1 && v[tx][ty][i] == 0)
{
v[tx][ty][i] = 1;
node ans;
ans.x = tx, ans.y = ty;
ans.step = ts + 1, ans.way = i;
q.push(ans);
}
}
}
}
puts("NEVER");
return 0;
}