Codeforces Round #745 (Div. 2)

发表于 更新于 分类于 本文字数： 908 阅读时长 ≈ 3 分钟

这场感觉自己就是个菜鸡不能再菜了

A题一开始想暴力打表出奇迹，但到n=5时，暴力方法就要几十秒出一个答案

然后看出了的几个数据猜测出答案为，而事实上对于题中限制条件来说，满足与不满足概率均等，所以才为此答案

赛后看了几个a掉了B题的代码，知道了题意图的连接不一定要组成一个多边形，可以是一点发散，所以对于的情况只需即可

思维局限

UPD:

C和D都是面向数据编程，TLE卡得难受

C题要构建一个除四角外的边均为1，内部为0的矩阵
所以最差的结果应该是,所以对一矩阵内部和已大于等于16的进行break剪枝，相应的，如果剩下的区域内和小于等于2也一并break

D题是个dp题

A: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const LL p = 1e9 + 7, N = 2e5 + 86;
LL  jc[N], cnt = 1;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    LL n, t, mark = 3;
    cin >> t;
    f(sb, 1, t)
    {
        cin >> n;
        jc[0] = 1;
        jc[1]=1;
        jc[2]=12;
        for (int j = mark; j <= n; j++)
        {
            jc[j]=(jc[j-1]*(2*j%p))%p;
            jc[j]=(jc[j]*((2*j-1)%p))%p;
        }
        mark=mark<n?n:mark;
        cout << jc[n]%p<<'\n';
    }
    return 0;
}
B: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
LL t, n, m, k;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    f(s, 1, t)
    {
        cin >> n >> m >> k;
        LL lens=(n-1)*n/2;
        if(n==1&&k>=2&&m==0){cout<<"YES\n";continue;}
        if(m<n-1||m>lens||k<=2)cout<<"NO\n";
        else {
            if(k>=4||m==lens)cout<<"YES\n";
            else cout<<"NO\n";
        }
    }
    return 0;
}

C:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
const LL N = 416;
LL t, a, b, s[N][N];

inline LL getsum(int x1, int y1, int x2, int y2)
{
    return s[x2][y2] + s[x1 - 1][y1 - 1] - s[x1 - 1][y2] - s[x2][y1 - 1];
}

inline LL getres(int x1, int y1, int x2, int y2)
{
    LL sum2 = getsum(x1 + 1, y1 + 1, x2 - 1, y2 - 1), sum1 = getsum(x1 + 1, y1, x2 - 1, y1) + getsum(x1, y1 + 1, x1, y2 - 1) + getsum(x1 + 1, y2, x2 - 1, y2) + getsum(x2, y1 + 1, x2, y2 - 1);
    return 2 * (y2 - 1 - y1 + x2 - 1 - x1) - sum1 + sum2;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    f(sb, 1, t)
    {
        char str[408];
        memset(s, 0, sizeof(s));
        cin >> a >> b;
        LL ma=a-4,mb=b-3;
        f(k, 1, a)
        {
            cin >> str;
            f(j, 1, b)
            {
                s[k][j] = s[k - 1][j] + s[k][j - 1] - s[k - 1][j - 1] + str[j - 1] - '0';
                if(str[j - 1] - '0'){
                    ma=k<ma?k:ma;
                    mb=j<mb?j:ma;
                }
            }
        }
        if (s[a][b] == 0)
        {
            cout << "10";
            continue;
        }
        LL res = 16;
        if(a<400&&b<400){
            ma=1;
            mb=1;
        }
        f(i, ma, a)
        {
            f(j, mb, b)
            {
                for (int k = i + 4; k <= a; k++)
                {
                    for (int v = j + 3; v <= b; v++)
                    {
                        if (getsum(i + 1, j + 1, k - 1, v - 1) >= res)
                        {
                            break;
                        }
                        LL sp = getres(i, j, k, v);
                        res = min(res, sp);
                        if (s[a][b] - s[k][v] <= 2)
                            break;
                    }
                }
            }
        }
        cout << res << '\n';
    }
    return 0;
}

D:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
const LL N=108;
LL n, m, k, p,dp[N][N][N],fac[N],c[N][N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>k>>p;
    if((n==m&&k>1)||k>45){
        cout<<"0";
        return 0;
    }
    fac[0]=c[0][0]=1;
    f(i,1,101){
        c[i][0]=c[i][i]=1;
        fac[i]=fac[i-1]*i%p;
        dp[i][1][1]=fac[i];
        for(int s=i+1;s<=m;s++) dp[i][0][s] = fac[i]; 
        for(int j=1;j<i;j++){
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%p;
        }
    }
    for(int a=2;a<=n;a++){
        for(int b=0;b<=a&&b<=k;b++){
            for(int d=2;d<=a&&d<=m;d++){
                dp[a][b][d]+=(2*dp[a-1][b][d-1])%p;
                for(int a_1=1;a-1-a_1>0;a_1++){
                    for(int b_1=0;b_1<=a_1&&b_1<=b;b_1++){
                        if(b-b_1>a-1-a_1)
                        continue;
                        dp[a][b][d]=(dp[a][b][d]+(((c[a-1][a_1]*dp[a_1][b_1][d-1])%p)*dp[a-1-a_1][b-b_1][d-1])%p)%p;
                    }
                }

            }
        }
    }
    cout<<dp[n][k][m];
    return 0;
}