构造

【190730】计蒜客 SEERC 2018

2019-07-30

目录

E题

对每条鱼计算贡献，差分数组维护。

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
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 200000 + 5;

int x[N], y[N];

struct man
{
    int x, id;
    bool operator<(const man &b) const
    {
        return x < b.x;
    }
};
man b[N];
vector<int> v;
int f[N], ans[N];

int main()
{
    int n, m, l;
    scanf("%d%d%d", &n, &m, &l);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &x[i], &y[i]);
    for (int i = 0; i < m; i++)
    {
        scanf("%d", &b[i].x);
        v.push_back(b[i].x);
        b[i].id = i;
    }
    sort(v.begin(), v.end());
    sort(b, b + m);
    for (int i = 0; i < n; i++)
    {
        if (y[i] > l)
            continue;
        int d = l - y[i];
        int lx = x[i] - d, rx = x[i] + d;
        int lid = lower_bound(v.begin(), v.end(), lx) - v.begin();
        int rid = upper_bound(v.begin(), v.end(), rx) - v.begin();
        f[lid]++;
        f[rid]--;
    }
    for (int i = 0; i < m; i++)
        f[i + 1] += f[i];
    for (int i = 0; i < m; i++)
        ans[b[i].id] = f[i];
    for (int i = 0; i < m; i++)
        printf("%d\n", ans[i]);
    return 0;
}

B题

按奇偶分类推公式，再考虑三指针长度相同、两相同、各不同。

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

using namespace std;

typedef unsigned long long ULL;

ULL s2(ULL x)
{
    ULL y = x + 1;
    if (x & 1)
        y /= 2;
    else
        x /= 2;
    return x * y;
}

ULL s3(ULL n)
{
    ULL f[3] = {n, n + 1, 2 * n + 1};
    for (int i = 0; i < 3; i++)
        if (f[i] % 2 == 0)
        {
            f[i] /= 2;
            break;
        }
    for (int i = 0; i < 3; i++)
        if (f[i] % 3 == 0)
        {
            f[i] /= 3;
            break;
        }
    return f[0] * f[1] * f[2];
}

ULL solve(ULL n)
{
    if (n & 1)
    {
        n /= 2;
        return s3(n);
    }
    else
    {
        n /= 2;
        n--;
        return 3 * s2(n) + s3(n);
    }
}

int main()
{
    int a[4];
    ULL n;
    for (int i = 0; i < 3; i++)
        scanf("%d", &a[i]);
    scanf("%llu", &n);
    ULL ans = solve(n);
    sort(a, a + 3);
    int d = unique(a, a + 3) - a;
    if (d == 2)
        ans *= 3;
    else if (d == 3)
        ans *= 6;
    printf("%llu\n", ans);
}

I题

拓扑序DP。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100+10;
ll dp[maxn];
int g[maxn][maxn];
int n,m,u,v;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0; i<=n+1; ++i)
        memset(g[i],0,sizeof(g[i]));
    memset(dp,0,sizeof(dp));
    for(int i=0; i<m; ++i)
    {
        scanf("%d%d",&u,&v);
        g[u][v]=1;
        g[v][u]=1;
    }
    dp[0]=1;
    for(int i=1; i<=n+1; ++i)
    {
        for(int j=0; j<i; ++j)
        {
            if(g[i][j]) continue;
            int flag=1;
            for(int k=j+1; k<i; ++k)
            {
                if(!g[i][k]&&!g[j][k])
                {
                    flag=0;
                    break;
                }
            }
            dp[i]+=dp[j]*flag;
        }
    }
    printf("%lld\n",dp[n+1]);
    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
#include <cstdio>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 105;
bool color[N];
int d[N][N];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%d", &color[i]);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            d[i][j] = i == j ? 0 : INF;
    int x, y;
    for (int i = 0; i < n - 1; i++)
    {
        scanf("%d%d", &x, &y);
        d[x - 1][y - 1] = d[y - 1][x - 1] = 1;
    }
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    int ans = INF;
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++)
            if (color[i] && color[j])
            {
                int cnt = 0, t = d[i][j];
                for (int k = 0; k < n; k++)
                    if (color[k] && d[i][k] <= t && d[k][j] <=t)
                        cnt++;
                if (cnt >= m)
                    ans = min(ans, t);
            }
    printf("%d\n", ans);
    return 0;
}

