#include<bits/stdc++.h>usingnamespace std;constint maxn =2019;intcheck(int i){while(i){if(i %10==9)return1;
i /=10;}return0;}intmain(){int ans =0;for(int i =1; i <= maxn; i++)if(check(i))
ans++;printf("%d", ans);return0;}
第二行包含 n 个整数 a[1], a[2], …, a[n]，相邻的整数间用空格分隔，表示给定的数列。
输出格式
输出一行包含一个整数，表示答案。
样例输入 7
5 2 4 1 3 7 2
样例输出
3
评测用例规模与约定
对于 50% 的评测用例，2 <= n <= 100，0 <= 数列中的数 <= 1000。
对于所有评测用例，2 <= n <= 1000，0 <= 数列中的数 <= 10000。
题解
设定一个计数器并初始化为1，遍历序列，比较当前元素与下一个元素
若当前元素小于下一元素，则计数器加1，继续遍历。
若当前元素大于等于下一元素，则子序列不满足递增，使用当前计数器的值去维护答案，将计数器重置为1。
#include<bits/stdc++.h>usingnamespace std;constint maxn =1004;int a[maxn];intmain(){int n;
cin>>n;int ans =0, temp =0;for(int i =0; i < n; i++)scanf("%d",&a[i]);for(int i =0; i < n; i++){if(a[i+1]<= a[i]){if(temp > ans)
ans = temp;
temp =1;}else
temp++;}printf("%d", ans);return0;}
F. 元音字母
问题描述
输入格式
输入一行，包含一个单词，单词中只包含小写英文字母。
输出格式
输出一行包含一个字母，为单词中第一个出现的元素字母。若单词中不存在元音字母，输出字母n。
样例输入
hello
样例输出
e
样例输入
fly
样例输出
n
评测用例规模与约定
对于所有评测用例，单词中的字母个数不超过100。
题解
题目有误，输出格式说明 中的
为单词中第一个出现的元素字母
应改为
为单词中第一个出现的元音字母
直接遍历字符串，遇到元音字母直接返回该字母，若遍历到字符串结尾，返回字母 n。
#include<bits/stdc++.h>usingnamespace std;constint maxn =103;char s[maxn];charwork(){int len =strlen(s);for(int i =0; i < len; i++)switch(s[i]){case'a':return s[i];case'e':return s[i];case'i':return s[i];case'o':return s[i];case'u':return s[i];}return'n';}intmain(){
cin>>s;printf("%c",work());return0;}
G. 大写字母
问题描述
一般情况下，如果一个单词在段首，则第一个字母大写，后面的字母小写。 给定一个单词，单词中可能包含大小写字母，请按第一个字母大写，后面字母小写的方式输出。 输入格式 输入一行，包含一个单词，单词中只包含大写或小写英文字母。 输出格式 输出单词在段首时的形式，第一个字母大写，其他字母小写。 样例输入 LanQiao 样例输出 Lanqiao 样例输入 cUp 样例输出 Cup 评测用例规模与约定 对于所有评测用例，单词中的字母个数不超过100。
题解
直接遍历字符串
如果第一个字符不是大写，换成大写
除第一个字符以外，如果是大写，换成小写。
#include<bits/stdc++.h>usingnamespace std;constint maxn =103;char s[maxn];intmain(){
cin>>s;int len =strlen(s);for(int i =0; i < len; i++)if(i ==0){if(s[i]>='a'&& s[i]<='z')
s[i]+='A'-'a';}elseif(s[i]>='A'&& s[i]<='Z')
s[i]+='a'-'A';printf("%s", s);return0;}
H. 螺旋矩阵
问题描述
对于一个 n 行 m 列的表格，我们可以使用螺旋的方式给表格依次填上正整数，我们称填好的表格为一个螺旋矩阵。 例如，一个 4 行 5 列的螺旋矩阵如下： 1 2 3 4 5 14 15 16 17 6 13 20 19 18 7 12 11 10 9 8 输入格式 输入的第一行包含两个整数 n, m，分别表示螺旋矩阵的行数和列数。 第二行包含两个整数 r, c，表示要求的行号和列号。 输出格式 输出一个整数，表示螺旋矩阵中第 r 行第 c 列的元素的值。 样例输入 4 5 2 2 样例输出 15 评测用例规模与约定 对于 30% 的评测用例，2 <= n, m <= 20。 对于 70% 的评测用例，2 <= n, m <= 100。 对于所有评测用例，2 <= n, m <= 1000，1 <= r <= n，1 <= c <= m。
题解
观察样例得到，填数的策略是：
往一个方向不断填数，直到下一个位置超出边界或者已经填过数字，切换一个方向，继续填数；
方向选择的优先级是 右>下>左>上。
首先按优先级顺序书写好四条while语句，代表往四个方向填数。
while(y +1< m &&!a[x][y+1]) a[x][++y]=++tot;//rightwhile(x +1< n &&!a[x+1][y]) a[++x][y]=++tot;//downwhile(y -1>=0&&!a[x][y-1]) a[x][--y]=++tot;//leftwhile(x -1>=0&&!a[x-1][y]) a[--x][y]=++tot;//up
然后在外层判断是否已经填满整个矩阵。
#include<bits/stdc++.h>usingnamespace std;constint maxn =1004;int a[maxn][maxn];intmain(){int n, m;int r, c;
cin>>n>>m>>r>>c;int num = n * m;int x =0, y =0, tot =1;
a[x][y]=1;while(tot < num){while(y +1< m &&!a[x][y+1]) a[x][++y]=++tot;//rightwhile(x +1< n &&!a[x+1][y]) a[++x][y]=++tot;//downwhile(y -1>=0&&!a[x][y-1]) a[x][--y]=++tot;//leftwhile(x -1>=0&&!a[x-1][y]) a[--x][y]=++tot;//up}/*
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
printf("%4d", a[i][j]);
printf("\n");
}
*/printf("%d", a[r-1][c-1]);return0;}
U
P
D
{UPD}
UPD : 题解中的
x
,
y
{x,y}
x,y 在二维数组中的使用与坐标轴中是相反的，请读者注意甄别。
I. 长草
问题描述
问题描述
小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。 小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。 这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，这四小块空地都将变为有草的小块。 请告诉小明，k 个月后空地上哪些地方有草。 输入格式 输入的第一行包含两个整数 n, m。 接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 g，表示种了草。 接下来包含一个整数 k。 输出格式 输出 n 行，每行包含 m 个字母，表示 k 个月后空地的状态。如果为小数点，表示为空地，如果字母为 g，表示长了草。 样例输入 4 5 .g… … …g… … 2 样例输出 gggg. gggg. ggggg .ggg. 评测用例规模与约定 对于 30% 的评测用例，2 <= n, m <= 20。 对于 70% 的评测用例，2 <= n, m <= 100。 对于所有评测用例，2 <= n, m <= 1000，1 <= k <= 1000。
题解
70分做法：
遍历k次矩阵，在每一个当前是字符 g 的上下左右处做上标记，每次遍历结束后将标记处改为字符 g 即可。
篇幅受限，代码不再给出。时间复杂度为
Θ
(
4
k
n
m
)
{ \Theta { \left( {4knm} \right) }}
Θ(4knm)，可以通过70%的测评用例。
100分做法：
考虑BFS（广度优先遍历）做法。
首先构造一个结构体，其中有如下属性
某个坐标的x值
某个坐标的y值
该坐标长草的天数
队列的初始化方式是：遍历一次矩阵，将第0天就存在的草的坐标和天数0入队。
不断将队头出队，且将其对应的坐标处字符修改为 g，然后判断天数是否与k相等
若不相等，则将该坐标的上下左右坐标均入队，天数为队头天数+1；
若相等，代表该处的草已是第
k
{k}
k 月长出，什么也不做。
直到队列为空。
令图中初始的 g 数量为
c
{c}
c，则复杂度为
Θ
(
n
m
+
m
i
n
(
n
m
,
(
4
c
)
k
)
)
{ \Theta { \left( {nm+min{ \left( {nm,\mathop{{{ \left( {4c} \right) }}}\nolimits^{{k}}} \right) }} \right) }}
Θ(nm+min(nm,(4c)k))，可以通过所有测评用例。
#include<bits/stdc++.h>usingnamespace std;constint maxn =1004;char a[maxn][maxn];typedefstruct{int x;int y;int cnt;} Node;intmain(){int n, m;int k;
cin>>n>>m;for(int i =0; i < n; i++)
cin>>a[i];
cin>>k;
queue<Node> q;
Node temp;for(int i =0; i < n; i++)for(int j =0; j < m; j++)if(a[i][j]=='g'){
temp.x = i, temp.y = j, temp.cnt =0;
q.push(temp);}while(!q.empty()){
Node mod = q.front();
a[mod.x][mod.y]='g';
q.pop();if(mod.cnt != k){for(int x =-1; x <=1; x++)for(int y =-1; y <=1; y++)if(!x ||!y){
temp.x = mod.x + x, temp.y = mod.y + y, temp.cnt = mod.cnt +1;if(temp.x <0|| temp.x >= n || temp.y <0|| temp.y >= m)continue;
q.push(temp);}}}for(int i =0; i <= n; i++)puts(a[i]);return0;}
J. 选节目
问题描述
小明要组织一台晚会，总共准备了 n 个节目。然后晚会的时间有限，他只能最终选择其中的 m 个节目。 这 n 个节目是按照小明设想的顺序给定的，顺序不能改变。 小明发现，观众对于晚上的喜欢程度与前几个节目的好看程度有非常大的关系，他希望选出的第一个节目尽可能好看，在此前提下希望第二个节目尽可能好看，依次类推。 小明给每个节目定义了一个好看值，请你帮助小明选择出 m 个节目，满足他的要求。 输入格式 输入的第一行包含两个整数 n, m ，表示节目的数量和要选择的数量。 第二行包含 n 个整数，依次为每个节目的好看值。 输出格式 输出一行包含 m 个整数，为选出的节目的好看值。 样例输入 5 3 3 1 2 5 4 样例输出 3 5 4 样例说明 选择了第1, 4, 5个节目。 评测用例规模与约定 对于 30% 的评测用例，1 <= n <= 20； 对于 60% 的评测用例，1 <= n <= 100； 对于所有评测用例，1 <= n <= 100000，0 <= 节目的好看值 <= 100000。
题解
60分做法：
令每个节目的好看程度依次为
a
1
,
a
2
,
.
.
.
,
a
n
{\mathop{{a}}\nolimits_{{1}},\text{ }\mathop{{{a}}}\nolimits_{{2}},\text{ }...,\text{ }\mathop{{{a}}}\nolimits_{{n}}}
a1,a2,...,an ，余下还需要选择的节目数量为
c
{c}
c，则
c
=
m
{c = m}
c=m 时，在
a
1
,
a
2
,
.
.
.
,
a
n
−
c
{\mathop{{a}}\nolimits_{{1}},\text{ }\mathop{{{a}}}\nolimits_{{2}},\text{ }...,\text{ }\mathop{{{a}}}\nolimits_{{n-c}}}
a1,a2,...,an−c 中找到最大值作为第一个节目即可，并令
i
{i}
i = 最大值的下标；
c
<
m
{c < m}
c<m 时，依次在
a
i
,
a
i
+
1
,
.
.
.
,
a
n
−
c
{\mathop{{a}}\nolimits_{{i}},\text{ }\mathop{{{a}}}\nolimits_{{i+1}},\text{ }...,\text{ }\mathop{{{a}}}\nolimits_{{n-c}}}
ai,ai+1,...,an−c 中遍历找到最大值而后调整
i
,
c
{i, c}
i,c 的值即可。
直到
(
n
−
c
)
−
i
=
=
c
{(n-c)-i == c}
(n−c)−i==c 为止（即当剩余可选区间长度与还需选择的数量相等时）。
时间复杂度分析：
总的时间复杂度等于遍历区间的长度乘以遍历的区间个数。在最糟糕的情况下，需要遍历的区间个数与
m
{m}
m 相等，需要遍历的区间长度为
n
−
m
{n-m}
n−m ，即
O
(
m
(
n
−
m
)
)
{ {\rm O} { \left( {m{ \left( {n-m} \right) }} \right) }}
O(m(n−m)) 。可以通过60%的数据。
100分做法：
实际上，该问题是一个求静态区间最值 (static RMQ) 问题，使用任何一种能在
O
(
log
2
n
)
{ {\rm O} { \left( {{{\mathop{{ \text{log} }}\nolimits_{{2}}n}}} \right) }}
O(log2n) 时间内求出长度为
n
{n}
n 的区间最值的数据结构都可以使本题有一个
O
(
m
log
2
(
n
−
m
)
)
{ {\rm O} { \left( {{{m\mathop{{ \text{log} }}\nolimits_{{2}} \left( n-m \right) }}} \right) }}
O(mlog2(n−m)) 的算法复杂度上界，从而能够拿到满分。
#include<bits/stdc++.h>usingnamespace std;intmain(){int a =1200000;int ans =0;for(int i =1; i <= a; i++)if(a % i ==0)
ans++;printf("%d", ans);return0;}
C. 多少条边
问题描述
一个包含有2019节点的有向图，最多包含多少条边？（不允许有重边）
题解
对于一个无向图，其完全图边数量的计算方式是
C
n
2
{C_{n}^{2}}
Cn2 ，其含义是在所有节点中选出各自独立的、不重复的两个顶点并连边。而对于有向图，将无向边视作两条有向边即可，答案为
2
∗
C
n
2
{2*C_{n}^{2}}
2∗Cn2 。
对于除
a
1
{\mathop{{a}}\nolimits_{{1}}}
a1 以外的每一个
a
i
{\mathop{{a}}\nolimits_{{i}}}
ai，遍历
a
1
{\mathop{{a}}\nolimits_{{1}}}
a1 到
a
i
−
1
{\mathop{{a}}\nolimits_{{i-1}}}
ai−1检查其是否大于
a
i
{\mathop{{a}}\nolimits_{{i}}}
ai，并维护一个变量来统计个数。
#include<bits/stdc++.h>usingnamespace std;constint maxn =1004;int a[maxn];intmain(){int n;
cin>>n;int ans =0;for(int i =0; i < n; i++)scanf("%d",&a[i]);for(int i =1; i < n; i++)for(int j = i -1; j >=0; j--)if(a[j]> a[i])
ans++;printf("%d", ans);return0;}
#include<bits/stdc++.h>usingnamespace std;intcheck(int i){while(i){if(i %10==2)return0;
i /=10;}return1;}intmain(){int n;
cin>>n;int ans =0;for(int i =1; i <= n; i++)if(check(i))
ans++;printf("%d", ans);return0;}
G. 梅花桩
问题描述
小明每天都要练功，练功中的重要的一项是梅花桩。
小明练功的梅花桩排列成 n 行 m 列， 相邻两行的距离为 1，相邻两列的距离也为 1。
小明站在第 1 行第 1 列上，他要走到第 n 行第 m 列上。小明已经练了一段时间，他现在可以一步移动不超过d的距离（直线距离）。
小明想知道，在不掉下梅花桩的情况下，自己最少要多少步可以移动到目标。
输入格式
输入的第一行包含两个整数 n, m，分别表示梅花桩的行数和列数。
第二行包含一个实数 d（最多包含一位小数），表示小明一步可以移动的距离。
输出格式
输出一个整数，表示小明最少多少步可以到达目标。
样例输入
3 4 1.5
样例输出
3
评测用例规模与约定
对于 30% 的评测用例，2 <= n, m <= 20，1 <= d <= 20。
对于 60% 的评测用例，2 <= n, m <= 100，1 <= d <= 100。
对于所有评测用例，2 <= n, m <= 1000，1 <= d <= 100。
题解
考虑BFS（广度优先遍历）做法。
将左上角坐标(1,1)入队，并在令 d[1][1] 处为0。不断将队头出队，并将与队头坐标
（
i
,
j
）
{（i,j）}
（i,j） 距离
d
i
s
<
d
{dis < d}
dis<d 的所有坐标入队，并将其坐标对应的 d[x][y] 标记为 d[i][j]+1 ，直到队列为空。
此时，d[n][m] 处即为答案。
#include<bits/stdc++.h>usingnamespace std;constint N =1004;int dis[N][N];int n,m;double d;
queue< pair<int,int>>q;voidbfs(){
q.push(make_pair(1,1));while(!q.empty()){
pair<int,int> t = q.front();
q.pop();int x = t.first, y = t.second;int tx = x, ty = y +(int)d;if((n-x)*(n-x)+(m-y)*(m-y)<= d*d){
dis[n][m]= dis[x][y]+1;break;}while(tx <= n && ty >= y && ty <= m){if((tx - x)*(tx - x)+(ty - y)*(ty - y)<= d * d && dis[tx][ty]==0){
q.push(make_pair(tx, ty));
dis[tx][ty]= dis[x][y]+1;
tx ++;}else ty --;}}
cout<<dis[n][m]<<endl;}intmain(){
cin>>n>>m>>d;bfs();return0;}
使用一个二维数组 d[n][m]，其含义代表第
n
{n}
n 个数选择
m
{m}
m 时的方案总数。
显然，当
n
=
1
{n = 1}
n=1 时，d[1][m] 的值均为1。
除此之外
当
n
{n}
n 为偶数时，d[n][m]的值显然应该为
∑
i
=
m
+
1
m
a
x
m
d
[
n
−
1
]
[
i
]
{{\mathop{{\mathop{ \sum }\limits_{{i=m+1}}^{{\mathop{{max}}\nolimits_{{m}}}}}}\nolimits_{{}}{d \left[ n-1 \left] \left[ i \right] \right. \right. }}}
i=m+1∑maxmd[n−1][i] 。
当
n
{n}
n 为奇数时，d[n][m]的值显然应该为
∑
i
=
m
i
n
m
m
−
1
d
[
n
−
1
]
[
i
]
{{\mathop{{\mathop{ \sum }\limits_{{i=\mathop{{min}}\nolimits_{{m}}}}^{{m-1}}}}\nolimits_{{}}{d \left[ n-1 \left] \left[ i \right] \right. \right. }}}
i=minm∑m−1d[n−1][i] 。
则 d[maxn][maxm] 为所求。
时间复杂度
O
(
n
m
2
)
{{ {\rm O} \left( n\mathop{{m}}\nolimits^{{2}} \right) }}
O(nm2) ,可以通过80%的评测用例。
//init
d[1][n]=1;for(int i = n -1; i >0; i--)
d[1][i]= d[1][i-1]+1;//cal
d[i][j]= d[i-1][j-1]+ d[i][j+1];//when i & 1 == 1
d[i][j]= d[i-1][j+1]+ d[i][j-1];//when i & 1 != 1
则对于奇数长度的序列，d[n][1] 为所求，对于偶数长度的序列， d[n][m] 为所求。
对d数组的一次遍历即可求出所有答案，则时间复杂度降为
O
(
n
m
)
{{ {\rm O} \left( nm \right) }}
O(nm) ，可以通过所有评测用例。
#include<bits/stdc++.h>usingnamespace std;constint MAXN =1004;constint MOD =10000;int d[MAXN][MAXN];intmain(){int m, n;
cin>>m>>n;for(int i =1; i <= n; i++)
d[1][i]= n - i +1;for(int i =2; i <= m; i++)if(i &1)for(int j = n; j >=1; j--)
d[i][j]=(d[i-1][j-1]+ d[i][j+1])% MOD;elsefor(int j =1; j <= n; j++)
d[i][j]=(d[i-1][j+1]+ d[i][j-1])% MOD;int ans = m &1? d[m][1]: d[m][n];printf("%d", ans);return0;}
U
P
D
:
{UPD:}
UPD: 本篇题解中
n
,
m
{n,m}
n,m 的含义与题中相反，但代码中相同，请读者注意甄别。
I. 植树
问题描述
小明和朋友们一起去郊外植树，他们带了一些在自己实验室精心研究出的小树苗。
小明和朋友们一共有 n 个人，他们经过精心挑选，在一块空地上每个人挑选了一个适合植树的位置，总共 n 个。
对于所有评测用例，1 <= n <= 30, 0 <= x, y <= 1000, 1 <= r <= 1000。
题解
考虑DFS+回溯做法。
枚举出长度为
n
{n}
n 的二进制01串，第
i
{i}
i 位上的二进制位代表其是否种植。逐一统计出可种植的情况，并以此维护种植面积的最大值即可。
周日上午
A. 大小
问题描述
在计算机存储中，15.125GB是多少MB？
题解
1GB = 1024MB。
#include<bits/stdc++.h>usingnamespace std;intmain(){double GB =15.125;double ans = GB *1024;printf("%f", ans);return0;}
答案：15488
B. 1949
见 周六上午 B。
C. 括号序列
问题描述
由1对括号，可以组成一种合法括号序列：()。
由2对括号，可以组成两种合法括号序列：()()、(())。
由4对括号组成的合法括号序列一共有多少种？
题解
问题规模较小，手动枚举所有可能即可。
实际上，对于任意正整数
n
{n}
n ，
n
{n}
n 对括号可组成合法的序列个数为第
n
{n}
n 个卡特兰
(
C
a
t
a
l
a
n
)
{(Catalan)}
(Catalan) 数。有兴趣的同学可以自行查阅资料并证明。
下面给出递推法求第
n
{n}
n 个卡特兰数的程序，一样可以求解本题。
#include<bits/stdc++.h>usingnamespace std;typedefunsignedlonglong ull;intmain(){int n =4;
ull catalan[34]={0,1};for(int i =2; i <34; i++)
catalan[i]= catalan[i -1]*(4* i -2)/(i +1);printf("%llu", catalan[n]);return0;}
答案：14
E. 多少条边
见 周六下午 C。
F. 反倍数
问题描述
给定三个整数 a, b, c，如果一个整数既不是 a 的整数倍也不是 b 的整数倍还不是 c 的整数倍，则这个数称为反倍数。
请问在 1 至 n 中有多少个反倍数。
输入格式
输入的第一行包含一个整数 n。
第二行包含三个整数 a, b, c，相邻的两个数之间用一个空格分隔。
输出格式
输出一个整数，表示答案。
样例输入
30
2 3 6
样例输出
10
评测用例规模与约定
对于 40% 的评测用例，1 <= n <= 10000。
对于 80% 的评测用例，1 <= n <= 100000。
对于所有评测用例，1 <= n <= 1000000， 1 <= a <= n，1 <= b <= n，1 <= c <= n。
题解
枚举 1 到 n 中的每个整数，逐一判断其是否是反倍数即可。
#include<bits/stdc++.h>usingnamespace std;int a, b, c;intcheck(int i){if(i % a ==0|| i % b ==0|| i % c ==0)return0;return1;}intmain(){int n;int ans =0;
cin>>n>>a>>b>>c;for(int i =1; i <= n; i++)if(check(i))
ans ++;printf("%d", ans);return0;}
G. 数位相同
问题描述
给定正整数 n，请问在整数 1 至 n 中， 数字中没有数位相同的数有多少个？
例如，当 n = 30时，除开 11 和 22 以外，其他的数都没有数位相同，因此答案为28。
输入格式
输入的第一行包含一个整数 n。
输出格式
输出一个整数，表示答案。
样例输入
30
样例输出
28
评测用例规模与约定
对于 40% 的评测用例，1 <= n <= 1000。
对于 80% 的评测用例，1 <= n <= 100000。
对于所有评测用例，1 <= n <= 1000000。
题解
枚举 1 到 n 中的每个整数，逐一判断其是否有数位相同即可。
#include<bits/stdc++.h>usingnamespace std;int v[10];intcheck(int i){memset(v,0,sizeof(v));while(i){if(v[i %10])return0;
v[i %10]=1;
i /=10;}return1;}intmain(){int n;
cin>>n;int ans =0;for(int i =1; i <= n; i++)if(check(i))
ans++;printf("%d", ans);return0;}
对于第
i
{i}
i 个向量，遍历从
i
+
1
{i+1}
i+1 到
i
m
a
x
{{\mathop{{i}}\nolimits_{{max}}}}
imax 的向量并统计有多少个能与其构成和谐向量对，统计答案即可。时间复杂度
O
(
n
2
)
{{ {\rm O} \left( \mathop{{n}}\nolimits^{{2}} \right) }}
O(n2)，可以通过70%的评测用例。
满分做法
分析
对于每个向量，令
t
=
x
−
y
{t = x - y}
t=x−y 。分析可得：若
t
i
=
−
t
j
{{{\mathop{{t}}\nolimits_{{i}}}=-\mathop{{t}}\nolimits_{{j}}}}
ti=−tj ，则
(
i
,
j
)
{(i,j)}
(i,j) 为一个和谐向量对。
设
t
=
t
i
{t={\mathop{{t}}\nolimits_{{i}}}}
t=ti 的向量有
a
{a}
a 个，
t
=
t
j
{t={\mathop{{t}}\nolimits_{{j}}}}
t=tj 的向量有
b
{b}
b 个，则这些向量共能组成
a
∗
b
{a*b}
a∗b 个和谐向量对。
求解
我们需要统计各个
t
{t}
t 值的向量数量，再使用乘法原理快速统计答案。
根据数据范围，
−
2000000
≤
t
≤
2000000
{{-2000000 \le t \le 2000000}}
−2000000≤t≤2000000。方便起见，我们令哈希函数为
h
(
x
)
=
x
+
2000000
{{h \left( x \left) =x+2000000\right. \right. }}
h(x)=x+2000000，在int a[4000001] 对整个
t
{t}
t 值序列进行散列。由于函数为完美哈希函数，我们可以用表内数据统计出现次数，即以 a[h(x)] 统计
t
=
x
{t=x}
t=x 的向量对个数。
然后遍历正整数
x
(
1
≤
x
≤
2000000
)
{x(1 \le x \le 2000000)}
x(1≤x≤2000000) ，将
a
[
h
(
x
)
]
×
a
[
h
(
−
x
)
]
{{a \left[ h \left( x \left) \left] \times a \left[ h \left( -x \left) \right] \right. \right. \right. \right. \right. \right. }}
a[h(x)]×a[h(−x)] 统计入答案。特别的，对
a
[
h
(
0
)
]
{a[h(0)]}
a[h(0)] ，其代表
t
{t}
t 值为
0
{0}
0 的向量个数，对于答案的贡献是
a
[
h
(
0
)
]
∗
(
a
[
h
(
0
)
]
−
1
)
/
2
{a[h(0)]*(a[h(0)]-1)/2}
a[h(0)]∗(a[h(0)]−1)/2 。
时间复杂度为
Θ
(
n
+
(
t
m
a
x
−
t
m
i
n
)
)
{{ \Theta \left( n+ \left( \mathop{{t}}\nolimits_{{max}}-\mathop{{t}}\nolimits_{{min}} \left) \right) \right. \right. }}
Θ(n+(tmax−tmin)) ，可以通过所有评测用例。
#include<bits/stdc++.h>usingnamespace std;typedeflonglong ll;constint maxn =100005;constint maxt =4000007;int t[maxn];
ll h[maxt];intHash(int n){return n +2000000;}voidcalHash(int n){for(int i =0; i < n; i++)
h[Hash(t[i])]++;}intmain(){int n;
cin>>n;int tx, ty;
ll ans =0;for(int i =0; i < n; i++){scanf("%d %d",&tx,&ty);
t[i]= tx - ty;}calHash(n);for(int i =1; i <=2000000; i++)
ans += h[Hash(i)]* h[Hash(-i)];
ans += h[Hash(0)]*(h[Hash(0)]-1)/2;printf("%lld", ans);return0;}
U
P
D
{UPD}
UPD ：对于此题，由于数据范围较小，我们选择使用编码容易且不易出错的直接散列法。若此题
t
{t}
t 的数据范围过大，可以选择 std::map 或 TreeMap(Java) 容器进行存储与计算。其内部实现是一颗红黑树（二叉平衡树的一种），可以在
Θ
(
log
2
n
)
{{ \Theta \left( {{\mathop{{ \text{log} }}\nolimits_{{2}}n}} \right) }}
Θ(log2n) 时间内完成 find() / [] 操作，使用树上遍历法可以在
O
(
n
log
2
n
)
{{ {\rm O} \left( {n{\mathop{{ \text{log} }}\nolimits_{{2}}n}} \right) }}
O(nlog2n) 时间完成答案统计。
对于
i
>
1
{i > 1}
i>1 的每个
a
i
{{\mathop{{a}}\nolimits_{{i}}}}
ai ，向前遍历从
i
{i}
i 到
1
{1}
1 的数直到第一个大于
a
i
{{\mathop{{a}}\nolimits_{{i}}}}
ai 的数，计算其前向距离并统计答案即可。
时间复杂度
O
(
n
2
)
{{ {\rm O} \left( \mathop{{n}}\nolimits^{{2}} \right) }}
O(n2)，可以通过70%的评测用例。
满分做法
分析
由题意得，对于一个数
a
i
{{\mathop{{a}}\nolimits_{{i}}}}
ai ，若在其后有
a
j
>
a
i
{{\mathop{{a}}\nolimits_{{j}}>\mathop{{a}}\nolimits_{{i}}}}
aj>ai ，则对于
a
j
{{\mathop{{a}}\nolimits_{{j}}}}
aj 之后的数，
a
j
{{\mathop{{a}}\nolimits_{{j}}}}
aj 必能替代其成为答案。
求解
我们可以考虑使用一个单调递减的栈。栈中元素是一个结构体，含有
序列中的某个元素
a
i
{{\mathop{{a}}\nolimits_{{i}}}}
ai ；
其下标
i
{i}
i 。
属性。
先将
a
1
{{\mathop{{a}}\nolimits_{{1}}}}
a1 对应结构体入栈，对于随后的元素
若要编写程序计算该值，需先了解换底公式
log
a
x
=
log
b
x
log
b
a
{\mathop{{ \text{log} }}\nolimits_{{a}}x=\frac{{\mathop{{ \text{log} }}\nolimits_{{b}}x}}{{\mathop{{ \text{log} }}\nolimits_{{b}}a}}}
logax=logbalogbx C语言的库函数 log() 是求自然对数的函数，若想求
log
a
x
{{\mathop{{ \text{log} }}\nolimits_{{a}}x}}
logax ，可使用换底公式求
log
e
x
log
e
a
{{\frac{{\mathop{{ \text{log} }}\nolimits_{{e}}x}}{{\mathop{{ \text{log} }}\nolimits_{{e}}a}}}}
logealogex ，即log(x)/log(a) 。
#include<bits/stdc++.h>usingnamespace std;intmain(void){int a =2019;int ans =floor(log(2019)/log(2))+1;printf("%d", ans);return0;}
E. 大写字母
见 周六上午 G。
F. 数位相同
见 周六上午 F。
H. 倍数对
问题描述
给定整数 m，在数列 a_1, a_2, …, a_n 中，如果两个数的和为 m 的倍数，则称为一个倍数对。
给定一个数列，请问数列中总共有多少个倍数对。
输入格式
输入的第一行包含两个整数 n,m ，分别表示数列中元素个数和给定的整数 m。
第二行包含 n 个整数 a_1, a_2, …, a_n，相邻的整数间用空格分隔，表示给定的数列。
输出格式
输出一个整数，表示答案。
样例输入
6 3
6 1 2 5 6 2
样例输出
4
评测用例规模与约定
对于 70% 的评测用例，1 <= n <= 100。
对于所有评测用例，1 <= n <= 1000。
题解
对于第
i
{i}
i 个整数，遍历从
i
+
1
{i+1}
i+1 到
i
m
a
x
{{\mathop{{i}}\nolimits_{{max}}}}
imax 的数字并统计有多少个能与其构成倍数对，统计答案即可。
#include<bits/stdc++.h>usingnamespace std;constint maxn =1004;int a[maxn];int m;intcheck(int i){if(i % m ==0)return1;return0;}intmain(void){int n;int ans =0;
cin>>n>>m;for(int i =0; i < n; i++)scanf("%d",&a[i]);for(int i =0; i < n -1; i++)for(int j = i +1; j < n; j++)if(check(a[i]+ a[j]))
ans++;printf("%d", ans);return0;}
I. 摆动序列
见 周六下午 H。
J. 螺旋矩阵
见 周六上午H。
K. 一带一路
问题描述
2015年，全中国实现了户户通电。作为一名电力建设者，小明正在帮助一带一路上的国家通电。
这一次，小明要帮助 n 个村庄通电，其中 1 号村庄正好可以建立一个发电站，所发的电足够所有村庄使用。
现在，这 n 个村庄之间都没有电线相连，小明主要要做的是架设电线连接这些村庄，使得所有村庄都直接或间接的与发电站相通。
小明测量了所有村庄的位置(坐标)和高度，如果要连接两个村庄，小明需要花费两个村庄之间的坐标距离加上高度差的平方，形式化描述为坐标为 (x_1, y_1) 高度为 h_ 1 的村庄与坐标为 (x_2, y_2) 高度为 h_ 2 的村庄之间连接的费用为
(
x
1
−
x
2
)
2
+
(
y
1
−
y
2
)
2
+
(
h
1
−
h
2
)
2
{{\sqrt{{\mathop{{{ \left( {\mathop{{{x}}}\nolimits_{{1}}-\mathop{{{x}}}\nolimits_{{2}}} \right) }}}\nolimits^{{2}}+\mathop{{{ \left( {\mathop{{{y}}}\nolimits_{{1}}-\mathop{{{y}}}\nolimits_{{2}}} \right) }}}\nolimits^{{2}}}}+}\mathop{{{{ \left( {\mathop{{{h}}}\nolimits_{{1}}-\mathop{{{h}}}\nolimits_{{2}}} \right) }}}}\nolimits^{{2}}}
(x1−x2)2+(y1−y2)2+(h1−h2)2 由于经费有限，请帮助小明计算他至少要花费多少费用才能使这n个村庄都通电。
题解
一道很明显的最小生成树题目。直接根据公式赋权值，然后求其最小生成树即可。
使用 Kruskal 算法，同时利用数据结构 二叉堆 进行优化，时间复杂度为
O
(
n
2
log
2
n
2
)
{{O \left( {\mathop{{n}}\nolimits^{{2}}{\mathop{{ \text{log} }}\nolimits_{{2}}\mathop{{n}}\nolimits^{{2}}}} \right) }}
O(n2log2n2) 。
考虑到该题为完全图，可以使用 Prim 算法，时间复杂度为
O
(
n
2
)
{{O \left( {\mathop{{n}}\nolimits^{{2}}} \right) }}
O(n2)。
#include<bits/stdc++.h>usingnamespace std;constint maxn =1004;constdouble MAX =1e9;int n;double a[maxn][maxn], d[maxn], ans;bool v[maxn];typedefstruct{int x;int y;int h;} point;
point p[maxn];voidinit(){for(int i =0; i <= n; i++){for(int j =0; j <= n; j++)
a[i][j]= MAX;
d[i]= MAX;}}voidPrim(){memset(v,0,sizeof(v));
d[1]=0;for(int i =1; i < n; i++){int x =0;for(int j =1; j <= n; j++)if(!v[j]&&(x ==0|| d[j]< d[x])) x = j;
v[x]=1;for(int y =1; y <= n; y++)if(!v[y]) d[y]=min(d[y], a[x][y]);}}intmain(void){
cin>>n;init();for(int i =1; i <= n; i++)scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].h);for(int i =1; i <= n -1; i++)for(int j = i +1; j <= n; j++){double temp =sqrt((p[i].x - p[j].x)*(p[i].x - p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y))+(p[i].h-p[j].h)*(p[i].h-p[j].h);
a[i][j]= a[j][i]=min(a[i][j], temp);}Prim();for(int i =2; i <= n; i++) ans += d[i];printf("%f", ans);return0;}
