Dylan's Blog
0%

Posted on Edited on In

11月15日 Educational Codeforces Round 56 题目链接：https://codeforces.com/contest/1093

D - Beautiful Graph

思路： 一个简单的计数题。

首先根据题意可以得知，一条边两端的奇偶性一定要是不同的，因此只有二分图是存在可行方案的。考虑计数，先二分图染色（假设染成黑白两色），那么对于每一个连通块可行的方案就是 $2^{白色点数}+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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 300005
#define p 998244353
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int T, n, m, ans, num, tot, cnt, head[MAXN], col[MAXN], Pow[MAXN];

struct Edge {int next, to;} edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

int ksm(int x, int y)
{
    LL sum=1;
    while(y)
    {
        if(y&1) sum=1LL*sum*x%p;
        x=1LL*x*x%p; y>>=1;
    }
    return sum;
}

bool dfs(int x, int color)
{
    col[x]=color; tot++;
    if(color==0) num++;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(col[to]==-1)
        {
            if(!dfs(to, 1-color)) return false;
        }
        else if(col[to]==col[x]) return false;
    }
    return true;
}

void solve()
{
    cnt=0; ans=1;
    scanf("%d%d", &n, &m);
    for(rint i=1; i<=n; i++) head[i]=0, col[i]=-1;
    for(rint i=1; i<=m; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    for(rint i=1; i<=n; ++i)
    {
        if(col[i]>=0) continue;
        tot=num=0;
        if(dfs(i, 0)) ans=1LL*ans*(Pow[num]+Pow[tot-num])%p;
        else {printf("0\n"); return ;}
    }
    printf("%d\n", ans);
}

int main()
{
    scanf("%d", &T);
    Pow[0]=1;
    for(rint i=1; i<=300000; ++i) Pow[i]=Pow[i-1]*2%p;
    while(T--) solve();
    return 0;
}

E -Intersection of Permutations

思路： E 题就是个这么毒瘤的数据结构。。正解似乎是树套树，但是 CDQ 显然能做。

先可以将问题转化一下，处理出数组 $b$ 中的数字在数组 $a$ 中的位置记为数组 $c$，那么询问操作就是询问 $c[lb~rb]$ 中有多少个数的值在 $la~ra$ 内。这是一个二维数点问题，可以使用树状数组维护，由于有修改操作，那么就用 CDQ 基于时间一维进行分治就好了。时间复杂度也是 $O((n+m)log^2n)$。

代码：

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 <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 200005
#define MAXM
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, m, cnt, a[MAXN], b[MAXN], pos[MAXN], t[MAXN], ans[MAXN];

struct Act
{
    int id, x, y, val;
    Act(int a=0, int b=0, int c=0, int d=0)
    {
        id=a; x=b; y=c; val=d;
    }
} act[MAXN*5], temp[MAXN*5];

bool CMP(Act x, Act y)
{
    return x.x<y.x;
}

void add(int x, int y)
{
    for(; x<=200001; x+=(x&-x)) t[x]+=y;
}

int ask(int x)
{
    int sum=0;
    for(; x; x-=(x&-x)) sum+=t[x];
    return sum;
}

void cdq(int l, int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l, mid); cdq(mid+1, r);
    int L=l, R=mid+1;
    for(; R<=r; ++R)
    {
        if(!act[R].id) continue;
        while(act[L].x<=act[R].x && L<=mid)
        {
            if(!act[L].id) add(act[L].y, act[L].val);
            L++;
        }
        ans[act[R].id]+=act[R].val*ask(act[R].y);
    }
    for(int i=l; i<L; i++)
        if(!act[i].id) add(act[i].y, -act[i].val);
    merge(act+l, act+mid+1, act+mid+1, act+r+1, temp+l, CMP);
    for(int i=l; i<=r; i++) act[i]=temp[i];
}