F题

有解当且仅当B相邻合并后为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
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
#include <bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
struct ddd
{
    int x,l,r;
};
ddd e[maxn];
int a[maxn],b[maxn],pos[maxn];
int n,cnt=0,now=1,ans=0;
char ch[maxn*2];
int L[maxn*2],R[maxn*2];
void add(char c, int l, int r)
{
    if(l>=r) return;
    ch[ans]=c;
    L[ans]=l;
    R[ans]=r;
    ++ans;
}
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; ++i) scanf("%d",&a[i]);
    for(int i=1; i<=n; ++i) scanf("%d",&b[i]);
    now=1;
    for(int i = 1;i <= n;i++)
    {
        while(now <= n && a[now] != b[i]) ++now;
        if(now > n)
        {
            printf("-1\n");
            return 0;
        }
        pos[i] = now;
    }
    now=1;
    cnt=0;
    for(int i = 1;i <= n;i++)
    {
        if(pos[i] == pos[i+1]) continue;
        e[cnt++] = (ddd){pos[i], now, i};
        now = i + 1;
    }
    ans=0;
    for(int i=cnt-1; i>=0; --i)
    {
        if(e[i].x >= e[i].l) continue;
        if(a[e[i].x] >= a[e[i].x+1])
        {
            add('m', e[i].x+1, e[i].r);
            add('M', e[i].x, e[i].r);
        }
        else
        {
            add('M', e[i].x+1, e[i].r);
            add('m', e[i].x, e[i].r);
        }
    }
    for(int i=0; i<cnt; ++i)
    {
        if(e[i].x <= e[i].r) continue;
        if(a[e[i].x] <= a[e[i].x-1])
        {
            add('M', e[i].l, e[i].x-1);
            add('m', e[i].l, e[i].x);
        }
        else
        {
            add('m', e[i].l, e[i].x-1);
            add('M', e[i].l, e[i].x);
        }
    }
    for(int i=0; i<cnt; ++i)
    {
        if(e[i].l > e[i].x || e[i].r < e[i].x) continue;
        if(e[i].x > e[i].l)
        {
            if(a[e[i].x] >= a[e[i].x-1])
            {
                add('m', e[i].l, e[i].x-1);
                add('M', e[i].l, e[i].x);
            }
            else
            {
                add('M', e[i].l, e[i].x-1);
                add('m', e[i].l, e[i].x);
            }
        }
        if(e[i].x < e[i].r)
        {
            if(a[e[i].x] >= a[e[i].x+1])
            {
                add('m', e[i].x+1, e[i].r);
                add('M', e[i].x, e[i].r);
            }
            else
            {
                add('M', e[i].x+1, e[i].r);
                add('m', e[i].x, e[i].r);
            }
        }
    }
    printf("%d\n",ans);
    for(int i=0; i<ans; ++i)
        printf("%c %d %d\n",ch[i],L[i],R[i]);
    return 0;
}

H题

随机输出。

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
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <vector>
using namespace std;
const int N = 200000 + 5;
vector<int> ans;
int u[N], v[N];
int k[N];
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++)
            scanf("%d%d", &u[i], &v[i]);
        do
        {
            ans.clear();
            for (int i = 1; i <= n; i++)
                k[i] = rand() % 2;
            for (int i = 1;i <= m; i++)
                if (k[u[i]] == 0 && k[v[i]] == 1)
                    ans.push_back(i);
        } while (ans.size() <= m / 4);
        printf("%d\n", ans.size());
        int t = ans.back();
        ans.pop_back();
        for (int id : ans)
            printf("%d ", id);
        printf("%d\n", t);
    }
    return 0;
}
© 2019 blog - Powered by Hexo - Theme Chan