A

略

B

略

C(计数)

题意：

　　有n个白球排成一行，故有n-1个空隙，我可以给一个空隙对应的两个白球都涂黑。n-1个空隙的一个排列就对应着一个涂黑顺序，定义这个涂黑顺序的价值是“将所有n个球都涂黑的最少步数”。对于n-1的所有排列，我们要求对应价值的和。

　　n<=1e6

分析：

　　首先易得最少步数一定在ceil(n/2)到n-1之间，我们去枚举最少步数，然后算对应的排列有多少个

　　设f(i)表示最少步数为i的排列有多少个

　　我们去观察n-1个空隙，假设我们取的空隙从小到大编号依次是$x_1,x_2,x_3,......,x_i$

　　那么x1一定是1，xi一定是n-1，并且满足$x_{i+1}-x_i=1 or 2$

　　那取哪些位置可以通过组合数算出来，然后它们在排列一下，剩下的(n-1-i)个无关空隙也丢在后面排列一下，就能计算了

D(贪心)

题意：

　　在一个数轴上有n个点，表示n个公寓，第i个公寓的坐标是xi，住了pi个人。这些人都是公司的员工，公司的坐标在S。

　　现在下班了，所有人坐上了大巴车，大巴车从S出发，大巴的速度是固定的，每秒1个单位长度。每次车上的人都进行投票，选择大巴是向左开还是向右开（平票就向左）。每个人的投票原则就是要让自己尽量早到家，并且每个人都是极其聪明的。大巴在到达了一个坐标之后，家住在这的人都会立刻下车。

　　问大巴会运行多长时间。

　　n<=1e5,pi<=1e9，坐标<=1e9

分析：

　　如果S在所有点的一侧，那么很显然就是直接一路开过去。

　　如果S在这些点的中间位置，那么显然下车顺序一定是从中间到两边不断吞噬。

　　我们来考察一下最外面的两个点1和n，不妨设p[1]>=p[n]

　　这样的话，在到达第n个点之前，一定到达了第1个点（假设现在在第n-1个点且第1个点还没到达，那么第一个点人多，所以他们会投票往左开）。在到达了第1个点后，再一路向右开。也就是说time[n]=time[1]+x[n]-x[1]

　　换句话说，住在第n个点人的到家时间是第1个点的人到家时间加上一个常数，第n个点的人希望自己到家时间尽量短，也就是希望第1个点的人到家时间尽量短，也就是说第n个点的人的投票一定是和第一个点的人投票是一样的

　　那这样我们就可以看成只有1~n-1个点，将p[n]加到[1]上，缩小了问题规模

　　p[1]<p[n]也是同理

　　这样不断从两边向中间缩小规模，最后得到一个点，直接从S开到这个点就行了，在贪心过程中记录下时间的计算关系，计算下时间就行了。

　　注意一下细节，在缩小规模的过程中，如果出现了S在目前所有点的一侧，要特殊处理后面的所有过程。

　　时间复杂度O(n)

1 #include
      
        2 using namespace std; 3 const int maxn=1e5; 4 typedef long long ll; 5 #define mp make_pair 6 ll x[maxn+5],p[maxn+5]; 7 vector
       
        
          > g[maxn+5]; 8 ll ans[maxn+5]; 9 int n,s;10 void addedge(int u,int v,ll w)11 {12     g[u].push_back(mp(v,w));13 }14 void dfs(int k)15 {16     for(auto x:g[k])17     {18         ans[x.first]=ans[k]+x.second;19         dfs(x.first);20     }21 }22 int main()23 {24  25     scanf("%d%d",&n,&s);26     for(int i=1;i<=n;++i) scanf("%lld%lld",&x[i],&p[i]);27     int l=1,r=n;28     while(l
         
          =s) addedge(l,l+1,x[l+1]-x[l]),++l;31         else32             if(x[r]<=s) addedge(r,r-1,x[r]-x[r-1]),--r;33         else34         if(p[l]>=p[r]) p[l]+=p[r],addedge(l,r,x[r]-x[l]),--r;35         else p[r]+=p[l],addedge(r,l,x[r]-x[l]),++l;36     }37     ans[l]=abs(x[l]-s);38     dfs(l);39     printf("%lld\n",max(ans[1],ans[n]));40     return 0;41 }
         
        
       
      

E(计数)

题意：

　　给出a1~an，表示每一个位置的上限，在满足这个上限要求的所有n的排列中，求逆序对个数的和。

　　n<=2e5

分析：

