Baltic Olympiad in Informatics 2018

发表于 更新于
polygon dna worm alternating genetics paths
$\color{green}{\texttt{+}}$ $\color{green}{\texttt{+}}$ $\color{red}{\texttt{+}}$ $\color{red}{\texttt{-}}$ $\color{green}{\texttt{+}}$ $\color{green}{\texttt{+}}$

链接 题面链接 中文题面

A. Love Polygon

注意到一个点至少有一条出边，而总边数是 $n$，所以这是一棵基环内向树。

除去原本的二元环，实际上答案就是 $n-匹配数$。

找出每一个块，非环部分先贪心匹配。如果环上有点已经被匹配了就从该点开始，否则任取一个点开始贪心匹配，容易证明是正确的。

复杂度 $O(n)$

代码 
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<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#define N 100010
using namespace std;
map<string,int>mp;
int fa[N];
bool vis[N];int cir[N],T;
vector<int>g[N];
int ans;bool col[N];
void dfs(int u){vis[u]=true;for(int v:g[u]) if(cir[v]!=T){dfs(v);if(!col[u] && !col[v]) col[u]=col[v]=true,++ans;}}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;if(n&1){puts("-1");return 0;}
    for(int i=1,tt=0;i<=n;i++)
    {
        string s1,s2;cin>>s1>>s2;
        if(!mp.count(s1)) mp[s1]=++tt;
        if(!mp.count(s2)) mp[s2]=++tt;
        int u=mp[s1],v=mp[s2];
        if(fa[u]){puts("-1");return 0;}
        fa[u]=v;g[v].push_back(u);
    }
    for(int i=1;i<=n;i++) if(!fa[i]){puts("-1");return 0;}
    for(int i=1;i<=n;i++) if(!vis[i])
    {
        int u=i;
        ++T;for(;cir[u]!=T;u=fa[u]) cir[u]=T;
        vector<int>c;
        ++T;for(;cir[u]!=T;u=fa[u]) cir[u]=T,c.push_back(u);
        if(c.size()==2){col[c[0]]=col[c[1]]=true,ans+=2;}
        for(int v:c) dfs(v);
        if(c.size()<=2) continue;
        int w=u;
        for(int v:c) if(col[v]){w=v;continue;}
        for(int v=fa[w];v!=w;v=fa[v]) if(!col[v] && !col[fa[v]]) col[v]=col[fa[v]]=true,++ans;
    }
    cout<<n-ans;
    return 0;
}

B. Martian DNA

签到题，直接双指针扫过去即可。

复杂度 $O(n)$。

代码 
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
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 200010
using namespace std;
int res,a[N],d[N],c[N];
void add(int x){if((++c[x])==d[x]) ++res;}
void del(int x){if((c[x]--)==d[x]) --res;}
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1,x,y;i<=k;i++) scanf("%d%d",&x,&y),d[x]=y;
    int ans=n+1;res=m-k;
    for(int i=1,j=1;i<=n;i++)
    {
        while(j<=n && res!=m) add(a[j++]);
        if(res!=m) break;
        ans=min(ans,j-i);
        del(a[i]);
    }
    if(ans>n) puts("impossible");
    else printf("%d\n",ans);
    return 0;
}

C. Worm Worries

这道题本质上有三个子任务。

子任务 1 (subtask 1,2)

子任务 1 约束：$M = K = 1, N = 10^6, Q = 35$

显然有一个查询次数 $2\log_2 N$ 的做法：每次查询中点与其右边的点，舍去较小权值对应的一半序列。容易证明，较大权值的部分一定存在可行的峰值。

毛估估一下要 $40$ 次，恰好过不去。

考虑优化：上述做法每次要用 2 个询问，有点浪费。

事实上如果询问点在 $x,y$，有 $a_x<a_y$，那么 $[1,x]$ 部分同样可以舍掉。

事实上取 $x$ 为黄金分割点（大约为 $0.38$），每次将 $y$ 取另一黄金分割点，每次可以舍去 $\phi$ 的部分，询问次数为 $\log_{\phi}n$，算一下大概 $30$ 次，可以通过。

子任务 2 (subtask 3,4)

子任务 2 约束：$K = 1, N=M=1000,Q=3500$

考虑每次取较长边的一半（不妨假设为横坐标），分成两段，找到其中的最大值，扩展最大值周围的格子。

