T1:

看到这种东西就想二维数点。

如果圆弧i和圆弧j能贡献答案的话(假设i在左边)，需要满足 Li<Lj && Ri<Rj && Lj<Ri && Coli!=Colj 。

我们先不管最后颜色的那个限制，如果我们确定了i之后，能有贡献的j需要满足: Li<Lj && Lj<Ri && Rj>Ri .

这样我们按照左端点建立主席树，把右端点插进去，就能统计了。

然后再按照颜色分类，计算颜色相同的贡献减去，就能得到答案。

复杂度O(sigma(Si^2)logn)，能获得70分。

正解大概是均衡不同复杂度算法之类的东西，然而并不能想到不同复杂度的算法(然后题解真是这样的)。

70分暴力代码:

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
          
         
        
       
      

T2:

全场就我不会做这题，高一学弟都会做......

我考虑枚举中间点，然后计算两遍有长度限制的大于/小于点数，发现并不可做，然后就O(n^2)暴力滚粗了。

正解是枚举右端点，计算中间点和左端点的贡献。

显然先要断环成链，我们用一颗权值线段树维护权值为i的点，左边比他小的点的个数fi。然后从左向右(n->2*n-1)枚举当前右端点，需要记录答案的就是sum(f1->f(in[i]-1))。

考虑怎么预处理出前n个点的区间的这个值，直接线段树求顺序对即可。

考虑怎么从区间[i,i+n-1]转移到区间[i+1,i+n]。显然对于权值>in[i]的所有点，其左边的点少了一个，应该区间-1。

考虑新加入的in[i+n]，所有的点都在他的左边，所以他的权值应该为in[i+n]-1。并且更新前权值为0(因为左边没有其他点)。

然后就是老年选手身败名裂的故事了。

60分暴力代码:

1 #include
      
        2 typedef long long int lli; 3 const int maxn=5e3+1e2; 4  5 int in[maxn<<1],n; 6 lli f[maxn][maxn],ans; 7  8 int main() { 9     scanf("%d",&n);10     for(int i=1;i<=n;i++) scanf("%d",in+i) , in[i+n] = in[i];11     for(int i=1;i<=n;i++) for(int j=1;j
       
         in[i] );12     for(int i=1;i<=n;i++) for(int j=i+1;j
        
          in[i] ) ans += f[j>n?j-n:j][n-(j-i+1)];13     printf("%lld\n",ans);14     return 0;15 }
        
       
      

正解代码:

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define debug cout 6 typedef long long int lli; 7 using namespace std; 8 const int maxn=2e5+1e2; 9 10 class SegmentTree {11     private:12     int l[maxn<<3],r[maxn<<3],lson[maxn<<3],rson[maxn<<3],cnt;13     lli dat[maxn<<3],lazy[maxn<<3];14     public:15     SegmentTree() { cnt = 1; }16     inline void build(int pos,int ll,int rr) {17         l[pos] = ll , r[pos] = rr;18         if( ll == rr ) return;19         const int mid = ( ll + rr ) >> 1;20         build(lson[pos]=++cnt,ll,mid) , build(rson[pos]=++cnt,mid+1,rr);21     }22     inline void apply(int pos,lli x) {23         dat[pos] += ( r[pos] - l[pos] + 1 ) * x , lazy[pos] += x;24     }25     inline void push(int pos) {26         apply(lson[pos],lazy[pos]) , apply(rson[pos],lazy[pos]) , lazy[pos] = 0;27     }28     inline void update(int pos,const int &ll,const int &rr,const lli &x) {29         if( rr < l[pos] || r[pos] < ll ) return;30         if( ll <= l[pos] && r[pos] <= rr ) return apply(pos,x);31         push(pos) , update(lson[pos],ll,rr,x) , update(rson[pos],ll,rr,x) , dat[pos] = dat[lson[pos]] + dat[rson[pos]];32     }33     inline lli query(int pos,const int &ll,const int &rr) {34         if( rr < l[pos] || r[pos] < ll ) return 0;35         if( ll <= l[pos] && r[pos] <= rr ) return dat[pos];36         return push(pos) , query(lson[pos],ll,rr) + query(rson[pos],ll,rr);37     }38 }pre,sgt;39 40 int in[maxn<<1],n;41 lli ans;42 43 int main() {44     scanf("%d",&n) , pre.build(1,1,n) , sgt.build(1,1,n);45     for(int i=1;i<=n;i++) scanf("%d",in+i) , in[i+n] = in[i] , pre.update(1,in[i]+1,n,1) , sgt.update(1,in[i],in[i],pre.query(1,in[i],in[i]));46     for(int i=n,lst=1;i
          
           <<1;i++,lst++) ans += sgt.query(1,1,in[i]-1) , sgt.update(1,in[lst]+1,n,-1) , sgt.update(1,in[lst],in[lst],in[lst]-1);47     printf("%lld\n",ans);48     return 0;49 }
          
         
        
       
      

