寒假补题

H-牛牛看云_2022牛客寒假算法基础集训营1 (nowcoder.com)

  思路：

赛时和队友都想到了二分的做法，但是我觉得这个数据量1000 * 1000完全可以过啊，于是赛后就看到了下面这个代码，这个代码的思维量比二分大不少

既然要求所有任意数对与1000差值的绝对值的和，每个数的范围又是 0 - 1000，统计个数就行

b.collections 相当于是把 a 里的出现的每个 x 放到 map 里使得：map[x]++，得到的 map 就是 b

第一个双重循环：对于每个数值相异数对，拿一个 i 有 b[i] 种取法，拿一个 j 有 b[j] 种取法，公式考虑顺序，因此除以排列数A22，也就是2

第二个单重循环：对于数值不相异的数对，如果位置相异，当作数值相异计算，因此包含在二重循环中，位置相同则是自己和自己的贡献

此时不需要用 b 单独算组合数，直接扫一遍 a 数组就行

  代码：

 1 import collections
 2 n = int(input())
 3 a = list(map(int, input().split()))
 4 b = collections.Counter(a)
 5 ans = 0
 6 for i in range(1001):
 7     for j in range(1001):
 8         ans += b[i] * b[j] * abs(i + j - 1000) / 2
 9 for i in range(n):
10     ans += abs(a[i] - 500)
11 print(int(ans))

F-小沙的算数_2022牛客寒假算法基础集训营2 (nowcoder.com)

  思路：

乘法块分出来之后wa了，问题出在题目数据太大而进行了取模运算，取模和除法的顺序不能换

因此用逆元，但是我队当时三个人都wa了，逆元好像用的不对。。。

 1 #include
 2 using namespace std;
 3 typedef long long ll;
 4 const int mod = 1e9 + 7;
 5 const int N = 1e6 + 8;
 6 char s[N];
 7 ll num[N], pos[N], n, q, a[N];
 8 ll ksm(ll a, ll b) {
 9     ll ans = 1;
10     while (b) {
11         if (b & 1) (ans *= a) %= mod;
12         (a *= a) %= mod;
13         b >>= 1;
14     }
15     return ans;
16 }
17 int main() {
18     cin >> n >> q;
19     scanf("%s", s + 1);
20     for (int i = 1; i <= n; i++) cin >> a[i];
21     int cnt = 1;
22     num[1] = a[1];
23     pos[1] = 1;
24     //放到块里
25     for (int i = 2; i <= n; i++) {
26         if (s[i - 1] == '*') {
27             pos[i] = cnt;
28             num[cnt] = num[cnt] * a[i] % mod;
29         }
30         else {
31             num[++cnt] = a[i];
32             pos[i] = cnt;
33         }
34     }
35     ll ans = 0, x = 0, y = 0;
36     for (int i = 1; i <= cnt; i++)  (ans += num[i]) %= mod;
37 
38     while (q--) {
39         cin >> x >> y;
40         //先把答案里去掉这块
41         ans = (ans - num[pos[x]] + mod) % mod;
42         //更新这块，然后加回去就完事了
43         //原块的值 * 修改值 % mod / 原值 % mod 错到西伯利亚去了
44         //原块的值 * 原值的逆元 % mod * 修改值 % mod
45         //就记住，乘上 k 的逆元相当于除 k 就完事了
46         num[pos[x]] = num[pos[x]] * ksm(a[x], mod - 2) % mod * y % mod;
47         ans = (ans + num[pos[x]]) % mod;
48         a[x] = y;
49         cout << ans << endl;
50     }
51     return 0;
52 }

A-小沙的炉石_2022牛客寒假算法基础集训营2 (nowcoder.com)

思路：

想到了伤害可以通过调整牌的顺序改变，应该是一个区间，但是没想到是二分攻击次数

不过复杂度最低的解法其实也不是二分，直接判断就得了

使用所有攻击牌最低伤害是：+sp，atk，+sp，atk，...

这样的伤害是1 + 3 + 5 + ... + min(n, m)  = min(n, m) ** 2是个奇数等差数列

最大伤害是：+sp，+sp，... ，atk，atk，atk...

这样伤害是 (m + 1) + (m + 2) + ... + (m + n) = (2 * m + n + 1) * n / 2

代码：

 1 n,m=map(int,input().split())
 2 a=(min(n,m)+1)**2-1;
 3 b=min(n,m+1)
 4 c=(2*m+1+b)*b//2
 5 t=int(input())
 6 while t:
 7     t-=1
 8     x=int(input())
 9     if x==a or x>c:
