9.10模拟赛

T1.bug

可以求出s(x)的表达式，s(x)=9*pow(10,(x-1)/2)

然后可以看出sum(x)具有一定的规律，开头是(x-2+(x%2))，然后是一些7，最后是一个9

构造这样一个数，需要用到9的逆元，注意到9和23333互质，用欧拉定理求即可

单次询问复杂度O(logn)

#include<iostream>
#include<cstdlib>
#include<cstdio>

using namespace std;

typedef long long ll;

inline ll rd(){
    ll ret=0,f=1;char c;
    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
    while(isdigit(c))ret=ret*10+c-'0',c=getchar();
    return ret*f;
}

const int MOD = 233333;
const ll inv = 29892;
ll qpow(ll x,ll y){
    register ll ret=1ll;
    while(y){
        if(y&1)(ret*=x)%=MOD;
        (x*=x)%=MOD;
        y>>=1ll;
    }
    return ret;
}

ll T,n;

void out(ll x){
    if(!x)return;
    out(x/10);
    putchar(x%10+'0');
}

inline void solve(){
    n=rd();
    ll v=(n-2+(n&1));
    ll tmp=qpow(10ll,(v/2)+1);
    ll ans=(tmp*v);
    tmp--;
    if(tmp<0)tmp+=MOD;
    tmp*=181482ll;
    ans+=tmp;
    out((ans+2)%MOD);
    putchar('
');
//    printf("%lld
",(ans+2)%MOD); 
}

int main(){
    freopen("bug.in","r",stdin);
    freopen("bug.out","w",stdout);
    T=rd();
    while(T--)solve();
    return 0;
}

T2.shopping

考虑两个区间的关系

1.相离：互不影响，都选择

2.包含：先选大区间

3.相交：设两个区间的和A=a+b,B=b+c，比较两边平方，发现最终取决于a和c的大小，也就是A和B的大小，因此选和更大的区间

相交的情况可以推广到任意多个区间相交，类比冒泡排序的思想，可以用区间和为关键字排序，找出选择序列

然后就是如何统计答案了，类似疯狂的馒头，用并查集维护，复杂度O(n)

总复杂度O(nlogn)

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>

using namespace std;

typedef long long ll;

inline ll rd(){
    ll ret=0,f=1;char c;
    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
    while(isdigit(c))ret=ret*10+c-'0',c=getchar();
    return ret*f;
}

int n,m;

const int MAXN=5005;

int a[MAXN],s[MAXN];

struct Ask{
    int l,r,sum;
    bool operator <(const Ask &rhs)const{
        return sum>rhs.sum;
    }
}q[1000005];
int fa[MAXN];
int fnd(int x){return x==fa[x]?x:fa[x]=fnd(fa[x]);}
void cat(int x,int y){x=fnd(x);y=fnd(y);if(x==y)return;fa[x]=y;}


int L[MAXN],R[MAXN];

int vis[MAXN],used[MAXN];
int ans=0;
void dfs(int dp,int sum){
    if(dp==m+1){ans=max(ans,sum);return;}
    for(int i=1;i<=m;i++){
        if(vis[i])continue;
        int u=L[i],v=R[i];
        int tmp=0,t=0;
        for(int j=u;j<=v;j++){
            if(used[j]){
                t+=tmp*tmp;
                tmp=0;
                continue;
            }
            tmp+=a[j];
            used[j]=dp;
        }
        if(tmp) t+=tmp*tmp;
        dfs(dp+1,sum+t);
        for(int j=u;j<=v;j++){
            if(used[j]==dp) used[j]=0;
        }
    }        
}

void violence(){
    for(int i=1;i<=n;i++) a[i]=rd();
    for(int i=1;i<=m;i++){
        L[i]=rd();R[i]=rd();
    }
    dfs(1,0);
    cout<<ans;
}

int main(){
    freopen("shopping.in","r",stdin);
    freopen("shopping.out","w",stdout);
//    freopen("testdata.in","r",stdin);
    n=rd();m=rd();
    
    if(m<=6&&n<=1000) return violence(),0;
    
    for(register int i=1;i<=n;i++){
        a[i]=rd();s[i]=s[i-1]+a[i];
        fa[i]=i;
    }
    fa[n+1]=n+1;
    int x,y;
    for(register int i=1;i<=m;i++){
        x=q[i].l=rd();y=q[i].r=rd();
        q[i].sum=s[y]-s[x-1];
    }
    sort(q+1,q+1+m);
    ll ans=0ll;
    for(register int i=1;i<=m;i++){
        int u=q[i].l,v=q[i].r;
        ll tmp=0ll;
        for(register int j=fnd(u);j<=v;j=fnd(j)){
            tmp+=a[j];
            cat(j,j+1);
            if(fa[j]!=j+1) ans+=tmp*tmp,tmp=0ll;
        }
        if(tmp) ans+=tmp*tmp;
    }
    cout<<ans;
    return 0;
}

T3.mo

没什么思路，字符串方面的知识还是太少，要是会写SAM就好了

写了O(n^2)的暴力，数据水放过去了

正解后缀数组+RMQ，待学习