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");
}