10         print("NO")
11     else:
12         print("YES")

I-小沙的构造_2022牛客寒假算法基础集训营2 (nowcoder.com)

思路：看似字符串，其实模拟题

把字符分为两类：第一类自身对称，见代码 s1，第二类相互对称，见 s2 和 s3

然后贪心的模拟就ok了

代码：

 1 #include
 2 using namespace std;
 3 int n, m;
 4 char ans[1000005];
 5 string s1 = "\"!'*+-.08:=^_WTYUIOAHXVM|";
 6 string s2 = "<\\[{(";
 7 string s3 = ">/]})";
 8 int main() {
 9     cin >> n >> m;
10     if (m > n || m > 35) {
11         cout << -1 << endl;
12         return 0;
13     }
14     int l = 1, r = n;
15     int p = 0, q = 0;
16     while (m > 2 || (m == 2 && l + 1 == r)) {
17         cout << "p: " << p << " ans: " << ans + 1 << endl;
18         if (p >= 5) {
19             break;
20         }
21         ans[l++] = s2[p];
22         ans[r--] = s3[p];
23         m -= 2;
24         p++;
25     }
26     while (l <= r) {
27         if (m == 0) {
28             ans[l++] = ans[r--] = s1[q - 1];
29         }
30         else {
31             ans[l++] = ans[r--] = s1[q++];
32             m--;
33         }
34     }
35     if (m) {
36         cout << "-1" << endl;
37         return 0;
38     }
39     else {
40         cout << ans + 1;
41     }
42     return 0;
43 }

E-智乃的数字积木(easy version)_2022牛客寒假算法基础集训营3 (nowcoder.com)

思路：

先按照题意同色相邻的为一段进行分段

贪心使每段都能做大得到的结果就是最大

对每一段进行sort还是 log2(1e5) * 1e5

注意到 k 的范围只有10，算一下复杂度发现是10 * log2(1e5) * 1e5，原来又是个模拟题

写个 modify 函数调用 k 次就可以了

代码：

 1 #include 
 2 using namespace std;
 3 const int p = 1e9 + 7, N = 1e6 + 10;;
 4 int n, m, k, c[N];
 5 char s[N];
 6 int modify(){
 7     for (int i = 1; i <= n;) {
 8         int j = i;
 9         while (j <= n && c[j] == c[i]) j++;
10         sort(s + i, s + j);
11         reverse(s + i, s + j);
12         i = j;
13     }
14     int res = 0;
15     for (int i = 1; i <= n; i++) {
16         res = (1ll * res * 10 + s[i] - '0') % p;
17     }
18     return res;
19 }
20 int main(){
21     ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
22     cin >> n >> m >> k >> s + 1;
23     for (int i = 1; i <= n; i++) cin >> c[i];
24     cout << modify() << '\n';
25     //cout<
26     while (k--) {
27         int x, y; cin >> x >> y;
28         for (int i = 1; i <= n; i++) if (c[i] == x) c[i] = y;
29         cout << modify() << '\n';
30     }
31 }

I-智乃的密码_2022牛客寒假算法基础集训营3 (nowcoder.com)

思路：

尺取还是比较好想的，只是我的实现能力有点狗屎吧

下面复制一段大佬的代码，偶尔复习一下能学到东西

代码：（是个压行大佬的，我这辈子都写不出这种）

 1 #include
 2 #define int long long
 3 #define endl '\n'
 4 using namespace std;
 5 int judge(char c) {
 6     if (isupper(c)) return 1;
 7     if (islower(c)) return 2;
 8     if (isdigit(c)) return 3;
 9     return 4;
10 }
11 int a[5], ans;
12 void answer() { cout << ans; exit(0); }
13 int nm() { int res = 0; for (int i = 1; i <= 4; ++i) if (a[i]) res++; return res; }
14 signed main() {
15     int n, l = 1, L, R, r = 0, len = 0; string s;
16     cin >> n >> L >> R >> s; s = " " + s;
17     while (1) {
18         while (r - l + 1 < L || nm() < 3) {
19             r++; if (r > n) answer(); a[judge(s[r])]++;
20         }
21         while (r - l + 1 >= L && nm() >= 3 && l <= r) {
22             ans += max(min(n - r + 1, l - r + R), 0ll);
23             a[judge(s[l])]--; l++;
24         }
25     }
26     return 0;
27 }