容易证明，当前极值在右边，如果最终极值在左边，一定会有当前极值引出的一条路径穿过中间的查询点，那么一定会被更新最大值。所以如果已知的最大值（包括之前询问得到的）在右边，那么递归处理右边的格子，否则递归左边格子一定合法。

$$T(n)=T(\frac n2)+1.5n$$

毛估估一下可以通过。

子任务 3 (subtask 5,6)

subtask 5 可以用类似子任务 2 的方法处理。

子任务 3 约束：$N = M = K = 500, Q = 1.5\times 10^5$

考虑一种很自然的想法：每次随机 $\frac Q2$ 个点，取其中最大的点，贪心向其四周查找最大值并转移。

分析一下正确概率：

不妨考虑最坏情况，一次转移认为要 $6$ 次查询，那么要能在 $\frac Q2$ 步内到达极大值，初始点一定要在前 $\frac Q{12}$ 大的点中。成功概率为：

$$1-(1-\frac{Q}{12NMK})^{\frac Q2}$$

用 python 算一下大约是 $97.6%$。

事实上上述式子根本跑不满，如果认为一次转移期望 $3$ 次查询，就有 $99.94%$ 的正确率。事实上正确率比这个更高。

代码 
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<random>
#include<chrono>
#include<cmath>
using namespace std;
int qry(int x,int y,int z){printf("? %d %d %d\n",x,y,z);fflush(stdout);int r;scanf("%d",&r);return r;}
int n,m,k,Q;
mt19937 Rand(std::chrono::system_clock::now().time_since_epoch().count());
int range(int l,int r){return Rand()%(r-l+1)+l;}
namespace c1{
    const int N=1000010;
    int a[N],qt=0;
    int qry(int x){if(a[x]) return a[x];++qt;int r=0;printf("? %d 1 1\n",x);fflush(stdout);scanf("%d",&r);return a[x]=r;}
    int getl(int l,int r){return l+(r-l+1)*0.38;}
    int getr(int l,int r){return r-(r-l+1)*0.38;}
    void solve(int l,int r,int p=0)
    {
        if(l==r){printf("! %d 1 1\n",l);cerr<<qt<<endl;fflush(stdout);exit(0);}
        if(r-l<=5)
        {
            int mid=(l+r)>>1;
            if(qry(mid)>qry(mid+1)) solve(l,mid);
            else solve(mid+1,r);
        }
        if(!p) p=getl(l,r);
        int mid=(l+r)>>1,u=0;
        if(p>=mid) u=getr(l,p);
        else u=getl(p,r),swap(u,p);
        if(qry(u)<qry(p)) solve(u+1,r,p);
        else solve(l,p-1,u);
    }
}
// int a[110][110];
namespace c2{
    const int N=1010;
    #define MP make_pair
    int mp[N][N],mx,my;
    void upd(int x,int y)
    {
        if(mp[x][y]<=mp[mx][my]) return;
        mx=x,my=y;
    }
    int qry(int x,int y)
    {
        if(x<=0 || y<=0 || x>n || y>m) return 0;
        if(mp[x][y]) return mp[x][y];
        int r=0;
        printf("? %d %d 1\n",x,y);fflush(stdout);scanf("%d",&r);
        // printf("%d\n",r);
        mp[x][y]=r;
        upd(x,y);
        return r;
    }
    int answer(int x,int y)
    {
        printf("! %d %d 1\n",x,y);
        cerr<<mx<<" "<<my<<endl;
        cerr<<x<<" "<<y<<endl;
        if(mx!=x || my!=y) throw;
        fflush(stdout);exit(0);
    }
    void solve(int xl,int xr,int yl,int yr)
    {
        if(xl==xr && yl==yr) answer(xl,yl);
        if(xr-xl>=yr-yl)
        {
            int xm=(xl+xr)>>1;
            int mw=0,p=0;
            for(int i=yl;i<=yr;i++)
            {
                int w=qry(xm,i);
                if(w>mw) mw=w,p=i;
            }
            qry(xm+1,p);qry(xm-1,p);
            if(mx==xm) answer(xm,p);
            if(mx>xm) solve(xm+1,xr,yl,yr);
            else solve(xl,xm-1,yl,yr);
        }
        else
        {
            int ym=(yl+yr)>>1;
            int mw=0,p=0;
            for(int i=xl;i<=xr;i++)
            {
                int w=qry(i,ym);
                if(w>mw) mw=w,p=i;
            }
            qry(p,ym+1);qry(p,ym-1);
            if(my==ym) answer(p,ym);
            if(my>ym) solve(xl,xr,ym+1,yr);
            else solve(xl,xr,yl,ym-1);
        }
    }
}
namespace c3{
    const int N=110;
    int mp[N][N][N],mx,my,mz;
    void upd(int x,int y,int z)
    {
        if(mp[x][y][z]<=mp[mx][my][mz]) return;
        mx=x,my=y,mz=z;
    }
    int qry(int x,int y,int z)
    {
        if(x<=0 || y<=0 || z<=0 || x>n || y>m || z>k) return 0;
        if(mp[x][y][z]) return mp[x][y][z];
        int r=0;
        printf("? %d %d %d\n",x,y,z);fflush(stdout);scanf("%d",&r);
        // printf("%d\n",r);
        mp[x][y][z]=r;
        upd(x,y,z);
        return r;
    }
    int answer(int x,int y,int z)
    {
        printf("! %d %d %d\n",x,y,z);
        fflush(stdout);exit(0);
    }
    void solve(int xl,int xr,int yl,int yr,int zl,int zr)
    {
        if(xl==xr && yl==yr && zl==zr) answer(xl,yl,zl);
        if(xr-xl>=yr-yl && xr-xl>=zr-zl)
        {
            int xm=(xl+xr)>>1;
            int mw=0,py=0,pz=0;
            for(int i=yl;i<=yr;i++)
                for(int j=zl;j<=zr;j++)
                {
                    int w=qry(xm,i,j);
                    if(w>mw) mw=w,py=i,pz=j;
                }
            qry(xm+1,py,pz);qry(xm-1,py,pz);
            if(mx==xm) answer(xm,py,pz);
            if(mx>xm) solve(xm+1,xr,yl,yr,zl,zr);
            else solve(xl,xm-1,yl,yr,zl,zr);
        }
        else if(yr-yl>=xr-xl && yr-yl>=zr-zl)
        {
            int ym=(yl+yr)>>1;
            int mw=0,px=0,pz=0;
            for(int i=xl;i<=xr;i++)
                for(int j=zl;j<=zr;j++)
                {
                    int w=qry(i,ym,j);
                    if(w>mw) mw=w,px=i,pz=j;
                }
            qry(px,ym+1,pz);qry(px,ym-1,pz);
            if(my==ym) answer(px,ym,pz);
            if(my>ym) solve(xl,xr,ym+1,yr,zl,zr);
            else solve(xl,xr,yl,ym-1,zl,zr);
        }
        else
        {
            int zm=(zl+zr)>>1;
            int mw=0,px=0,py=0;
            for(int i=xl;i<=xr;i++)
                for(int j=yl;j<=yr;j++)
                {
                    int w=qry(i,j,zm);
                    if(w>mw) mw=w,px=i,py=j;
                }
            qry(px,py,zm+1);qry(px,py,zm-1);
            if(mz==zm) answer(px,py,zm);
            if(mz>zm) solve(xl,xr,yl,yr,zm+1,zr);
            else solve(xl,xr,yl,yr,zl,zm-1);
        }
    }
}
namespace all{
    struct node{
        int x,y,z;
        node(int X=0,int Y=0,int Z=0):x(X),y(Y),z(Z){}
        bool operator <(const node a)const{return x==a.x?(y==a.y?z<a.z:y<a.y):x<a.x;}
    };
    const int N=1010;
    map<node,int>mp;
    int mx,my,mz;
    void upd(int x,int y,int z)
    {
        if(mp[node(x,y,z)]<=mp[node(mx,my,mz)]) return;
        mx=x,my=y,mz=z;
    }
    int answer(int x,int y,int z)
    {
        printf("! %d %d %d\n",x,y,z);
        fflush(stdout);exit(0);
    }
    int qry(int x,int y,int z)
    {
        if(x<=0 || y<=0 || z<=0 || x>n || y>m || z>k) return 0;
        if(mp[node(x,y,z)]) return mp[node(x,y,z)];
        int r=0;
        printf("? %d %d %d\n",x,y,z);fflush(stdout);scanf("%d",&r);
        // printf("%d\n",r);
        mp[node(x,y,z)]=r;
        upd(x,y,z);
        return r;
    }
    void init()
    {
        int t=Q/2;
        while(t --> 0)
        {
            int x=range(1,n),y=range(1,m),z=range(1,k);
            qry(x,y,z);Q--;
        }
    }
    node find_bigger(node a)
    {
        int t=qry(a.x,a.y,a.z);
        if(qry(a.x+1,a.y,a.z)>t) return node(a.x+1,a.y,a.z);
        if(qry(a.x,a.y+1,a.z)>t) return node(a.x,a.y+1,a.z);
        if(qry(a.x,a.y,a.z+1)>t) return node(a.x,a.y,a.z+1);
        if(qry(a.x-1,a.y,a.z)>t) return node(a.x-1,a.y,a.z);
        if(qry(a.x,a.y-1,a.z)>t) return node(a.x,a.y-1,a.z);
        if(qry(a.x,a.y,a.z-1)>t) return node(a.x,a.y,a.z-1);
        answer(a.x,a.y,a.z);exit(0);
    }
    void solve()
    {
        init();
        node a(mx,my,mz);
        while(true) a=find_bigger(a);
    }
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&k,&Q);
    if(m==1 && k==1) c1::solve(1,n);
    if(k==1) c2::solve(1,n,1,m);
    // c3::solve(1,n,1,m,1,k);
    all::solve();
    return 0;
}

