XP04-day02

集团-陈超杰

2026-08-13 20:52:05

发布于：广东

112阅读

0回复

0点赞

回文子数组

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n;
int a[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    long long ans=0;
    //枚举区间的左右端点 不相同
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(a[i]!=a[j]){
                ans+=min(i,n-j+1);
            }
        }
    }
    cout<<ans;
    return 0;
}

// 回文 贡献 a[i]!=a[j]

// 整体贡献 - 不合法  a[i]==a[j]
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int n;
int a[N];
vector<int> pos[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pos[a[i]].push_back(i);
    }
    long long ans=0;
    // 先计算所有位置对的贡献
    for(int i=1;i<=n;i++){
        long long len=n-i;
        if(len<i){
            ans+=len*(len+1)/2;
        }else{
            ans+=1LL*i*(i+1)/2;
            ans+=1LL*(len-i)*i;
        }
    }
    // 减去相同元素位置对的贡献
    for(int x=1;x<=n;x++){
        int sz=pos[x].size();
        for(int i=0;i<sz;i++){
            for(int j=i+1;j<sz;j++){
                int l=pos[x][i];
                int r=pos[x][j];
                ans-=min(l,n-r+1);
            }
        }
    }
    cout<<ans;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int n;
int a[N];
vector<int> pos[N];
long long s[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pos[a[i]].push_back(i);
    }
    long long ans=0;
    // 计算所有位置对的贡献
    for(int i=1;i<=n;i++){
        long long len=n-i;
        if(len<i){
            ans+=len*(len+1)/2;
        }else{
            ans+=1LL*i*(i+1)/2;
            ans+=1LL*(len-i)*i;
        }
    }
    // 减去相同元素位置对的贡献
    for(int x=1;x<=n;x++){
        int sz=pos[x].size();
        // s[i]表示前i个位置之和
        s[0]=0;
        for(int i=1;i<=sz;i++)s[i]=s[i-1]+pos[x][i-1];
        // 固定右边位置pos[x][j]
        for(int j=1;j<sz;j++){
            int r=pos[x][j];
            // 右边最多还能扩展多少层
            int t=n-r+1;
            // 在前j个位置中，寻找最后一个<=t的位置
            int cnt=upper_bound(pos[x].begin(),pos[x].begin()+j,t)-pos[x].begin();
            // 前cnt个位置贡献为位置本身
            ans-=s[cnt];
            // 剩余位置贡献都是t
            ans-=1LL*(j-cnt)*t;
        }
    }
    cout<<ans;
    return 0;
}

最喜欢∑的一集之子序列"+w+"

#include<bits/stdc++.h>
using namespace std;
long long ans = 0,mod = 1e9+7;
long long bpow(long long a,long long b){
    long long res = 1;
    while(b){
        if(b%2==1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        ans+=x;
        ans%=mod;
    }
    long long tot = bpow(2,n-1);
    cout<<tot*ans%mod;
    return 0;
}

最喜欢∑的一集之子数组"+w+"

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    long long ans = 0;
    //  i-1  i  n-i
    for(int i=1;i<=n;i++){
        long long x;
        cin>>x;
        ans += x * i * (n-i+1); 
    }
    cout<<ans;
    return 0;
}

拍照

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
long long a[N][N],s[N][N];
int main(){
    int n,k,q;
    cin>>n>>k>>q;
    long long mx = 0;
    while(q--){
        int x,y,c;
        cin>>x>>y>>c;
        for(int i=x-k+1;i<=x;i++){
            for(int j=y-k+1;j<=y;j++){
                if(i<1 || i>n || j<1 || j>n)continue;
                s[i][j]+=c-a[x][y];
                mx=max(mx,s[i][j]);
            }
        }
        a[x][y] = c;
        cout<<mx<<endl;
    }
    return 0;
}

可能是签到题

#include<bits/stdc++.h>
using namespace std;
int n, q;
string s;
int a[1000010][26];
// 97 - 122   0 - 25
int main() {
    cin >> n >> q;
    cin >> s;
    s = ' ' + s;
    for(int i = 1; i <= n; i ++) {
        for(int j = 0; j < 26; j ++) a[i][j] = a[i - 1][j];
        a[i][s[i] - 'a'] ++;
    }
    while(q --) {
        int l, r;
        cin >> l >> r;
        int ans = 0;
        for(int i = 0; i < 26; i ++) {
            ans = max(ans, a[r][i] - a[l - 1][i]);
        }
        cout << ans << endl;
    }
}

第k大的数

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e8 + 5;

ll a[N];
int n,k;
ll f,t,m;

// 找第 k 大
ll quick_select(int l,int r,int k){
    if(l==r) return a[l];
    // 随机选择基准值
    int p=l+rand()%(r-l+1);
    ll x=a[p];
    int i=l,j=r;
    // 按照从大到小进行划分
    while(i<=j){
        // 大于基准值的放左边
        while(a[i]>x) i++;
        // 小于基准值的放右边
        while(a[j]<x) j--;
        if(i<=j){
            swap(a[i],a[j]);
            i++;
            j--;
        }
    }
    // 左边一共有 j-l+1 个数
    if(k<=j-l+1){
        return quick_select(l,j,k);
    }
    // 右边从第 i 个位置开始
    if(k>i-l){
        return quick_select(i,r,k-(i-l));
    }
    // 第 k 大落在中间基准值区域
    return x;
}

int main(){
    srand(time(0));
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k>>f>>t>>m;
    a[1]=f;
    for(int i=2;i<=n;i++){
        a[i]=(a[i-1]+t)%m;
    }
    cout<<quick_select(1,n,k);
    return 0;
}

时间复杂度：期望 $O(n)$ ，最坏 $O(n^2)$ 。

quick_select 每次划分时，i 只向右走，j 只向左走，因此当前区间只会被扫描一遍，复杂度是 $O(len)$ 。

划分后只递归第 $k$ 大所在的一边，不会像快速排序一样两边都递归。随机选择基准值后，区间规模期望会不断缩小，因此总复杂度为：

$O(n)+O(n/2)+O(n/4)+\cdots=O(n)$

所以整体期望时间复杂度是： $O(n)$

如果每次都随机到很差的基准，使区间只减少一个元素，则：

$n+(n-1)+\cdots+1=O(n^2)$

因此最坏复杂度为 $O(n^2)$ 。

快速排序

求逆序对

合并

归并排序

忠诚

撤硕管理员

细胞

神庙迷宫1

马的遍历

拓扑排序

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int n;
int a[200005];
vector<int> cnti[200005];
vector<ll> cnts[200005];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    ll ans=0;
    // 所有对称位置对的贡献
    for(int i=2;i<=n;i++){
        ans+=1LL*(n-i+1)*(i/2);
    }
    for(int i=1;i<=n;i++){
        int val=a[i];
        if(cnti[val].size()>0){
            int tal=n-i+1;
            auto it=lower_bound(cnti[val].begin(),cnti[val].end(), tal);
            // < tal 的位置个数
            int small=it-cnti[val].begin();
            ll sumsma=0;
            if(small>0){
                sumsma=cnts[val][small-1];
            }
            // >= tal 的位置个数
            int lsz=cnti[val].size()-small;
            ll lasts=1LL*lsz*tal;
            ans-=sumsma+lasts;
        }
        cnti[val].push_back(i);
        if(cnts[val].empty()){
            cnts[val].push_back(i);
        }
        else{
            cnts[val].push_back(cnts[val].back()+i);
        }
    }
    cout<<ans;
    return 0;
}