C18-team4

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

太土了

by yxdb

-------------------------------

赛后过了E题, 理清楚了思路以后写了不到20分钟就写好了

由于要取模, 中间的减法可能会产生负数, 改对后提交, 2Y

代码:

{{{
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long LL;

const int MOD = 1000000007;

LL dp[1005][1005], sum[1005][1005];

int gao(char s[]) {
    int n = strlen(s) + 1;
    sum[1][1] = 1;
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            if (s[i-2] == 'I')
                dp[i][j] = sum[i-1][j-1]; 
            else if (s[i-2] == 'D')
                dp[i][j] = (sum[i-1][i-1] - sum[i-1][j-1] + MOD) % MOD;
            else
                dp[i][j] = sum[i-1][i-1];
            sum[i][j] = (sum[i][j-1] + dp[i][j]) % MOD;
        }
    }
    return sum[n][n];
}

int main() {
    char s[1005];
    while (1 == scanf("%s", s)) {
        printf("%d\n", gao(s));
    }
}

}}}

感觉我们队在遇到比较难的套题的时候就会乱了阵脚, 主要还是实力不够吧... 像今天又被ac自动机和线段树虐了...

搞不出题, 就会后半场打酱油!

by yxdb

太土了

by yxdb

赛后过了E题, 理清楚了思路以后写了不到20分钟就写好了

由于要取模, 中间的减法可能会产生负数, 改对后提交, 2Y

代码:

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int MOD = 1000000007;
LL dp[1005][1005], sum[1005][1005];
int gao(char s[]) {
    int n = strlen(s) + 1;
    sum[1][1] = 1;
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            if (s[i-2] == 'I')
                dp[i][j] = sum[i-1][j-1]; 
            else if (s[i-2] == 'D')
                dp[i][j] = (sum[i-1][i-1] - sum[i-1][j-1] + MOD) % MOD;
            else
                dp[i][j] = sum[i-1][i-1];
            sum[i][j] = (sum[i][j-1] + dp[i][j]) % MOD;
        }
    }
    return sum[n][n];
}
int main() {
    char s[1005];
    while (1 == scanf("%s", s)) {
        printf("%d\n", gao(s));
    }
}

感觉我们队在遇到比较难的套题的时候就会乱了阵脚, 主要还是实力不够吧... 像今天又被ac自动机和线段树虐了...

搞不出题, 就会后半场打酱油!

by yxdb

附加文件