int main()
{
    memset(ans, -1, sizeof(ans));
    scanf("%d%d", &n, &m);
    for(rint i=1; i<=n; ++i)
    {
        scanf("%d", &a[i]);
        pos[a[i]]=i;
    }
    for(rint i=1; i<=n; ++i)
    {
        scanf("%d", &b[i]);
        act[++cnt]=Act(0, i+1, pos[b[i]]+1, 1);
    }
    for(rint i=1; i<=m; ++i)
    {
        int op, la, ra, lb, rb, x, y;
        scanf("%d", &op);
        if(op==1)
        {
            ans[i]=0;
            scanf("%d%d%d%d", &la, &ra, &lb, &rb);
            act[++cnt]=Act(i, lb, la, 1);
            act[++cnt]=Act(i, lb, ra+1, -1);
            act[++cnt]=Act(i, rb+1, la, -1);
            act[++cnt]=Act(i, rb+1, ra+1, 1);
        }
        else
        {
            scanf("%d%d", &x, &y);
            act[++cnt]=Act(0, x+1, pos[b[x]]+1, -1);
            act[++cnt]=Act(0, y+1, pos[b[y]]+1, -1);
            swap(b[x], b[y]);
            act[++cnt]=Act(0, x+1, pos[b[x]]+1, 1);
            act[++cnt]=Act(0, y+1, pos[b[y]]+1, 1);
        }
    }
    cdq(1, cnt);
    for(int i=1; i<=m; i++)
        if(ans[i]!=-1) printf("%d\n", ans[i]);
}

F - Vasya and Array

思路： 是一个很有趣的 DP。

如果不考虑限制可以得到转移：$f[i][j]=\sum_{x=1}^{k} f[i-1][x]$，其中如果 $a[i]=-1$ 那么 $j$ 可以取 $1~k$ 所有数，否则 $j$ 只能取 j。接下来就是要把不合法的状态减去，我们记录一个数组 $pre[i]$ 表示从下标 $pre[i]$ 开始全可以取数字 $i$，由此我们就可以判断一个状态是否合法。如果数字 $j$ 在位置 $i$ 上不合法，那么我们就应该减去 $\sum_{x!=j} f[i-len][x]$。

代码：

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 100005
#define p 998244353
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, k, len, ans, a[MAXN], f[MAXN][105], pre[105], sum[MAXN];

void add(int &x, int y)
{
    x=(x+y>=p)?x+y-p:x+y;
}

int main()
{
    scanf("%d%d%d", &n, &k, &len);
    for(rint i=1; i<=n; ++i) scanf("%d", &a[i]);
    memset(pre, -1, sizeof(pre));
    sum[0]=1;
    for(rint i=1; i<=n; ++i)
    {
        if(a[i]!=-1)
        {
            f[i][a[i]]=(i==1)?1:sum[i-1];
            for(rint j=1; j<=k; ++j)
            {
                if(j!=a[i]) pre[j]=-1;
                else if(pre[j]==-1) pre[j]=i;
            }
            if(pre[a[i]]!=-1 && i-pre[a[i]]+1>=len)
                add(f[i][a[i]], p-sum[i-len]), add(f[i][a[i]], f[i-len][a[i]]);
                //f[i][a[i]]=(f[i][a[i]]-sum[i-len]+f[i-len][a[i]]+p)%p;
        }
        else
        {
            for(rint j=1; j<=k; ++j)
            {
                if(pre[j]==-1) pre[j]=i;
                f[i][j]=(i==1)?1:sum[i-1];
            }

            for(rint j=1; j<=k; ++j)
                if(i-pre[j]+1>=len) add(f[i][j], p-sum[i-len]), add(f[i][j], f[i-len][j]);
                    //f[i][j]=(f[i][j]-sum[i-len]+f[i-len][j]+p)%p;
        }
        for(rint j=1; j<=k; j++) add(sum[i], f[i][j]);
            //sum[i]=(sum[i]+f[i][j])%p;
    }
    printf("%d\n", sum[n]);
}

G - Multidimensional Queries

思路： G 题与 E 题比反而是一个比较简单的数据结构题。

