RCC 2014 Warmup (Div. 2)_html/css_WEB-ITnose-html教程-PHP中文网

RCC 2014 Warmup (Div. 2)_html/css_WEB-ITnose

php中文网

发布： 2016-06-24 12:05:58

原创

1498人浏览过

a题：看是全用c好还是全用d好还是都用的问题最少，注意 n * m

B题：题意坑死了，就开一个vis数组记录每个人前面的提交数，如果矛盾就false

C题：构造，只要判断n - k 是否

D题：状压DP，按k排序，然后dp数组只要记录完成集合，利用滚动数组优化空间，然后每次加上k * d去取最小值即可

E题：构造问题，不过用随机算法貌似更简便。构造出来的矩阵应该是

立即学习“前端免费学习笔记（深入）”；

a a a a a b

c c c c c d

这样的，然后只要去随机a, b, c, d判断每行每列和是不是完全平方数即可

代码：

A：

知我AI

一款多端AI知识助理，通过一键生成播客/视频/文档/网页文章摘要、思维导图，提高个人知识获取效率；自动存储知识，通过与知识库聊天，提高知识利用效率。

101

查看详情

#include <stdio.h>#include <string.h>#include <math.h>2 #define min(a,b) ((a)<(b)?(a):(b))int c, d, n, m, k;int main() {    scanf("%d%d%d%d%d", &c, &d, &n, &m, &k);    int sb = n * m - k;    if (sb <= 0) printf("0\n");    else printf("%d\n", min(sb * d, min((int)ceil(sb * 1.0 / n) * c, sb / n * c + sb % n * d)));    return 0;}

登录后复制

B：

#include <stdio.h>#include <string.h>const int N = 100005;int n, vis[N];struct Solu {    int x, k;} s[N];bool judge() {    memset(vis, 0, sizeof(vis));    for (int i = 0; i < n; i++) {        int x = s[i].x, k = s[i].k;        if (x == vis[k])            vis[k]++;        else if (x > vis[k])            return false;    }    return true;}int main() {    scanf("%d", &n);    for (int i = 0; i < n; i++)        scanf("%d%d", &s[i].x, &s[i].k);    if (judge()) printf("YES\n");    else printf("NO\n");    return 0;}

登录后复制

C：

#include <stdio.h>#include <string.h>int n, k;int main() {    scanf("%d%d", &n, &k);    if ((n - k) <= k) printf("-1\n");    else {        printf("%d\n", n * k);        for (int i = 1; i <= n; i++) {            for (int j = 1; j <= k; j++) {                int a = i, b = i + j;                if (b > n) b -= n;                printf("%d %d\n", a, b);            }        }    }    return 0;}

登录后复制

D：

#include <stdio.h>#include <string.h>#include <algorithm>#define min(a,b) ((a)<(b)?(a):(b))using namespace std;__int64 one = 1;const int N = 105;const int M = (1<<20) + 5;const __int64 INF = (one<<62);__int64 b, dp[M];int i, j, n, m;struct F {    __int64 x, k, s;} f[N];bool cmp(F a, F b) {    return a.k < b.k;}int main() {    __int64 ans = INF;    scanf("%d%d%I64d", &n, &m, &b);    for (i = 1; i <= n; i++) {        int num, ss;        scanf("%I64d%I64d%d", &f[i].x, &f[i].k, &num);        while (num--) {            scanf("%d", &ss);            f[i].s |= (1<<(ss-1));        }    }    int smax = (1<<m);    sort(f + 1, f + n + 1, cmp);    for (i = 1; i < smax; i++)        dp[i] = INF;    for (i = 1; i <= n; i++) {        for (j = 0; j < smax; j++) {            int ss = (j|f[i].s);            dp[ss] = min(dp[ss], dp[j] + f[i].x);        }        ans = min(ans, dp[smax - 1] + f[i].k * b);    }    if (ans == INF) ans = -1;    printf("%I64d\n", ans);    return 0;}

登录后复制

E：

#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>int n, m;bool check(int num) {    int m = (int)sqrt(num);    return m * m == num;}int main() {    scanf("%d%d", &n, &m);    int a, b, c, d, i, j;    while (1) {        a = rand() % 100 + 1;        b = rand() % 100 + 1;        c = rand() % 100 + 1;        d = rand() % 100 + 1;        if (check((m - 1) * a * a + b * b) &&             check((m - 1) * c * c + d * d) &&             check((n - 1) * a * a + c * c) &&             check((n - 1) * b * b + d * d))            break;    }    for (i = 0; i < n - 1; i++) {        for (j = 0; j < m - 1; j++)            printf("%d ", a);        printf("%d\n", b);    }    for (j = 0; j < m - 1; j++)        printf("%d ", c);    printf("%d\n", d);    return 0;}

登录后复制