AtCoder Beginner Contest 296
好久没写题解了~~
D - M<=ab
题意就是给定N,M, 求一个最小的数x同时满足x>=M且x=a*b(a<=N,b<=N);
N,M<=1e12
开始脑瘫想了二分,仔细一想很明显x不满足单调性,想了下暴力的时间复杂度巨大...
纠结了一会,发现因子最大是sqrt(m),只需要枚举一下因子x,然后求出最小的y使得M<=x*y最小, 推一下就会发现y=(m/i)上取整。
时间负责度: O(sqrt(m)), 不超过1e6
注意:枚举到sqrt(m)+1, wa4 -_-
void solve(int Tcase = 1) {
ll n, m;
cin >> n >> m;
ll ans = 1e18;
for (ll i = 1; i <= min(n, (ll)sqrt(m) + 1); i++) {
ll j = m / i + (m % i != 0);
if (j > n) continue;
if (i * j >= m) ans = min(ans, i * j);
}
cout << (ans==1e18?-1:ans) << '\n';
}
E - Transition Game
简单来说,就是a给出的数字x要在一个环内,如果x不在一个环内,那么b可以给一个巨大的循环次数,那么x永远不可能出现在黑板上,如果x在环内,那么无论你给出什么数字,最终只要一直循环便可恰好停留在黑板上。
想到拓扑排序,那么问题就解决了。
const int N = 200010;
int n;
vec<int> e[N];
void solve(int Tcase = 1) {
cin >> n;
vec<int> a(n + 1, 0);
vec<int> idg(n + 1, 0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
idg[a[i]]++;
e[i].pb(a[i]);
}
queue<int> que;
for (int i = 1; i <= n; i++) {
if (!idg[i]) que.push(i);
}
int ans = n;
while (!que.empty()) {
int t = que.front();
que.pop();
ans--;
for (auto v : e[t]) {
if (--idg[v] == 0) {
que.push(v);
}
}
}
cout << ans << '\n';
}
F - Simultaneous Swap
满足:
-
数组中各个数出现次数相同
-
如果有数组中有相同的数,那么就一定可以
例如: A:1 1 2 3 4 5 i j B:5 2 4 3 1 1 k 通过保持a数组不变,不停的调整b数组
-
否则,数组中每个数各不相同,那么考虑,每次交换会产生什么影响
会改变a和b中的逆序数对数量 A: +1 -1 -1 +1 B: +1 -1 +1 -1 2 -2 0 0 会发现,变化都是以+、-2或0为单位;(x) 而最终a和b的逆序对是相等的。 所以a和b的初始逆序对的奇偶性要相等,因为条件(x)
那么问题就解决了,归并排序或者数据结构维护一下逆序对即可。
const int N = 200010;
int c[N];
int n;
void modify (int x, int y) {
for (x; x <= n; x += x & -x) c[x] += y;
}
int query(int x) {
int s = 0;
for (x; x; x -= x & -x) s += c[x];
return s;
}
void solve(int Tcase = 1) {
cin >> n;
vec<int> a(n), b(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
}
ll res1 = 0, res2 = 0;
for (int i = n - 1; i >= 0; i--) {
modify(a[i], 1);
res1 += query(a[i] - 1);
}
for (int i = 1; i <= n; i++) c[i] = 0;
for (int i = n - 1; i >= 0; i--) {
modify(b[i], 1);
res2 += query(b[i] - 1);
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
bool f = 0;
for (int i = 0; i < n; i++) {
if (a[i] != b[i]) {
cout << "No\n";
return ;
}
if (i && a[i] == a[i - 1]) {
f = 1;
}
}
if (f) {
cout << "Yes\n";
return ;
}
cout << ((res1+res2)%2==0? "Yes":"No");
}
- Beginner AtCoder Contest 296beginner atcoder contest 296 contest programming beginner atcoder beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 310 beginner atcoder contest 315