考虑 $k$ 比较小，于是我们可以对一个点枚举在每一维上对答案的贡献情况，即在公式 $\sum \limits_{i = 1}^{k} |a_{x, i} - a_{y, i}|$ 去掉绝对值时的符号。对于我们枚举的每一种情况，由于去掉了绝对值，答案便是求一个区间内最大值与最小值之差，这个可以很简单的用线段树去维护。

为了减小码量，对于每一棵线段树可以只维护最小值。而最大值与最小值之差就是当前状态下的最小值与相反状态下最小值的和。

代码：

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
Copy
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 200005
#define ls (root<<1)
#define rs (root<<1|1)
#define mid ((l+r)>>1)
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, k, q, w[6], sum[32];

struct Segtree
{
    int val[MAXN*4], num[MAXN];

    void up(int root)
    {
        val[root]=min(val[ls], val[rs]);
    }

    void build(int root, int l, int r)
    {
        if(l==r)
        {
            val[root]=num[l];
            return;
        }
        build(ls, l, mid);
        build(rs, mid+1, r);
        up(root);
    }

    void update(int root, int l, int r, int x, int k)
    {
        if(l>x || r<x) return;
        if(l==r)
        {
            val[root]=k;
            return;
        }
        update(ls, l, mid, x, k);
        update(rs, mid+1, r, x, k);
        up(root);
    }

    int query(int root, int l, int r, int x, int y)
    {
        if(l>y || r<x) return INF;
        if(l>=x && r<=y) return val[root];
        return min(query(ls, l, mid, x, y), query(rs, mid+1, r, x, y));
    }
} t[32];


int main()
{
    scanf("%d%d", &n, &k);
    for(rint i=1; i<=n; ++i)
    {
        for(rint j=0; j<k; ++j) scanf("%d", &w[j]);
        for(rint sta=0; sta<(1<<k); ++sta)
            for(rint j=0; j<k; ++j)
            {
                if((sta>>j)&1) t[sta].num[i]+=w[j];
                else t[sta].num[i]-=w[j];
            }
    }
    for(rint sta=0; sta<(1<<k); ++sta) t[sta].build(1, 1, n);
    scanf("%d", &q);
    while(q--)
    {
        int op, x, y, ans=0;
        scanf("%d", &op);
        if(op==2)
        {
            scanf("%d%d", &x, &y);
            for(rint sta=0; sta<(1<<k); ++sta)
                sum[sta]=t[sta].query(1, 1, n, x, y);
            for(rint sta=0; sta<(1<<k); ++sta)
                ans=max(ans, -(sum[sta]+sum[(1<<k)-1-sta]));
            printf("%d\n", ans);
        }
        else
        {
            scanf("%d", &x);
            for(rint i=0; i<k; ++i) scanf("%d", &w[i]);
            for(rint sta=0; sta<(1<<k); ++sta)
            {
                int temp=0;
                for(rint i=0; i<k; ++i)
                {
                    if((sta>>i)&1) temp+=w[i];
                    else temp-=w[i];
                }
                t[sta].update(1, 1, n, x, temp);
            }
        }
    }
}

Posted on Edited on In

问题描述

windy 定义了一种 windy 数。不含前导零且相邻两个数字之差至少为 2 的正整数被称为 windy 数。windy 想知道在 A 和 B 之间（包括 A 和 B）总共有多少个 windy 数？

输入

包含两个整数，A B。

输出

一个整数，同题目要求

思路

一个比较简单的数位DP吧，直接按照套路来就好了。$f[i][j]$ 表示在第 $i$ 位上为 $j$ 的可能情况数，利用 $f$ 数组记忆化。然后需要注意的是，处理前导零时也不能够记忆化（仅针对我这种写法）。

代码

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

int l, r, dig[12], f[10][10];

int dp(int x, int lim, int tag, int num)
{
    if(x==0) return tag;
    if(!lim && tag && f[x][num]!=-1) return f[x][num];
    int temp=0;
    if(!tag)
    {
        for(int i=0; i<=(lim?dig[x]:9); i++)
        {
            if(i==0) temp+=dp(x-1, lim&&i==dig[x], 0, 0);
            else temp+=dp(x-1, lim&&i==dig[x], 1, i);
        }
    }
    else
    {
        for(int i=0; i<=(lim?dig[x]:9); i++)
        {
            if(abs(num-i)<2) continue;
            temp+=dp(x-1, lim&&i==dig[x], 1, i);
        }
    }
    if(!lim && tag) f[x][num]=temp;
    return temp;
}

