A.Alice and Bob
标签：博弈论，打表
题意：给定两堆石子(5e3)，每次可以取一堆石子中k(k>=1)，另一堆取k的整数倍个石子，不能取判负。
解法：根据sg函数打表发现规律，先手必负状态中每种石子数量只会出现一次，根据规律打第二个表，得到所有先手必负状态。
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 10000 + 10;
bool c[N], a[N];
vector<pair<int, int>> ans;
bool check(int x, int y) { return x % y == 0 || y % x == 0; }
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n = 5000;
for (int i = 2; i <= n; ++i) {
if (1) {
for (int j = 1; j <= n; ++j) {
if (!c[j]) {
bool flag = true;
for (auto k : ans) {
if (i - k.first == 0 || i + j - k.second == 0 ||
i + j - k.first == 0 || i - k.second == 0 ||
(i - k.first > 0 && i + j - k.second > 0 &&
check(i - k.first, i + j - k.second)) ||
(i + j - k.first > 0 && i - k.second > 0 &&
check(i + j - k.first, i - k.second))) {
flag = false;
break;
}
}
if (flag) {
c[j] = true;
ans.push_back(make_pair(i, i + j));
if (i + j <= 5000)
cout << "s[" << i << "] = " << i + j << ";" << endl;
a[i] = a[i + 1] = a[i + j] = a[i + j + 1] = true;
break;
}
}
}
}
}
return 0;
}B.Ball Dropping
标签：计算几何
#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
double r, a, b, h;
cin >> r >> a >> b >> h;
if (2 * r <= b) {
cout << "Drop\n";
} else {
cout << "Stuck\n";
double rad = atan((a - b) / 2.0 / h);
double ans = r / sin(rad) - b / 2.0 / tan(rad);
cout << fixed << setprecision(10) << ans << '\n';
}
return 0;
}D.Determine the Photo Position
标签：模拟
题意：给定n*n(2000)的01矩阵，把1*m(2000)的矩阵放入给定矩阵中，求方案数
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2000 + 10;
char a[N][N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, ans = 0;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
int c = 0;
for (int j = 0; j < n; ++j) {
cin >> a[i][j];
if (a[i][j] == '0') {
c++;
} else {
if (c >= m)
ans += c - m + 1;
c = 0;
}
}
if (c >= m)
ans += c - m + 1;
}
cout << ans << endl;
return 0;
}F.Find 3-friendly Integers
标签：模拟，思维
题意：T(10000)组数据，求[l, r](1e18)之间有多少个数满足存在子串为3的倍数
解法：发现当某个数大于等于100后，这个数必定满足条件，0-99可以模拟。
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int a[100];
LL fun(LL n) {
if (n <= 99)
return a[n];
else
return a[99] + n - 99;
}
bool check(int n) {
if (n < 10)
return n % 3 == 0;
if (n % 3 == 0)
return true;
if ((n / 10) % 3 == 0)
return true;
if ((n % 10) % 3 == 0)
return true;
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
for (int i = 1; i <= 99; ++i) {
a[i] = a[i - 1] + check(i);
}
while (t--) {
LL l, r;
cin >> l >> r;
cout << fun(r) - fun(l - 1) << endl;
}
return 0;
}H.Hash Function
标签：随机，模拟
题意：给定n(500000)个数，求最小的正整数使得所有的数对其取余结果不同。
解法：现场做法首先随机选择两个数，求出他们的差值，把差值的所有因数从答案集中删除，最后进行暴力判断。
赛后发现不用随机也能过，据说数据假了。
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 500000 + 10;
const int RAND = 100000;
int a[N];
bool b[N];
bool c[N];
void fun(int n) {
for (int i = 1; i <= sqrt(n); ++i) {
if (n % i == 0) {
b[i] = false;
b[n / i] = false;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a, a + n);
for (int i = n; i <= a[n - 1] + 1; ++i) {
b[i] = true;
}
srand(time(nullptr));
auto t = clock();
for (int i = 0; i < RAND; ++i) {
auto t1 = clock();
if ((t1 - t) / CLOCKS_PER_SEC >= 1)
break;
int l = rand() % n;
int r = rand() % n;
if (l > r)
swap(l, r);
fun(a[r] - a[l]);
}
for (int i = 0; i < n; i++)
c[a[i]] = 1;
for (int i = n; i <= a[n - 1] + 1; ++i) {
if (!b[i])
continue;
int fl = 0;
for (int j = 0; j < i; j++) {
int cnt = 0;
for (int k = 0; k <= 500000 / i && k * i + j <= 500000; k++)
if (c[k * i + j] == 1)
cnt++;
if (cnt > 1) {
fl = 1;
break;
}
}
if (fl == 0) {
cout << i << endl;
break;
}
}
return 0;
}K.Knowledge Test about Match
标签：随机
题意：给定随机n(sum_n<4e5)个数，重新排序，使得与0~n-1差的开方和尽可能小，允许4%的误差
解法：首先排序，随机交换两个数，如果交换后更优则保留
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
srand(time(NULL));
int n, x;
cin >> n;
set<int> a;
vector<int> b;
vector<int> c;
for (int i = 0; i < n; ++i)
a.insert(i);
for (int i = 0; i < n; ++i) {
cin >> x;
if (a.count(x)) {
a.erase(x);
} else {
b.push_back(x);
}
}
for (auto i : a)
c.push_back(i);
sort(b.begin(), b.end());
for (int j = 0; j < (n / 40000.0) * 10000000.0; ++j) {
int l = rand() % b.size(), r = rand() % b.size();
if (sqrt(abs(b[r] - c[l])) + sqrt(abs(b[l] - c[r])) -
sqrt(abs(b[l] - c[l])) - sqrt(abs(b[r] - c[r])) <
0) {
auto tmp = b[l];
b[l] = b[r];
b[r] = tmp;
}
}
int p = 0;
for (int i = 0; i < n; ++i) {
if (a.count(i)) {
cout << b[p++] << " ";
} else {
cout << i << " ";
}
}
cout << endl;
}
return 0;
}
Comments NOTHING