题目链接

2018 ACM 国际大学生程序设计竞赛上海大都会

下午午休起床被同学叫去打比赛233

然后已经过了2.5h了

先挑过得多的做了

....

A题

rand x*n 次点，每次judge一个点位端点的共线向量数判断是否大于给定x

强行rand 500次

代码

#include<bits/stdc++.h>

using namespace std;

inline int read() {

    int x = 0,f = 1;

    char c = getchar();

    while(c < '0' || c > '9') {if(c == '-')f =- 1;  c = getchar(); }

    while(c <= '9' &&c >= '0') x = x * 10 + c - '0',c = getchar();

    return x * f;

}

const int maxn = 20007;

#define eps (1e-13)

double k;

int n;

struct points {

    int x,y;

} p[maxn];

bool solve(int p1,int p2) {

    int tx = p[p1].x - p[p2].x,ty = p[p1].y - p[p2].y;

    int cnt = 2;

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

        if(i == p1 || i == p2) continue;

        int px = p[p1].x - p[i].x,py = p[p1].y - p[i].y;

        if((long long)tx * py - (long long)ty * px == 0) cnt ++;

    }

    double K = (double) cnt /  (double) n;

    return (K >= k);

}

int main() {

    srand(time(0));

    srand(rand());

    int t = read();

    while(t -- ) {

        n = read(); scanf("%lf",&k);

        for(int i = 1;i <= n;++ i) p[i].x = read(),p[i].y = read();

        int p1,p2;

        bool flag = false;

        for(int i = 500;i --;) {

            p1 = rand() % n + 1;

            p2 = p1;

            while(p2 == p1) p2 = rand() % n + 1;

            if(solve(p1,p2)) {

                flag = true; break;

            }

            if(flag) break;

        }

        if(t != 0) {

            if(flag) puts("Yes");

            else puts("No");

        }

        if(t == 0) {

            if(flag)printf("Yes");

            else printf("No");

        }

    }

    return 0;

}

B题

很sb的打了nlogn筛

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 200000;

vector<int>vec[maxn + 10];

int num[maxn  + 10]; 

int main() {

    for(int i = 1;i <= maxn;++ i) {

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

            num[j] += i;vec[j].push_back(i);

        }

    }

    int t;

    scanf("%d",&t);

    int cas = 0;

    while(t --) {

        cas++;

        int k ;

        scanf("%d",&k); printf("Case %d: ",cas);

        if(num[k] - k != k) {

            if(k != 0)puts("Not perfect.");

            else printf("Not perfect.");

        } else {

            int p = vec[k].size() - 1;

            printf("%d = ",k);

            for(int i = 0;i < p;++ i) {

                if(i != p - 1)printf("%d + ",vec[k][i]);

                else printf("%d",vec[k][i]);

            }

            if(t != 0)puts("");

        }

    }

    return 0;

}

D题Thinking-Bear magic

发现每次面积变为原来的$\frac{1}{\cos(\frac{\pi}{n})^2} $

代码

#include<bits/stdc++.h>

#define Pi 3.14159265359 

double Sin(int n){

    return sin((2.0*Pi)/n);

}

double Cos(int n){

    return cos((2.0*Pi)/n);

}

double Tan(int n){

    return tan((2.0*Pi)/n);

}

double S(int n, double R) {

    return ((0.25*n*R*R)/(double)tan(Pi/n));

}

double calc(int n){

    return cos(Pi/(1.0*n))*cos(Pi/(1.0*n));

}

int main () {

    int T,n,a,l;

    scanf("%d",&T);

    double s;

    int t;

    while(T --) {

        scanf("%d%d%d",&n,&a,&l);

        double gg = calc(n);

        t = 0; s = S(n,(double)a);

        while(s > l) s = gg * s, ++ t;

        printf("%d\n",t);

    }

    return 0;

}

J题目 Beautiful Numbers

数位dp

代码

#include<bits/stdc++.h>

using namespace std;

inline int read() {

	int x = 0,f = 1;

	char c = getchar();

	while(c < '0' || c > '9')c = getchar();

	while(c <= '9' && c >= '0') x = x * 10 + c - '0', c = getchar();

	return x * f;

}

const int maxn=3e5+5;

const int INF =0x3f3f3f3f;

#define LL long long

int a[20];

LL dp[13][105][150];

int mod;

LL dfs(int pos,int sum,int res,bool limit) {

    if(pos == -1) return (sum == mod && !res);

    if(dp[pos][sum][res] != -1 && !limit) return dp[pos][sum][res];

    int up = limit ? a[pos] : 9;

    LL res = 0;

    for(int i = 0;i <= up;++ i) {

        if(i + sum > mod) break;

        res += dfs(pos - 1,sum + i,(res * 10 + i) % mod,limit && i == a[pos]);

    }

    if(!limit) dp[pos][sum][res] = res;

    return res;

}

LL solve(LL n) {

    int pos=0;

    LL x = n;

    while(x) a[pos ++] = x % 10, x /= 10;

    LL res = 0;

    for(int i = 1;i <= 9 * pos;++ i) {

        mod = i;

        memset(dp,-1,sizeof(dp));

        res += dfs(pos-1,0,0,true);

    }

    return res;

}

int main() {

    int T = read();

    int cas = 0;

    while(T --) {

        cas ++;

        LL n = read();

        printf("Case %d: %lld\n",cas,solve(n));

    }

    return 0;

}

K题 Matrix Multiplication

矩乘裸题

代码

#include<bits/stdc++.h>

using namespace std;

struct MMMM {

    int m[21][21];

    int r,c;

    MMMM() {}

    MMMM(int n) {memset(m, false, sizeof m);r = c = n; for (int i = 0; i < r; i +=1) m[i][i] = 1;}

    MMMM(int R,int C) {memset(m, false, sizeof m);r = R,c = C;}

    MMMM operator * (const MMMM & o)const {

        MMMM res = MMMM(r, o.c);

        for (int i = 0; i< r;i += 1)

            for (int  j = 0 ;j < o.c; j += 1)

                for (int k = 0; k < c; k += 1 )

                    res.m[i][j] += 1ll * m[i][k] * o.m[k][j];

        return res;

    }

    void print() {

        for (int i =0 ;i < r;i += 1) {

            for (int j = 0; j < c; j += 1) {

                if(j!=c-1)printf("%d ",m[i][j]);

                else printf("%d",m[i][j]);

            }

            puts("");

        }

    }

    void input() {

        for (int i = 0; i< r; i += 1)

            for (int j = 0; j < c; j += 1)

                scanf("%d", &m[i][j]);

    }

};

int main () {

    int T;

    scanf("%d",&T);

    for (int i =1; i <= T; i += 1) {

        int r1,c1,r2,c2;

        scanf("%d%d%d%d", &r1,&c1,&r2,&c2);

        MMMM a,b;

        a=MMMM(r1,c1), b= MMMM(r2,c2);

        a.input(); b.input();

        printf("Case %d:\n",i);

        if (c1 != r2) {

            printf("ERROR\n");

            continue;

        }

        MMMM c = a * b;

        c.print();

    }

    return 0;

}

2018 ACM 国际大学生程序设计竞赛上海大都会部分题解的相关教程结束。