L-智乃的数据库_2022牛客寒假算法基础集训营3 (nowcoder.com)

思路：

模拟题，待补

代码：

待补

I-爆炸的符卡洋洋洒洒_2022牛客寒假算法基础集训营4 (nowcoder.com)

思路：

稍作改动的01背包（给涛涛写）

注意取模的操作就行

代码：

 1 #include
 2 #define int long long
 3 using namespace std;
 4 const int N = 1100;
 5 int a[N], b[N], dp[N][N];
 6 
 7 signed main() {
 8     ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
 9     int n, k; cin >> n >> k;
10     for (int i = 1; i <= n; i++)  cin >> a[i] >> b[i];
11     memset(dp, -0x3f, sizeof dp);
12     dp[0][0] = 0;
13     for (int i=1;i <= n; i++)
14         for (int j = 0; j < k; j++)
15         dp[i][j] = max(dp[i - 1][j], dp[i - 1][(j - a[i] % k + k) % k] + b[i]);
16     if (dp[n][0] > 0) cout << dp[n][0];
17     else cout << -1;
18     return 0;
19 }

J-区间合数的最小公倍数_2022牛客寒假算法基础集训营4 (nowcoder.com)

思路：

假设把区间内每个合数都分解出来，比如说 {4, 6, 8, 9} 中，那么因子再某个数中出现次数最高有 {2: 3, 3:2}

则上述合数的最小公倍数则为 2**3 * 3**2

数据量只有30000，那我肯定用py啊

代码：

 1 cnt = 0
 2 mod = int(1e9 + 7)
 3 n = 30001
 4 #质数是0，合数是1
 5 st = [0 for i in range(30005)]
 6 prime = [0 for i in range(30005)]
 7 #指数筛
 8 for i in range(2, n+1):
 9     if not st[i]:
10         prime[cnt] = i
11         cnt += 1
12     for j in range(n):
13         if prime[j] > n / i: break
14         st[prime[j] * i] = 1
15         if i%prime[j] == 0: break
16 #模拟
17 l, r = map(int, input().split())
18 dic = {}
19 for i in range(l, r + 1):
20     if st[i]:
21         tmp = i
22         for j in prime:
23             if tmp == 1: break
24             tmp_cnt = 0
25             while tmp % j == 0 and tmp != 1:
26                 tmp /= j
27                 tmp_cnt += 1
28             if j not in dic or dic[j] < tmp_cnt:
29                 dic[j] = tmp_cnt
30 #累计答案
31 ans = 1
32 for i in dic:
33     ans = ans * (i**dic[i] % mod) % mod
34 if ans == 1:
35     print(-1)
36 else:
37     print(ans)

D-雪色光晕_2022牛客寒假算法基础集训营4 (nowcoder.com)

思路：

计算几何，点到射线的最短距离即是答案

下面是py题解（人生苦短，我用py），返校去实验室机子找找lmgg的板子再用c++补（挖坑）

题解：

 1 n=int(input())
 2 s = input()
 3 s=s.split(' ')
 4 x0=int(s[0])
 5 y_0=int(s[1])
 6 X=int(s[2])
 7 Y=int(s[3])
 8 ans=1e18
 9 for i in range(n):
10     s=input().split(' ')
11     x=int(s[0])
12     y=int(s[1])
13     A=x*x+y*y
14     B=2*(x*(x0-X)+y*(y_0-Y))
15     C=(x0-X)*(x0-X)+(y_0-Y)*(y_0-Y)
16     
17     if -B>=0and-B<=2*A:
18         ans=min(ans,(4*A*C-B*B)/(4*A))
19     else:
20         ans=min(ans,min(A+B+C,C))
21     x0+=x;
22     y_0+=y;
23 print(pow(ans,0.5))

D-数位小孩_2022牛客寒假算法基础集训营5 (nowcoder.com)

思路：

众所周知DP是一种暴力算法，既然是暴力，那DFS说不定也可以

相邻两数相加为质数，也就18以内的质数，数出来

记录 last 和当前位的值，如果不是质数就break，大剪枝

然后算一下复杂度，看似10**10，其实两个数的和为0 - 18， 一共19种，而只有7种是符合情况的质数

那么不正确且粗略的估算下，复杂度不会过分偏离（10 * 7 / 19）** 10  ≈ 4 ** 10 = 2 ** 20 ≈ 1e6

