赞
踩
芬兰木棋(Mölkky,又称芬兰木柱)是源自芬兰的一项运动。哲哲将这个运动改造成了赛博朋克单人版,现在场上一开始有 N 根立起的小木棋(上面分别标有一个非负整数),哲哲投掷一根大木棋去击倒这些小木棋以获得分数。分数规则如下:
哲哲固定站在 (0,0) 点上,四周放着若干个小木棋 (Xi,Yi),坐标均为整数。每次哲哲可以朝一个方向扔出大木棋,大木棋会打倒这个方向上离哲哲最近的 k 个小木棋。哲哲游戏水平很高超,所以这个 k 可以自由控制。
请问哲哲最多能拿多少分,在获得最多分数的情况下最少需要扔出多少次大木棋?
规则与真实规则有较大出入,真实游玩时请以国际莫尔基组织的规则为准
输入第一行是一个正整数 N (1 ≤ N ≤ 105),表示场上一开始有 N 个木棋。
接下来 N 行,每行 3 个整数 Xi,Yi,Pi,分别表示木棋放置在 (Xi,Yi),木棋上的分数是 Pi。坐标在 32 位整数范围内,分数为小于等于 1000 的正整数。
保证 (0,0) 点没有木棋,也没有木棋重叠放置。
输出一行两个数,表示最多分数以及获得最多分数最少需要投掷大木棋多少次。
- 11
- 1 2 2
- 2 4 3
- 3 6 4
- -1 2 2
- -2 4 3
- -3 6 4
- -1 -2 1
- -2 -4 1
- -3 -6 1
- -4 -8 2
- 2 -1 999
1022 9
思路:
经典斜率的遍历问题,出了老多次了,我们用map去存化简后的斜率的分母和分子,然后第二个map记录x轴的位置,那么我们就可以得出这个点了,然后我们已知需要最多分数那么我需要把得分大于1的木牌都进行单独击倒,而等于1的木牌如果可以的话连续击倒,我们就可以得出最大分数和最小次数(注意特判X和Y轴!!!!)
代码
- #include<bits/stdc++.h>
-
- using namespace std;
- #define int long long
- #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- #define endl '\n'
- const int N = 2e5 + 5;
- const int inf = 0x3f3f3f3f3f3f3f3f;
- int n, m, k, t;
- struct node {
- int x, y, w;
- int tx, ty;
- } x[N];
- map<pair<int, int>, map<int, int>> mp;
- //斜率-----位置------应该连击还是单独
- map<int, int> mp1, mp2;
- //x轴y轴
-
- signed main() {
- cin >> n;
- int ans = 0;
- int num = 0;
- for (int i = 0; i < n; i++) {
- cin >> x[i].x >> x[i].y >> x[i].w;
- ans += x[i].w;
- int tx = x[i].x;
- int ty = x[i].y;
- if (x[i].x == 0) {//y轴
- if (x[i].w != 1)mp1[x[i].y] = 2;
- else mp1[x[i].y] = 1;
- continue;
- }
- if (x[i].y == 0) {//x轴
- if (x[i].w != 1)mp2[x[i].x] = 2;
- else mp2[x[i].x] = 1;
- continue;
- }
- //其余部分(分母分子化简)
- int op = __gcd(tx, ty);
- tx /= op;
- ty /= op;
- x[i].tx = tx;
- x[i].ty = ty;
- if (x[i].w != 1) {
- mp[{x[i].tx, x[i].ty}][x[i].x] = 2;
- } else {
- mp[{x[i].tx, x[i].ty}][x[i].x] = 1;
- }
- }
- int f = 0;
- int flag = 0;
- for (auto it: mp) {//遍历全图
- f = 0;
- flag = 0;
- for (auto i: it.second) {
- if (i.first < 0) {// x轴为负数
- if (i.second == 1) {
- f = 1;
- } else {
- num++;
- if (f == 1) {
- num++;
- }
- f = 0;
- }
- } else {//x轴为正数
- if (flag == 0) {//第一次进入正数的时候需要去清理f
- if (f == 1)num++;
- f = 0;
- }
- flag = 1;
- if (i.second == 1) {
- f = 1;
- } else {
- num++;
- if (f == 1) {
- num++;
- }
- f = 0;
- }
- }
- }
- if (f == 1)num++;
- }
- f = 0;
- flag = 0;
- for (auto it: mp1) {//跑y轴
- if (it.first < 0) {
- if (it.second == 1) {
- f = 1;
- } else {
- num++;
- if (f == 1) {
- num++;
- }
- f = 0;
- }
- } else {
- if (flag == 0) {
- if (f == 1)num++;
- f = 0;
- }
- flag = 1;
- if (it.second == 1) {
- f = 1;
- } else {
- num++;
- if (f == 1) {
- num++;
- }
- f = 0;
- }
- }
- }
- if(f==1)num++;
- f=0;
- flag=0;
- for (auto it: mp2) {//跑x轴
- if (it.first < 0) {
- if (it.second == 1) {
- f = 1;
- } else {
- num++;
- if (f == 1) {
- num++;
- }
- f = 0;
- }
- } else {
- if (flag == 0) {
- if (f == 1)num++;
- f = 0;
- }
- flag = 1;
- if (it.second == 1) {
- f = 1;
- } else {
- num++;
- if (f == 1) {
- num++;
- }
- f = 0;
- }
- }
- }
- if(f==1)num++;
- cout << ans << ' ' << num << endl;
- return 0;
- }

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。