A - Median?
题目大意
给定正整数\(a,b,c\),判断\(b\)是否为三个数中的中位数(即从小到大排序后是第二个,不是平均数)。
\(1\le a,b,c\le 100\)
输入格式
\(a~b~c\)
输出格式
如果\(b\)是三个数中的中位数,输出Yes
;否则,输出No
。
样例
\(a\) | \(b\) | \(c\) | 输出 |
---|---|---|---|
\(5\) | \(3\) | \(2\) | Yes |
\(2\) | \(5\) | \(3\) | No |
\(100\) | \(100\) | \(100\) | No |
分析
本来就是A题,其实没什么难的,比赛的时候就是看成平均数WA了..(上面应该讲的够清楚了)
当然可以直接将三个数排序(简单粗暴),也可以判断\(a\le b\le c\)和\(c\le b\le a\)中是否有至少一个成立。
代码
#include <cstdio>
using namespace std;
int main()
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
puts((a <= b && b <= c) || (c <= b && b <= a)? "Yes": "No");
return 0;
}
B - Distance Between Tokens
题目大意
在\(H\times W\)的网格上,有恰好两个位置上各有一颗棋子,别的都是空位。
你可以从任意一个棋子开始,通过上下左右移动,前往另一个棋子的位置。
求至少要移动多少次?
输入格式
先是一行\(H,W\),用空格隔开,然后有\(H\)行,每行是一个长度为\(W\)的字符串,-
表示这个位置是空位,o
表示这里有一颗棋子(详见样例)。
输出格式
输出一行,即至少要移动的次数。
样例
样例输入1
2 3
--o
o--
样例输出1
3
样例输入2
5 4
-o--
----
----
----
-o--
样例输出2
4
分析
本题不需要\(\text{BFS}\),由于没有障碍物,直接找到两颗棋子,并输出\(x_\text{diff}+y_\text{diff}\)(即\(x,y\)的坐标差之和)即可。
代码
#include <cstdio>
#include <vector>
using namespace std;
int main()
{
int h = 0, w = 0, x1 = -1, y1 = -1, x2 = -1, y2 = -1;
char c;
while((c = getchar()) != ' ')
h = (h << 3) + (h << 1) + (c ^ 48);
while((c = getchar()) != '\n')
w = (w << 3) + (w << 1) + (c ^ 48);
for(; h--; getchar())
for(int i=w; i--; )
if(getchar() == 'o')
if(x1 == -1) x1 = h, y1 = i;
else { x2 = h, y2 = i; break; }
printf("%d\n", x1 - x2 + (y1 > y2? y1 - y2: y2 - y1));
return 0;
}
C - Max - Min Query
题目大意
我们有一个序列\(S\),初始为空。
请处理如下\(Q\)个操作:
1 x
:将\(x\)插入至\(S\)的末尾。2 x c
:从\(S\)中删除\(c\)个\(x\),如果不够删就直接删完。3
:求\(S\)中最大值与最小值的差。
\(1\le Q\le 2\times 10^5\)
\(0\le x\le 10^9\)
\(1\le c\le Q\)
输入格式
\(Q\)
\(\text{query}_1\)
\(\text{query}_2\)
\(\vdots\)
\(\text{query}_Q\)
输出格式
对于每个操作\(3\),输出\(S\)中最大值与最小值的差。
分析
典型STL练习题
本题可以用multiset
或map
解决,这里介绍使用map
的方法(仅限C++
使用)。
C++
中,我们需要用到std::map<int, int>
的如下方法:
mp[x]
或int& operator[](int&& key)
返回key
对应的value
的引用,如果之前没有用到过则创建并返回\(0\)。
时间复杂度:\(\mathcal O(\log n)\),其中\(n\)为map
中元素总数。iterator begin()
返回最小的元素对应的指针,mp.begin()->first
可以获得mp
的最小元素
时间复杂度:\(\mathcal O(1)\)iterator rbegin()
返回最大的元素对应的指针,mp.rbegin()->first
可以获得mp
的最大元素
时间复杂度:\(\mathcal O(1)\)size_type erase(const int& key)
将key
以及对应的value
从map
中删除,返回删除的元素个数(\(0\)或\(1\)),返回值一般可以忽略。
时间复杂度:\(\mathcal O(\log n)\),其中\(n\)为map
中元素总数。
这时,每个查询都可转换为上述操作,详见代码。
代码
#include <cstdio>
#include <map>
using namespace std;
int main()
{
int q;
scanf("%d", &q);
map<int, int> cnt;
while(q--)
{
int op;
scanf("%d", &op);
if(op == 3) printf("%d\n", cnt.rbegin()->first - cnt.begin()->first);
else if(op == 1)
{
int x;
scanf("%d", &x);
cnt[x] ++;
}
else if(op == 2)
{
int x, m;
scanf("%d%d", &x, &m);
if(cnt[x] > m) cnt[x] -= m;
else cnt.erase(x);
}
}
return 0;
}
D - FizzBuzz Sum Hard
题目大意
输出\(1\)到\(N\)之间不是\(A\)或\(B\)的倍数的数之和。
\(1\le N,A,B\le 10^9\)
输入格式
\(N~A~B\)
输出格式
输出答案。
分析
根据容斥原理,\(1\)到\(N\)之间是\(A\)或\(B\)的倍数的数之和为:
\((A\)的倍数之和\()+(B\)的倍数之和\()-(\)同时为\(A,B\)的倍数之和\()\)。
又因为同时为\(A,B\)的倍数的数是\([A,B]\)(最小公倍数)的倍数,所以可转化为\((A\)的倍数之和\()-(B\)的倍数之和\()+([A,B]\)的倍数之和\()\)。
再设\(f(N)=1+2+\dots+N,g(x,N)=xf(\lfloor\frac N X\rfloor)=(N\)以内所有\(x\)的倍数之和\()\),
则答案为
总时间复杂度为求解\([A,B]\)的复杂度,即\(\mathcal O(\log \max\{A,B\})\)。
代码
这里使用了另一种\(g(x,N)\)的求法,思路类似。
#include <cstdio>
using namespace std;
using LL = long long;
inline LL sum(const LL& x, const LL& n)
{
LL cnt = n / x;
return x * cnt * (cnt + 1LL) >> 1LL;
}
int main()
{
int n, a, b;
scanf("%d%d%d", &n, &a, &b);
LL x = b, y = a;
while(b ^= a ^= b ^= a %= b);
LL t = x / a * y; // t = lcm(a, b)
printf("%lld\n", sum(1, n) - sum(x, n) - sum(y, n) + sum(t, n));
return 0;
}
E - Distance Sequence
题目大意
求符合如下条件的\(A=(A_1,\dots,A_N)\)的个数,对\(998244353\)取模:
- \(1\le A_i\le M\)(\(1\le i\le N\))
- \(|A_i-A_{i+1}|\ge K\)(\(1\le i<N\))
\(2\le N\le 1000\)
\(1\le M\le 5000\)
\(0\le K<M\)
输入格式
\(N~M~K\)
输出格式
输出符合条件的序列的个数,对\(998244353\)取模。
分析
很明显是\(\text{DP}\)(动态规划)的思路,仿照01背包的方式,我们设计如下状态:
\[\text{dp}(i,j)=(A_i=j\text{的可能数}) \]状态转移方程也很简单,即:
\[\text{dp}(i,j)=\sum_{p=1}^{j-k}\text{dp}(i-1,p)+\sum_{p=j+k}^m\text{dp}(i-1,p) \]那么,如果直接暴力循环计算,整个算法的时间复杂度是\(\mathcal O(NM^2)\),显然不能通过。
但是注意到这里有个求和的操作,显然可以用前缀/后缀和优化,用\(\mathcal O(1)\)的时间复杂度求出两个和,因此时间复杂度降到\(\mathcal O(NM)\),可以通过。
最后一个坑,需要注意特判\(K=0\)的情况,答案为\(M^N\bmod 998244353\)。
本题到此结束。
代码
特判使用快速幂,\(\text{DP}\)建议使用滚动表(又称数组重复利用)技巧,优化后实测:
- 时间:\(49\mathrm{ms}\to39\mathrm{ms}\)
- 空间:\(21220\mathrm{kb}\to1664\mathrm{kb}\)
#include <cstdio>
#define maxn 1002
#define maxm 5005
#define MOD 998244353
using namespace std;
using LL = long long;
int qpow(LL a, LL b)
{
LL ans = 1LL;
while(b > 0)
{
if(b & 1LL) ans = ans * a % MOD;
a = a * a % MOD, b >>= 1LL;
}
return ans;
}
inline void mod(int& x) { if(x >= MOD) x -= MOD; }
int dp[2][maxm];
int main()
{
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
if(k == 0)
{
printf("%d\n", qpow(m, n));
return 0;
}
for(int i=1; i<=m; i++)
dp[0][i] = 1;
for(int i=1; i<n; i++)
{
int c = i & 1, p = c ^ 1, s = 0;
for(int j=k+1; j<=m; j++)
mod(s += dp[p][j]);
for(int j=1; j<=m; j++)
{
if(j > k) mod(s += dp[p][j - k]);
mod(dp[c][j] = s);
if(j + k <= m)
{
mod(s -= dp[p][j + k]);
if(s < 0) s += MOD;
}
}
}
int ans = 0, t = n & 1 ^ 1;
for(int i=1; i<=m; i++)
mod(ans += dp[t][i]);
printf("%d\n", ans);
return 0;
}
标签:AtCoder,cnt,le,输出,int,题解,LL,text,253
From: https://www.cnblogs.com/stanleys/p/18403502/abc253