首页 > 代码库 > 【组队训练】2014北京区域赛

【组队训练】2014北京区域赛

四题,排名107,铜尾。。。。

发挥还真是稳定阿。。。。

这场队友终于给力了,我怂了。。。。QAQ

A 水题,10min 1A

K 水题,28min 2A 还是需要一点点想法的。我傻逼了,错了一次……

技术分享
#include <cstdio>const int maxn = 3e6 + 10;int T,n;int a[maxn];int main() {    //freopen("in.txt","r",stdin);    scanf("%d", &T);    int cas = 0;    while(T--){        scanf("%d",&n);        for(int i = 1;i <= n; i++) scanf("%d", a+i);        int mi = a[n], ans = 0;        for (int i = n-1; i >= 1; --i)            if (mi < a[i]) ++ans;            else mi = a[i];        printf("Case #%d: %d\n", ++cas, ans);    }    return 0;}
View Code

H 水dp 1h14min 2A

dp[i][j]表示前i个数的答案 dp[j^a[i]] = dp[i-1][j] + dp[i-1][j^a[i]]

MLE一次,其实我想到了可能会爆内存,偷懒了。。。。非要mle再改滚动数组。。。。

技术分享
#include <cstdio>#include <cstring>typedef long long ll;const int maxn = 210;using namespace std;int T,n,m;const int st = (1<<21);int a[50];ll dp[2][st+10];int main() {    freopen("in.txt","r",stdin);    scanf("%d", &T);    int cas = 0;    while(T--){        scanf("%d%d",&n, &m);        for(int i = 1;i <= n;i++) scanf("%d",&a[i]);        memset(dp, 0, sizeof dp);        dp[0][0] = 1;        int now = 1;        for (int i = 1; i <= n; ++i) {            for (int j = 0; j <= st; ++j) dp[now][j] = 0;            for (int j = 0; j < st; ++j)                dp[now][j^a[i]] += dp[now^1][j^a[i]] + dp[now^1][j];            now ^= 1;        }        now ^= 1;        ll ans = 0;        for (int i = m; i <= st; ++i) ans += dp[now][i];        printf("Case #%d: %lld\n", ++cas, ans);    }    return 0;}
View Code

I 简单计算几何

求两个圆相交的面积和简单的容斥思想吧。不过面积交挺麻烦的,队友wa了好几次,以至于最后A了让我感觉超惊喜。。

这时还不到三个小时,可是后面就比较惨了,一道题没做出来

------

B题,看到数据范围我就说——傻逼暴力加剪枝

然后我就是很傻逼。。。没想到怎么剪枝。。。。

马丹。。。。我觉得我dfs已经无力了。。。。

和ys讨论 一致认为n*m+1<maxn就输出NO,然后我就在那构造,构造了半天也没对。。。。

结果赛后查题解发现剪枝就是这个条件。。。蠢阿!!!

技术分享
#include <cstdio>using namespace std;int c[30], a[30][30];int n, m, k;bool check(int x, int y, int v) {    if (x>1 && a[x-1][y] == v) return false;    if (y>1 && a[x][y-1] == v) return false;    return true;}bool dfs(int x, int y, int rest) {    for (int i = 1; i <= k; ++i) if (c[i] * 2 > rest + 1) return false;    if (y == m+1) x++, y = 1;    if (rest == 0) {        puts("YES");        for (int i = 1; i <= n; ++i)            for (int j = 1; j <= m; ++j)                printf("%d%c", a[i][j], j==m?\n: );        return true;    }    for (int i = 1; i <= k; ++i) {        if (c[i]) {            c[i]--; a[x][y] = i;            if (check(x, y, i) && dfs(x, y+1, rest-1)) return true;            c[i]++;        }    }    return false;}int main() {    //freopen("in.txt","r",stdin);    int T;    scanf("%d", &T);    int cas = 1;    while(T--){        printf("Case #%d:\n", cas++);        scanf("%d%d%d",&n, &m, &k);        for (int i = 1; i <= k; ++i) scanf("%d", &c[i]);        if (!dfs(1, 1, n*m)) puts("NO");    }    return 0;}
View Code

 

D题,一眼就是区间dp,因为数据范围n^3刚刚好,描述也比较像区间dp

恩。。。想和几种状态方程没想明白。。。zr后来都开始在那里贪心了 = =。。

讲道理虽然区间dp很显然,但是转移方程还是有点难的= =但是几个小时还是应该想出来的。。。啊。。。。

dp[i][j]表示区间i~j所需的最小伤害

转移时枚举最后一个打死的狼就好了阿。。。

果然我傻逼= =

技术分享
#include <cstdio>#include <cstring>#include <algorithm>const int N = 210;using namespace std;int T,n;int a[N], b[N];int dp[N][N];inline void scan(int &ret) {    char c; ret=0;    while((c=getchar())<0||c>9);    while(c>=0&&c<=9) ret=ret*10+(c-0),c=getchar();}inline void mi(int &x, int y) { if(y<x) x=y; }int main() {    //freopen("in.txt", "r", stdin);    scanf("%d", &T);    int cas = 0;    while(T--){        scanf("%d", &n);        for (int i = 1; i <= n; ++i) scan(a[i]);        for (int i = 1; i <= n; ++i) scan(b[i]); b[n+1] = 0;        for (int i = 1; i <= n; ++i)            dp[i][i] = a[i] + b[i-1] + b[i+1];        for (int k = 1; k < n; ++k) {            for (int l = 1; l+k <= n; ++l) {                int r = l + k;                dp[l][r] = min(a[l]+dp[l+1][r], a[r]+dp[l][r-1]);                for (int last = l+1; last < r; ++last)                    mi(dp[l][r], dp[l][last-1]+dp[last+1][r]+a[last]);                dp[l][r] += b[l-1] + b[r+1];            }        }        printf("Case #%d: %d\n", ++cas, dp[1][n]);    }    return 0;}
View Code

 

 

还差的远呢。。。

【组队训练】2014北京区域赛