Round 2的题目总体而言较难，对有基础的学生区分度较好。
题目难度系数：
- A : 3
- B : 2
- C : 4
- D : 5
- E : 4
- F : 5
- G : 1
A.跳格子
题目分析
建完图跑最小生成树即可。
代码
Prim1
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
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=50005;
struct Edge {int from,to,dist;};
struct HeapNode {
int d,u;
bool operator < (HeapNode a) const {return d>a.d;}
};
struct Prim {
int n,ans,dist[maxn];
vector<Edge> edges;
vector<int> G[maxn];
bool vst[maxn];
void init(int n) {this->n=n;}
void AddEdge(int from,int to,int dist) {
edges.push_back((Edge) {from,to,dist});
int m=edges.size();
G[from].push_back(m-1);
}
int main(int s) {
for(int i=1; i<=n; i++)dist[i]=INT_MAX;
priority_queue<HeapNode> Q;
Q.push((HeapNode) {
0,s
});
dist[s]=0;
while(!Q.empty()) {
HeapNode Now=Q.top();
Q.pop();
if(vst[Now.u])continue;
vst[Now.u]=1;
ans+=dist[Now.u];
for(int id:G[Now.u]) {
Edge& e=edges[id];
int Next=e.to,v=e.dist;
if(!vst[Next]&&v<dist[Next]) {
dist[Next]=v;
Q.push((HeapNode) {
dist[Next],Next
});
}
}
}
return ans;
}
} prim;
int n,m,a[205][205];
int id(int x,int y) {return (x-1)*m+y;}
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)a[i][j]=Get_Int();
prim.init(n*m);
for(int i=1; i<n; i++)
for(int j=1; j<=m; j++) {
prim.AddEdge(id(i,j),id(i+1,j),-a[i][j]*a[i+1][j]);
prim.AddEdge(id(i+1,j),id(i,j),-a[i][j]*a[i+1][j]);
}
for(int j=1; j<m; j++)
for(int i=1; i<=n; i++) {
prim.AddEdge(id(i,j),id(i,j+1),-a[i][j]*a[i][j+1]);
prim.AddEdge(id(i,j+1),id(i,j),-a[i][j]*a[i][j+1]);
}
printf("%d\n",-prim.main(1));
return 0;
}
Kruskal1
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
using namespace std;
int a[205][205];
int n,m;
int id(int x,int y) {
return (x - 1) * m + y - 1;
}
struct edge {
int u,v,w;
friend bool operator < (const edge &x,const edge &y) {
return x.w > y.w;
}
}e[2*205*205];
struct unionset {
int f[205*205];
unionset() {
for (int i=0;i<205*205;i++) f[i] = i;
}
int find(int x) {
if (f[x] == x) return x;
else return f[x] = find(f[x]);
}
void uni(int x,int y) {
f[find(x)] = find(y);
}
bool check(int x,int y) {
return find(x) == find(y);
}
}us;
int ecnt;
int main() {
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) scanf("%d",&a[i][j]);
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) {
if (i != n) e[ecnt++] = (edge){id(i,j),id(i+1,j),a[i][j]*a[i+1][j]};
if (j != m) e[ecnt++] = (edge){id(i,j),id(i,j+1),a[i][j]*a[i][j+1]};
}
sort(e,e+ecnt);
int cnt = 0;
int ans = 0;
for (int i=0;i<ecnt && cnt < n*m;i++) {
if (!us.check(e[i].u,e[i].v)) {
us.uni(e[i].u,e[i].v);
cnt ++;
ans += e[i].w;
}
}
printf("%d\n",ans);
return 0;
}
B.串串游戏
题目分析
一个简单的博弈论问题。
使用必胜必败态转移关系进行递推即可：
- 一个状态是必胜态当且仅当其后继状态包含一个必败态
- 一个状态是必败态当且仅当其后继状态均为必胜态
代码
1 |
|
C.滑稽树
题目大意
求编号连续的区间的点在树上的最近公共祖先
题目分析
这道题有很多种做法。
首先需要敲一个LCA的板子，可以用倍增，可以用Dfs序。
如果用Dfs序，题目中有两种编号任意混淆，建议使用倍增。
第一种做法：线段树合并LCA
用线段树维护区间的LCA，因为LCA有可并性，因此可以这样做，询问时直接查询对应区间即可。
时间复杂度是$O(n\log^2 n+q\log^2n)$，另外还包含线段树的巨大常数，可能需要卡常才能通过。
第二种做法：Dfs序+RMQ+线段树
同样类似第一种做法，但使用Dfs序+RMQ来查询LCA，这样可以做到查询LCA只需要$O(1)$的时间。
然后建立线段树维护区间LCA，时间复杂度是$O(n\log n+q\log n)$。
第三种做法：Tarjan求LCA
没有深究
第四种做法：两次ST表+RMQ
首先求出编号为$i$和编号为$i+1$的LCA。
考虑，区间$[x,y]$的LCA一定在区间中$[i,i+1]$的LCA列表中。
然后建立第二个ST表，将区间中深度更小的那一个LCA保存下来，使用RMQ回答询问。
时间复杂度是$O(n\log n+q)$
代码
第一种做法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
using namespace std;
int q,l,r,x,y,k,ss[ni];
int vis[ni],f[ni][35],fi[ni],p,n,a,b,deep[ni],s;
struct
{
int l,r;
int dat;
}t[1000000];
struct
{
int next,to;
}w[ni];
int read()
{
int xx=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
{
xx=xx*10+ch-'0';ch=getchar();
}
return xx;
}
void jiabian(int x,int y)
{
w[++p].next=fi[x];
w[p].to=y;
fi[x]=p;
}
void dfs(int u)
{ vis[u]=1;
for (int i=fi[u];i;i=w[i].next)
if(!vis[w[i].to])
{
f[w[i].to][0]=u;
deep[w[i].to]=deep[u]+1;
dfs(w[i].to);
}
}
int lca(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y);
for(int i=31;i>=0;i--)
if(deep[f[x][i]]>=deep[y])
x=f[x][i];
if(x==y) return x;
for(int i=30;i>=0;i--)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
void bulid(int p,int l,int r)
{
t[p].l=l;t[p].r=r;
if(l==r) {
t[p].dat=l;return;
}
int mid=(l+r)>>1;
bulid(p*2,l,mid);
bulid(p*2+1,mid+1,r);
t[p].dat=lca(t[p*2].dat,t[p*2+1].dat);
}
void ask(int p,int l,int r)
{
if(l<=t[p].l&&r>=t[p].r)
{
ss[++k]=t[p].dat;
return;
}
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid) ask(p*2,l,r);
if(r>mid) ask(p*2+1,l,r);
}
int main()
{ // freopen("st.in","r",stdin);
// freopen("st.out","w",stdout);
n=read();
for(int i=1;i<=n-1;i++)
{ x=read();y=read();
jiabian(x,y);
jiabian(y,x);
}
deep[1]=1;
dfs(1);
for(int j=1;j<=30;j++)
for(int i=1;i<=n;i++)
f[i][j]=f[f[i][j-1]][j-1];
bulid(1,1,n);
cin>>q;
for(int i=1;i<=q;i++)
{
l=read();r=read();
k=0;ask(1,l,r);
int ak=ss[1];
for(int j=2;j<=k;j++)
ak=lca(ak,ss[j]);
printf("%d\n",ak);
}
return 0;
}
第二种做法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
using namespace std;
const int maxn = 2e5 + 5 + 5;
struct edge {
int v,next;
}e[2*maxn];
int ecnt;
int head[maxn];
inline void AddEdge(int u,int v) {
e[ecnt].v = v;
e[ecnt].next = head[u];
head[u] = ecnt;
ecnt ++;
}
bool vis[2*maxn];
int depth[2*maxn];
int node[2*maxn];
int first[maxn];
int t = 0;
int st[2*maxn][20];
inline int pow2(int n) {
return 1 << n;
}
void init_RMQ(int range){
for (int i=0;i<=range;i++) st[i][0] = i;
for (int j=1;pow2(j)<=range;j++) {
for (int i=0;i+pow2(j)-1<range;i++) {
int l = st[i][j-1];
int r = st[i+pow2(j-1)][j-1];
st[i][j] = depth[l] < depth[r] ? l : r;
}
}
}
inline int RMQ(int u,int v) {//返回位置
if (u > v) swap(u,v);
int k = log(v-u+1) / log(2);
int l = st[u][k];
int r = st[v-pow2(k)+1][k];
return depth[l] < depth[r] ? l : r;
}
inline int LCA(int u,int v) {
return node[RMQ(first[u],first[v])];
}
void DFS(int u,int d) {
node[t] = u;
depth[t] = d;
first[u] = t;
t++;
vis[u] = true;
for (int i=head[u];~i;i=e[i].next) {
int v = e[i].v;
if (!vis[v]) {
DFS(v,d+1);
node[t] = u;
depth[t] = d;
t++;
}
}
}
namespace Seg {
//两倍空间公式 {
//两倍空间公式 }
int lca[maxn*2];
void build(int l,int r) {
if (l == r) {
lca[node] = l;
}
else {
build(l,mid);
build(mid+1,r);
lca[node] = LCA(lca[lson],lca[rson]);
}
}
int query(int l,int r,int L,int R) {
if (L <= l && r <= R) {
return lca[node];
}
else {
if (R <= mid) return query(l,mid,L,R);
if (L > mid) return query(mid+1,r,L,R);
return LCA(query(l,mid,L,R),query(mid+1,r,L,R));
}
}
};
int main() {
int n;
scanf("%d",&n);
memset(head,-1,sizeof(head));
for (int i=1;i<n;i++) {
int u,v;
scanf("%d%d",&u,&v);
AddEdge(u,v);
AddEdge(v,u);
}
DFS(1,0);
init_RMQ(t);
Seg::build(1,n);
int m;
scanf("%d",&m);
while (m --) {
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",Seg::query(1,n,l,r));
}
return 0;
}
第四种做法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
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=300005;
int n,q,p[maxn][35],f[maxn][35],a[maxn],father[maxn],Depth[maxn];
vector<int>edges[maxn];
void AddEdge(int x,int y) {edges[x].push_back(y);}
void Sparse_Table() {
for(int i=1; i<=n; i++)
for(int j=0; j<=log2(n); j++)p[i][j]=-1;
for(int i=1; i<=n; i++)p[i][0]=father[i];
for(int j=1; j<=log2(n); j++)
for(int i=1; i<=n; i++)
if(p[i][j-1]!=-1)p[i][j]=p[p[i][j-1]][j-1];
}
int LCA(int a,int b) {
if(Depth[a]<Depth[b])swap(a,b);
int k=log2(Depth[a]);
for(int i=k; i>=0; i--) {
if(Depth[a]==Depth[b])break;
if(Depth[a]-(1<<i)>=Depth[b])a=p[a][i];
}
if(a==b)return b;
for(int i=k; i>=0; i--)
if(p[a][i]!=-1&&p[a][i]!=p[b][i]) {
a=p[a][i];
b=p[b][i];
}
return p[a][0];
}
void Dfs(int Now,int depth) {
Depth[Now]=depth;
for(int i=0; i<edges[Now].size(); i++) {
int Next=edges[Now][i];
if(Next==father[Now])continue;
father[Next]=Now;
Dfs(Next,depth+1);
}
}
void Sparse_Table2() {
for(int i=1; i<n; i++)f[i][0]=a[i];
for(int j=1; (1<<j)<n; j++)
for(int i=1; i+(1<<j)-1<n; i++) {
int L=f[i][j-1],R=f[i+(1<<(j-1))][j-1];
if(Depth[L]<Depth[R])f[i][j]=L;
else f[i][j]=R;
}
}
int Query(int Left,int Right) {
int x=log2(Right-Left+1);
int L=f[Left][x],R=f[Right-(1<<x)+1][x];
if(Depth[L]<Depth[R])return L;
else return R;
}
int main() {
n=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
}
father[1]=-1;
Dfs(1,1);
Sparse_Table();
for(int i=1; i<n; i++)a[i]=LCA(i,i+1);
Sparse_Table2();
q=Get_Int();
for(int i=1; i<=q; i++) {
int x=Get_Int(),y=Get_Int();
if(x==y)printf("%d\n",x);
else printf("%d\n",Query(x,y-1));
}
return 0;
}
D.cyy玩牌牌
题目大意
cyy打牌有个习惯，他很喜欢打顺子。
顺子的定义是，3至5张序号连续且不重复的扑克牌。
现在他有了一堆扑克牌，他想考考你，是否存在一种方案，在只打顺子的情况下，能把这些牌打完？
题目分析
首先需要注意到的是，$5$张以上的顺子都可以由$3,4,5$组成，所以对于顺子只需要要求它的长度大于$3$即可。
考虑差分，将区间减法转化为左端点减法与右端点加法。
差分后问题转化为正数与负数的匹配，利用左端点减一个数，右端点加同样的数，将差分序列全部变为$0$。
可以做一个匹配，但是写起来很复杂，可以乱搞一下简化代码。
代码
1 |
|
E.ytrsk的键盘
题目分析
显然，每一个键位只对应一个字符。
首先，搜索是阶乘级别的，显然是不可能的。
动规？在确定一个位置后是有后效性的，无法划分阶段。
$1\le m\le20$，这一个条件告诉我们，可以用二进制状态压缩来表示当前键盘按键的状态。
不妨考虑贡献，统计某个字符$i$下一个字符是$j$的总数，每一次确定一个键位，就增加这么多总数的贡献。这些贡献由所有已经确定了键位的字符到所有还没有确定键位的字符构成，每一个的贡献均为$1$。
这样计算贡献，与原题的绝对值之和等价。
因此设置状态$f(S)$表示键位确定状态为$S$时的贡献，枚举子集进行转移即可。
另外，由于状态的设置问题，统计相邻字符的时候下一个字符和上一个字符均需要统计。
详见代码1，时间复杂度为$O(2^m·m^2)$。
这个时间复杂度还可以进行优化，我们可以事先统计出$g(S,i)$表示$S$状态中的已确定字符与未确定字符$i$构成的贡献。
$g(S,i)$可以通过lowbit转移，从而将时间复杂度优化到$O(2^m·m)$。
代码
代码一1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
using namespace std;
int n,m,cnt[25][25],f[1<<20];
string s;
int main() {
ios::sync_with_stdio(false);
cin>>n>>m>>s;
for(int i=0; i<n-1; i++) {
cnt[s[i]-'a'][s[i+1]-'a']++;
cnt[s[i+1]-'a'][s[i]-'a']++;
}
for(int S=1; S<(1<<m); S++) {
f[S]=INT_MAX/2;
int sum=0;
for(int i=0; i<m; i++)
for(int j=i+1; j<m; j++)if(((S>>i)&1)^((S>>j)&1))sum+=cnt[i][j];
for(int i=0; i<m; i++)if((S>>i)&1)f[S]=min(f[S],f[S^(1<<i)]+sum);
}
printf("%d\n",f[(1<<m)-1]);
return 0;
}
优化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
using namespace std;
int n,m,cnt[20][20],f[1<<20],g[1<<20][20];
string s;
int main() {
ios::sync_with_stdio(false);
cin>>n>>m>>s;
for(int i=0; i<n-1; i++) {
cnt[s[i]-'a'][s[i+1]-'a']++;
cnt[s[i+1]-'a'][s[i]-'a']++;
}
for(int S=1; S<(1<<m); S++)
for(int i=0; i<m; i++)if(!((S>>i)&1))g[S][i]=g[S^lowbit(S)][i]+cnt[(int)log2(lowbit(S))][i];
for(int S=1; S<(1<<m); S++) {
f[S]=INT_MAX/2;
int sum=0;
for(int i=0; i<m; i++)if(!((S>>i)&1))sum+=g[S][i];
for(int i=0; i<m; i++)if((S>>i)&1)f[S]=min(f[S],f[S^(1<<i)]+sum);
}
printf("%d\n",f[(1<<m)-1]);
return 0;
}
F.小马过河
题目分析
这显然是一个动态规划，首先不考虑方案数。
设置状态$f(x,y,0/1)$表示，河对岸有$x$条50kg的马，有$y$条100kg的马，船在河对岸还是在当前位置，此时的最少乘船次数。
注意一下转移的条件，这个动规就完成了。
然而并没有结束，怎么统计方案数呢？
我们用$g(x,y,0/1)$来表示方案数。
首先如果$f$在转移时发生了更新，$g$也应该重新更新。
如果$f$在转移时数据相同，$g$应该累加。
除此之外，由于相同体重的马是不一样的（带有标号的），还需要乘上对应的组合数，预处理一下杨辉三角即可。
但是，这个动规的转移没有顺序性，不能使用递推来实现。
我们可以发现，虽然转移的阶段没有顺序性，但却有明显的层次，因此我们可以使用Bfs来转移动规，这也被称作记忆化搜索。（使用Dfs是错误的，想一想，为什么？）
代码
1 |
|
G.Accepted!
题目分析
签到题，没过的同学请扇自己一巴掌。
代码
1 |
|
