京东3.18笔试

顺便贴一下我第二题和第三题代码

第二题：

#include<bits/stdc++.h>
# define DEBUG ios::sync_with_stdio(false);cin.tie(nullptr)
using namespace std;
typedef pair<int,int>PII;
typedef long long ll;
# define x first
# define y second
const int N = 200010; 
int n,a[N];
int f[N];

int main()
{
	DEBUG;
    cin >> n;
    ll ans = 0;
    for(int i=1;i<=100000;++i) f[i] = i-1;
    for(int i=3;i<=100000;++i){
        f[i] = min(f[i],f[i-1] + 1);
        int num = i;
        for(int j=2;j*j<=num;++j){
            if(num % j == 0) {
                f[i] = min(f[i],f[j] + f[num / j] + 1);
            }
        }
    }
    for(int i=1;i<=n;++i){
        cin >> a[i];
        ans += f[a[i]];
    }
    cout << ans << '\n';
	return 0;
} 

第三题：

#include<bits/stdc++.h>
# define DEBUG ios::sync_with_stdio(false);cin.tie(nullptr)
using namespace std;
typedef pair<int,int>PII;
typedef long long ll;
# define x first
# define y second
const int N = 200010;
char str[N];
int l[N];

int main()
{
	DEBUG;
    cin >> (str + 1);
    int n = strlen(str+1);
    stack<int> s;
    for(int i=1;i<=n;++i){
        if(str[i] == '(') s.push(i);
        else{
            if(s.empty()) continue;
            l[i] = s.top();
            s.pop();
        }
    }
    ll ans = 0;
    for(int i=1;i<=n;++i){
        if(str[i] == ')'){
            if(l[i] == 0) continue;
//             cout << i << " " << l[i] << "\n";
            ans += 1LL * l[i] * (n - i + 1) * 2;
        }
    }
    cout << ans << '\n';
	return 0;
}