因此可以DFS。

但是我写不出优美的DFS，贴上某佬的代码以供学习

代码：

 1 #include 
 2 using namespace std;
 3 int a[20];
 4 long long l, r;
 5 int ans = 0;
 6 void dfs(long long x, int last, int flag) {
 7     if (x > r) return;
 8     if (x >= l && flag == 1) ans++;
 9     for (int i = 0; i <= 9; i++) {
10         if (a[i + last]) dfs(x * 10 + i, i, flag || i == 1);
11     }
12 }
13 
14 int main() {
15     cin >> l >> r;
16     a[2] = a[3] = a[5] = a[7] = a[11] = a[13] = a[17] = 1;
17     for (long long i = 1; i <= 9; i++) {
18         dfs(i, i, i == 1);
19     }
20     cout << ans << endl;
21 }

2022牛客寒假算法基础集训营6_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

思路：

好题，数学题，一开始思路被题目描述带偏了，搁那推公式

后面看题解发现都是暴力，算一下复杂度能过，暴力能过为什么要推公式呢？

1、首先注意到 a 的值仅有0，1，2

如果累乘中出现了0，那么该项为0；

如果累乘中出现了1，那么该项不变；

如果累乘中出现了2，那么该项 * 2；

显然，答案应该是累加了一堆 2 的幂，先把 p2[maxn]算出来备用；

并且，统计0，1，2的个数，存入a[3]中

2、当某项可以产生贡献时，该项是个n次多项式，其中k项为1，则有n-k项为2

从a[1]中选择k项，从a[2]中选择n - k项，组合数经典问题，因此提前求出逆元inv[maxn]备用

代码：

 1 #include
 2 #define int long long
 3 using namespace std;
 4 const int N = 1e7 + 10, mod = 998244353;
 5 
 6 int ksm(int a, int b){
 7     int ans = 1;
 8     while (b)    {
 9         if (b & 1)ans = ans * a % mod;
10         b >>= 1;
11         a = a * a % mod;
12     }
13     return ans;
14 }
15 
16 int f[N], inv[N], p2[N], a[5];
17 
18 signed main(){
19     int n, k; cin >> n >> k;
20     for (int i = 1; i <= n; i++){
21         int x; cin >> x;
22         a[x]++;
23     }
24     f[0] = inv[0] = p2[0] = 1;
25     for (int i = 1; i <= max(a[1], a[2]); i++){
26         p2[i] = p2[i - 1] * 2 % mod;
27         f[i] = f[i - 1] * i % mod;
28         inv[i] = inv[i - 1] * ksm(i, mod - 2) % mod;
29     }
30     int ans = 0;
31     for (int i = 0; i <= min({ k,a[2] }); i++){
32         int y = i, x = a[2];
33         int z = ((f[x] * inv[y] % mod) * inv[x - y] % mod) * p2[i] % mod;
34         x = a[1], y = k - i;
35         ans = ans + ((z * (f[x] * inv[y] % mod) % mod) * inv[x - y] % mod) % mod;
36         ans %= mod;
37     }
38     cout << ans << endl;
39 }

B-价值序列_2022牛客寒假算法基础集训营6 (nowcoder.com)

思路：

单调子串可以删掉中间的数（只保留波峰和波谷）不改变贡献

其余数可删可不删，也就是01的情况

找出所有可以删掉的数的数量 k，然后求 pow(2, k)即可

代码：

 1 #include 
 2 #define int long long
 3 using namespace std;
 4 const int maxn = 2e5 + 5;
 5 const int mod = 998244353;
 6 int arr[maxn], p2[maxn];
 7 
 8 signed main() {
 9     ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
10     p2[0] = 1;
11     for (int i = 1; i <= 100000; i++) p2[i] = p2[i - 1] * 2 % mod;
12     int t; cin >> t; while (t--) {
13         int n, res = 1; cin >> n;
14         for (int i = 1; i <= n; i++) cin >> arr[i];
15         for (int i = 1; i <= n; i++) {
16             int j = i;
17             while (j < n && arr[j + 1] == arr[i]) j++; //值不改变
18             if (i - 1 >= 1 && j + 1 <= n && //范围内
19                 (arr[i - 1] < arr[i] && arr[j + 1] > arr[i] || //单调上升 
20                 arr[i - 1] > arr[i] && arr[j + 1] < arr[i])) { //单调下降
21                 res = res * p2[2, j - i + 1] % mod;
22             }
23             else {
24                 res = res * (p2[2, j - i + 1] + mod - 1) % mod;
25             }
26             i = j;
27         }
28         cout << res << endl;
29     }
30     return 0;
31 }

