1001 

定义两个数组L[i],R[i]保存第i个数左右最近的因子。

那么第i个数对ans的贡献就是(R[i]-i)*(i-L[i])。

更新L,R数组的方法如下：

用向量预存[1,10000]中每个数的位置。

对于a[i]，枚举它的所有倍数，记为j。

若j在a[i]左边，且a[i]小于原来的R[j]，即a[i]与j更近，那么R[j]的位置更新为i。

若j在a[i]右边，且a[i]大于原来的L[j]，即a[i]与j更近，那么L[j]的位置更新为i。

【标程做了一个优化，将小于100的因子先处理。】

1 # include 
      
        2 # include 
       
         3 # include 
        
          4 # include 
         
           5 using namespace std; 6 typedef long long LL; 7 # define MOD 1000000007 8 # define maxn 100010 9 vector 
          
            vec[10001];10 int a[maxn],L[maxn],R[maxn];11 12 int main(void)13 {14     int n;15     while((scanf("%d",&n))!=EOF)16     {17         for(int i=1;i<=10000;i++) vec[i].clear();18         for(int i=1;i<=n;i++)19         {20             scanf("%d",a+i);21             L[i]=0; R[i]=n+1;22             vec[a[i]].push_back(i);23         }24         for(int i=1;i<=n;i++)25             for(int j=a[i];j<=10000;j+=a[i])26                 for(int k=0;k
           
            =i) break;29 else R[vec[j][k]]=min(R[vec[j][k]],i);30 }31 for(int i=1;i<=n;i++)32 for(int j=a[i];j<=10000;j+=a[i])33 for(int k=vec[j].size()-1;k>=0;k--)34 {35 if(vec[j][k]<=i) break;36 else L[vec[j][k]]=max(L[vec[j][k]],i);37 }38 LL ans=0;39 for(int i=1;i<=n;i++) ans= ( ans+ (LL)(R[i]-i) * (LL)(i-L[i]) )%MOD;40 printf("%I64d\n",ans);41 }42 return 0;43 }
           
          
         
        
       
      

 

 

1002 

先用ST表处理好所有区间的最大值最小值。

枚举区间的左端点L，区间内最大值与最小值的差值随着右端点的增加单调递增。

于是可以二分出合法的右端点最大值Rmax。

找到右端点的最大值，则只要右端点R满足L<=R<=Rmax的区间均可。

即找出每组L，Rmax对ans的贡献是Rmax-L+1。

答案超出了int范围。注意LL。

【跑完时间并不宽裕。慎用线段树与树状数组。】

【先不说ST表。感觉自己二分一直写很丑阿。】