int solve(int x)
{
    int cnt=0;
    memset(f, -1, sizeof(f));
    while(x) dig[++cnt]=x%10, x/=10;
    return dp(cnt, 1, 0, 0);
}

int main()
{
    scanf("%d%d%", &l, &r);
    //printf("%d %d!!!\n", solve(r), solve(l-1));
    printf("%d\n", solve(r)-solve(l-1));
}

Posted on Edited on In

问题描述

Tehran 的一家每天 $24$ 小时营业的超市，需要一批出纳员来满足它的需要。超市经理雇佣你来帮他解决问题——超市在每天的不同时段需要不同数目的出纳员为顾客提供优质服务。他希望雇佣最少数目的出纳员。

经理已经提供给你一天的每一小时需要出纳员的最少数量——$R(0),R(1),⋯,R(23)$。表示从午夜到上午 $0:00$ 需要出纳员的最小数目，每一天，这些数据都是相同的。有 $N$ 人申请这项工作，每个申请者 $i$ 在每 $24$ 小时中，从一个特定的时刻开始连续工作恰好 $8$ 小时。定义 $t_i$ 为上面提到的开始时刻。也就是说，如果第 $i$ 个申请者被录取，他将从 $t_i$ 时刻开始连续工作 $8$ 小时。

输入

第一行为测试点的数目 $T$。

对于每组测试数据，第一行为 $24$ 个整数，表示 $R(0),R(1),R(2),⋯ ,R(23)$ 接下来一行一个正整数 $N$，表示申请者数目； 接下来 $N$ 行每行一个整数 $t_i$

输出

对于每个测试点，输出一行，包含一个整数，表示需要出纳员的最小数目。如果无解，输出 No Solution。

思路

一道差分约束很好的例题。本题思路引用了 这篇 Discuss

首先考虑约束关系。设：$r_i$ 为时间 $i$ 需要的人数 $t_i$ 为时间 $i$ 应聘的人数 $s_i$ 为时间 $i$ 以及之前录用的人数和

那么就存在约束关系： $s_i-s_{i-8}\geq r_i (8\leq i\leq 24)$ $s_i-s_{16+i}\geq r_i-s_{24} (1\leq i\leq 7)$ $s_i-s_{i-1}\geq 0 (1\leq i\leq 24)$ $s{i-1}-s_i\geq -t_i (1\leq i\leq 24)$

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define MAXN 1005
using namespace std;

int T, n, m, cnt, ans, tag[MAXN], need[MAXN], vis[MAXN], head[MAXN], dis[MAXN], num[MAXN];

struct Edge {int next, to, dis;} edge[MAXN];

queue<int> q;

void addedge(int from, int to, int dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    head[from]=cnt;
}

bool spfa()
{
    memset(dis, -0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    memset(num, 0, sizeof(num));
    while(!q.empty()) q.pop();

    q.push(0); dis[0]=0;
    while(!q.empty())
    {
        int x=q.front(); q.pop();
        vis[x]=0;
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(dis[to]<dis[x]+edge[i].dis)
            {
                dis[to]=dis[x]+edge[i].dis;
                num[to]=num[x]+1;
                if(num[to]>25) return false; 
                if(!vis[to]) vis[to]=1, q.push(to);
            }
        }
    }
    return true;
}