D-删除子序列_2022牛客寒假算法基础集训营6 (nowcoder.com)

思路：

从左往右枚举当前下标的状态

贪心的想，删字符肯定是尽量靠左，给右边删除其他的留空间

动态规划的想，如果当前位置有机会为答案产生贡献，其左边一定可以组成前缀串

用一个一维数组记录被贡献串某下标可以组成的前缀串数量

由于没有重复字母，降低了难度，只需要26 * 1e6就能过

代码：

 1 #include 
 2 //#define int long long
 3 using namespace std;
 4 const int maxn = 2e5 + 5;
 5 int p[30];
 6 
 7 signed main() {
 8     ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
 9     int t; cin >> t; while (t--) {
10         memset(p, 0, sizeof p);
11         int n, m; cin >> n >> m;
12         string s1, s2; cin >> s1 >> s2;
13         for (int i = 0; s1[i]; i++) {
14             for (int j = 0; s2[j]; j++) {
15                 if (s1[i] == s2[j]) { // 有机会产生贡献
16                     if (j == 0) { // 作为开头或是延长左边字串的贡献
17                         p[j]++;
18                     }
19                     else if (p[j - 1]) { // 道路不断向前延伸（我在干什么啊
20                         p[j]++, p[j - 1]--;
21                     }
22                 }
23             }
24         }
25         cout << p[m - 1] << '\n';
26     }
27     return 0;
28 }

Problem - D - Codeforces

题意：

在给定的数组中，选择某相邻两数间的位置进行操作

操作：任意选择一个数，在任意位置插入两次，使串最终变成多组对称串

输出：

第一行：操作次数 x；

接下来 x 行：操作位置 p 和插入数 n

思路：

我们想象一个隔板，左边是当前拥有的，右边是还未进行操作的

用桶把左边的数装起来，对于某个数字 x，如果他的数量是1，那么无论如何进行操作，由于每次增加偶数个，因此不可能消掉 x

现在隔板向右移动一格，将一个数字加入了左边

如果加入数字后，这个桶里存在两个相同的数，那么肯定可以消除：凑回文串

那么我们可以通过一直进行凑回文的操作，保证左边的桶里都只有0或1个数（出现2时消除变成0）来构造

赛时想到了，但是我的代码水平，那就是一坨*

代码：

抄某个大佬的，有空照着模一模

 1 #include
 2 #define int long long
 3 #define PII pair
 4 using namespace std;
 5 
 6 const int N = 505;
 7 int a[N],tmp[N],n;
 8 map<int,int> mp;
 9 vector<int> v;
10 vector ans;
11 void solve(){
12     cin>>n;
13     for(int i=1;i<=n;i++)
14         cin>>a[i];
15     mp.clear();
16     for(int i=1;i<=n;i++) 
17         mp[a[i]]++;
18     bool flag = 1;
19     for(PII p:mp){
20         if(p.second%2==1){
21             flag=0;
22             break;
23         }
24     }
25     if(!flag){
26         cout<<"-1\n";
27         return ;
28     }
29     
30     v.clear();
31     ans.clear();
32     int now=1,last=0;
33     while(now<=n){
34         int index=-1;
35         for(int i=now+1;i<=n;i++){
36             if(a[i]==a[now]){
37                 index=i;
38                 break;
39             }
40         }
41         v.push_back((index-now)*2);//该子段配置完毕后的长度贡献
42         for(int i=now+1;i)
43             ans.push_back({last+index-now+i-now,a[i]});
44         
45         for(int i=now+1;i)
46             tmp[i]=a[index-(i-now)];
47         for(int i=now+2;i<=index;i++)
48             a[i]=tmp[i-1];
49         //以上操作为进行数组内的子段倒置
50             
51         last+=(index-now)*2;//最后一组配对完后的下标 
52         now+=2;//下一个待构造
53     }
54     cout<endl;
55     for(auto p:ans)
56         cout<" "<endl;
57     cout<endl;
58     for(auto val:v)
59         cout<" ";
60     cout<<endl;
61 }
62 
63 signed main(){
64     int t;
65     cin>>t;
66     while(t--){
67         solve();
68     }
69     return 0;
70 }