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('\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<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; } View Code

T3.mo

沒什么思路，字符串方面的知識還是太少，要是會寫SAM就好了

寫了O(n^2)的暴力，數據水放過去了

正解后綴數組+RMQ，待學習

轉載于:https://www.cnblogs.com/ghostcai/p/9630089.html

總結

以上是生活随笔為你收集整理的9.10模拟赛的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。