B-密码学
Solution
模拟
注意:key长度需补齐至大于等于m
Code
#include<bits/stdc++.h> #define O_O ios::sync_with_stdio(false);cin.tie(0); cout.tie(0); using namespace std; typedef long long ll; const int maxn = 5000 + 10; int x[maxn], y[maxn]; string s[maxn]; map<char, int>mp; map<int, char>mmp; void init() { for (int i = 'a'; i <= 'z'; i++) mp[char(i)] = i - 'a',mmp[i - 'a']=i; for (int i = 'A'; i <= 'Z'; i++) mp[char(i)] = i - 'A' + 26,mmp[i - 'A' + 26]=i; } void func(int a, int b) { string sa = s[a]; string sb = s[b]; string actually; while (sa.length() < sb.length()) sa += sa; for (int i = 0; i < sb.length(); i++) { int z = mp[sb[i]] - mp[sa[i]]; while (z >= 52) z -= 52; while (z < 0) z += 52; actually += mmp[z]; } s[b] = actually; } int main(){ O_O; init(); int n, m; cin >> n >> m; for (int i = 1; i <= m; i++) cin >> x[i] >> y[i]; for (int i = 1; i <= n; i++) cin >> s[i]; for (int i = m; i >= 1; i--) func(x[i], y[i]); for (int i = 1; i <= n; i++) cout << s[i] << "\n"; return 0; }
H-最大公约数
Solution
寻找规律可知,答案为 在满足n>=a*k的条件下,所有质数a的乘积再乘上k。
且y一定存在,不存在输出为-1
注意:大数
Code
import math r=[1 for x in range(0,501)] for i in range(1,501): if i==1: r[i]=0 elif i>2: for j in range(2,int(math.sqrt(i))+1): if i%j==0: r[i]=0 break t=int(input()) for i in range(1,t+1): n,k=input().split() ans=int(k) n=int(n) k=int(k) z=int(n/k) for j in range(1,z+1): if r[j]==1 : ans*=j print(ans)
F-乘法
Solution
main():二分答案K,check小于等于K的乘积有多少个。
check():排序A、B,遍历A或B数组,使用lower-bound()、upper_bound()二分查找。
注意:数可为0或负数,需分类讨论
Code
#include<bits/stdc++.h> #define O_O ios::sync_with_stdio(false);cin.tie(0); cout.tie(0); using namespace std; typedef long long ll; const int maxn = 1e5 + 10; ll a[maxn], b[maxn]; int n, m; ll k; bool check(ll v) { ll res = 0; for (int i = 0; i < n; i++) { if (a[i] == 0) res += v < 0 ? m : 0; else if (a[i] < 0) res += lower_bound(b, b + m, ceil((double)v / a[i])) - b; else res += m - (upper_bound(b, b + m, floor((double)v / a[i])) - b); } return res<=k; } int main() { O_O; cin >> n >> m >> k; k--; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < m; i++) cin >> b[i]; sort(a, a + n); sort(b, b + m); ll l = -1e12, r = 1e12, ans; while (l <= r) { ll mid = (l + r) >> 1; if (check(mid)) r = mid - 1, ans = mid; else l = mid + 1; } cout << ans << "\n"; return 0; }