RCC 2014 Warmup (Div. 2)

A題：看是全用c好還是全用d好還是都用的問題最少，注意 n * m <= k的時候特判

B題：題意坑死了，就開一個vis數組記錄每個人前面的提交數，如果矛盾就false

C題：構造，只要判斷n - k 是否 <= k，輸出就按當前一個和後面k個連即可

D題：狀壓DP，按k排序，然後dp數組只要記錄完成集合，利用滾動數組優化空間，然後每次加上k * d去取最小值即可

E題：構造問題，不過用隨機算法貌似更簡便。構造出來的矩陣應該是

a a a a a b

a a a a a b

a a a a a b

c c c c c d

這樣的，然後只要去隨機a, b, c, d判斷每行每列和是不是完全平方數即可

代碼：

A：

#include 
#include 
#include 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;
}

#include 
#include 

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;
}

#include 
#include 

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;
}

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

E：

#include 
#include 
#include 
#include 

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;
}