E. Genetics

首先显然有一个 $O(\frac{n^3}{\omega})$ 的做法，卡一卡常在 LOJ 上能过。这里考虑一个高明的 $O(n^2)$ 做法：

定义每个字符串长度为 $m$。

如果我们定义第 $i$ 个字符串价值是 $m^i$，定义 $f(i,j)$ 表示第 $i$ 个字符串与第 $j$ 个字符串不同字符个数乘上 $m^j$，要对于每个 $i$ 求 $g_i=\sum f(i,j)$。显然只要对每个位置的某个字符统计贡献即可 $O(n)$ 计算。

可以发现 $g_i=k\sum_{j\neq i}m^j$ 当且仅当字符串 $i$ 是要找的那个串。

事实上并不需要权值为 $m^i$，只需要钦定一个随机价值即可。可以证明上述做法在 long long 范围内随机的错误概率大约是 $2^{-50}$。

代码 
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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<algorithm>
#include<chrono>
#include<random>
#include<cmath>
#define N 4100
#define ll long long
using namespace std;
char s[N][N];
int pos(char c){return c=='A'?0:(c=='C'?1:(c=='G'?2:3));}
mt19937 Rand(std::chrono::system_clock::now().time_since_epoch().count());
ll p[N],f[N][4];
int main()
{
    int n,m,k;scanf("%d%d%d",&n,&m,&k);
    bool only=true;ll sum=0;
    for(int i=0;i<n;i++)
    {
        scanf("%s",s[i]),p[i]=Rand(),sum+=p[i];
        for(int j=0;j<m;j++) f[j][pos(s[i][j])]-=p[i];
    }
    for(int i=0;i<m;i++) for(int j=0;j<4;j++) f[i][j]+=sum;
    for(int i=0;i<n;i++)
    {
        ll res=0;for(int j=0;j<m;j++) res+=f[j][pos(s[i][j])];
        if(res==k*(sum-p[i])){printf("%d\n",i+1);return 0;}
    }
    return 0;
}

F. Paths

签到题。

令 $f_{i,S}$ 表示到点 $i$，其中 $S$ 子集的颜色已经走过的方案数。直接 dp 即可。复杂度 $O(m2^k)$。

代码 
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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define N 300010
#define ll long long
#define M 5
using namespace std;
int col[N];
vector<int>g[N];
ll f[N][1<<M];
int main()
{
    int n,m,k;scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++) scanf("%d",&col[i]),col[i]--;
    for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),g[u].push_back(v),g[v].push_back(u);
    for(int i=1;i<=n;i++) f[i][1<<col[i]]=1;
    ll ans=0;
    for(int s=1;s<1<<k;s++)
    {
        for(int u=1;u<=n;u++) if(f[u][s])
            for(int v:g[u]) if(!(s>>col[v]&1)) f[v][s^(1<<col[v])]+=f[u][s];
    }
    for(int u=1;u<=n;u++)
        for(int s=1;s<1<<k;s++) ans+=f[u][s];
    printf("%lld\n",ans-n);
    return 0;
}