1 # include 
      
        2 # include 
       
         3 # include 
        
          4 # include 
         
           5 using namespace std; 6 typedef long long LL; 7 # define maxn 100010 8 LL a[maxn],MAX[maxn][20],MIN[maxn][20]; 9 10 int main(void)11 {12     int T; cin>>T;13     while(T--)14     {15         int n,k; scanf("%d%d",&n,&k);16         for(int i=1;i<=n;i++)17         {18             scanf("%I64d",a+i);19             MAX[i][0]=MIN[i][0]=a[i];    20         }21         for(int j=1;j<20;j++)22             for(int i=1;i<=n;i++)23                 if(i+(1<
          
           <=n)24                 {25                     MAX[i][j]=max(MAX[i][j-1],MAX[i+(1<
           
            =k) r=mid-1;38 else l=mid+1;39 }40 int t=(log(double(l-i+1))/log(2));41 LL tem=max(MAX[i][t],MAX[l-(1<
            
             <
             
              =k) l--;43 ans+=l-i+1;44 }45 printf("%I64d\n",ans);46 }47 return 0;48 }
             
            
           
          
         
        
       
      

 

 

1003 

 

 

1004 

 

 

1005 

前面百度之星做过一个魔方。

纯模拟即可。也有看色向的优化方法。但是并没有去了解。

这题一看就知道是判色向的。然而并不知道怎么算QAQ。

【比赛的时候学姐竟然还叫我看一下这个题目。太看得起我了。】

题解很良心的证明了一下定理。想再讲一下自己的理解。

因为只会三阶公式。我一般是把二阶魔方看成三阶的角块。

所有安装正确的二阶魔方是一个等价类。通过旋转置换还原。

【二阶有自己更为简洁的公式。】

首先。必定能做到将底层还原。

其次。运用角块归位公式。将角块的位置摆对。不看色向。（即官方题解图3）

【上面两步即便是装错的也能做到。】

最后。顶块翻色。这个公式是两个相邻的角块同时向内侧翻色。（即官方题解图2）

一个安装正确的魔方只要反复翻色。每次至少使一个角块颜色正确。便能还原。

错误安装的魔方翻色至最后一个角块的色向是顺时针或者逆时针的。

证明的主要内容就是说明了。这个翻色的操作不会改变色向和%3的值。

而一个还原的二阶魔方色相和%3是为零的。

因此只有色相和%3为零的魔方才是正确安装魔方的等价类。

1 # include 
      
        2 # include 
       
         3 using namespace std; 4  5 int main(void) 6 { 7     int T; cin>>T; 8     for(int kase=1;kase<=T;kase++) 9     {10         int sum=0;11         for(int i=1;i<=24;i++)12         {13             char color[5];14             scanf(" %s",color);15             if(color[0]=='w'||color[0]=='y')16             {17                 if(i==1||i==4||i==6||i==10||i==11||i==15||i==17||i==20) sum++;18                 else if(i==2||i==3||i==5||i==9||i==12||i==16||i==18||i==19) sum--;19             }20         }21         printf("Case #%d: ",kase);22         if(sum%3==0) printf("YES\n");23         else printf("NO\n");24     }25     return 0;26 }
       
      

 

 

1006 

码这个真的超级不容易。希望我能把这个问题讲清楚。

菊苣们必然是有很厉害的方法的。

对于我等渣而言。做这个题至少要了解以下内容。

会些dp。时间戳。会一个区间求和工具（线段树或者树状数组。会LCA（离线。在线。

我对dp了解并不多。求和图方便用的树状数组。LCA只会离线的。

 

首先要理解题意。题目中u,v间链是从u出发向上绕过LCA(u,v)再往下连到v的。

（一开始我连sample都看不懂。

整体上是一个树形dp。看成1为根的有根树。

用dp[i]表示以i为根节点的子树的答案。那么我们要求的是dp[1]。

为了方便。引进了sum[i]=sigma(dp[k]|k为i的孩子)。

状态转移是这样的。

如果我们取的链不经过i。

那么dp[i]=sum[i]。即子树上的链重和就是答案。

如果我们要取经过i的链。注意到dp[i]的含义是以i为根节点的子树的答案。

既然i是根了。而且链经过了i。那么i必然也是链两端节点的LCA了。

取了这条链之后。对于链上的每个节点j。我们就不能再取经过它们的链了。

那么它们对dp[i]的贡献就由原来的dp[j]减少为sum[j]。

所以我们在sum[i]的基础上先减去sigma(dp[j]|j为链上的节点)再加回sigma(sum[j]|j为链上的节点)。

考虑完所有的链。

dp[i]=max(sum[i],sum[i]+weight-sigma(dp[j]|j为链上的节点)+sigma(sum[j]|j为链上的节点))。

这里官方题解似乎忘记加上sum[i]了。

 

到这里我们还有两个问题。

1.如何处理LCA。

2.计算sigma很大程度上决定了总效率。如何求和。

 

LCA我用的是离线的算法。

用一个结构体向量存以每个节点为LCA的链的端点和重量。

每找出一个LCA往向量里push。dp的时候扫一遍即可。

 

求和这里用了一个神奇的方法。

想想的话也不难理解。用了时间戳的一些性质。 

对于N个节点的情况。dfs的时候进出都打时间戳。范围就是[1,2*N]。

把进入i的时间记为Time_in[i]。出i的时间记为Time_out[i]。

然后重点来了。树状数组(或线段树)加和的对象不是节点。

而是时间。也就是上面所说的[1,2*N]的范围。

对于每个dp[i]。我们在Time_in[i]点+dp[i]。在Time_out[i]点-dp[i]。

（因为相当于是成段更新单点询问的。之前在线段树/树状数组的题目有出现过。）

那么当我们处理以i为根的子树中的链时。对于链的端点u。

询问Time_in[u]的前缀和就是从u到i的dp和。（sum同理）

原因如下。

在dfs的时候有一个性质。节点j在节点i的子树中当且仅当j的进入时间比i晚。且退出时间比i早。

递归操作在update树状数组前面。所以处理到i的时候。树状数组里加的还只有i的子树。

不在u到i之间的节点无非四种情况。

i)不在i的子树中。还没加到树状数组里。

