省赛顺利闭幕，榜单和题目在这里，简要发一下题解吧。

前四题出题人只给了简要题解╮(╯_╰)╭

有同学要的A题的标程：

A.Rui and her cylinders

可以使用各种办法来做这道题，包括模拟退火，三分等。需要注意到两个在圆柱侧面的点的最短路可能经过底面。

B.Rui and her functions

主要x的单调性，可以问题进行整体的分治。

C.Rui and her sequences

注意到操作1是没有意义的，因为操作1结束后，局部来说需要用最多次数的操作2才能实现目标，这一定是比只考虑操作2要更劣的。

修改题面之后删除条件1

D.Rui and her triangles

对于任意一对点a,b，假设它们的木棍长度是x,y(x>y)，如果第三边的长度在(x-y,x+y)内就可以组成三角形。于是用cnt[i][j]表示子树i中有多少对木棍满足“与长度为j的木棍可以组成三角形”。那么对所有的点对a,b，设a和b的lca是c，给cnt[c][]的(x-y,x+y)一段加1。然后按各个子树对cnt求和。那么一个子树i中的三角形总数就等于sigma cnt[i][j]，对子树i中所有的木棍长度j。再减去包含重复木棍的三角形，这个也可以用类似的方法算出。

E.HE

题目本身没啥好说的了，关于几个坑点其实已经在题目原本的描述中和样例数据中给的非常详细了。

赛中评测出来的大部分情况是行末空格和多余的空行（包括最末尾的空行）没有处理。

这里把数据都贴出来，大家自己回去试试就明白了。

  • Input
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
1341242 /* --- */23424242
/*--------------------------------*- C++ -*----------------------------------*\
| =========                 |                                                 |
| \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox           |
|  \\    /   O peration     | Version:  3.0.1                                 |
|   \\  /    A nd           | Web:      www.OpenFOAM.org                      |
|    \\/     M anipulation  |                                                 |
\*---------------------------------------------------------------------------*/
FoamFile
{
    version     2.0;
    format      ascii;
    class       dictionary;
    note        "mesh decomposition control dictionary";
    object      decomposeParDict;
}
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
numberOfSubdomains  2;
//- Keep owner and neighbour on same processor for faces in zones:
// preserveFaceZones (heater solid1 solid3);
//- Keep owner and neighbour on same processor for faces in patches:
//  (makes sense only for cyclic patches)
//preservePatches (cyclic_half0 cyclic_half1);
//- Keep all of faceSet on a single processor. This puts all cells
//  connected with a point, edge or face on the same processor.
//  (just having face connected cells might not guarantee a balanced
//  decomposition)
// The processor can be -1 (the decompositionMethod chooses the processor
// for a good load balance) or explicitly provided (upsets balance).
//singleProcessorFaceSets ((f0 -1));
//- Keep owner and neighbour of baffles on same processor (i.e. keep it
//  detectable as a baffle). Baffles are two boundary face sharing the
//  same points.
//preserveBaffles true;
//- Use the volScalarField named here as a weight for each cell in the
//  decomposition.  For example, use a particle population field to decompose
//  for a balanced number of particles in a lagrangian simulation.
// weightField dsmcRhoNMean;
method          scotch;
//method          hierarchical;
// method          simple;
// method          metis;
// method          manual;
// method          multiLevel;
// method          structured;  // does 2D decomposition of structured mesh
multiLevelCoeffs
{
    // Decomposition methods to apply in turn. This is like hierarchical but
    // fully general - every method can be used at every level.
    level0
    {
        numberOfSubdomains  64;
        //method simple;
        //simpleCoeffs
        //{
        //    n           (2 1 1);
        //    delta       0.001;
        //}
        method scotch;
    }
    level1
    {
        numberOfSubdomains  4;
        method scotch;
    }
}
// Desired output
simpleCoeffs
{
    n           (2 1 1);
    delta       0.001;
}
hierarchicalCoeffs
{
    n           (1 2 1);
    delta       0.001;
    order       xyz;
}
metisCoeffs
{
 /*
    processorWeights
    (
        1
        1
        1
        1
    );
  */
}
scotchCoeffs
{
    //processorWeights
    //(
    //    1
    //    1
    //    1
    //    1
    //);
    //writeGraph  true;
    //strategy "b";
}
manualCoeffs
{
    dataFile    "decompositionData";
}
structuredCoeffs
{
    // Patches to do 2D decomposition on. Structured mesh only; cells have
    // to be in 'columns' on top of patches.
    patches     (movingWall);
    // Method to use on the 2D subset
    method      scotch;
}
//// Is the case distributed? Note: command-line argument -roots takes
//// precedence
//distributed     yes;
//// Per slave (so nProcs-1 entries) the directory above the case.
//roots
//(
//    "/tmp"
//    "/tmp"
//);
// ************************************************************************* //
int main()
{
    return 0;
}
int main()
{
    //
}
#include<stdio.h>
//test
int main()
{
    printf("Helloworld.");
    return 0;
}
#include<stdio.h>
// test
int main()
{
    // test
    printf("Helloworld.");
    return 0;
}
       /*/
       jgjhhj
       /*/
