美文网首页
Codeforces Round #558 (Div. 2)

Codeforces Round #558 (Div. 2)

作者: 阿臻同学 | 来源:发表于2019-05-10 15:14 被阅读0次

A. Eating Soup

题意

给定n个人围成一圈，在离开m个人后，问最多能分成多少个不连通的部分。

关键词

构造

思路

分成几种情况进行考虑：

  • m=n：
    人全走了，结果为0。
  • m=0或m=1：
    最多走了一个人，所有人还是连在一起，结果为1。
  • m>\frac{n}{2}：
    走了超过一半的人，剩下的人，每个人都可以单独坐，结果为n-m。
  • m<=\frac{n}{2}：
    超过一半的人剩下，可以假设走的m个人不相连，则最多分成m个不相连的部分，结果为m。

代码

//#include <bits/stdc++.h>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <climits>
#include <cmath>
#include <stack>
#include <functional>


#define Debug 0
#define MAXN 115
#define MAXM 200
#define MAXK 10000010
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
#define MSET(arr, v) memset((arr),(v),sizeof(arr))
#define SCAND(n) scanf("%d", &n)
#define PRINTD(n) printf("%d", n)
#define EPS 1e-6
#define null Point(EPS/10, EPS/10)
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;

int main ()
{
#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
//    SYNC

    int n, m;
    cin >> n >> m;
    int t = n / 2;
    int ans = 0;
    if (m == n)
        ans = 0;
    else if (m == 0 || m == 1)
        ans = 1;
    else if (m > t)
        ans = n - m;
    else
        ans = m;

    cout << ans << endl;


#ifdef FILE_IN
    fclose(stdin);
#endif

    return 0;
}

B. Cat Party (Hard Edition)

题意

给定n个颜色，问从第一个颜色开始，能够满足在去除其中一个颜色后，剩余每种颜色数量全部相同的最长颜色序列长度为多少。

关键词

构造、贪心

思路

对于一个长度为 i 颜色序列，可以分为四种情况：

  • 恰好有 i 个不同的颜色。
  • 恰好 i 个颜色都为同一种颜色。
  • 恰好有 1 种颜色数量为 1，其他颜色数量相同。
  • 其他颜色数量相同，恰好有 1 种颜色数量比其他颜色多 1 个。

显然，每当从 1 开始的长度为 i 的序列满足以上四种情况之一时，可以用长度 i 更新结果，取最大值。

代码

#include <bits/stdc++.h>

#define Debug 0
#define MAXN 100006
#define MAXM 100006
#define MAXK 10000010
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
#define MSET(arr, v) memset((arr),(v),sizeof(arr))
#define SCAND(n) scanf("%d", &n)
#define PRINTD(n) printf("%d", n)
#define EPS 1e-6
#define null Point(EPS/10, EPS/10)
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;

int arr[MAXN];
int cnt[MAXN] = {0};    // cnt[i]:      有多少种颜色出现了i次
int color[MAXN] = {0};  // color[i]:    第i种颜色出现的次数
int n;
int main ()
{
#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
//    SYNC

    cin >> n;
    set<int> se;
    int ans = 1;
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
        se.insert(arr[i]);
    }
    if (se.size() == 1 || se.size() == n)
    {
        ans = n;
    } else
    {
        int ma = 0;
        for (int i = 0; i < n; ++i)
        {
            int c = arr[i];
            cnt[color[c]]--;
            color[c]++;
            cnt[color[c]]++;
            ma = max(ma, color[c]);

            if (cnt[1] == 1 && ma * cnt[ma] == i)
                ans = i + 1;
            else if (cnt[ma] == 1 && (ma-1) * cnt[ma-1] + ma == i + 1)
                ans = i + 1;

        }
    }

    cout << ans << endl;
#ifdef FILE_IN
    fclose(stdin);
#endif
    return 0;
}

C. Power Transmission (Hard Edition)

题意

给定n个点，并且任意两点连一条直线，问有多少对直线相交。

当三点共线时，其所在直线为同一条直线。

关键词

计算几何、暴力

思路

计算任意两点的连线，并排除共线的情况，在余下的直线中，排除平行的情况，其他直线都相交。

设给定两个点 (x_1,y_1)、(x_2,y_2) 所连成的直线为 l ，这里用直线的一般公式ax+by+c=0来表示一条直线会更方便。
对于系数 a 、 b 和常数 c ，有：

\begin{align} a &= {y_1}-{y_2} \\ b &= {x_1}-{x_2} \\ c &= {y_1x_2}-{y_2x_1}=ax_1-by_1 \\ \end{align}

对 a 和 b 约分化简，并保证符号相同，在该前提下：

  • 可以通过 a 、 b 来唯一表示一条直线的斜率 k 。
  • 对于相同的斜率 k ，可以通过常数 c 来区分平行的不同直线。
  • 当 a 和 b 相同且 c 也相同时，则可以判定2条直线相同（共线）。

显然，可以按照斜率 k 将直线分组，对于每条直线，与其相交的直线数则为：(总直线数量-斜率为k的直线数量)。

