A - 孤独的数组
大意
每一可以选择一个下标i和数k, 使得$a_i = a_i * k$, 问经过多少次操作可以使数组相邻两个值的最大公约数为1, 否则输出-1
思路
无论经过多少次相乘, 两个数之间的最大公约数只会增大, 所以可能的结果只能为0或-1.
而相邻两个数之间均互质时, 输出0
代码
#include <iostream>
using namespace std;
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int main() {
int n;
cin >> n;
int a = 1;
for (int i = 1; i <= n; i ++ ) {
int x;
cin >> x;
if (gcd(a, x) != 1) {
puts("-1");
return 0;
}
a = x;
}
puts("0");
return 0;
}
B - 博弈大师
大意
有n个苹果, 第i轮取i个苹果, 第一个不够取的人失败, 同时每个人有卡牌, 卡牌可以使当前角色互换. 问最后谁取得胜利
思路
如果卡牌足够多的话, 那么是可以决定胜利的. 否则相等, 就相当于都没有卡牌, 按照要求计算轮到谁.
代码
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;
void solve() {
LL n, a, b;
cin >> n >> a >> b;
bool ok;
if (a == b) {
ok = ! ((LL)((sqrt(1ll + 8ll * n) - 1) / 2ll) & 1ll);
} else if (a > b) ok = true;
else ok = false;
cout << (ok ? "niuniu" : "niumei") << endl;
}
int main() {
int T;
cin >> T;
while (T -- ) {
solve();
}
return 0;
}
C - 可疑的区间
大意
问长度为len的有趣值和权重最大的区间有多少个.
有趣值: 和当前区间有交集的区间个数.
权重: 和当前区间有交集的区间的编号和.
思路
题目要求的区间不是给定的区间. 所以, 所有可能的区间都需要查看.
对于题目给定的区间[l, r], 和他有交集的合法区间为[l - len + 1, l]到[r, r + len - 1].
因为已经有区间长度的限制, 所以我们只需要固定一个端点, 那么另外一个端点也就固定了.
以左端点为例, dp1表示以左端点开始的长度为len的区间有趣值, dp2就是权重.
那么对于题目给定的区间[l, r], 也就是[l - len + 1, r]会 + 1, + i. 如此便是求出了每个区间的值, 剩下就是求最大值.
代码
#include <iostream>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
const int N = 5e6 + 10;
int n, len;
LL dp1[N], dp2[N];
int main() {
cin >> n >> len;
for (int i = 1; i <= n; i ++ ) {
int a, b;
cin >> a >> b;
dp1[max(1, a - len + 1)] ++;
dp1[b + 1] --;
dp2[max(1, a - len + 1)] += i;
dp2[b + 1] -= i;
}
for (int i = 1; i < N; i ++ ) {
dp1[i] += dp1[i - 1];
dp2[i] += dp2[i - 1];
}
LL a, b, cnt;
a = b = cnt = 0;
for (int i = 1; i < N; i ++ ) {
if (dp1[i] > a) {
a = dp1[i];
b = dp2[i];
cnt = 1;
}
else if (dp1[i] == a) {
if (dp2[i] > b) {
b = dp2[i];
cnt = 1;
}
else if (dp2[i] == b) cnt ++;
}
}
cout << cnt << endl;
return 0;
}
D - 交替加乘
大意
一种新的计算方式, +*交替, 问在某种排序下, 结构的最大值为多少
思路
在枚举几次发现之后发现, 乘法应该和较大的数搭配, 而且越大的数越应该后面乘(很明显的样子).
加法就和较小数搭配, 较大数在前面加, 这样的乘的次数就多.
代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, mod = 1e9 + 7;
int n;
LL a[N];
int main() {
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
sort(a + 1, a + n + 1);
LL ans = 1;
for (int l = n / 2, r = n / 2 + 1; r <= n; l -- , r ++)
ans = (ans * a[r] + a[l]) % mod;
cout << ans << endl;
return 0;
}
E - 或与异或
大意
两个数和目标值, 每次可以将两个数中的某个变为这两个数的与, 或, 异或.
思路
爆搜?
什么逢二必贪在这里不太起作用, 每一次操作不仅会导致当前位改变, 其他位置也会有不同的变化.
代码
#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PII;
LL a, b, c;
queue<PII> q;
set<PII> st;
void push(LL a, LL b) {
if (a > b) swap(a, b);
if (st.count({ a, b })) return ;
q.push({ a, b });
}
void solve() {
while (q.size()) q.pop();
st.clear();
cin >> a >> b >> c;
push(a, b);
while (!q.empty()) {
auto t = q.front();
q.pop();
if (t.first == c || t.second == c) {
puts("YES");
return ;
}
if (st.count(t)) continue;
st.insert(t);
LL x = t.first | t.second, y = t.first & t.second, z = t.first ^ t.second;
push(x, t.first);
push(y, t.first);
push(z, t.first);
push(x, t.second);
push(y, t.second);
push(z, t.second);
}
puts("NO");
}
int main() {
int T;
cin >> T;
while (T --) {
solve();
}
return 0;
}
F - 孤独的树
大意
A题的进阶版, 除去是去掉自己的因子之外, 还要在树上进行.
思路
考虑到一条边上, 如果两个点的最大公约数不为1, 那么至少要有一个点进行除法.
应该是谁除呢? 考虑一个极端: 父亲和叶子节点. 最好在父亲身上除, 而父亲身上除掉之后, 可能会对父亲的父亲也有影响. 所以, 我们直接递归到叶子节点, 然后从父亲身上出去公因子.
另外每个因子要除多少次也要进行预处理.
代码
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int n;
int w[N];
vector<int> g[N];
int p[N], idx;
bool st[N];
int cnt[N];
int ans = 0;
void init() {
for (int i = 2; i < N; i ++ ) {
if (!st[i]) {
p[idx ++] = i;
cnt[i] = 1;
}
for (int j = 0; p[j] * i < N; j ++ ) {
st[p[j] * i] = true;
cnt[p[j] * i] = cnt[i] + 1;
if (i % p[j] == 0) break;
}
}
}
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
void dfs(int u, int fa) {
for (auto i : g[u]) {
if (i == fa) continue;
dfs(i, u);
int t = gcd(w[u], w[i]);
ans += cnt[t];
w[u] /= t;
}
}
int main() {
init();
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> w[i];
for (int i = 1; i < n; i ++ ) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1, -1);
cout << ans << endl;
return 0;
}