A. Eating Soup

题意

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

关键词

构造

思路

分成几种情况进行考虑：

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

代码

//#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个颜色，问从第一个颜色开始，能够满足在去除其中一个颜色后，剩余每种颜色数量全部相同的最长颜色序列长度为多少。

关键词

构造、贪心

思路

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

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

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

代码

#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)

题意

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

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

关键词

计算几何、暴力

思路

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

设给定两个点所连成的直线为 $l$ ，这里用直线的一般公式来表示一条直线会更方便。
对于系数、和常数 $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}$

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

可以通过、来唯一表示一条直线的斜率 $k$ 。
对于相同的斜率 $k$ ，可以通过常数 $c$ 来区分平行的不同直线。
当和相同且 $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)

A. Eating Soup

题意

关键词

思路

代码

B. Cat Party (Hard Edition)

题意

关键词

思路

代码

C. Power Transmission (Hard Edition)

题意

关键词

思路

代码