　　首先需要会两个子问题：

　　1、给定上限要求a1~an，一共有多少个排列满足这个上限限制呢？

　　　　记cnt[k]=(满足ai>=k的个数)-(n-k)，那么排列个数就是cnt[1]*cnt[2]*...*cnt[n]。这是因为我们从大到小去安排，对于最大的数字n，我们看看它有多少个位置可以放；对于次大的数字n-1，我们看看它有多少个位置可以放（注意之前在某个位置已经放过了一个n）……。这样总排列数就是所有cnt的乘积。

　　2、如何求n的所有排列的逆序对的个数和？

　　　　算任意两个位置的贡献。考虑枚举两个位置i和j(i<j)，我们去计算有多少个排列满足pi>pj。那么怎么计算有多少个排列满足这个条件呢？考虑对称性，pi>pj的排列个数=pi<pj的排列个数，故pi<pj的排列个数就是总排列个数的一半，也就是n!/2

　　　　这个思想就是解决这个问题的关键。当然如果计算逆序对个数和的话，再化化简就能得出一个通式，这里就不推导了。

　　现在回到这个问题，我们假设满足限制的排列个数是S（如果S是0，就直接返回0了）。

　　我们去枚举任意两个位置i,j(i<j)，我们去计算有多少个排列满足pi>pj，且满足a[i]的限制

　　①对于ai<=aj的情况，相当于把aj变成ai，然后求有多少个排列满足这个限制，再除以2。我们考虑把aj变成ai会带来什么影响，其实就是cnt[a[i]+1]~cnt[a[j]]这一段都减去了1，我们可以用一个D[]来表示(cnt[i]-1)/cnt[i]的前缀积，那么答案就是1/2*S*D[a[j]]/D[a[i]]。这样时间复杂度是O(n^2)的，但是很显然这个是可以用bit来维护的，O(nlogn)

　　②对于ai>aj的情况，处理思路也是差不多的，但这个时候就要计算反面，即满足i<j,ai>aj,pi>pj的排列数等于总排列数S-"满足i<j,ai>aj,pi<pj的排列数"，后面这个东西的处理和第一种情况是类似的。

　　但还有一个麻烦的问题，就是D[x]/D[y]可能会出现分母为0的情况，我们来考虑它的实际意义

　　0 0 1 2 3 0 2

　　比如这里D[5]/D[3]虽然是0/0，但是是合法的，它表示将[4,5]这一段的cnt用cnt-1替换，我们可以将每一个D[i]看做是$D[i]*0^{x[i]}$，若作除法的两个D的0上指标相同，那就可以得到正确结果，否则就得到0。

　　那么怎么具体实现呢？注意到指标相同的两个数一定是这个数组里连续的无0的一段，所以我们可以预处理出每个位置的pre[]和suf[]，表示0的上指标相同的左右位置极限，然后在树状数组求解的时候强化一下询问范围就行了。

　　时间复杂度O(nlogn)

1 #include
      
        2 using namespace std; 3 typedef long long ll; 4 const int maxn=2e5; 5 const ll mod=1e9+7; 6 ll a[maxn+5],num[maxn+5],cnt[maxn+5],S,D[maxn+5]; 7 int pre[maxn+5],suf[maxn+5]; 8 int n; 9 ll c[2][maxn+5];10 ll ans=0;11 ll Pow(ll a,ll b,ll mod)12 {13     ll ans=1;14     while(b)15     {16         if(b&1) ans=ans*a%mod;17         a=a*a%mod;18         b>>=1;19     }20     return ans;21 }22 ll inv(ll a)23 {24     return Pow(a,mod-2,mod);25 }26 int lowbit(int x)27 {28     return x&(-x);29 }30 ll add(ll *c,int k,ll data)31 {32     for(;k<=n+1;k+=lowbit(k)) c[k]=(c[k]+data)%mod;33 }34 ll query(ll *c,int k)35 {36     ll ans=0;37     for(;k;k-=lowbit(k)) ans=(ans+c[k])%mod;38     return ans;39 }40 int main()41 {42  43     scanf("%d",&n);44     for(int i=1;i<=n;++i) scanf("%lld",&a[i]),++num[a[i]];45     for(int i=n-1;i>=1;--i) num[i]+=num[i+1];46     S=1;47     D[0]=1;48     for(int i=1;i<=n;++i)49     {50         cnt[i]=num[i]-(n-i),S=S*cnt[i]%mod;51         if(cnt[i]<=0) return 0*printf("0\n");52         D[i]=D[i-1];53         if(cnt[i]>1) D[i]=D[i]*(cnt[i]-1)%mod*inv(cnt[i])%mod,pre[i]=pre[i-1];else pre[i]=i;54     }55     suf[n]=n;56     for(int i=n-1;i>=1;--i)57         if(cnt[i]>1)58         {59             if(cnt[i+1]>1) suf[i]=suf[i+1];else suf[i]=i;60         }61         else suf[i]=i;62     for(int i=1;i<=n;++i)63     {64         ans=(ans+(query(c[0],a[i])-query(c[0],pre[a[i]]-1))%mod*S%mod*D[a[i]]%mod*inv(2LL)%mod)%mod;65         if(ans<0) ans+=mod;66         add(c[0],a[i],inv(D[a[i]]));67     }68     for(int i=1;i<=n;++i) c[0][i]=0;69     for(int i=1;i<=n;++i)70     {71         ans=(ans+S*(query(c[1],n)-query(c[1],a[i]))%mod-inv(2LL)*S%mod*inv(D[a[i]])%mod*(query(c[0],suf[a[i]])-query(c[0],a[i]))%mod)%mod;72         if(ans<0) ans+=mod;73         add(c[0],a[i],D[a[i]]);74         add(c[1],a[i],1LL);75     }76     printf("%lld\n",ans);77     return 0;78 }
      

