A.最小的數字
題目：
分析：
簡單列舉一下，找到第一個大于等于n的且是3的倍數的數
代碼：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
bool loop = true;
if (n % 3 == 0)
loop = false;
while (loop)
{
n ++;
if (n % 3 == 0)
loop = false;
}
cout << n;
return 0;
}
B.優美的GCD
題目:
分析:
根據題目條件，用兩個質數分別乘以n即可構造出答案，
代碼：
#include <bits/stdc++.h>
using namespace std;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n;
cin >> n;
cout << n * 2 << " " << n * 3 << endl;
}
return 0;
}
C.優美的序列
題目：
分析：
如果序列中存在相同項，由于下標差值最小是1，所以無解，
如果序列中不存在相同項，不妨對序列從小到大排序，由于兩兩各不相同，因此任意相鄰兩項的差的絕對值都至少是1，對任意1 <= i,j <= n都有|ai - aj| >= |i - j|成立
代碼：
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n;
cin >> n;
unordered_map<int, bool> mp;
unordered_map<int, int> mp2;
bool check = false;
for (int i = 0; i < n; i ++)
{
cin >> a[i];
if (mp[a[i]])
check = true;
mp[a[i]] = true;
}
if (check)
cout << -1 << endl;
else
{
sort(a, a + n);
for (int i = 0; i < n; i ++)
cout << a[i] << " ";
cout << endl;
}
}
return 0;
}
D/E Kevin喜歡零
題目：
分析：
hard版本：
x的末尾恰好有k個0，則x = p×10k = p×2k×5k且p與10互質，換句話說，設x中2的因子數位a, 5的因子數位b，當且僅當min(a, b) = k使得x的末尾恰好有k個0，因此，判斷一個區間內元素的累乘結果是否恰好有k個0，即看min(區間內因子2的總數，區間內因子5的總數)是否為k，這個查詢判斷可以用前綴和來做，接著就是列舉有多少個滿足此要求的區間，列舉區間我們可以采用固定一個端點然后列舉另一個端點的方式，不妨固定左端點，列舉右端點，由于我們統計的因子數量是非遞減的，因此可以二分右端點，設對于因子2的數量等于k的區間是[l2,r2],因子5的數量等于k的區間是[l5,r5]，由于右端點的位置要滿足所選區間最小值是k，因此右端點的選擇范圍是[max(l2,l5), max(r2,r5)]，最后統計所有滿足條件的區間數量即可，
代碼：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5;
int a[N];
LL s2[N], s5[N];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n, k;
cin >> n >> k;
for (int i = 0; i <= n; i ++)
{
s2[i] = s5[i] = 0;
}
for (int i = 1; i <= n; i ++)
{
cin >> a[i];
int m = a[i];
while (m % 2 == 0)
{
s2[i] ++;
m /= 2;
}
m = a[i];
while (m % 5 == 0)
{
s5[i] ++;
m /= 5;
}
s2[i] += s2[i - 1];
s5[i] += s5[i - 1];
}
LL res = 0;
for (int i = 1; i <= n; i ++)
{
LL t2 = s2[i - 1] + k, t5 = s5[i - 1] + k;
int l2 = lower_bound(s2, s2 + n + 1, t2) - s2, r2 = upper_bound(s2, s2 + n + 1, t2) - s2 - 1;
int l5 = lower_bound(s5, s5 + n + 1, t5) - s5, r5 = upper_bound(s5, s5 + n + 1, t5) - s5 - 1;
int l = max(l2, l5), r = max(r2, r5);
l = max(i, l); // 避免l列舉到i的左邊
if (l == n + 1) // l為n + 1則說明沒有滿足條件的右端點
continue;
res += r - l + 1;
}
cout << res << endl;
}
return 0;
}
Kevin的哈希構造
題目：
分析：
考慮dp，定義f[i][j][k]為前i個字符中有j個相同項且字串哈希值為k的方案是否可行，
初始：f[0][0][0] = 1
轉移：
①可以考慮用前面的值來推當前：f[i][j][k] |= f[i - 1][j - (s[i] == c)][(k - (c - 'a' + 1) × bi + p) % p]
②也可以考慮用當前的值來推后面的值：f[i + 1][j + (s[i] == c)][(k × b + (c - 'a' + 1)) % p] |= f[i][j][k]
本人選擇的是第二種方式，
目標狀態： f[n][k][hash]
至于記錄方案則可以用一個pre_h陣列記錄上一個方案的哈希值以及ch陣列記錄當前方案的選擇的字符，
代碼：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 55, M = 1010;
bool f[N][N][M];
LL pre_h[N][N][M];
char ch[N][N][M], s[N];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n, p, k;
LL b, H = 0;
cin >> n >> b >> p >> k;
cin >> s + 1;
memset(f, false, sizeof f);
f[0][0][0] = true;
for (int i = 1; i <= n; i ++)
H = (H * b + s[i] - 'a' + 1) % p;
for (int i = 0; i <= n; i ++)
{
for (int j = 0; j <= min(i, k); j ++)
{
for (int l = 0; l < p; l ++)
{
if (f[i][j][l])
{
for (char c = 'a'; c <= 'z'; c ++)
{
LL h2 = (l * b + (c - 'a' + 1)) % p;
if (s[i + 1] == c)
{
f[i + 1][j + 1][h2] = true;
pre_h[i + 1][j + 1][h2] = l;
ch[i + 1][j + 1][h2] = c;
}
else
{
f[i + 1][j][h2] = true;
pre_h[i + 1][j][h2] = l;
ch[i + 1][j][h2] = c;
}
}
}
}
}
}
if (!f[n][k][H])
cout << -1 << endl;
else
{
string res;
for (int i = n, j = k, h2 = H; i >= 1; i --)
{
res += ch[i][j][h2];
int tmp = h2;
h2 = pre_h[i][j][h2];
if (s[i] == ch[i][j][tmp])
j --;
}
reverse(res.begin(), res.end());
cout << res << endl;
}
}
return 0;
}
G.MoonLight的冒泡排序難題
題目：
分析：
代碼：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5, mod = 998244353;
LL f[N];
LL qmi(LL m, LL k)
{
LL res = 1, t = m;
while (k)
{
if (k & 1)
res = res * t % mod;
t = t * t % mod;
k >>= 1;
}
return res;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
for (int i = 1; i <= N; i ++)
{
f[i] = (f[i - 1] + (i - 1) * qmi(i, mod - 2)) % mod;
}
int t;
cin >> t;
while (t --)
{
int n;
cin >> n;
cout << f[n] << endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/553846.html
標籤：其他
下一篇：返回列表