牛客小白月赛79
A. 数位dp？
解题思路:
如果开始就是偶数，那么直接不用变化。
如果开始不是偶数，那么个位数位上的数字一定不是偶数。换句话讲，只有个位数位上为偶数时，该数字才是偶数。
所以，一直闪末尾数位，直到该数位为偶数或者删完为止。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
int x;
cin >> x;
if (x & 1)
{
int res = x;
vector<int> v;
while (res)
{
v.push_back(res % 10);
res /= 10;
}
int suf = v.size();
// cout << suf << endl;
for (int i = 0; i < v.size(); i++)
{
// cout << i << ' ' << v[i] << endl;
if (v[i] & 1)
{
continue;
}
suf = i;
break;
}
cout << suf << endl;
}
else
{
puts("0");
}
}
int main()
{
int t = 1;
while (t--)
{
solve();
}
return 0;
}
B. 灵异背包？
解题思路:
奇数加奇数等于偶数，偶数加偶数等于偶数。
将所有数累加起来，记录奇数的个数和奇数的最小数。如果奇数有奇数个，那么减去一个最小的奇数。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
int n;
cin >> n;
vector<int> v;
ll ans = 0;
int minv = 1e9 + 10;
int cnt = 0;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
if (x & 1)
{
minv = min(minv, x);
cnt++;
}
ans += x;
}
if (cnt & 1)
{
ans -= minv;
}
cout << ans;
}
int main()
{
int t = 1;
while (t--)
{
solve();
}
return 0;
}
C. mex和gcd的乘积
解题思路:
如果\(mex = 0\),那么\(mex * gcd = 0\)。
如果\(mex = 1\),那么这段连续序列一定是沿着\(0\)向左右展开且其中不包含\(1\)。此时，随着展开长度的增加\(gcd\)只有可能变小，不会变大。所以此时\(mex * gcd\)的最大值就在\(0\)的左边或者右边。
如果\(mex \geq 2\),此时\(gcd = 1\).此时我们选取整个序列\(gcd\)不会变得更小，\(mex\)会取得最大。
注意:\(gcd(0,0) = 0\)。
代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
ll gcd(ll a, ll b)
{
return b ? gcd(b, a % b) : a;
}
void solve()
{
int n;
cin >> n;
vector<ll> v(n + 1);
vector<bool> st(n + 1);
vector<int> pos;
ll ans = 0;
ll g = 0;
for (int i = 1; i <= n; i++)
{
cin >> v[i];
st[v[i]] = true;
if (v[i] == 0)
{
pos.push_back(i);
}
g = gcd(g, v[i]);
}
ll amex = 0;
while (st[amex])
{
amex++;
}
if (amex == 0 || g == 0)
{
puts("0");
return;
}
ans = max(ans, amex);
for (auto idx : pos)
{
if ((idx - 1 >= 1 && idx - 1 <= n))
{
ans = max(ans, v[idx - 1]);
}
if ((idx + 1 >= 1 && idx + 1 <= n))
{
ans = max(ans, v[idx + 1]);
}
}
cout << ans;
}
int main()
{
int t = 1;
while (t--)
{
solve();
}
return 0;
}
D. 2^20
解题思路:
两种操作花费都为\(1\)：
操作一：加一。
操作二：乘二。
我们要用最少的花费将\(x\)变为\(2^{20}\)的倍数。
\(2^{20}\)的倍数等价于二进制表示最后20个数位都是0.
操作二等价于将二进制右移末尾补零。所以任何数最多进行20次操作二一定能得到\(2^{20}\)的倍数。
我们可以先全部进行操作二，用\(cnt\)记录这个花费上限。
加法可能一次性让末尾多出多个零（基于末尾有多个1的情况下），所以我们的操作一定是先加后乘。我们用之前记录的操作上限，枚举先加的次数，对答案进行更新。
时间复杂度:\(O(400T)\)
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
ll qmi(ll a, ll b)
{
ll res = 1;
while (b)
{
if (b & 1)
{
res = res * a;
}
a = a * a;
b >>= 1;
}
return res;
}
void solve()
{
ll bas = qmi(2, 20);
ll n;
cin >> n;
ll t = n;
int cnt = 0;
ll ans = 0;
while (t % bas)
{
t <<= 1;
cnt++;
}
ans = cnt;
for (int i = 0; i <= cnt; i++)
{
t = n;
t += i;
int m = cnt - i;
ll num = i;
while (m--)
{
if (t % bas == 0)
{
ans = min(ans, num);
break;
}
t <<= 1;
num++;
}
}
cout << ans << endl;
}
int main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
E. 重生之我是QQ邮箱
解题思路:
我们每次输入密码正确的概率为\(p\)。
只有\(7\)个位置的字符需要正确性判断，每个位置输入正确的概率为\(\frac{1}{6}\),所以,\(p = \frac{1}{6^7}\)。
每次输错了就要重新输入，直到输入正确位置，这是几何概型，期望为\(\frac{1}{p} = 6^7\)。
此时，我们就能得到没用道具前的期望时间，其个位数位为\(res = 6^7 \% 10\)。接下来我们要对其进行\(m\)次平方操作，得到最终的末尾值。
这里，我们发现这个最终数应当是\((6^7)^{2^m}\)的个位数位上的数字。但这里的数很大，无法直接运算。快速幂的运算性质也无法在过程中进行保留运算啥的。
这里通过观察，我们能发现一个性质，就是个位数的平方总会陷入一个无限循环。
\(0 \to 0 \to ...\)
\(1 \to 1 \to 1 \to ...\)
\(2 \to 4 \to 6 \to 6 \to ...\)
\(3 \to 9 \to 1 \to 1\to ...\)
\(4 \to 6 \to 6 \to ...\)
\(5 \to 5 \to ...\)
\(6 \to 6 \to ...\)
\(7 \to 9 \to 1\to 1\to ...\)
\(8 \to 4 \to 6 \to 6 \to ...\)
\(9 \to 1\to 1\to ...\)
所以直接暴力运算，当一个数出现第二次时，就是答案。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
ll qmi(ll a, ll b)
{
ll res = 1;
while (b)
{
if (b & 1)
{
res = res * a;
}
a = a * a;
b >>= 1;
}
return res;
}
void solve()
{
ll bas = qmi(6, 7);
ll n, m;
cin >> n >> m;
if (n < 7)
{
cout << -1 << endl;
return;
}
ll res = n * bas;
ll ans = res % 10;
vector<int> cnt(11);
for (int i = 1; i <= m; i++)
{
ans = ans * ans;
cnt[ans % 10]++;
if (cnt[ans % 10] == 2)
{
cout << ans % 10 << endl;
return;
}
}
cout << ans % 10 << endl;
}
int main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
int t = 1;
while (t--)
{
solve();
}
return 0;
}