9.10模拟赛-白红宇

9.10模拟赛

阅读量：6441 次

发布时间：2019-06-23

本文共 2725 字，大约阅读时间需要 9 分钟。

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
      
       #include
       
        #include
        
         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('\n');//    printf("%lld\n",(ans+2)%MOD); }int main(){    freopen("bug.in","r",stdin);    freopen("bug.out","w",stdout);    T=rd();    while(T--)solve();    return 0;}

View Code

T2.shopping

考虑两个区间的关系

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

2.包含：先选大区间

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

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

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

总复杂度O(nlogn)

#include
      
       #include
       
        #include
        
         #include
         
          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<