Starry

发表于 更新于 分类于 本文字数： 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;
}

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

转移方程推出来的和题解一样，但dp代码不同导致WA

AC的：

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
LL s, n, m, a[301][301], dp[30010],ans;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s >> n >> m;
    f(i, 1, s)
    {
        f(j, 1, n) cin >> a[j][i - 1];
    }
    f(i, 1, n) sort(a[i], a[i] + s);
    for (int k = 1; k <= n; k++)
    {

        for (int i = m; i >= 0; i--)
        {
            for (int j = 0; j < s; j++)
            {
                if(i >=2 * a[k][j] + 1)
                dp[i] = max(dp[i], dp[i - 2 * a[k][j] - 1] + k * (j + 1));
            }
            ans=max(ans,dp[i]);
        }
    }
    cout << ans;
    return 0;
}

WA的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s >> n >> m;
    f(i, 1, s)
    {
        f(j, 1, n) cin >> a[j][i - 1];
    }
    f(i, 1, n) sort(a[i], a[i] + s);
    for (int k = 1; k <= n; k++)
    {
        for (int j = 0; j < s; j++)
        {
            for (int i = m; i >= 2 * a[k][j] + 1; i--)
            {
                dp[i] = max(dp[i], dp[i - 2 * a[k][j] - 1] + k );
            }
        }
    }
    cout << dp[m];
    return 0;
}
update:9.29 8:59

WA会有重复计算变成完全背包

我是菜鸡

菜

发表于 更新于 分类于 本文字数： 53 阅读时长 ≈ 1 分钟 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const LL N=1e5+86;
int main()
{
    //IN;OUT;
    ios::sync_with_stdio(false);
    cin.tie(0);
    LL n,m,v,p,dp[N];
    cin>>n>>m;
    f(i,1,m){
        cin>>v>>p;
        for(int j=n;j>=v;j--){
            dp[j]=max(dp[j],dp[j-v]+v*p);
        }
    }
    cout<<dp[n];
    return 0;
}

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

用bitset的位操作来优化过程

但却不知道怎么普通的做，，，，

菜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bitset>
using namespace std;

LL v,n,res;
bitset<30000> dp;

int main()
{
    IN;OUT;
    v=io.xint();
    n=io.xint();
    dp.reset();
    dp.set(0);
    f(i,0,n-1){
        dp|=(dp<<io.xint());
    }
    for (res=v;dp[res]==0;res--);
    io.wll(v-res);
    return 0;
}

发表于 更新于 分类于 本文字数： 418 阅读时长 ≈ 2 分钟 
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr1(x) printf("Case %lld: ", x)
#define pn1(x) printf("Case %lld:\n", x)
#define pr2(x) printf("Case #%d: ", x)
#define pn2(x) printf("Case #%d:\n", x)
#define lowbit(x) (x & (-x))

typedef unsigned long long ull;

const LL N = 1e5 + 86;
LL n, m, a[N], d[N << 2], tag[N << 2];

void build(LL l, LL r, LL p)
{
    if (l == r)
    {
        d[p] = a[l];
        return;
    }
    LL m = l + ((r - l) >> 1);
    build(l, m, p << 1);
    build(m + 1, r, (p << 1) | 1);
    d[p] = d[p << 1] + d[(p << 1) | 1];
}

void update(LL l, LL r, LL c, LL nl, LL nr, LL p)
{
    if (l <= nl && r >= nr)
    {
        d[p] += (nr - nl + 1) * c;
        tag[p] += c;
        return;
    }
    LL m = nl + ((nr - nl) >> 1);
    if (tag[p])
    {
        tag[p << 1] += tag[p];
        tag[(p << 1) | 1] += tag[p];
        d[p << 1] += (m - nl + 1) * tag[p];
        d[(p << 1) | 1] += (nr - m) * tag[p];
        tag[p] = 0;
    }
    if (l <= m)
        update(l, r, c, nl, m, p << 1);
    if (r > m)
        update(l, r, c, m + 1, nr, (p << 1) | 1);
    d[p] = d[p << 1] + d[(p << 1) | 1];
    return;
}

LL getsum(LL l, LL r, LL nl, LL nr, LL p)
{
    if (l <= nl && nr <= r)
        return d[p];
    LL m = nl + ((nr - nl) >> 1);
    LL res = 0;
    //pn1(m);
    if (tag[p])
    {
        tag[p << 1] += tag[p];
        tag[(p << 1) | 1] += tag[p];
        d[p << 1] += (m - nl + 1) * tag[p];
        d[(p << 1) | 1] += (nr - m) * tag[p];
        tag[p] = 0;
    }
    if (l <= m)
        res += getsum(l, r, nl, m, p << 1);
    //pn1(m);
    if (r > m)
        res += getsum(l, r, m + 1, nr, (p << 1) | 1);
    return res;
}

int main()
{
    // IN;OUT;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    f(i, 1, n) cin >> a[i];
    build(1, n, 1);
    f(i, 1, m)
    {
        int temp, x, y, k;
        cin >> temp;
        if (temp & 1)
        {
            cin >> x >> y >> k;
            update(x, y, k, 1, n, 1);
        }
        else
        {
            cin >> x >> y;
            cout << getsum(x, y, 1, n, 1) << '\n';
        }
    }
    return 0;
}
0%