8.26 oppo笔试题解

后端T1

O(n^2)枚举即可

void solve(int u) {
    cin>>n;
    for(int i=1;i<=n;i++)cin>>w[i];
    ll res=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            int dist=min(j-i,i-j+n);
            res=max(res,1ll*dist*(w[i]+w[j]));
        }
    }
    cout<<res<<endl;
}
int main() {
    T = 1;
    for (int i = 1; i <= T; i++) {
        solve(i);
    }
    return 0;
}

后端T2

本题是一道很难的思维题：主要的思想就是贡献法：枚举当前辅音字母p所构成的贡献(当前辅音字母p是字符串中的第三个字符)

当前字母p的贡献=左边qp的方案数（q为元音字母)*右边q的个数（乘法原理）

右边q的个数可以使用倒序遍历预处理(下面代码中的r数组)

左边qp的方案数可以通过两个前缀和数组记录（一边遍历一边记录）

数组cnts表示遍历到位置i时,对应的五个元音的个数

数组cnt_map[i][j]表示，辅音字母i左边的元音字母j的个数

因此最终计算的贡献值就等于r[i][j]*cnt_map[s[i]][j]

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int>PII;
#define x first
#define y second
typedef long long ll;
const int N = 2E5 + 10, mod = 1e9 + 7;
ll T, w[N], n,k;
string s;
int cnt_map[26][5]; // 表示每个辅音之前所有的辅音贡献
void solve(int u) {
    map<char,int>st={{'a',0},{'e',1},{'i',2},{'o',3},{'u',4}};
    cin>>s;
    n=s.size();
    s=' '+s;
    int r[n+1][5];  //预处理后缀和
    vector<int>cnts(5,0);  //统计当前最新的五个元音的数量
    memset(r,0,sizeof r);
    for(int i=n;i>=1;i--){
        if(st.count(s[i])){
            cnts[st[s[i]]]++;  //对应元音+1
        }
        else{
            for(int j=0;j<5;j++){
                r[i][j]=cnts[j]; //记录[i,n]区间内有多少个元音字母
            }
        }
    }
    ll res=0;
    cnts.clear();cnts.resize(5,0);
    for(int i=1;i<=n;i++){
        if(st.count(s[i])){  //当前是元音 对应元音字母+1即可
            cnts[st[s[i]]]++;
        }
        else{
            for(int j=0;j<5;j++){
                res=(res+1ll*r[i][j]*cnt_map[s[i]-'a'][j]%mod)%mod;  //枚举当前辅音字母为p,元音字母为q 右边元音字母为q的方案数(乘法原理，二者的乘积)
            }
            for(int j=0;j<5;j++){
                cnt_map[s[i]-'a'][j]+=cnts[j];
            }
        }
    }
    cout<<res<<endl;
}
int main() {
    T = 1;
    for (int i = 1; i <= T; i++) {
        solve(i);
    }
    return 0;
}

后端T3

数论题：对于一个数字x，想要去求他的因子个数，可以先对x进行质因数分解，记录每个质数出现的个数

比如6=2*3 6对应的因子个数就是(1+1)*(1+1)=4

比如12=2^2*3 对应的因子个数就是(2+1)*(1+1)=6

假设我们计算数字x的因子个数为sum，数字x中2的质因子个数为k

则其他的质因子乘积a=sum/k

假设sum=k 返回0 0即可

假设sum<k 需要对数字x进行操作1 即增加质因子2的个数，最终得到的sum1一定>=k

质因子2的最终个数就等于k/a或者k/a+1

然后去比较这两种情况 哪个得到的距离最小即可

假设sum>k 需要对数字x进行操作2 减少质因子2的个数

首先 如果当前数字没有质因子2 则直接返回0 0即可

然后 我们可以看出 a_i<=100 每个a_i含有的2的质因子不会超过7个

因此总共的2的质因子个数不会超过7e5

我们直接枚举进行几次操作2即可

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int>PII;
#define x first
#define y second
typedef long long ll;
const int N = 2E5 + 10, mod = 1e9 + 7;
ll T, w[N], n,k;
void f(int x){
    for(int i=2;i<=x;i++){
        while(x%i==0){
            x/=i;
            w[i]++;
        }
    }
    if(x>1)w[x]++;
}
void solve(int u) {
    cin>>n>>k;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        f(x);
    }
    ll total=1;
    for(int i=2;i<=100;i++){
        total*=(w[i]+1);
    }
    if(total==k){
        puts("0 0");
        return;
    }
    ll c=total/(w[2]+1),c1=w[2]+1;
    if(total<k){
        ll cnt1=k/c,cnt2=cnt1+1;
        ll d1=abs(1ll*cnt1*c-k),d2=abs(cnt2*c-k);
        if(d1<=d2)cout<<abs(cnt1-c1)<<" "<<0<<endl;
        else cout<<abs(cnt2-c1)<<" "<<0<<endl;
        return;
    }
    if(w[2]==0){
        puts("0 0");
        return;
    }
    ll dist=1e18,maxcnt=0;
    for(int i=1;i<=w[2];i++){  //枚举操作次数
        ll d=1ll*c*(c1-i);
        if(abs(d-k)<dist){
            dist=abs(d-k);
            maxcnt=i;
        }
    }
    cout<<0<<" "<<maxcnt<<endl;
}
int main() {
    T = 1;
    for (int i = 1; i <= T; i++) {
        solve(i);
    }
    return 0;
}

软开T3

贡献法+乘法原理：考虑每个"oppo"子串对整个结果的贡献

假设该子串对应的区间为[i,i+3] 则贡献为(左边字符的个数+1)*(右边字符的个数+1)

void solve(int u) {
    cin>>s;
    n=s.size();
    ll res=0;
    for(int i=0;i<n;i++){
        if(s.substr(i,4)=="oppo"){
            int l=i+1,r=n-l-2;
            res+=1ll*l*r;
        }
    }
    cout<<res<<endl;
}