#include<iostream>
int main()
{
    return 0;// end
}
/* ***********************************************
MYID    : Chen Fan
LANG    : G++
PROG    : Bitset
************************************************ */
#include <iostream>
#include <cstdio>
#include <bitset>
using namespace std;
int main()
{
    bitset<1000> a;
    a[100]=1;   //
    cout << a.count() << endl;  //
    cout << a.size() << endl;   //
    cout << a.test(1) << endl;
    cout << a.test(100) << endl;    //
    cout << a.any() << endl;    //
    cout << a.none() << endl;   //
    cout << a.all() << endl;    //
    a.set(2);   //
    cout << a[2] << endl;   //
    a.reset();  //
    cout << a.count() << endl;
    cout << a.none() << endl;
    a.flip();   //
    cout << a.count() << endl;
    cout << a.all() << endl;/* --- */
}

#include<stdio.h>
//test
int main()
{
    printf("Helloworld.");
    return 0;
}
#include<stdio.h>
/* ----
---- */

int main()
{
    // test
    printf("Helloworld.");     // test
    return 0;   /* -- */
}
  • Output
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
1341242 23424242
FoamFile
{
    version     2.0;
    format      ascii;
    class       dictionary;
    note        "mesh decomposition control dictionary";
    object      decomposeParDict;
}
numberOfSubdomains  2;
method          scotch;
multiLevelCoeffs
{
    level0
    {
        numberOfSubdomains  64;
        method scotch;
    }
    level1
    {
        numberOfSubdomains  4;
        method scotch;
    }
}
simpleCoeffs
{
    n           (2 1 1);
    delta       0.001;
}
hierarchicalCoeffs
{
    n           (1 2 1);
    delta       0.001;
    order       xyz;
}
metisCoeffs
{
}
scotchCoeffs
{
}
manualCoeffs
{
    dataFile    "decompositionData";
}
structuredCoeffs
{
    patches     (movingWall);
    method      scotch;
}
int main()
{
    return 0;
}
int main()
{
}
#include<stdio.h>
int main()
{
    printf("Helloworld.");
    return 0;
}
#include<stdio.h>
int main()
{
    printf("Helloworld.");
    return 0;
}
#include<iostream>
int main()
{
    return 0;
}
#include <iostream>
#include <cstdio>
#include <bitset>
using namespace std;
int main()
{
    bitset<1000> a;
    a[100]=1;
    cout << a.count() << endl;
    cout << a.size() << endl;
    cout << a.test(1) << endl;
    cout << a.test(100) << endl;
    cout << a.any() << endl;
    cout << a.none() << endl;
    cout << a.all() << endl;
    a.set(2);
    cout << a[2] << endl;
    a.reset();
    cout << a.count() << endl;
    cout << a.none() << endl;
    a.flip();
    cout << a.count() << endl;
    cout << a.all() << endl;
}
#include<stdio.h>
int main()
{
    printf("Helloworld.");
    return 0;
}
#include<stdio.h>
int main()
{
    printf("Helloworld.");
    return 0;
}

