AtCoder Beginner Contest 280
A.Pawn on a Grid
题目大意
输入一个由.
和#
组成的方阵
输出有几个#
解题思路
签到题
具体代码
#include <bits/stdc++.h>
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n, m;
std::cin >> n >> m;
int res = 0;
for (int i = 1; i <= n * m; ++i)
{
char t;
std::cin >> t;
res += t == '#';
}
std::cout << res << '\n';
return 0;
}
B.Inverse Prefix Sum
题目大意
给定一个长度为$n$的数列$S$
构造长度为$n$的数列$a$,使得对于任意$k(1\leq k\leq n)$,有$S_k=\sum_{i=1}^{k}{a_i}$
解题思路
显然数列$S$的差分数列就是需要的数列$a$
具体代码
#include <bits/stdc++.h>
const int N = 15;
int a[N];
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n;
std::cin >> n;
for (int i = 1; i <= n; ++i)
{
std::cin >> a[i];
std::cout << a[i] - a[i - 1] << ' ';
}
return 0;
}
C.Extra Character
题目大意
输入字符串$s$和$t$
保证$t$是由在$s$中任意一个位置插入了一个字符得到的
找出插入的这个字符是$t$中第几个字符
解题思路
扫描两个字符串,不一样的位置肯定就是插入的位置
如果扫完了$s$还没找到,那肯定就是$t$的最后一位
具体代码
#include <bits/stdc++.h>
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::string s, t;
std::cin >> s >> t;
for (int i = 0; i < s.size(); ++i)
{
if (s[i] != t[i])
{
std::cout << i + 1 << '\n';
return 0;
}
}
std::cout << t.size() << '\n';
return 0;
}
D.Factorial and Multiple
题目大意
输入$k(2\leq k\leq 10^{12})$
找出最小的$n$,满足$n!$是$k$的整数倍
解题思路
因为$k\geq 2$,由算术基本定理,$k={p_1}^{c_1}{p_2}^{c_2}\cdots {p_m}^{c_m}$
其中$c_i$都是正整数,$p_i$都是质数,且$p_1<p_2<\cdots <p_m$
很容易想到可以正常枚举$n$,对于每一个$n$,让$k$除掉它和$k$的最大公因数
这样$k$被除到$1$的时候就得到了$n$
代码如下,复杂度$O(nlogn)$
LL n = 1;
while (k >= 2)
{
k /= std::__gcd(k, n);
++n;
}
--n;
std::cout << n << '\n';
但是因为这题$k$的范围到了$10^{12}$
可以想到当$k$是一个大质数的时候,$n$也会一直枚举到很大,就会超时
或者$k$的质因子有一个大质数的时候,$n$也会一直枚举到很大
解决方法也很简单,因为对于一个整数$N$,最多只有一个大于$\sqrt{N}$的质因子
所以$k$最多只有一个大于$10^6$的质因子
所以只要先试除看有没有这样的质因子即可
有的话直接输出这个质因子
没有的话就按原来的方法做
具体代码
#include <bits/stdc++.h>
typedef long long LL;
LL k;
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> k;
LL backup = k;
for (int i = 2; i <= 1e6; ++i)
while (backup % i == 0)
backup /= i;
if (backup > 1)
{
std::cout << backup << '\n';
return 0;
}
LL n = 1;
while (k >= 2)
{
k /= std::__gcd(k, n);
++n;
}
--n;
std::cout << n << '\n';
return 0;
}
E.Critical Hit
题目大意
有一个怪兽,生命值为$n$
主人公会一直攻击怪兽,直到怪兽生命值变为非正数
主人公每次攻击怪兽,有$\frac{p}{100}$的概率造成$2$点伤害,$1-\frac{p}{100}$的概率造成$1$点伤害
问打倒怪兽需要的攻击次数的期望(模$998244353$意义下)
解题思路
作为$E$题好像有点太模板了
设$dp_i$为怪兽生命值为$i$,打倒怪兽需要的攻击次数的期望
初始状态$dp_0=0,dp_1=1$
转移方程$dp_i=1+(dp_{i-2}\times \frac{p}{100}+dp_{i-1}\times \frac{100-p}{100})$
取模直接用了自动取模类$ModInt$
具体代码
#include <bits/stdc++.h>
typedef long long LL;
const int MOD = 998244353;
template <int T>
struct ModInt
{
const static int MD = T;
int x;
ModInt(LL x = 0) : x(x % MD) {}
int get() { return x; }
ModInt operator+(const ModInt &that) const
{
int x0 = x + that.x;
return ModInt(x0 < MD ? x0 : x0 - MD);
}
ModInt operator-(const ModInt &that) const
{
int x0 = x - that.x;
return ModInt(x0 < MD ? x0 + MD : x0);
}
ModInt operator*(const ModInt &that) const { return ModInt((long long)x * that.x % MD); }
ModInt operator/(const ModInt &that) const { return *this * that.inverse(); }
void operator+=(const ModInt &that)
{
x += that.x;
if (x >= MD)
x -= MD;
}
void operator-=(const ModInt &that)
{
x -= that.x;
if (x < 0)
x += MD;
}
void operator*=(const ModInt &that) { x = (long long)x * that.x % MD; }
void operator/=(const ModInt &that) { *this = *this / that; }
ModInt inverse() const
{
int a = x, b = MD, u = 1, v = 0;
while (b)
{
int t = a / b;
a -= t * b;
std::swap(a, b);
u -= t * v;
std::swap(u, v);
}
if (u < 0)
u += MD;
return u;
}
};
typedef ModInt<MOD> mint;
const int N = 2e5 + 10;
int n, p;
mint dp[N];
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> n >> p;
dp[0] = 0, dp[1] = 1;
for (int i = 2; i <= n; ++i)
dp[i] = mint{1} + (dp[i - 2] * mint{p} / mint{100} + dp[i - 1] * mint{(100 - p)} / mint{100});
std::cout << dp[n].get() << '\n';
return 0;
}
F.Pay or Receive
题目大意
$n$个城镇,$m$条路
若$u$到$v$有一条边权为$w$的路
则$v$到$u$有一条边权为$-w$的路
回答$q$个询问
每个询问给定$x$和$y$
输出$x$和$y$间的最长路径(长度就是边权和)
如果$x$和$y$间不连通,输出$nan$
如果$x$和$y$间的最长路径可以是无穷大,输出$inf$
解题思路
$nan$的情况很好说,并查集判连通分量就行
然后剩下两种情况,$x$和$y$一定在同一个连通分量
$inf$的情况显然就是连通分量里有了一个正环
注意这里的正环不是说环里每一条边都是正权,而是这个环的边权和为正
而且一个连通分量里如果有一个正环,那么这个连通分量里任意两点的最长路径都是无穷大(不停走正环)
想清这两点很重要
那么该怎么判一个连通分量里是否有正环呢
基于这个图的特殊性质,可以这样判正环:
以这个连通分量里地任意一点作为起点,正常地$bfs$,若到达某一点的距离不唯一,则说明存在正环
简单证明见下图:
正环问题也解决了
剩下的情况就是正常求最长路径了
还是因为此题中图的性质,正环的情况已经排掉了两点间距离不唯一的情况
因此一个连通分量内部任意两点的距离是唯一的,不存在是不是最长或最短的区别
那么我们可以在判正环的$bfs$过程中,顺便处理出连通分量的代表节点$start$到连通分量内所有点的距离
那么$x$到$y$的距离就是$dist[y]-dist[x]$了(实际意义是$x$走到$start$,再由$start$走到$y$)
感觉这个题的模型还挺有趣的,可以记一下
具体代码
#include <bits/stdc++.h>
typedef std::pair<int, int> PII;
typedef long long LL;
const int N = 1e5 + 10;
int n, m, q;
int p[N];
std::vector<PII> e[N];
bool vis[N];
LL dist[N];
bool has_positive_cycle[N];
int find(int x)
{
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
void bfs(int start)
{
vis[start] = true;
dist[start] = 0;
std::queue<int> q;
q.push(start);
while (q.size())
{
auto u = q.front();
q.pop();
for (auto it : e[u])
{
int v = it.first, w = it.second;
if (dist[v] == 0xfefefefefefefefe)
{
dist[v] = dist[u] + w;
q.push(v);
vis[v] = true;
}
else if (dist[u] + w != dist[v])
{
has_positive_cycle[start] = true;
return;
}
}
}
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> n >> m >> q;
for (int i = 1; i <= n; ++i)
p[i] = i;
for (int i = 1; i <= m; ++i)
{
int u, v, w;
std::cin >> u >> v >> w;
e[u].push_back({v, w});
e[v].push_back({u, -w});
p[find(u)] = find(v);
}
memset(dist, 0xfe, sizeof dist);
for (int i = 1; i <= n; ++i)
if (!vis[find(i)])
bfs(find(i));
for (int i = 1; i <= q; ++i)
{
int u, v;
std::cin >> u >> v;
if (find(u) != find(v))
std::cout << "nan" << '\n';
else if (has_positive_cycle[find(u)])
std::cout << "inf" << '\n';
else
std::cout << dist[v] - dist[u] << '\n';
}
return 0;
}