HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）
A - Yay!
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
void solve()
{
string s;
cin >> s;
int n = s.size();
vector<int> cnt(30), pos(30);
for (int i = 0; i < n; i++)
{
cnt[s[i] - 'a']++;
pos[s[i] - 'a'] = i + 1;
}
for (int i = 0; i < 26; i++)
{
if (cnt[i] == 1)
{
cout << pos[i] << endl;
return;
}
}
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
B - Which is ahead?
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1), pos(110);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
pos[a[i]] = i;
}
int q;
cin >> q;
while (q--)
{
int l, r;
cin >> l >> r;
if (pos[l] < pos[r])
{
cout << l << endl;
}
else
{
cout << r << endl;
}
}
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
C - Many Replacement
解题思路:
每次变换，\(26\)个字母一个个看。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
void solve()
{
int n;
cin >> n;
string s;
cin >> s;
int q;
cin >> q;
vector<char> f(40);
for (int i = 0; i < 26; i++)
{
char c = i + 'a';
f[i] = c;
}
while (q--)
{
char a, b;
cin >> a >> b;
for (int i = 0; i < 26; i++)
{
if (f[i] == a)
{
f[i] = b;
}
}
}
for (auto c : s)
{
cout << f[c - 'a'];
}
cout << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
D - Square Pair
解题思路:
\(cnt[i]:表示在序列A中， 指数为奇数的质因子的乘积为i，这样的数字的个数。\)
平方数的质因子指数都是偶数。
对于两个平方数而言，相乘还是平方数。他们指数为奇数的质因子个数为零。
对于两个非平方数，只有他们指数为奇数的质因子相乘起来，这些质因子指数变为偶数才会变为平方数。由于奇数加奇数一定为偶数，我们不用记录指数具体是多少，只要记录其奇偶性即可。
最后计数时，\(0\)不止和自己可以组合，它还可以和任何其他数组合。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
void solve()
{
int n;
cin >> n;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
vector<ll> primes, minp(2e5 + 10);
for (int i = 2; i <= 2e5; i++)
{
if (!minp[i])
{
minp[i] = i;
primes.push_back(i);
}
for (auto p : primes)
{
if (i * p > 2e5)
{
break;
}
minp[i * p] = p;
if (i % p == 0)
{
break;
}
}
}
vector<ll> cnt(2e5 + 10);
// 平方数的质因子指数都是偶数。
for (int i = 1; i <= n; i++)
{
if (a[i] == 0)
{
cnt[a[i]]++;
continue;
}
// 只留下指数为奇数的质因子，奇数加奇数为偶数
for (auto p : primes)
{
if (p * p > a[i])
{
break;
}
while (a[i] % (p * p) == 0)
{
a[i] /= p * p;
}
}
cnt[a[i]]++;
}
ll ans = 0;
ll res = 0;
for (int i = 1; i <= 2e5; i++)
{
ans += cnt[i] * (cnt[i] - 1) / 2;
res += cnt[i];
}
ans += cnt[0] * (cnt[0] - 1) / 2;
// 这里特例，0和任何数相乘都是平方数
ans += cnt[0] * res;
cout << ans << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
E - Last Train
解题思路:
从点\(N\)开始跑最长路。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
void solve()
{
int n, m;
cin >> n >> m;
vector<vector<array<ll, 5>>> e(n + 10, vector<array<ll, 5>>());
for (int i = 1; i <= m; i++)
{
ll l, d, k, c, a, b;
cin >> l >> d >> k >> c >> a >> b;
e[b].push_back({a, l, d, k, c});
}
vector<ll> dist(n + 10, -1);
priority_queue<pii> q;
q.push({inf, n});
while (q.size())
{
auto [ds, u] = q.top();
q.pop();
if (dist[u] != -1)
{
continue;
}
dist[u] = ds;
for (auto [v, l, d, k, c] : e[u])
{
// 减去路途时间
ll t = ds - c;
if (t >= l)
{
// 最晚出发时间
t = l + min((k - 1), (t - l) / d) * d;
q.emplace(t, v);
}
}
}
for (int i = 1; i < n; i++)
{
if (dist[i] == -1)
{
puts("Unreachable");
}
else
{
cout << dist[i] << "\n";
}
}
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}