对每条直线累加该值即为结果。

代码

#include <bits/stdc++.h>
#define Debug 0
#define MAXN 115
#define MAXM 100006
#define MAXK 10000010
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
#define MSET(arr, v) memset((arr),(v),sizeof(arr))
#define SCAND(n) scanf("%d", &n)
#define PRINTD(n) printf("%d", n)
#define EPS 1e-8
#define null Point(EPS/10, EPS/10)
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;

// 二维向量
struct Vector
{
    double x, y;


    Vector ()
    {}

    Vector (double x, double y) : x(x), y(y)
    {}

    // 点积
    double operator* (Vector v)
    {
        return x * v.x + y * v.y;
    }

    // 叉积
    double operator^ (Vector v)
    {
        return x * v.y - y * v.x;
    }

    // 乘法
    Vector operator* (double d)
    {
        return Vector(x * d, y * d);
    }

    // 加法
    Vector operator+ (Vector v)
    {
        return Vector(x + v.x, y + v.y);
    }

    // 减法
    Vector operator- (Vector v)
    {
        return Vector(x - v.x, y - v.y);
    }


    bool operator== (const Vector &rhs) const
    {
        return x == rhs.x &&
               y == rhs.y;
    }

    bool operator!= (const Vector &rhs) const
    {
        return !(rhs == *this);
    }

    // 模
    double length ()
    {
        return sqrt((*this) * (*this));
    }

    // 单位化
    Vector unit ()
    {
        return (*this) * (1.0 / length());
    }

    // 逆时针旋转alpha角（弧度）
    Vector rotate (double alpha)
    {
        return Vector(x + (x * cos(alpha) - y * sin(alpha)),
                      y + (x * sin(alpha) + y * cos(alpha)));
    }

    // v的投影
    double project (Vector v)
    {
        return v * unit();
    }

    bool operator< (Vector v) const
    {
        if (x != v.x)
            return x < v.x;
        else
            return y < v.y;
    }

    bool operator> (Vector v) const
    {
        if (x != v.x)
            return x > v.x;
        else
            return y > v.y;
    }

};

typedef Vector Point;

// 二维直线
struct Line
{
    Point x, y;

    // 通过两点构造直线
    Line (Point x, Point y) : x(x), y(y)
    {}

    Line ()
    {}

    // 点和方向向量来构造线
    static Line makeLine (Point x, Vector v)
    {
        return Line(x, x + v);
    }

    bool operator== (const Line &rhs) const
    {
        return x == rhs.x &&
               y == rhs.y;
    }

    bool operator!= (const Line &rhs) const
    {
        return !(rhs == *this);
    }

    // 线长度
    double length ()
    {
        return (y - x).length();
    }

    // 点到该直线的距离
    double dist (Point p)
    {
        return fabs((x - p) ^ (y - p)) / length();
    }

    // #define EPS 1e-6
    // 判断点和直线的位置
    int side (Point p)
    {
        double result = (y - x) ^(p - x);
        if (fabs(result) < EPS)
            return 0;   // 在线上
        else if (result > 0)
            return 1;   // 左侧
        else
            return -1;  // 右侧
    }

    // 过点做垂线
    Line vertical (Point p)
    {
        return makeLine(p, (y - x).rotate(PI / 2));
    }

    // 垂足
    Point foot (Point p)
    {
        Vector self = y - x;
        return x + self.unit() * self.project(p - x);
    }

    pair<int, Point> intersect (Line l)
    {
        double s1 = ((x - l.x) ^ (l.y - l.x)) / 2;
        double s2 = ((l.y - l.x) ^ (y - l.x)) / 2;
        if (fabs(s1 + s2) < EPS)
        {
            if (l.dist(x) < EPS)
                return make_pair(1, l.x);   // 重合
            else
                return make_pair(2, l.y);   // 平行
        } else
            return make_pair(0, x + (y - x) * (s1 / (s1 + s2))); // 交点
    }

};

int n;

int main ()
{
#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
    SYNC

    cin >> n;
    vector<Point> pt;
    vector<Line> ls;
    map<Pair, set<ll>> ma;
    for (int i = 0; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;
        pt.pb(Point(a, b));
    }
    ll tot = 0;
    ll ans = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            int a = pt[i].y - pt[j].y;
            int b = pt[i].x - pt[j].x;
            int d = __gcd(a, b);
            a /= d;
            b /= d;
            if (a < 0 || (a == 0 && b < 0))
            {
                a *= -1;
                b *= -1;
            }
            ll c = 1LL * pt[i].x * a - 1LL * pt[i].y * b;
            Pair pr(a, b);
            if (ma[pr].count(c) == 0)
            {
                tot++;
                ma[pr].insert(c);
                ans += tot - ma[pr].size();
            }

        }
    }

    cout << ans << endl;

#ifdef FILE_IN
    fclose(stdin);
#endif

    return 0;
}

相关文章

网友评论

      本文标题：Codeforces Round #558 (Div. 2)

      本文链接：https://www.haomeiwen.com/subject/wkaooqtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|Codeforces Round #558 (Div. 2)|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！