codeforces round#432 div2

C:这道题没做出来...写了个类似极角排序的东西被卡掉了...事实上暴力就行了，因为如果在二维平面内那么最多只能有4个点，因为每个象限只能有一个点，然后这里拓展一下就是最多只能有2*k个点，k是维数，所以大概枚举2*k=10就跳出循环了

#include<bits/stdc++.h>

using namespace std;

const int N = ;

const double pi = acos(-);

struct points {

    double a[];

    points friend operator - (points a, points b)

    {

        points ret;

        for(int i = ; i <  ; ++i) ret.a[i] = a.a[i] -b.a[i];

        return ret;

    }

} p[N];

int n, ans;

int mark[N];

double calc(points a, points b)

{

    double ret = ;

    for(int i = ; i < ; ++i) ret += a.a[i] * b.a[i];

    return ret;

}

int main()

{

    scanf("%d", &n);

    for(int i = ; i <= n; ++i)

        for(int j = ; j < ; ++j)

            scanf("%lf", &p[i].a[j]);

    ans = n;

    for(int i = ; i <= n; ++i)

        for(int j = ; j <= n && !mark[i]; ++j) if(i != j)

            for(int k = ; k <= n; ++k) if(i != j && k != j)

            {

                points a = p[j] - p[i], b = p[k] - p[i];

                if(calc(a, b) > )

                {

                    mark[i] = , --ans;

                    break;

                }

            }

    cout << ans << endl;

    for(int i = ; i <= n; ++i) if(!mark[i]) cout << i << endl;

    return ;

}

D:暴力枚举GCD，然后贪心计算一下，具体看程序，gcd的题见到过有几种方法，1.gcd个数不超过log个,2.修改可以差分，3.类似莫比乌斯反演的容斥，4.像这样暴力枚举。大概也逃不出这几种方法了吧

#include<bits/stdc++.h>

using namespace std;

const int N = ;

int n, x, y, m;

int mark[N], a[N];

long long s[N], c[N];

long long ans = 1ll << ;

int main()

{

    cin >> n >> x >> y;

    for(int i = ; i <= n; ++i) scanf("%d", &a[i]), ++ c[a[i]], s[a[i]] += a[i], m = max(m, a[i]);

    for(int i = ; i <= ; ++i) c[i] += c[i - ], s[i] += s[i - ];

    for(int i = ; i <= ; ++i)

    {

        long long sum = ;

        for(int j = i; j <=  + i; j += i)

        {

            int p = max(j - i + , j - (x / y));

            sum += ((c[j] - c[p - ]) * (long long)j - s[j] + s[p - ]) * (long long)y;

            sum += (c[p - ] - c[j - i]) * (long long)x;

        }

//        printf("i = %d sum = %lld\n", i, sum);

        ans = min(ans, sum);

    }

    cout << ans << endl;

    return ;

}

巴特西

codeforces round#432 div2

最新文章

热门文章