A
只要往相邻的里面插入 1 就好了。
const int MAXN = 1000 + 10;
int n, aa[MAXN];
std::vector<int> ans;
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
n = read();
rep (i, 1, n) aa[i] = read();
rep (i, 1, n - 1) {
// comp a[i], a[i + 1];
ans.push_back(aa[i]);
if (std::__gcd(aa[i], aa[i + 1]) != 1) ans.push_back(1);
}
ans.push_back(aa[n]);
printf("%d
", (int) ans.size() - n);
for (auto v : ans) printf("%d ", v);
puts("");
return 0;
}
B
暴力根据题意模拟即可。
然而我又双叒叕读错题了，甚至连图都看错了，然后重写了两遍 QAQ 浪费了不少时间
const int MAXN = 100 + 10;
int n, m;
std::vector<int> window[2], mid[2];
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
n = read(); m = read();
rep (i, 1, m) {
if (i <= 2 * n) {
window[(i - 1) & 1].push_back(i);
} else {
mid[(i - 1) & 1].push_back(i);
}
}
window[0].resize(n + 1); window[1].resize(n + 1);
mid[0].resize(n + 1); mid[1].resize(n + 1);
// rep (i, 0, n - 1) {
// printf("%d %d %d %d
", window[0][i], mid[0][i], mid[1][i], window[1][i]);
// }
for (int row = 0; row < n; ++row) {
if (mid[0][row]) printf("%d ", mid[0][row]);
if (window[0][row]) printf("%d ", window[0][row]);
if (mid[1][row]) printf("%d ", mid[1][row]);
if (window[1][row]) printf("%d ", window[1][row]);
}
puts("");
return 0;
}
C. Hard Process
一眼双指针或者二分答案。和之前做的一个题很相似。
写双指针不大熟练所以保底写了个二分。
const int MAXN = 3e5 + 10;
int n, aa[MAXN];
int k;
bool check(int mid) {
if (mid == 0) return true;
int cnt[2] = {0, 0};
for (int i = 1; i <= mid; ++i) {
++cnt[aa[i]];
}
for (int l = 1; l <= n; ++l) {
int r = l + mid - 1;
if (r > n) break;
if (cnt[0] <= k) return true;
// move
--cnt[aa[l]]; ++cnt[aa[r + 1]];
}
return false;
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
n = read(); k = read();
for (int i = 1; i <= n; ++i) aa[i] = read();
int l = 0, r = n, ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) { ans = mid; l = mid + 1; }
else r = mid - 1;
}
printf("%d
", ans);
int cnt[2] = {0, 0};
for (int i = 1; i <= ans; ++i) {
++cnt[aa[i]];
}
for (int l = 1; l <= n; ++l) {
int r = l + ans - 1;
if (r > n) break;
if (cnt[0] <= k) {
for (int i = l; i <= r; ++i) aa[i] = 1;
break;
}
// move
--cnt[aa[l]]; ++cnt[aa[r + 1]];
}
rep (i, 1, n) printf("%d ", aa[i]);
return 0;
}
D. Number of Parallelograms
本来以为是个计算几何然后打算直接 run 的……
停了几秒发现好像只是个幌子，因为没有三点共线，所以直接把所有直线按照斜率分类，统计有多少长度相同的，把答案除以 2 就做完了。
然后写了一个 long double 存斜率的发现在 map 里面会出问题……样例都过不去
接着意识到其实根本就不需要存实数斜率，直接存 {x1 - x0, y1 - y0} 相同的直线个数就可以了（假定 y1 - y0 >= 0）。
然后光荣 WA on 28，很快就意识到没处理 y1 - y0 = 0 时 x1 - x0 的符号问题，稍微改了一下就过了。
const int MAXN = 2000 + 10;
struct Vector {
lli x, y;
}; typedef Vector Point;
int n; Point pp[MAXN];
struct E {lli dx, dy;};
bool operator < (const E &x, const E &y) {
return x.dx == y.dx ? x.dy < y.dy : x.dx < y.dx;
}
std::map<E, lli> mp;
lli sqr(lli x) { return x * x; }
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
rep (i, 1, n) {
cin >> pp[i].x >> pp[i].y;
}
rep (i, 1, n) {
rep (j, i + 1, n) {
lli dx = pp[i].x - pp[j].x;
lli dy = pp[i].y - pp[j].y;
if (dy < 0) { dy = -dy; dx = -dx;}
if (dy == 0) dx = std::abs(dx);
// printf("dx = %d, dy = %d
", dx, dy);
++mp[{dx, dy}];
}
}
// puts("");
lli ans = 0;
for (auto v : mp) {
// printf("dx = %d, dy = %d, sz = %d
", v.first.dx, v.first.dy, v.second);
ans += 1ll * v.second * (v.second - 1) / 2ll;
}
cout << ans / 2 << endl;
return 0;
}
E. Different Subsets For All Tuples
计数题哈哈哈哈哈哈哈我不会数数怎么办
首先把空序列单独拿出来，一共 (m^n) 个，最后加上。然后计算非空序列。
然后（据说）有一个经典套路是按照子序列的长度分类计算，比如当前我要算的就是长度为 (i) 的子序列，有 (m^i) 个。记这 (i) 个数在原序列中的位置是 (p_1, p_2 dots p_i)，值分别为 (v_1, v_2 dots v_i)。
然后我们强制让 ([1, p_1 - 1]) 之间不出现 (v_1)，([p_1 + 1, p_2 - 1]) 之间不出现 (v_2)，以此类推，直到 ([p_i + 1, n]) 最后这一段才可以随便填。
可以列出一个式子：
[sum_{i = 1}^n m^i sum_{j = i}^n C_{j - 1}^{i - 1} (m - 1)^{j - i} m^{n - j}
]
第一个 (sum) 枚举长度 (i)，第二个 (sum) 枚举 (p_i) 的位置，(C_{j - 1}^{i - 1})，((m - 1)^{j - i}) 是那些被钦定不能出现某个 (v_i) 的位置选数的方案数，(m^{n - j}) 是最后那一段的选数方案数。
然后就是大力化简这个式子：
首先交换求和顺序，
[sum_{j = 1}^n sum_{i = 1}^j C_{j - 1}^{i - 1} (m - 1)^{j - i} m^{n - j + i}
]
然后把两个 (-1) 都搞掉并把后面的东西换个形式，
[sum_{j = 0}^{n - 1}m^{n - j} sum_{i = 0}^j C_{j}^{i} (m - 1)^{j - i}m^i
]
然后发现后面这玩意是个二项式定理，
[sum_{j = 0}^{n - 1}m^{n - j}(2m - 1)^j
]
直接算就好了。
const int HA = 1e9 + 7;
int n, m;
int fp(int a, int b, int p) {
int r = 1; while (b) { if (b & 1) r = 1ll * r * a % p; a = 1ll * a * a % p; b >>= 1; } return r;
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
n = read(); m = read();
int ans = fp(m, n, HA);
for (int j = 0; j <= n - 1; ++j) {
ans = (ans + 1ll * fp(m, n - j, HA) * fp(2 * m - 1, j, HA) % HA) % HA;
}
printf("%d
", ans);
return 0;
}
F
好像是个斜率优化 DP……