F(贪心)

题意：

　　给一个n个点的树，每个点表示一个数字0/1。你需要找出一个拓扑序，使得这个拓扑序对应的01序列逆序对个数尽量少。

　　n<=2e5

分析：

　　0应该尽量放前面，于是我们在树中找一个是0的点，让它和其父亲绑定。（即我们希望它的父亲出现后，紧跟在后出现的就是这个点）

　　假设这样的限制都弄出来了，会有一些互相无限制的点集，那么我们怎么决定先后取的顺序呢?

　　假设有这样两个点集a和b，a里有a0个0，a1个1，b中有b0个0，b1个1

　　那么如果ab比ba优秀，那么一定有a1*b0<a0*b1，即a1/a0<b1/b0

　　于是我们的贪心方法出来了，刚开始，每个点自己作为一个点集，我们记录每个点集的cnt0和cnt1。

　　然后我们选出cnt1/cnt0最小的点集，把这个点集和其父亲所在的点集合并就行了，一直合并只剩最后一个根节点

　　用set实现就行了

　　时间复杂度O(nlogn)

1 #include
      
        2 using namespace std; 3 const int maxn=2e5; 4 struct wjmzbmr 5 { 6     int c0,c1,id; 7     wjmzbmr(){} 8     wjmzbmr(int a,int b,int c):c0(a),c1(b),id(c) {} 9     bool operator < (const wjmzbmr& x) const10     {11         if(1LL*c0*x.c1!=1LL*c1*x.c0) return 1LL*c0*x.c1>1LL*c1*x.c0;12         return id
       
         s;21 int find(int x)22 {23     if(f[x]==x) return f[x];else return f[x]=find(f[x]);24 }25 int main()26 {27 28     scanf("%d",&n);29     for(int i=2;i<=n;++i) scanf("%d",&p[i]);30     for(int i=1;i<=n;++i)31     {32         scanf("%d",&tmp[i]);33         f[i]=i,tail[i]=i;34         if(tmp[i]==0) a[i]={
    1,0,i},c0[i]=1;else a[i]={
    0,1,i},c1[i]=1;35         if(i>=2)36         s.insert(a[i]);37     }38     while(s.size()>0)39     {40         wjmzbmr x=*s.begin();41         s.erase(s.begin());42         int u=x.id;43  44         int v=find(p[x.id]);45         nx[tail[v]]=u;46         ++d[u];47         f[u]=v,tail[v]=tail[u];48         if(v!=1) s.erase(s.find(wjmzbmr(c0[v],c1[v],v)));49         c0[v]+=c0[u],c1[v]+=c1[u];50         if(v!=1) s.insert(wjmzbmr(c0[v],c1[v],v));51     }52     for(int i=1;i<=n;++i)53         if(d[i]==0)54         {55             root=i;56             break;57         }58     for(int i=1;i<=n;++i,root=nx[root])59     {60         b[i]=tmp[root];61     }62  63     int now=0;64     for(int i=n;i>=1;--i)65         if(b[i]==1) ans+=now;else now+=1;66     printf("%lld\n",ans);67     return 0;68 }