F.Go

签到题，前面2页都是废话，只要对比每次19*19方格中0和1的个数即可。

G.CountingStar

大意是给出一个(n+1)(n+1)的数字方阵，然后针对多个顶点，询问该顶点与(0,0)点以及*该顶点在x轴上的投影点所围成的三角形内区域的数字和。

事实上这题的出题思路来自于2014年北京regional网赛的一题

正解的思路是：

二维转一维：将最大1000*1000个点按照斜率排序，对于每次的询问也是按照斜率排序。

之后想象有一根轴，从x轴的0°角开始逆时针扫整个平面，将扫到的点按照x坐标加入树状数组。如果扫到与一条询问线重合时，则对该次询问求sum(x)。这样就能避免了重复操作。把结果按照原始顺序重新输出即可。

不太理解的同学可以画图看一下。

赛中事实上这题的数据较弱，有的同学维护前缀和暴力搞一搞也都过了。

H.LaserCannon

这题是个非常简单的DP，赛中没有人出真是让我好伤心……

题目大意是：平面上有若干个带权点，用倾斜角为$\alpha$的直线将其分为若干部分，每部分可以得到一 个分值，求一个最大得分。

对于$\alpha$为0或90度的情况进行特判，当斜率为任意值时，可以计算出过每个点的斜角为$\alpha$的直线与y轴的交点，并按照这个交点的y坐标d进行排序。其计算公式为：$d = y – k * x$。

这样就把二维的面问题简化成一维了有木有！！！！！！！

然后很容易就能写出DP方程：

本来这里还准备设置一个坑点的，即：同一条直线上的点是不能被分成2个部分分开打掉的，而数据完全有可能出成分开更优的情况，若是不考虑这点的话也会WA。只是最后我出数据的时候没有把这个部分加上去。

然而比赛时没有人做╮(╯_╰)╭

I.MarsCity

本题是一个裸的最小树形图。

首先构建图，即生成从高建筑到不高于该建筑的其他建筑的有向边。高度最高的建筑就是树形图的中心点，若存在多个相同高度的最高建筑，则需要另外设置一个虚拟的根，从虚拟根向所有最高建筑连有向边，边长设置一个特别大的值即可，最后结束时减掉。

出于省赛难度考虑，本题数据也非常弱。有同学可能担心朱刘算法复杂度不够，事实上标程就是个裸的朱刘算法╮(╯_╰)╭

J.MagicNum

数位DP。

其实也没啥可说的，这里给出标程中用的状态吧：

dp[i][j][k][p][l][x]

i：第i位；

j：是否比原数字大，0表示小，1表示等，2表示大；

k：mod7的余数；

p：上一位是否是8；

l：这一位是不是0；

x：是否包含2、3、5

K.Skill

艾教的题解：

非常简单的模拟题，涉及一点点数学知识。

首先考虑最高位是不是1，如果最高位是1，那么满足题目要求的情况有:

C(K-1,P-1)*(N-1)^(N-K)种。

如果这个数字>=X,说明答案的首位是1，否则答案的首位不是1，X减去这个数字，再来考虑2即可。

时间复杂度O(K)，空间复杂度O(1)。

后话

在知乎上发现一个问题：

看到大家的评价还都不错我们筹办方也就放心啦~

前四题的详细题解我们会再找出题人要一下，是在有疑问的可以找艾教讨论，最后2题也是艾教的题。

然后中间的E到I是本人出的题，若有疑问可以再与我交流。

—-Jcf