T3:

这不是BZOJ4774吗?斯坦纳树板子题。

写写写，和原来的代码对拍，发现要跑5s？

赶紧大力卡常，卡到3s，没办法了不管了(不知道评测机具体体位架构所以不敢target("avx"))。

然后发现这题竟然A了(震惊!1.5s竟然能让斯坦纳树AC)

然后又发现zhy的乱搞算法也A了(他枚举点对顺序然后贪心最短路，显然不对)，这数据是有多水？

辣鸡出题人不会造数据费我时间掉我排名！

代码:

1 #pragma GCC optimize("Ofast,no-stack-protector") 2 //#pragma GCC target("avx") 3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 #include
          
            8 #define bool unsigned char 9 const unsigned maxn=1e4+1e2+3,maxs=(1<<9)+5,maxq=11;10 const unsigned inf=0x3f3f3f3f;11 // I know it's impossible for me to AC this problem in 1.5s, but I have to try.12 13 unsigned s[maxn],t[maxn<<1],nxt[maxn<<1],l[maxn<<1];14 unsigned f[maxs][maxn],g[maxs],pts[maxq];15 unsigned n,m,d,full;16 17 __inline void addedge(unsigned from,unsigned to,unsigned len) {18     static unsigned cnt = 0;19     t[++cnt] = to , l[cnt] = len ,20     nxt[cnt] = s[from] , s[from] = cnt;21 }22 __inline void spfa(unsigned* dis) {23     static bool inq[maxn];24     static std::queue
           
             q;25 for(unsigned i=1;i<=n;i++) if( dis[i] != inf ) q.push(i) , inq[i] = 1;26 while( q.size() ) {27 const unsigned pos = q.front(); q.pop() , inq[pos] = 0;28 for(register unsigned at=s[pos];at;at=nxt[at])29 if( dis[t[at]] > dis[pos] + l[at] ) {30 dis[t[at]] = dis[pos] + l[at];31 if( !inq[t[at]] ) q.push(t[at]) , inq[t[at]] = 1;32 }33 }34 }35 __inline void getf() {36 memset(f,0x3f,sizeof(f));37 for(register unsigned i=0;i<(d<<1);i++) f[1<
            
             > i ) & 1 ) != ( sta >> ( ( d << 1 ) - i - 1 ) & 1 ) ) return 0;48 return 1;49 }50 __inline void getg() {51 memset(g,0x3f,sizeof(g));52 for(register unsigned sta=0;sta
             
              << 22;58 static unsigned char buf[BS],*st=buf+BS,*ed=buf+BS;59 if( st == ed ) ed = buf + fread(st=buf,1,BS,stdin);60 return st == ed ? -1 : *st++;61 }62 __inline unsigned getint() {63 register unsigned ret = 0 , ch;64 while( !isdigit(ch=nextchar()) );65 do ret=ret*10+ch-'0'; while( isdigit(ch=nextchar()) );66 return ret;67 }68 69 int main() {70 n = getint() , m = getint() , full = 1 << ( ( d = getint() ) << 1 );71 for(register unsigned i=1,a,b,l;i<=m;i++) a = getint() , b = getint() , l = getint() , addedge(a,b,l) , addedge(b,a,l);72 for(register unsigned i=0;i
             
            
           
          
         
        
       
      

 

话说我似乎是这个机房中历届存在过的常数最大的人了。

虽然我知道怎么优化，然而我懒......

于是就有了自带大常数的属性。

话说这不是萌点吗，怎么就变成槽点了(雾)。

我怎么知道......