[关闭]
@LittleRewriter 2017-10-08T03:21:04.000000Z 字数 4946 阅读 775

D7题解

题解 爆零

T1

60

暴力

另外20

简单的容斥

100

容斥硬搞
暴力枚举一下，求一个lcm然后算一算

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<cstdlib>
  7. using namespace std;
  8. typedef long long ll;
  9. typedef long double ld;
  10. typedef pair<int,int> pr;
  11. const double pi=acos(-1);
  12. #define rep(i,a,n) for(int i=a;i<=n;i++)
  13. #define per(i,n,a) for(int i=n;i>=a;i--)
  14. #define Rep(i,u) for(int i=head[u];i;i=Next[i])
  15. #define clr(a) memset(a,0,sizeof a)
  16. #define pb push_back
  17. #define mp make_pair
  18. #define putk() putchar(' ')
  19. ld eps=1e-9;
  20. ll pp=1000000007;
  21. ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
  22. ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
  23. ll gcd(ll a,ll b){return (!b)?a:gcd(b,a%b);}
  24. ll read(){
  25.     ll ans=0;
  26.     char last=' ',ch=getchar();
  27.     while(ch<'0' || ch>'9')last=ch,ch=getchar();
  28.     while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
  29.     if(last=='-')ans=-ans;
  30.     return ans;
  31. }
  32. void put(ll a){
  33.     if(a<0)putchar('-'),a=-a;
  34.     int top=0,q[20];
  35.     while(a)q[++top]=a%10,a/=10;
  36.     top=max(top,1);
  37.     while(top--)putchar('0'+q[top+1]);
  38. }
  39. //head
  40. ll ans=0;
  41. int n,m,a[25];
  42. ll Gcd(ll a,ll b){
  43.     if(!b)return a;
  44.     return gcd(b,a%b);
  45. }
  46. void dfs(int dep,ll t,int flag){
  47.     if(t>n)return;
  48.     if(dep==m+1){
  49.         ans+=n/t*flag;
  50.         return;
  51.     }
  52.     dfs(dep+1,t,flag);
  53.     dfs(dep+1,t/Gcd(t,a[dep])*a[dep],-flag);
  54. }
  55. int main(){
  56.     n=read();
  57.     m=read();
  58.     rep(i,1,m)a[i]=read();
  59.     dfs(1,1,1);
  60.     cout<<ans<<endl;
  61.     return 0;
  62. }

T2

30

取出，排序，中位数即可，然后再排个序

60

固定左端点
新出现一个区间就用下一个元素插排O(n)更新一下
最后求k大

80

求第k大可以二分答案。
以中位数>=k的区间个数有多少来二分
那么大于等于k设置为1，否则设置为-1.如果这些和加起来大于等于0，就说明这个区间的中位数是>=k的。
暴力统计每个区间的总和即可

100

考虑上述做法，相当于统计S[R]>S[L-1]的对数。
其实相当于求顺序对。用树状数组维护即可。 

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<cstdlib>
  7. using namespace std;
  8. typedef long long ll;
  9. typedef long double ld;
  10. typedef pair<int,int> pr;
  11. const double pi=acos(-1);
  12. #define rep(i,a,n) for(int i=a;i<=n;i++)
  13. #define per(i,n,a) for(int i=n;i>=a;i--)
  14. #define Rep(i,u) for(int i=head[u];i;i=Next[i])
  15. #define clr(a) memset(a,0,sizeof a)
  16. #define pb push_back
  17. #define mp make_pair
  18. #define fi first
  19. #define sc second
  20. ld eps=1e-9;
  21. ll pp=1000000007;
  22. ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
  23. ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
  24. ll read(){
  25.     ll ans=0;
  26.     char last=' ',ch=getchar();
  27.     while(ch<'0' || ch>'9')last=ch,ch=getchar();
  28.     while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
  29.     if(last=='-')ans=-ans;
  30.     return ans;
  31. }
  32. //head
  33. #define N 110000
  34. int a[N],b[N],c[N],d[N],e[N],n,m;
  35. ll k;
  36. int lowbit(int x){
  37.     return x&(-x);
  38. }
  39. int bin(int k){
  40.     int l=1,r=m;
  41.     while(l<r){
  42.         int mid=(l+r)/2;
  43.         if(k<=d[mid])r=mid;
  44.         else l=mid+1;
  45.     }
  46.     return l;
  47. }
  48. void add(int x){
  49.     for(;x<=m;x+=lowbit(x))e[x]++;
  50. }
  51. int find(int x){
  52.     int ans=0;
  53.     for(;x;x-=lowbit(x))ans+=e[x];
  54.     return ans;
  55. }
  56. ll check(int k){
  57.     c[0]=0;
  58.     rep(i,1,n)c[i]=c[i-1]+(a[i]>=k);
  59.     rep(i,0,n)c[i]=c[i]*2-i,d[i+1]=c[i];
  60.     sort(d+1,d+n+2);
  61.     d[0]=1;
  62.     rep(i,2,n+1)
  63.         if(d[i]!=d[d[0]])d[++d[0]]=d[i];
  64.     m=d[0];
  65.     ll ans=0;
  66.     rep(i,0,n)c[i]=bin(c[i]);
  67.     rep(i,0,m)e[i]=0;
  68.     rep(i,0,n)
  69.         if(i&1)add(c[i]);
  70.         else ans+=find(c[i]-1);
  71.     rep(i,0,m)e[i]=0;
  72.     rep(i,0,n)
  73.         if((i&1)==0)add(c[i]);
  74.         else ans+=find(c[i]-1);
  75.     return ans;
  76. }
  77. int main(){
  78.     n=read();k=read();
  79.     rep(i,1,n)a[i]=read(),b[i]=a[i];
  80.     sort(b+1,b+n+1);
  81.     b[0]=1;
  82.     rep(i,2,n)
  83.         if(b[i]!=b[b[0]])b[++b[0]]=b[i];
  84.     int l=1,r=b[0];
  85.     while(l<r){
  86.         int mid=(l+r)/2+1;
  87.         ll tt=check(b[mid]);
  88.         if(tt==k){
  89.             cout<<b[mid]<<endl;
  90.             return 0;
  91.         }
  92.         if(check(b[mid])>k)l=mid;
  93.         else r=mid-1;
  94.     }
  95.     cout<<b[l]<<endl;
  96.     return 0;
  97. }

