Rank 663/3064. AC 7/12.
A. 阿宁的签到题
题意
根据分数输出等级。
思路
一门编程语言的基础之基础。
时间复杂度：\(O(1)\)
对应AC代码
import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long x = scanner.nextLong();
if(1 <= x && x <= 7) System.out.println("very easy");
else if(x <= 233) System.out.println("easy");
else if(x <= 10032) System.out.println("medium");
else if(x <= 114514) System.out.println("hard");
else if(x <= 1919810) System.out.println("very hard");
else System.out.println("can not imagine");
}
}送分还不写快点啊（（
B. 阿宁的倍数
题意
给定一个长度为 \(n\) 的数组 \(a\)，下标从 \(1\) 开始，对于 \(q\) 次操作，输出需要输出的内容。
操作分为两种：
- 修改操作：数组末尾增加一个数 \(x\)。
- 询问操作：对于所有 \(i>x\)，输出有多少 \(a_i\) 是 \(a_x\) 的倍数。
思路
我们考虑维护两个数组 \(tot,pre\)。
其中，\(tot[a[i]]\) 表示整个序列有多少数是 \(a[i]\) 的倍数，\(pre[i]\) 表示 \([0, i]\) 区间内有多少数是 \(a[i]\) 的倍数。
那么，对于每次查询的 \(x\)，输出 \(tot[a[x]]-pre[x]\) 即可。
我们来考虑一下这两个数组如何构建：
我们可以从前往后遍历，枚举 \(a[i]\) 的所有因数 \(j\)，将所有 \(tot[j]\) 加上 \(1\)，那么我们可以保证最后得到的 \(tot\) 是我们想要的数组，与此同时， 按照上述遍历方法，\(tot[a[i]]\) 就是 \(pre[i]\) 的值。
在修改操作时，我们只需在加入新加的数 \(x\) 的同时，更新 \(tot,pre\) 即可。
时间复杂度：\(O(n \sqrt n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 400010;
int a[N], tot[N], pre[N];
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, q;
cin >> n >> q;
for(int i=1;i<=n;i++){
cin >> a[i];
for(int j=1;j<=a[i]/j;j++){
if(a[i] % j == 0){
tot[j] ++;
if(j != a[i] / j) tot[a[i] / j] ++;
}
}
pre[i] = tot[a[i]];
}
while(q --){
int op, x;
cin >> op >> x;
if(op == 1){
a[++ n] = x;
for(int j=1;j<=a[n]/j;j++){
if(a[n] % j == 0){
tot[j] ++;
if(j != a[n] / j) tot[a[n] / j] ++;
}
}
pre[n] = tot[a[n]];
}else cout << tot[a[x]] - pre[x] << '\n';
}
return 0;
}
比较暴力但又不太暴力的做法
C. 阿宁的大背包
题意
给定背包的数量 \(n\)，\(n\) 个背包的大小构成一个 \(n\) 的排列，按照将相邻背包合成一个新的大背包的方式，经过 \(n-1\) 次合并，得到一个大背包。输出一个排列，满足最终背包最大，并输出值。
合并方式：\([a, b, c, d] \rightarrow [a + b , b + c , c + d]\)
思路
我们直接来考虑 \(5\) 个物品时的合并结果：
\(\begin{array}{l}>>[a, b, c, d, e] \\ => [a + b, b + c, c + d, d + e] \\ => [a + 2b + c, b + 2c + d, c + 2d + e] \\ => [a + 3b + 3c + d, b + 3c + 3d + e] \\ => [a + 4b + 6c + 4d + e] \end{array}\)
我们不妨留意一下从第二次合并后每项的系数，没错，就是杨辉三角。
于是，构建数组就非常明显了：我们只要按 中间向两侧递减 排列即可。
接着，考虑到数据范围并不大，于是下列两种方法均可行：
- 暴力合并；
- 计算出杨辉三角，作为系数和数组相乘。
考虑到暴力合并更不用脑子，这边采取方案 \(1\)。
时间复杂度：\(O(n ^ 2)\)
对应AC代码
import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;
public class Main{
public static void main(String[] args) throws Exception{
Console console = new Console();
int n = console.nextInt();
long mod = 1000000007;
int[] a = new int[n];
for(int i=0;i<n/2;i++) a[i] = i * 2 + 1;
if(n % 2 == 1) a[n / 2] = n;
for(int i=0;i<n/2;i++) a[n - i - 1] = (i + 1) * 2;
List<Integer> ans = new ArrayList<>();
for(int i=0;i<n;i++) ans.add(a[i]);
for(int t=n;t>=2;t--){
List<Integer> now = new ArrayList<>();
for(int i=0;i<t-1;i++) now.add((int)(((long) ans.get(i) + ans.get(i + 1)) % mod));
ans = now;
}
console.println(ans.get(0));
for(int i=0;i<n;i++) console.print(a[i] + " ");
console.close();
}
//快读模板，此处略去
//public static class Console implements Closeable {}
}优雅的暴力
D. 阿宁的毒瘤题
题意
给定一个字符串 \(s\)，修改任意一个字符为其他字符，让子序列 \(udu\) 的数量最小，子序列不一定连续。输出修改后的 \(s\)。
思路
不是 \(dp\) !!!!
首先，如果不删掉字符的话，做法就是很简单的 \(dp\)，但这题如果用 \(dp\) 解的话，会特别麻烦，且我无法证明正确性。
反而，这题是一道偏模拟的前缀和。
我们分别考虑删掉一个 \(d\) 和删掉一个 \(u\) 的代价：
- 对于一个 \(d\)，它的价值为 \(u_{pre} \times u_{suf}\)；
- 对于一个 \(u\)，它的价值为 \(ud_{pre} + du_{suf}\)。
于是，我们可以考虑前缀和的方法，统计正方向第 \(i\) 位前面有多少 \(u\)，反方向后面有多少 \(u\) 即可。
注意，不止有 \(u,d\) 这两个字符，不要偷懒不写 \(else\ if\)。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200010, inf = 0x3f3f3f3f;
int pre[N], ps[N], ss[N];
string s;
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> s;
int n = s.length();
int cu = 0;
for(int i=0;i<n;i++) if(s[i] == 'u') cu ++;
int maxx = 0, maxi = 0;
for(int i=0;i<n;i++){
if(i > 0) {
pre[i] = pre[i - 1];
ps[i] = ps[i - 1];
}
if(s[i] == 'u'){
pre[i] ++;
}else if(s[i] == 'd'){
if(maxx < pre[i] * (cu - pre[i])){
maxx = pre[i] * (cu - pre[i]);
maxi = i;
}
ps[i] += pre[i];
}
}
for(int i=n-1;i>=0;i--){
ss[i] = ss[i + 1];
if(s[i] == 'd') ss[i] += (cu - pre[i]);
else if(s[i] == 'u'){
if(maxx < ps[i] + ss[i]){
maxx = ps[i] + ss[i];
maxi = i;
}
}
}
for(int i=0;i<n;i++) cout << (maxi == i ? 'a' : s[i]);
}做了一个小时dp，最后10分钟才大彻大悟，人快哭出来力
E. 阿宁的生成树
待补充
F. 阿宁的二进制
题意
给定一个长度为 \(n\) 的数组 \(a\)，下标从 \(1\) 开始，定义 \(F(x)=cnt_1\ of\ binary\ x\)。如 \(F(5)=2\)。
对于独立的 \(q\) 次询问，定义一次操作为选定任意一个 \(i\)，执行 \(a_i=F(a_i)\)。给定操作数 \(k\) ，输出 整个数组的最大值 的最小值。
每次询问输出答案后，数组 \(a\) 恢复原样。
思路
我们不妨来考虑 \(1e9\) 范围内二进制下 \(1\) 最多的数，它总共有 \(30\) 个 \(1\)。
对于最大值 \(30\)，我们可以知道，第二次操作后最多只会有 \(4\) 个 \(1\)。
继续操作，剩下最多 \(2\) 个 \(1\)；
继续操作，剩下 \(1\) 个 \(1\)。
也就是说，对于任意 \(1e9\) 范围内的数，我们最多也只能进行 \(4\) 次操作，之后值就为固定的 \(1\)。
换句话说，题给 \(k\) 的范围是唬人的，真正 \(k\) 的范围应为 \(8 e 5\)。
那么，我们不妨先将所有询问都读入，然后桶排序一下，再枚举操作 \(p\) 次后的答案，若次数和询问相同，那么记录答案。我们不妨用大根堆来存储，让时间复杂度降到 \(k \log k\)。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200010;
pair<int, int> qs[N];
int ans[N];
int F(int x) {
int cnt = 0;
while (x != 0) {
if ((x & 1) == 1) cnt++;
x >>= 1;
}
return cnt;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, q;
cin >> n >> q;
priority_queue<int> pq;
for(int i=0;i<n;i++) {
int t;
cin >> t;
pq.emplace(t);
}
for(int i=0;i<q;i++){
int t;
cin >> t;
qs[i] = {t, i};
}
sort(qs, qs + q, [](pair<int, int> o1, pair<int, int> o2){return o1.first < o2.first;});
int i = 0, to = 0;
while(to < q){
int t = pq.top();
if(t == 1) break;
pq.pop();
i ++;
pq.push(F(t));
while(to < q && qs[to].first == i) ans[qs[to ++].second] = pq.top();
}
for(int t=0; t < q; t++) {
if(ans[t] == 0) cout << 1 << '\n';
else cout << ans[t] << '\n';
}
}自从上次做过某题后，老想着会不会可以收敛（（
G. 阿宁的整数配对
题意
给定一个长度为 \(n\) 的数组 \(a\)，选出 \(k\) 对整数，输出每对整数相乘并求和的最大值。
思路
排一个序，从两端取即可。
时间复杂度：\(O(n \log n)\)
对应AC代码
import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), k = scanner.nextInt();
long[] a = new long[n];
for(int i=0;i<n;i++) a[i] = scanner.nextInt();
Arrays.sort(a);
int l = 0, r = n - 1;
long ans = 0;
for(int i=0;i<k;i++){
if(a[l] * a[l + 1] > a[r] * a[r - 1]){
ans += a[l] * a[l + 1];
l += 2;
}else{
ans += a[r] * a[r - 1];
r -= 2;
}
}
System.out.println(ans);
}
}打卡打卡~
H. 阿宁讨伐虚空
题意
给定 \(x\) 个敌人，在 \([L,R]\) 内随机选一个 \(y\) ，若 \(y < x\)，那么敌人能被攻击到。输出能被攻击到的概率。
思路
如题，分类讨论算一下概率即可。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100010;
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int x, l, r;
cin >> x >> l >> r;
if(l > x - 1) cout << 0;
else if(r < x) cout << 1;
else cout << ((double) (x - l) / (double) (r - l + 1));
}简简单单签到题
I. 阿宁前往沙城
题意
给定一个无向图，定义操作为选定两条边，将一条边删除，并将另一条边的长度改为 \(1\)。在 操作可在任意时间可执行无限次 的条件下，输出 \(1\) 到 \(n\) 的最短路。
思路
很显然，从第二条路开始，我们直接把前面的路毁掉即可。
所以我们不妨直接把所有边改成 \(1\)，用 \(dijkstra\) 跑一遍最短路即可。
但得到的答案会出现一种特殊情况：最短路将所有边都覆盖了。
在该情况下，第一条只能用原来的长度替代了。
因此，直接套板子然后略微修改一下即可。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200010;
struct edge {
int v, w;
};
struct node {
int dis, u;
bool operator>(const node& a) const { return dis > a.dis; }
};
vector<edge> e[N];
int dis[N], vis[N], cnt[N];
priority_queue<node, vector<node>, greater<> > q;
void dijkstra(int s) {
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
q.push({0, s});
while (!q.empty()) {
int u = q.top().u;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto ed : e[u]) {
int v = ed.v, w = ed.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1;
q.push({dis[v], v});
}
}
}
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
int minn = 0x3f3f3f3f;
for(int i=0;i<m;i++){
int u, v, w;
cin >> u >> v >> w;
if(u == 1 || v == 1) minn = min(minn, w);
e[u].push_back({v, 1});
e[v].push_back({u, 1});
}
dijkstra(1);
cout << (cnt[n] < m ? cnt[n] : dis[n] + minn - 1);
}oi-wiki的板子真好用（划掉
J. 阿宁指指点点
待补充
K. 阿宁大战小红
待补充
L. 阿宁睡大觉
题意
给定一个 \(n\) 行 \(n-i+1\) 列的地图（正方形的左上角），每行的最后一个格子是美梦格子，除 \(m\) 个噩梦格子外，其余格子都可以通过，输出从 \((1,1)\) 走到美梦格子的方案总数。
注意，\(m \leq 10\)。
思路
这题有一个很明显的特点：障碍数远小于总格子数。
不考虑噩梦格子的话，总方案数很好求，即为 \(2^{n-1}\)。但若用类似于 \(dfs\) 的方法去枚举能走的路径，显然是过于复杂的。
有没有一种算法，可以用类似于取补集的方法来大大降低时间复杂度呢？
也许我们可以枚举不能走的路径，但暴力枚举也是不行的。
这里需要用到 容斥 。
对于两个噩梦格子，它们之间的方案数可以用组合数来求：
每条路径的节点数量是一致的，为 \((\Delta x - 1) + (\Delta y - 1)\)，而每条路径一定会有 \(\Delta x - 1\) 个节点是在 \(x\) 轴方向移动的，所以方案数即为 \(C_{\Delta x + \Delta y - 2}^{\Delta x - 1}\)。
于是，我们只需枚举所有选择即可，这里我们可以考虑用二进制进行状态压缩，直接用二进制位是否是 \(1\) 来考虑这个噩梦节点是否选上。当然也可以无脑递归套 \(for\)，但状压会更好写。
还有一个问题，若我们每次都算一遍两个节点的方案数，未免有些复杂，所以我们可以用 \(O1\) 复杂度的组合数求法。
容斥
我们来考虑三个集合，它们两两相交，且有一部分三个相交在一起，如下图：
对，这是一个韦恩图，而且我们可以很容易的得到下面这个式子：
\(|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C|\)
推广之后，对于 \(n\) 个集合的并集，我们只需按上述式子写，其中符号取决于选了几个集合，奇数为正偶数为负。
因而，对于所有噩梦格子的走法，利用容斥即可解决。
线性复杂度的组合数求法
显然，当数据量过大的时候，每次都用一遍 \(for\) 循环是不合理的，那么我们可以考虑预处理阶乘。
由于存在除法取模，我们需要用到乘法逆元，将除法取模转化为乘法取模。
逆元有一个很简单的求法，即费马小定理：对于 \(ab \equiv 1 \pmod p\)，乘法逆元 \(b = a ^ {p - 2}\)。
但每次用一遍快速幂也会提高时间复杂度，因而我们考虑线性求逆元，用到如下递推式：
\(inv[i] = (mod - mod / i) \times inv[mod\%i] \ \%mod\)
对于阶乘的逆元，满足 \(facInv[i] = facInv[i - 1] \times inv[i]\ \% mod\)
满足上述条件后，\(C_n^m = fac[n] \times facInv[m]\ \% mod \times facInv[n - m]\ \% mod\)。
线性求逆元的证明
时间复杂度：\(O(m \times 2 ^ m)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 400010, mod = 1e9 + 7;
pii a[N], b[N];
int n, m, inv[N], fac[N], facInv[N], pow2[N];
//O1复杂度求组合数
int c(int n, int m){
return fac[n] * facInv[m] % mod * facInv[n - m] % mod;
}
signed main() {
ios::sync_with_stdio(0);
cin >> n >> m;
for(int i=0;i<m;i++) cin >> a[i].first >> a[i].second;
inv[1] = fac[0] = fac[1] = facInv[0] = facInv[1] = pow2[0] = 1;
for(int i=2;i<=n*2;i++){
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
fac[i] = fac[i - 1] * i % mod;
facInv[i] = facInv[i - 1] * inv[i] % mod;
}
for(int i=1;i<=n;i++) pow2[i] = pow2[i - 1] * 2 % mod;
int ans = pow2[n - 1];
for(int i=1;i<(1 << m);i++){
int t = 0;
b[t ++] = {1, 1};
int sign = 1;
for(int j=0;j<m;j++){
if((i >> j) & 1){
b[t ++] = a[j];
sign = -sign;
}
}
sort(b, b + t);
int now = pow2[n - 1 - (b[t - 1].first + b[t - 1].second - 2)];
for(int j=1; j < t; j++){
if(b[j - 1].second <= b[j].second){
int x = b[j].first - b[j - 1].first + 1, y = b[j].second - b[j - 1].second + 1;
now = now * c(x + y - 2, x - 1) % mod;
}else{
now = 0;
break;
}
}
ans += sign * now;
}
ans = (ans % mod + mod) % mod;
cout << ans << '\n';
return 0;
}
有点震撼的说...