ii)在i的子树中。但不在u的子树中。访问的时间在u的前面。退出时间也在u的前面。计算Time_in[u]前缀和的时候抵消了。

iii)在i的子树中。但不在u的子树中。访问的时间在u的后面。不被加到Time_in[u]里。

iiii)在u的子树中。访问时间在u的后面。不被加到Time_in[u]里。

从而说明了Time_in[u]的前缀和只有u到i链上的节点。

这样所有问题都解决了。

 

最后说一下整个过程。

1.初始化。读边。

2.求所有链的LCA。在算LCA递归的同时处理出每个点的时间戳。

3.按照上面说的状态转移方程树形dp。用树状数组对时间点求前缀和。

4.算出dp[1]即为答案。

以上是我自己对这道题的理解。可能代码表达的更清楚。

最后注意防爆栈黑科技。

1 #pragma comment(linker, "/STACK:1024000000,1024000000")  2 # include 
      
         3 # include 
       
          4 # include 
        
           5 # include 
         
            6 # include 
          
             7 using namespace std;  8 # define maxn 100010  9 # define CLR(x) memset(x,0,sizeof(x)) 10 vector 
           
             edge[maxn],chain[maxn],weight[maxn]; 11 int n,time,dp[maxn],sum[maxn],father[maxn],Tin[maxn],Tout[maxn]; 12 int Cdp[2*maxn],Csum[2*maxn]; 13 bool vis[maxn]; 14 15 struct node 16 { 17 int u,v,weight; 18 }; 19 vector 
            
              Vchain[maxn]; 20 21 int Find(int x) 22 { 23 return father[x]==x?x:father[x]=Find(father[x]); 24 } 25 26 void LCA(int x) 27 { 28 Tin[x]=++time; vis[x]=1; 29 for(int i=0;i
             
              0){ans+=Cdp[i]; i-=lowbit(i);} 64 return ans; 65 } 66 67 void update_sum(int i,int x) 68 { 69 while(i<=2*n){Csum[i]+=x; i+=lowbit(i);} 70 return; 71 } 72 73 int getsum(int i) 74 { 75 int ans=0; 76 while(i>0){ans+=Csum[i]; i-=lowbit(i);} 77 return ans; 78 } 79 80 void dfs(int x) 81 { 82 vis[x]=1; 83 for(int i=0;i
              
               >T;104 while(T--)105 {106 int m; scanf("%d%d",&n,&m);107 for(int i=1;i<=n;i++)108 {109 father[i]=i;110 edge[i].clear();111 chain[i].clear();112 weight[i].clear();113 Vchain[i].clear();114 }115 for(int i=0;i
              
             
            
           
          
         
        
       
      

 

 

1007 

 这个题如果知道的话就是个模板题。

先求个最短路。Dijkstra或者SPFA。

求最短路的时候用cnt数组标记下最少要几条边。

然后根据最短路所在的边重新建图。每条边权1。

存边时注意别被重边或者环坑到。

求出最大流就是第一问答案。M-cnt[N]是第二问答案。

最大流用EK必然是T的。刚学的SAP。题解用的Dinic。

1 # include 
      
         2 # include 
       
          3 # include 
        
           4 # include 
         
            5 # include 
          
             6 # include 
           
             7 using namespace std; 8 # define CLR(x) memset(x,0,sizeof(x)) 9 # define INF 2147483647 10 # define maxn 2020 11 int N,M,vis[maxn],cnt[maxn],dist[maxn]; 12 int map[maxn][maxn],pre[maxn],level[maxn],gap[maxn]; 13 vector< pair
            
              > edge[maxn]; 14 priority_queue< pair
             
               , vector< pair
              
                > , greater< pair
               
                 > > pq; 15 16 void dijkstra(void) 17 { 18 CLR(cnt); CLR(vis); 19 for(int i=1;i<=N;i++) dist[i]=INF; 20 dist[1]=0; cnt[1]=0; 21 while(!pq.empty()) pq.pop(); 22 pq.push(make_pair(0,1)); 23 while(!pq.empty()) 24 { 25 pair
                
                  tem=pq.top(); pq.pop(); 26 int to=tem.second; 27 if(vis[to]) continue; 28 vis[to]=1; 29 for(int i=0;i
                 
                  dist[to]+l) 35 { 36 dist[next]=dist[to]+l; 37 cnt[next]=cnt[to]+1; 38 pq.push(make_pair(dist[next],next)); 39 } 40 else if(dist[next]==dist[to]+l) cnt[next]=min(cnt[next],cnt[to]+1); 41 } 42 } 43 return; 44 } 45 46 void buildG(void) 47 { 48 CLR(map); 49 for(int i=1;i
                  
                    tem=edge[i][j]; 54 int to=tem.second,l=tem.first; 55 if(dist[i]+l==dist[to]) map[i][to]+=1; 56 } 57 } 58 return; 59 } 60 61 int SAP(void) 62 { 63 CLR(pre); CLR(level); CLR(gap); 64 gap[0]=N; pre[1]=1; 65 int pos=1,flow=0,aug; 66 while(level[1]
                   
                    0&&level[pos]==level[to]+1) 71 break; 72 if(to<=N) 73 { 74 pre[to]=pos; pos=to; 75 if(pos==N) 76 { 77 aug=INF; 78 for(int i=pos;i!=1;i=pre[i]) aug=min(aug,map[pre[i]][i]); 79 flow+=aug; 80 for(int i=pos;i!=1;i=pre[i]) 81 { 82 map[pre[i]][i]-=aug; 83 map[i][pre[i]]+=aug; 84 } 85 pos=1; 86 } 87 } 88 else 89 { 90 int minlevel=N; 91 for(int i=1;i<=N;i++) 92 if(map[pos][i]>0) 93 minlevel=min(minlevel,level[i]); 94 gap[level[pos]]--; 95 if(!gap[level[pos]]) break; 96 level[pos]=minlevel+1; 97 gap[level[pos]]++; 98 pos=pre[pos]; 99 } 100 }101 return flow;102 }103 104 int main(void)105 {106 // freopen("1007.in","r",stdin);107 while((scanf("%d%d",&N,&M))!=EOF)108 {109 for(int i=1;i<=N;i++) edge[i].clear();110 for(int i=1;i<=M;i++)111 {112 int a,b,l; scanf("%d%d%d",&a,&b,&l);113 edge[a].push_back(make_pair(l,b));114 edge[b].push_back(make_pair(l,a));115 }116 dijkstra(); buildG();117 printf("%d %d\n",SAP(),M-cnt[N]);118 }119 return 0;120 }
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      

 

1008 

 

1009 

按官方题解。

先处理dfs序。每添加一个点。找到集合中dfs序在它两旁且与它最邻近的点。

记为x，y。如果没有比它大的或者没有比它小的。就取字典序最大最小的两个点为x，y。

增加的花费为dis[u]-dis[lca(x,u)]-dis[lca(y,u)]+dis[lca(x,y)]

删点的时候减少的费用也是一样的。

关键在于dis[u]-dis[lca(x,u)]-dis[lca(y,u)]+dis[lca(x,y)]这个式子。

我是这样理解的。（只看增点。删点一样的。）

增点过程实际上是建一颗新树。

对于新节点u。如果找到了在它近旁的x，y。那么它就在以lca(x,y)为根的子树中。

我们只要把它连到离它最近的点即可。而这个点不是lca(x,u)就是lca(y,u)。

所以增加的费用就是u到lca(x,u)或者lca(y,u)的距离。

假设u连到lca(x,u)了。观察式子dis[u]-dis[lca(x,u)]-dis[lca(y,u)]+dis[lca(x,y)]。

其中dis[u]-dis[lca(x,u)]就是u到lca(x,u)的距离。

而lca(y,u)=lca(x,y)。后两项抵消。连到lca(y,u)同理。

再考虑找不到x，y的情况。

若u还在集合中点构成的子树中。那么情况和刚才的是一样的。

还有一种情况。就是集合中点构成的树和新点u不在同一颗子树中。

我们要做其实是先找到它们的根，即为lca(x,u) 【注意此时lca(x,u)=lca(y,u)】

再把集合中的树的根【即lca(x,y)】连到lca(x,u)。再把u连到lca(x,u)。

费用是lca(x,y)到lca(x,u)的距离加上u到lca(x,u)的距离。

再看看dis[u]-dis[lca(x,u)]-dis[lca(y,u)]+dis[lca(x,y)]。

刚才说过lca(x,u)=lca(y,u)。所以还是符合的。 

【这里LCA需要在线的。于是学了下倍增法。】

1 # include 
      
         2 # include 
       
          3 # include 
        
           4 # include 
         
            5 # include 
          
             6 # include 
           
             7 using namespace std; 8 # define maxn 100010 9 # define CLR(x) memset(x,0,sizeof(x)) 10 # define pii pair
            
              11 # define mp make_pair 12 int t,dep[maxn],p[maxn][20],dist[maxn],time[maxn],f[maxn]; 13 vector< pii > vec[maxn]; 14 set
             
               s; 15 set
              
               ::iterator it; 16 17 void dfs(int x) 18 { 19 time[x]=++t; f[t]=x; 20 for(int i=0;i
               
                =0;i--) 41 if(dep[a]-(1<
                
                 =dep[b]) 42 a=p[a][i]; 43 if(a==b) return a; 44 for(int i=log;i>=0;i--) 45 if(p[a][i]!=-1&&p[a][i]!=p[b][i]) 46 { 47 a=p[a][i]; 48 b=p[b][i]; 49 } 50 return p[a][0]; 51 } 52 53 int cal(int t) 54 { 55 if(s.empty()) return 0; 56 it=s.lower_bound(t); 57 int x,y; 58 if(it==s.begin()||it==s.end()) 59 { 60 x=(*s.begin()); 61 it=s.end(); it--; 62 y=*(it); 63 } 64 else 65 { 66 y=(*it); 67 it--; x=(*it); 68 } 69 return dist[f[t]]-dist[lca(f[x],f[t])]-dist[lca(f[y],f[t])]+dist[lca(f[x],f[y])]; 70 } 71 72 73 int main(void) 74 { 75 int T;cin>>T; 76 for(int kase=1;kase<=T;kase++) 77 { 78 int n,q; scanf("%d%d",&n,&q); 79 for(int i=1;i<=n;i++) vec[i].clear(); 80 for(int i=1;i
                
               
              
             
            
           
          
         
        
       
      

 

 

1010 

 

1011 

 

1012