T3

30

枚举每个区间，排序，求前缀和，爆算一下

60

枚举区间，右端点递增，插入排序，然后前缀和维护

80

一个数字在所有区间被统计的次数总和就是小于它的区间个数总和
对于j来说，比k小的数的下标有
那么这些东西的贡献，在(n-j+1)个区间中，贡献总和就是
也就是求出所有比k小的数的位置的下标总和
对于t在k右边，反过来求即可。
枚举比它小的数可以暴力一下，总复杂度

100

我们的操作是查询比它小的下标总和，将这个数存入数组中。
可以用树状数组来维护，也可以归并排序。 

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<cstdlib>
  7. using namespace std;
  8. typedef long long ll;
  9. typedef long double ld;
  10. typedef pair<int,int> pr;
  11. const double pi=acos(-1);
  12. #define rep(i,a,n) for(int i=a;i<=n;i++)
  13. #define per(i,n,a) for(int i=n;i>=a;i--)
  14. #define Rep(i,u) for(int i=head[u];i;i=Next[i])
  15. #define clr(a) memset(a,0,sizeof a)
  16. #define pb push_back
  17. #define mp make_pair
  18. #define fi first
  19. #define sc second
  20. ld eps=1e-9;
  21. ll pp=1000000007;
  22. ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
  23. ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
  24. ll read(){
  25.     ll ans=0;
  26.     char last=' ',ch=getchar();
  27.     while(ch<'0' || ch>'9')last=ch,ch=getchar();
  28.     while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
  29.     if(last=='-')ans=-ans;
  30.     return ans;
  31. }
  32. //head
  33. #define N 1100000
  34. pr a[N];
  35. int c1[N],c2[N],n;
  36. ll A,B,C;
  37. int lowbit(int x){return x&(-x);}
  38. void add(int *c,int x,int w){
  39.     c[0]+=w;
  40.     if(c[0]>=pp)c[0]-=pp;
  41.     for(;x<=n;x+=lowbit(x)){
  42.         c[x]=c[x]+w;
  43.         if(c[x]>=pp)c[x]-=pp;
  44.     }
  45. }
  46. int find(int *c,int x){
  47.     int ans=0;
  48.     for(;x;x-=lowbit(x)){
  49.         ans+=c[x];
  50.         if(ans>=pp)ans-=pp;
  51.     }
  52.     return ans;
  53. }
  54. int main(){
  55.     cin>>n>>a[1].fi>>A>>B>>C;
  56.     a[1].sc=1;
  57.     rep(i,2,n){
  58.         a[i].sc=i;
  59.         a[i].fi=(a[i-1].fi*A+B)%C;
  60.     }
  61.     sort(a+1,a+n+1);
  62.     ll ans=0;
  63.     rep(i,1,n){
  64.         int t1=find(c1,a[i].sc);
  65.         int t2=c2[0]-find(c2,a[i].sc-1);
  66.         t2=(t2+pp)%pp;
  67.         int t3=(1ll*t1*(n-a[i].sc+1)+1ll*t2*a[i].sc)%pp;
  68.         t3=(t3+1ll*a[i].sc*(n-a[i].sc+1))%pp;
  69.         ans=(ans+1ll*t3*a[i].fi)%pp;
  70.         add(c1,a[i].sc,a[i].sc);
  71.         add(c2,a[i].sc,n-a[i].sc+1);
  72.     }
  73.     cout<<ans<<endl;
  74.     return 0;
  75. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注