Warning: mysqli_query(): (HY000/1021): Disk full (/tmp/#sql_51b_2.MAI); waiting for someone to free some space... (errno: 28 "No space left on device") in /opt/lampp/htdocs/wordpress/wp-includes/wp-db.php on line 2033
AtCoder Beginner Contest 296()-其他 – 知识波

# AtCoder Beginner Contest 296()-其他

## AtCoder Beginner Contest 296()

### D – M<=ab

N,M<=1e12

``````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

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

``````
————————

### D – M<=ab

N,M<=1e12

``````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

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

``````