bool check(int mid)
{
    cnt=0;
    memset(head, 0, sizeof(head));

    for(int i=1; i<=7; i++) addedge(i+16, i, need[i]-mid);
    for(int i=8; i<=24; i++) addedge(i-8, i, need[i]);
    for(int i=1; i<=24; i++)
    {
        addedge(i-1, i, 0);
        addedge(i, i-1, -tag[i]);
    }
    addedge(0, 24, mid);
    return spfa();
}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        int l=0, r=1000, ans=-1;
        memset(tag, 0, sizeof(tag));

        for(int i=1; i<=24; i++) scanf("%d", &need[i]);
        scanf("%d", &n);
        for(int i=1; i<=n; i++)
        {
            int x;
            scanf("%d", &x);
            tag[x+1]++;
        }

        for(int i=0; i<=n; i++)
            if(check(i)) {ans=i; break;}
        if(ans==-1) printf("No Solution\n");
        else printf("%d\n", ans);
    }
}

Posted on Edited on In

问题描述：

$n$只奶牛构成了一个树形的公司，每个奶牛有一个能力值$p_i$，$1$号奶牛为树根。问对于每个奶牛来说，它的子树中有几个能力值比它大的。

输入：

第一行一个整数$n$，表示有$n$头奶牛 接下来$n$行为$1-n$号奶牛的能力值$p_i$ 接下来$n-1$行为$2-n$号奶牛的经理（树中的父亲）

输出：

共$n$行，每行输出奶牛$i$的下属中有几个能力值比$i$大

思路：

其实看完题后第一反应是树上启发式合并（不过应该可做，这种方法先坑着）。既然这是线段树合并的模版，那么还是先用这种方法做一遍吧。

首先离散化，然后对于每一个节点都建一颗权值线段树（里面都只有一个节点），接着dfs一遍，将每个节点儿子的线段树并在该节点上，然后跟新这个节点的答案就好了。

不过合并的操作复杂度是取决于线段树重合部分的大小，空间也要开很多倍。

代码：

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define MAXN 100005
using namespace std;

int n, m, cnt, tot, a[MAXN], b[MAXN], head[MAXN], root[MAXN], ans[MAXN];

struct Node {int size, ls, rs;} t[MAXN*20];
struct Edge {int next, to;} edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

void up(int root)
{
    t[root].size=t[t[root].ls].size+t[t[root].rs].size;
}

void insert(int &root, int l, int r, int x)
{
    root= ++tot;
    if(l==r) {t[root].size=1; return;}
    int mid=(l+r)>>1;
    if (x<=mid) insert(t[root].ls, l, mid, x);
    else insert(t[root].rs, mid+1, r, x);
    up(root);
}

int merge(int x, int y)
{
    if((!x) || (!y)) return x+y;
    t[x].ls=merge(t[x].ls, t[y].ls);
    t[x].rs=merge(t[x].rs, t[y].rs);
    up(x);
    return x;
}

int query(int root, int l, int r, int x, int y)
{
    if(r<x || l>y) return 0;
    if(l>=x && r<=y) return t[root].size;
    int mid=(l+r)>>1;
    return query(t[root].ls, l, mid, x, y)+query(t[root].rs, mid+1, r, x, y);
}

void dfs(int x)
{
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        dfs(to);
        root[x]=merge(root[x], root[to]);
    }
    ans[x]=query(root[x], 1, n, a[x]+1, tot);
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]), b[i]=a[i];
    sort(b+1, b+n+1);
    m=unique(b+1, b+n+1)-b-1;
    for(int i=1; i<=n; i++) a[i]=lower_bound(b+1, b+m+1, a[i])-b;
    for(int i=2; i<=n; i++)
    {
        int x;
        scanf("%d", &x);
        addedge(x, i);
    }
    for(int i=1; i<=n; i++) insert(root[i], 1, n, a[i]);
    dfs(1);
    for(int i=1; i<=n; i++) printf("%d\n", ans[i]);
}

Posted on Edited on In

·9月4日 Codeforces Round #505 题目链接：http://codeforces.com/contest/1025

A - Doggo Recoloring

过水，就不说了。。

B - Weakened Common Divisor

思路： 首先我们不难想到将每一对数乘起来，然后求这些乘积的GCD，如果这个GCD为1则应该输出-1。但是这个GCD不一定是答案，但答案一定是这个GCD的约数。这时我就想到了找这个GCD最小的约数做为答案，但这样是会T的。于是我们考虑造成GCD不一定是答案的原因，然后我们可以将这个GCD与每一对中的一个数再求一遍GCD，这样的答案就是符合要求的了。

