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;
}