牛客周賽 Round 98 [A-F]
A-小紅與奇數
題意
給你一個\(x\)（\(1 \leqslant x \leqslant 10^3\)）, 請問\(x\)加上自己的一個因子能否變成奇數
tag:暴力
Code (C++)
void whx()
{
int n;
vector a;
cin >> n;
for (int i = 1; i <= n / i; i ++ )
{
if (n % i == 0)
{
if (i != n / i) a.push_back(n / i);
a.push_back(i);
}
}
for (int i = 0; i < a.size(); i ++ )
{
if ((n + a[i]) % 2 != 0)
{
cout << "Yes\n";
return;
}
}
cout << "No\n";
}
思路
暴力，預處理出x的所有因子，然后一個一個試找到奇數輸出Yes，找不到輸出No
B-小紅與gcd三角形
題意
給你\(x\)，\(y\)，\(gcd(x, y)\)，判斷能否組成非退化三角形
tag：gcd性質，數學判斷三角形。
思路
記\(z=gcd(x, y)\)， 然后根據定義判斷兩邊之和大于第三條邊,又因為\(gcd(x, y)\)一定 \(\leqslant\) \(x\) 或 \(y\)。所以只要滿足\(z + y \leq x\)
Code (C++)
void whx()
{
cin >> x >> y;
int z = __gcd(x, y);
if (x < y) swap(x, y);
// z, y, x
if (z + y > x)
{
cout << "Yes\n";
}
else cout << "No\n";
}
C-小紅與red
題意
給你一個長度為n（\(1 \leqslant n \leqslant 10^3\)）的僅由'r'，'e'，'d'組成的字符串，可以把任意個字符修改為'r'，'e'，'d'。
請你用最少的修改次數構造出一個不存在任何相鄰相同字符的字符串。
tag: 分類討論。
思路
對于每一位是否要更換，以及更換為什么字符要結合前一位和后一位綜合考慮。
如果存在相鄰相同，更改靠后的字符，并且換成和前后都不同的字符。
Code (C++)
void whx()
{
cin >> n >> s;
for (int i = 1; i < n; i ++ )
{
if (s[i] == s[i - 1])
{
if (i == n - 1)
{
if (s[i] == 'r')
{
s[i] = 'e';
}
else if (s[i] == 'e')
{
s[i] = 'd';
}
else if (s[i] == 'd')
{
s[i] = 'r';
}
}
else
{
if (s[i] == 'r')
{
if (s[i + 1] == 'r' || s[i + 1] == 'e')
{
s[i] = 'd';
}
else if (s[i + 1] == 'd')
{
s[i] = 'e';
}
}
else if (s[i] == 'e')
{
if (s[i + 1] == 'r' || s[i + 1] == 'e')
{
s[i] = 'd';
}
else if (s[i + 1] == 'd')
{
s[i] = 'r';
}
}
else if (s[i] == 'd')
{
if (s[i + 1] == 'd' || s[i + 1] == 'e')
{
s[i] = 'r';
}
else if (s[i + 1] == 'r')
{
s[i] = 'e';
}
}
}
}
}
for (int i = 0; i < n; i ++ )
{
cout << s[i];
}
cout << "\n";
}
D-小紅與好數組
題意
定義一個[好數組]當且僅當相鄰元素不同且元素均為正整數。
現在輸入一個正整數n（\(1 \leqslant n \leqslant 20\)），找到所有滿足下述條件的數組：
- 數組的所有元素之和等于n
- 數組是[好數組]
按字典序從小到大的順序依次輸出所有滿足條件的數組
tag: 暴搜，dfs。
思路
\(n \leq 20\)，所以可以暴搜（分配n個數）所有情況，對于每個數給最后一位加1或者在末尾添加一位填上1，直到n次操作所有元素之和都是1，然后篩出滿足條件的數組。
復雜度：\(O(2^n*n)\)
Code (C++)
int n;
set> st;
bool check(vector& a)
{
int sum = 0;
for (int i = 0; i < a.size(); i ++ )
{
sum += a[i];
if (i)
{
if (a[i] == a[i - 1]) return false;
}
}
return sum == n;
}
void dfs(int u, vector& a)
{
// debug(u);
if (u > n)
{
if (check(a))
{
st.insert(a);
}
return;
}
if (a.size() > 0)
{
int v = a.back();
a[a.size() - 1] = ++ v;
dfs(u + 1, a);
a[a.size() - 1] = -- v;
}
a.push_back(1);
dfs(u + 1, a);
a.pop_back();
}
void whx()
{
cin >> n;
vector a;
dfs(1, a);
for (auto arr : st)
{
for (auto x : arr)
{
cout << x << " ";
}
cout << "\n";
}
}
E-小紅與gcd和sum
題意
定義一個長度為k的數組a的權值為 \(gcd(a1,a2,...,ak) * Sk\)， Sk表示前k項和。
請你從a中挑選出權值最大的非空子序列
tag：埃氏篩思想。
思路
預先開一個權值桶記錄每個數的權值，枚舉每個約數d[1, ma], 然后根據d來計算sum，只要是d的倍數就會對sum產生貢獻，利用埃氏篩的思想枚舉所有倍數同時從桶中拿出權值累加起來。
Code (C++)
void whx()
{
int n;
vector cnt(1e6 + 10, 0);
cin >> n;
int d = 0;
for (int i = 1, x; i <= n; i ++ )
{
cin >> x;
cnt[x] += x;
d = max(d, x);
}
// for (int i = 1; i <= n; i ++ ) cout << cnt[i] << " \n"[i == n];
int ans = 0;
for (int i = 1; i <= d; i ++ )
{
int sum = 0;
for (int j = i; j <= d; j += i)
{
sum += cnt[j];
}
// debug(i, sum);
ans = max(ans, sum * i);
}
cout << ans << "\n";
}
F-小紅與天使貓貓醬
題意
有一個無限長的數組\(a = \{22^2, 22^{22}, 22^{222},...\}\)，記下標從 1 開始，相應的b數組中 \(b_i = a_i的因子個數\)。設\(B_i\) 為\(b_i\)的前i項和，給你一個 \(n\)，求 \(B_n\)
tag：推式子
思路
\(22^2 = 2^2 * 11^2\) \(因數個數 = (2 + 1) * (2 + 1) = (2 + 1)^2\)
\(=>\) \(22^{k}\) \(因數個數 = (k + 1)^2\)
\(B_n = b_1 + b_2 + ... + b_n\)
\(= (2 + 1) ^ 2 + (22 + 1) ^ 2 + ..。 + (2...2{n個} + 1) ^ 2\)
\(= (2^2 + 22^2 + ... + 2...2^2) + 2*(2 + 22 + ... + 2...2) + n\)
\(= 4*(1^2 + 11^2 + ... + 1...1^2) + 4 * (1 + 11 + ... + 1...1) + n\)
設上式 $ = 4(S_n + T_n) + n$
利用高中數列知識推出來
\(S_n = \frac{10^{n+1} - 10 - 9i}{81}\)
\(T_n = \frac{n + \frac{100^{n + 1} - 100}{99} - 2(10^{n + 1} - 10)}{81}\)
\(B_n = \frac{\frac{400(100^n - 1)}{99} - \frac{280(10^n - 1)}{9} + 49n}{81}\)
題目中要求取模，所以計算除法時要用乘法逆元來處理。
Code (C++)
int n;
int ksm(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1) res = res * a % mod;
b >>= 1;
a = a * a % mod;
}
return res;
}
int inv(int x)
{
return ksm(x, mod - 2);
}
void whx()
{
cin >> n;
int fz, fm, a, b, c;
fm = 81;
a = 400 * (ksm(100, n) - 1) % mod * inv(99) % mod;
b = 280 * (ksm(10, n) - 1) % mod * inv(9) % mod;
c = 49 * (n % mod) % mod;
fz = (a + b + c) % mod;
cout << fz * inv(fm) % mod << "\n";
}
浙公網安備 33010602011771號