代码：

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
#include <bits/stdc++.h>
#define MAXN 150005
#define LL long long
using namespace std;

int n;
LL a[MAXN], b[MAXN], c[MAXN];

LL gcd(LL x, LL y)
{
    return y==0?x: gcd(y, x%y);
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%lld%lld", &a[i], &b[i]);
        c[i]=a[i]*b[i];
    }
    LL ans=c[1];
    for(int i=2; i<=n; i++) ans=gcd(ans, c[i]);
    if(ans==1) printf("-1\n");
    else
    {
        for(int i=1; i<=n; i++)
        {
            if(gcd(ans, a[i])＞=1) ans=gcd(ans, ａ[i]);
            else ans=gcd(ans, ｂ[i]);
        }
        printf("%lld\n", ans);
    }
}

C - Plasticine zebra

思路： 一开始什么思路都没有，卡了很久。后面有一种直觉就是如果头和尾相等，那么如何翻转都是不会增加答案的（虽然一直不会证明）。

设$1-i$的字符串为’zebra’，这样的话只要头尾不相等，在位置$i$进行一次操作，这样’zebra’的长度一定会增加。由于开始提到的‘直觉’，只要操作后头和尾相等就break出循环。

后面看了题解后，就更加奇怪了，不明白自己这种乱搞的做法为什么是对的。

代码：

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
#include <bits/stdc++.h>
#define MAXN 100005
#define LL long long
using namespace std;

char a[MAXN];
int ans=1, n, f[MAXN];

void print()
{
    for(int i=0; i<n; i++) printf("%c", a[i]);
    printf("\n");
}

int main()
{
    scanf("%s", a);
    n=strlen(a);
    for(int i=0; i<n; i++)
    {
        if(a[0]==a[n-1]) break;
        if(a[i]==a[i+1])
        {
            reverse(a, a+i+1);
            reverse(a+i+1, a+n);
        }
    }
    f[0]=1;
    for(int i=1; i<n; i++)
    {
        if(a[i]==a[i-1]) f[i]=1;
        else f[i]=f[i-1]+1;
        ans=max(ans, f[i]);
    }
    printf("%d\n", ans);
}

D - Recovering BST

思路： 其实这和平衡树并没有半毛钱关系，只是根据BST的性质让你做区间DP。

对于一个递增序列，你可以任意选一个数作为BST的根，这个数将序列分为两部分，分别作为这个根的左子树和右子树。然后这两个部分又是递增序列，于是可以这样递归下去DP。

大致的思路是这样，但要注意一些细节。首先是要记忆化以保证复杂度，然后就是要记录自己序列是在左子树还是右子树，以便判断是否符合要求（也就是边两端的数GCD>1）。

代码：

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
#include <bits/stdc++.h>
#define MAXN 705
#define LL long long
using namespace std;

int n, f[MAXN][MAXN][2], a[MAXN];

int gcd(int x, int y)
{
    return y==0? x:gcd(y, x%y);
}

bool dp(int l, int r, int k, int fa)
{
    if(f[l][r][k]!=-1) return f[l][r][k];
    if(l==r) return 1;
    if(k==0)
    {
        for(int i=l; i<r; i++)
            if(gcd(a[i], a[r])>1 && dp(l, i, 0, i) && dp(i, r-1, 1, i)) return f[l][r][k]=1;
    }
    else
    {
        for(int i=l+1; i<=r; i++)
            if(gcd(a[l], a[i])>1 && dp(l+1, i, 0, i) && dp(i, r, 1, i)) return f[l][r][k]=1;
    }
    return f[l][r][k]=0;
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    memset(f, -1, sizeof(f));
    for(int i=1; i<=n; i++)
        if(dp(1, i, 0, i) && dp(i, n, 1, i))
        {
            printf("Yes\n");
            return 0;
        }
    printf("No\n");
}