A - kcal
题目大意
我们有一种每\(100\)毫升含有\(A\)千卡热量的饮料。\(B\)毫升的这种饮料含有多少千卡热量?
\(0\le A, B\le 1000\)
输入格式
\(A~B\)
输出格式
输出\(B\)毫升这种饮料包含的的千卡数。最大允许浮点数精度误差\(10^{-6}\)。
样例
\(A\) | \(B\) | 输出 |
---|---|---|
\(45\) | \(200\) | \(90\) |
\(37\) | \(450\) | \(166.5\) |
\(0\) | \(1000\) | \(0\) |
\(50\) | \(0\) | \(0\) |
分析
废话不多说,答案就是\(\frac{AB}{100}\)~
代码
#include <cstdio>
using namespace std;
int main()
{
int a, b;
scanf("%d%d", &a, &b);
a *= b;
printf("%d.%d\n", a / 100, a % 100);
return 0;
}
B - Permutation Check
题目大意
给定长度为\(N\)的序列\(A=(A_1,A_2,\dots,A_N)\)。
判断\(A\)是否为\((1,2,\dots,N)\)的一种排列。
\(1\le A_i\le N\le 10^3\)
输入格式
\(N\)
\(A_1~A_2~\dots~A_N\)
输出格式
如果\(A\)是\((1,2,\dots,N)\)的一种排列,输出Yes
;否则,输出No
。
样例
样例输入1
5
3 1 2 4 5
样例输出1
Yes
\((3,1,2,4,5)\)是\((1,2,3,4,5)\)的一种排列,所以我们输出Yes
。
样例输入2
6
3 1 4 1 5 2
样例输出2
No
\((3,1,4,1,5,2)\)不是\((1,2,3,4,5,6)\)的一种排列,所以我们输出No
。
样例输入3
3
1 2 3
样例输出3
Yes
样例输入4
1
1
样例输出4
Yes
分析
由于题目保证\(1\le A_i\le N\),所以\((1,2,\dots,N)\)的一种排列\(A\)定义如下:
- \(A\)中\(1\)到\(N\)每个数字不重复出现。
因此,我们可以用数组记录每个数字是否出现,所以总时间复杂度为\(\mathcal O(n)\)。
代码
#include <cstdio>
#define maxn 1005
using namespace std;
bool used[maxn];
int main()
{
int n;
scanf("%d", &n);
for(int i=0; i<n; i++)
{
int a;
scanf("%d", &a);
if(used[a])
{
puts("No");
return 0;
}
used[a] = true;
}
puts("Yes");
return 0;
}
C - POW
题目大意
给定三个整数\(A,B,C\),判断\(A^C\)和\(B^C\)哪个更大。
\(-10^9\le A,B\le 10^9\)
\(1\le C\le 10^9\)
输入格式
\(A~B~C\)
输出格式
本题分如下三种情况输出:
- 如果\(A^C<B^C\),输出
<
; - 如果\(A^C>B^C\),输出
>
; - 如果\(A^C=B^C\),输出
=
。
样例
\(A\) | \(B\) | \(C\) | 输出 |
---|---|---|---|
\(3\) | \(2\) | \(4\) | > |
\(-7\) | \(7\) | \(2\) | = |
\(-8\) | \(6\) | \(3\) | < |
分析
首先,由于负负得正,\((-a)^2=a^2\)。
这样,我们可以根据奇偶性得出,如果\(n\)为偶数,\((-a)^n=a^n\);但如果\(n\)为奇数,则\((-a)^n=-(a^n)\)。
因此,我们只需判断如果\(C\)为偶数,将\(A\)替换为\(|A|\),再将\(B\)替换为\(|B|\)。
最后,\(A\)和\(B\)的大小关系就是\(A^C\)和\(B^C\)的大小关系。
代码
#include <cstdio>
using namespace std;
int main()
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if(!(c & 1))
{
if(a < 0) a = -a;
if(b < 0) b = -b;
}
puts(a < b? "<": a > b? ">": "=");
return 0;
}
D - Kth Excluded
题目大意
给定长度为\(N\)的正整数序列\(A=(A_1,A_2,\dots,A_N)\)和\(Q\)次查询。
在第\(i\)次查询中,给定正整数\(K_i\),求第\(K_i\)小的不在\(A\)中的正整数。
\(1\le N,Q\le 10^5\)
\(1\le A_1<A_2<\dots<A_N\le10^{18}\)
\(1\le K_i\le 10^{18}\)
输入格式
\(N~Q\)
\(A_1~A_2~\dots~A_N\)
\(K_1\)
\(K_2\)
\(\hspace{5pt}\vdots\)
\(K_N\)
输出格式
输出\(Q\)行。第\(i\)行应该包含第\(K_i\)小的不在\(A\)中的正整数。
样例
样例输入1
4 3
3 5 6 7
2
5
3
样例输出1
2
9
4
不在\(A\)中的正整数有\(1,2,4,8,9,10,11,\dots\),其中有:
- 第\(2\)小的\(2\);
- 第\(5\)小的\(9\);
- 第\(3\)小的\(4\)。
因此,我们应该依次输出2
,9
,4
。
样例输入2
5 2
1 2 3 4 5
1
10
样例输出2
6
15
分析
本题我们可以先预处理出\(A\)中每个元素比它小的元素的数量,再二分查找即可。
代码
#include <cstdio>
#include <algorithm>
#define maxn 100005
using namespace std;
using LL = long long;
LL a[maxn];
int main()
{
int n, q;
scanf("%d%d", &n, &q);
for(int i=0; i<n; i++)
{
scanf("%lld", a + i);
a[i] -= i;
}
while(q--)
{
LL k;
scanf("%lld", &k);
printf("%lld\n", k + (upper_bound(a, a + n, k) - a));
}
return 0;
}
E - White and Black Balls
题目大意
有多少种排列\(N\)个白球和\(M\)个黑球的方法使得下列条件成立?
- 对于每个\(i\) (\(1\le i\le N+M\)),设\(w_i\)和\(b_i\)分别是最左边\(i\)个球中白球和黑球的数量,\(w_i\le b_i+K\)成立。
答案对\((10^9+7)\)取模。
\(0\le N,M\le10^6\)
\(1\le N+M\)
\(0\le K\le N\)
输入格式
\(N~M~K\)
输出格式
输出答案,对\((10^9+7)\)取模。
样例
\(N\) | \(M\) | \(K\) | 输出 |
---|---|---|---|
\(2\) | \(3\) | \(1\) | \(9\) |
\(1\) | \(0\) | \(0\) | \(0\) |
\(1000000\) | \(1000000\) | \(1000000\) | \(192151600\) |
分析
首先,本题中合法排列数就是如下符合任意\(y\le x+K\)的\((0,0)\to(M,N)\)的最短路径的数量:
由此可见,如果\(N>M+K\)(即终点超出限制),答案一定为\(0\)。
我们还可以发现,如果没有\(y\le x+K\)这个限制,答案为\(\binom{N + M}{N}\)。
我们再考虑不合法的路径数,数量为\(\binom{N + M}{M + K + 1}\)。
因此,答案为\(\binom{N + M}{N}-\binom{N + M}{M + K + 1}\)。
代码
这里用AtCoder Library
好像比较方便唉~
#include <iostream>
#include <atcoder/modint>
using namespace std;
using modint = atcoder::modint1000000007;
modint f(int n, int m)
{
if(n < 0 || m < 0)
return 0;
modint ret = 1;
for(int i=1; i<=m; i++)
ret = ret * (n + i) / i;
return ret;
}
int main()
{
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
if(n > m + k) puts("0");
else printf("%d\n", (f(n, m) - f(n - k - 1, m + k + 1)).val());
return 0;
}
标签:dots,输出,le,205,AtCoder,int,题解,样例,10
From: https://www.cnblogs.com/stanleys/p/18403477/abc205