一个人抛了三个骰子，它们的顶面分别是$a,b,c$。求它们的底面之和。
这里用的骰子是标准骰子，即两个相对的面之和为$7$。
$1\le a,b,c\le 6$
输入格式
$a~b~c$
输出格式
输出答案。
样例
| $a$ |
$b$ |
$c$ |
答案 |
| $1$ |
$4$ |
$3$ |
$13$ |
| $5$ |
$6$ |
$4$ |
$6$ |
分析
因为两个相对的面之和为$7$，所以本题的答案为$(7-a)+(7-b)+(7-c)=21-a-b-c$。
代码
1
2
3
4
5
6
7
8
9
10
|
#include <cstdio>
using namespace std;
int main()
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
printf("%d\n", 21 - a - b - c);
return 0;
}
|
给定一个由0、1、6、8、9组成的字符串$S$。将其旋转$180\degree$并输出。
一个字符串旋转$180\degree$的方法：
- 将其翻转（
reverse）。
- 将其中的
6替换为9，9替换为6。
$1\le |S|\le10^5$
输入格式
$S$
输出格式
输出$S$旋转$180\degree$后的字符串。
样例
| $S$ |
输出 |
0601889 |
6881090 |
86910 |
01698 |
01010 |
01010 |
分析
本题直接按要求模拟即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include <cstdio>
#define maxn 100005
using namespace std;
char s[maxn];
int main()
{
int n = 0;
char c;
while((c = getchar()) != '\n')
s[n++] = c;
while(n--)
putchar(s[n] == '6'? '9': s[n] == '9'? '6': s[n]);
putchar('\n');
return 0;
}
|
给定三个长度为$N$的序列：$A,B,C$。
有多少对$(i,j)$符合$A_i=B_{C_j}$？
$1\le N\le 10^5$
$1\le A_i,B_i,C_i\le N$
输入格式
$N$
$A_1~A_2~\dots~A_N$
$B_1~B_2~\dots~B_N$
$C_1~C_2~\dots~C_N$
输出格式
输出符合$A_i=B_{C_j}$的$(i,j)$的对数。
样例
样例输入1
1
2
3
4
|
3
1 2 2
3 1 2
2 3 2
|
样例输出1
$4$对$(i,j)$符合条件：$(1,1),(1,3),(2,2),(3,2)$。
样例输入2
1
2
3
4
|
4
1 1 1 1
1 1 1 1
1 2 3 4
|
样例输出2
所有$(i,j)$都符合条件。
样例输入3
1
2
3
4
|
3
2 3 3
1 3 3
1 1 1
|
样例输出3
没有$(i,j)$符合条件。
分析
我们很容易想到$O(n^2)$的算法：暴力枚举所有$(i,j)$，并统计符合条件的对数。
可惜，这样会TLE。
我们考虑将所有的$A_i$和$B_{C_j}$分别放入两个桶$\mathrm{acnt}$和$\mathrm{bcnt}$。
根据乘法原理我们得出答案为$\sum\limits_{i=1}^n\mathrm{acnt}_i\mathrm{bcnt}_i$。
代码
注意：不要忘记使用long long！
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
|
#include <cstdio>
#define maxn 100005
using namespace std;
using LL = long long;
int acnt[maxn], b[maxn], bcnt[maxn];
int main()
{
int n;
scanf("%d", &n);
for(int i=0; i<n; i++)
{
int a;
scanf("%d", &a);
acnt[a] ++;
}
for(int i=0; i<n; i++)
scanf("%d", b + i);
for(int i=0; i<n; i++)
{
int c;
scanf("%d", &c);
bcnt[b[--c]] ++;
}
LL ans = 0LL;
for(int i=1; i<=n; i++)
ans += LL(acnt[i]) * LL(bcnt[i]);
printf("%lld\n", ans);
return 0;
}
|
在由$A$个a和$B$个b（均不要求连续）组成的字符串中，求字典序第$K$小的。
$1\le A,B\le 30$
$1\le K\le S$（$S$为由$A$个a和$B$个b组成的字符串的个数）
输入格式
$A~B~K$
输出格式
输出由$A$个a和$B$个b组成的字符串中字典序第$K$小的。
样例
| $A$ |
$B$ |
$K$ |
输出 |
| $2$ |
$2$ |
$4$ |
baab |
| $30$ |
$30$ |
$118264581564861424$ |
（$30$个b$+30$个a) |
分析
我们令$\mathrm{dp}(a,b)$为由$a$个a和$b$个b组成的字符串的个数，则：
- 我们在长度为$a+b-1$的字符串上再添上一个
a或b：
- $\mathrm{dp}(a,b)=\mathrm{dp}(a-1,b)+\mathrm{dp}(a,b-1)$。
$$f(a,b,k)=\begin{cases}
``" & (a=b=0)\\
``a"+f(a-1,b,k) & (b=0)\\
``b"+f(a,b-1,k) & (a=0)\\
``a"+f(a-1,b,k) & (k\le \mathrm{dp}(a-1,b))\\
``b"+f(a,b-1,k- \mathrm{dp}(a-1,b)) & (k>\mathrm{dp}(a-1,b))
\end{cases}$$代码
写代码时，可以用递归形式，也可以使用非递归形式（更快）：
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 <cstdio>
#define maxn 35
using namespace std;
using LL = long long;
LL dp[maxn][maxn];
int main()
{
int a, b;
LL k;
scanf("%d%d%lld", &a, &b, &k);
for(int i=0; i<=a; i++) dp[i][0] = 1;
for(int i=0; i<=b; i++) dp[0][i] = 1;
for(int i=1; i<=a; i++)
for(int j=1; j<=b; j++)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
while(a && b)
{
LL t = dp[a - 1][b];
if(k <= t) putchar('a'), a --;
else putchar('b'), b --, k -= t;
}
while(a--) putchar('a');
while(b--) putchar('b');
putchar('\n');
return 0;
}
|
我们有一棵$N$个节点的树，节点的编号分别为$1,2,\dots,N$。
$1$号点是根节点，且第$i$个点（$2\le i\le N$）的父亲节点是$P_i$。
给你$Q$个查询，第$i$个查询包含两个整数$U_i$和$D_i$，求符合下列条件的点$u$的个数：
- $u$到根节点的最短路径正好有$D_i$条边；
- $U_i$在$u$到根节点的最短路径中（包含两端）。
$1\le N\le 2\times10^5$
$1\le P_i < i$
$1\le Q\le 2\times10^5$
$1\le U_i\le N$
$0\le D_i < N$
输入格式
$N$
$P_2~P_3~\dots~P_N$
$Q$
$U_1~D_1$
$U_2~D_2$
$\vdots$
$U_Q~D_Q$
输出格式
输出$Q$行。第$i$行包含对第$i$个查询的回应。
样例
样例输入
1
2
3
4
5
6
7
|
7
1 1 2 2 4 2
4
1 2
7 2
4 1
5 5
|
样例输出
在第一个查询中，节点$4,5,7$符合条件。
在第二个查询中，只有节点$7$符合条件。
在最后两个查询中，没有节点符合条件。
分析
我们可以先在整棵树上从根节点开始跑一遍$\text{DFS}$，对于节点$i$预处理出$\mathrm{in}_i$和$\mathrm{out}_i$，分别表示进入和走出这个节点的时间，同时将第$i$层节点的所有$\mathrm{in}$放入$\mathrm{depin}_i$。
如果节点$u$到根节点的路径中有$v$，则$\mathrm{in}_v\le\mathrm{in}_u < \mathrm{out}_v$。
因此，对于每个查询，我们利用二分查找即可快速算出符合条件的节点个数。
代码
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
|
#include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 200005
using namespace std;
int in[maxn], out[maxn], dep[maxn], cnt;
vector<int> G[maxn], depin[maxn];
void dfs(int v)
{
depin[dep[v]].push_back(in[v] = cnt++);
for(int u: G[v])
dfs(u);
out[v] = cnt++;
}
int main()
{
int n;
scanf("%d", &n);
dep[0] = cnt = 0;
for(int i=1; i<n; i++)
{
int p;
scanf("%d", &p);
dep[i] = dep[--p] + 1;
G[p].push_back(i);
}
dfs(0);
int q;
scanf("%d", &q);
while(q--)
{
int u, d;
scanf("%d%d", &u, &d);
const auto& din = depin[d];
auto first = lower_bound(din.begin(), din.end(), in[--u]);
auto last = lower_bound(din.begin(), din.end(), out[u]);
printf("%lld\n", last - first);
}
return 0;
}
|