1001 

线段树。根据奇偶性分成4个区间。维护子列和最大值。

想法很简单。但是并不好写。

首先初始化的时候对于不存在的点要写成-INF。

然后pushup的时候。对于每个区间要考虑四个情况。

例如sum01。

他可能是左子树的sum01右子树的sum01。

或者左子树的sum01+右子树的sum01。

或者左子树的sum00+右子树的sum11。

最后注意query函数的写法。

如果在递归的时候就讨论奇偶性。

下层的每个区间都要被重复调用。而且是层数的指数级。

于是参考学习了一种直接把子区间合并成一个区间类型返回的方法。

合成目标区间后再讨论奇偶性。

【其实pushup和query可以写好看些。好不容易调对。懒得改了。】

1 # include 
      
         2 # include 
       
          3 # include 
        
           4 using namespace std;  5 typedef long long LL;  6 # define maxn 100010  7 # define INF (LL)1000000000000  8 LL a[maxn];  9  10 struct node 11 { 12     int l,r; 13     LL sum00,sum01,sum10,sum11; 14 }tree[4*maxn]; 15  16 void pushup(int i) 17 { 18     tree[i].sum00=tree[i].sum01=tree[i].sum10=tree[i].sum11=-INF; 19     tree[i].sum00=max(tree[i].sum00,tree[2*i].sum00+tree[2*i+1].sum10); 20     tree[i].sum00=max(tree[i].sum00,tree[2*i].sum01+tree[2*i+1].sum00); 21     tree[i].sum00=max(tree[i].sum00,tree[2*i].sum00); 22     tree[i].sum00=max(tree[i].sum00,tree[2*i+1].sum00); 23     tree[i].sum01=max(tree[i].sum01,tree[2*i].sum00+tree[2*i+1].sum11); 24     tree[i].sum01=max(tree[i].sum01,tree[2*i].sum01+tree[2*i+1].sum01); 25     tree[i].sum01=max(tree[i].sum01,tree[2*i].sum01); 26     tree[i].sum01=max(tree[i].sum01,tree[2*i+1].sum01); 27     tree[i].sum10=max(tree[i].sum10,tree[2*i].sum10+tree[2*i+1].sum10); 28     tree[i].sum10=max(tree[i].sum10,tree[2*i].sum11+tree[2*i+1].sum00); 29     tree[i].sum10=max(tree[i].sum10,tree[2*i].sum10); 30     tree[i].sum10=max(tree[i].sum10,tree[2*i+1].sum10); 31     tree[i].sum11=max(tree[i].sum11,tree[2*i].sum10+tree[2*i+1].sum11); 32     tree[i].sum11=max(tree[i].sum11,tree[2*i].sum11+tree[2*i+1].sum01); 33     tree[i].sum11=max(tree[i].sum11,tree[2*i].sum11); 34     tree[i].sum11=max(tree[i].sum11,tree[2*i+1].sum11); 35     return; 36 } 37  38 void buildtree(int i,int l,int r) 39 { 40     tree[i].l=l; tree[i].r=r; 41     if(l
         
          =l&&tree[i].r<=r) return tree[i]; 82     if(r<=(tree[i].l+tree[i].r)/2) return query(2*i,l,r); 83     if(l>=(tree[i].l+tree[i].r)/2+1) return query(2*i+1,l,r); 84     node t,t1,t2; 85     t1=query(2*i,l,r); 86     t2=query(2*i+1,l,r); 87     t.sum00=max(t1.sum00,t2.sum00); 88     t.sum00=max(t.sum00,t1.sum00+t2.sum10); 89     t.sum00=max(t.sum00,t1.sum01+t2.sum00); 90     t.sum01=max(t1.sum01,t2.sum01); 91     t.sum01=max(t.sum01,t1.sum00+t2.sum11); 92     t.sum01=max(t.sum01,t1.sum01+t2.sum01); 93     t.sum10=max(t1.sum10,t2.sum10); 94     t.sum10=max(t.sum10,t1.sum10+t2.sum10); 95     t.sum10=max(t.sum10,t1.sum11+t2.sum00); 96     t.sum11=max(t1.sum11,t2.sum11); 97     t.sum11=max(t.sum11,t1.sum10+t2.sum11); 98     t.sum11=max(t.sum11,t1.sum11+t2.sum01); 99     return t;100 }101 102 int main(void)103 {104     int T; cin>>T;105     while(T--)106     {107         int n,m; scanf("%d%d",&n,&m);108         for(int i=1;i<=n;i++) scanf("%I64d",a+i);109         buildtree(1,1,n);110         while(m--)111         {112             int type,x,y; scanf("%d%d%d",&type,&x,&y);113             if(type) update(1,x,y);114             else115             {116                 node tem=query(1,x,y);117                 LL ans=-INF;118                 ans=max(ans,tem.sum00);119                 ans=max(ans,tem.sum01);120                 ans=max(ans,tem.sum10);121                 ans=max(ans,tem.sum11);122                 printf("%I64d\n",ans);123             }124         }    125     }126     return 0;127 }
         
        
       
      

 

 

1002 

先枚举1000000内所有质因数。

然后统计区间内每个数的质因数个数。

注意到最大只有7。

对于因子个数为1-7的数的个数处理一下前缀和。

对于每个询问。算区间内因子数分别为1-7的数的个数。

找到最大的gcd就是答案。

1 # include 
      
        2 # include 
       
         3 # include 
        
          4 # include 
         
           5 # include 
          
            6 using namespace std; 7 # define maxn 1000010     8 bool tag[maxn]={
    1,1}; 9 int prime[42000],cnt[maxn]={
    0},presum[8][maxn]={
    0};10 11 int main(void)12 {13     int t=0;14     for(int i=2;i
           
            >T;33 while(T--)34 {35 int l,r; scanf("%d%d",&l,&r);36 int mark[8]={ 0};37 for(int i=1;i<8;i++) mark[i]=max(0,presum[i][r]-presum[i][l-1]);38 if(mark[7]>=2) printf("7\n");39 else if(mark[6]>=2) printf("6\n");40 else if(mark[5]>=2) printf("5\n");41 else if(mark[4]>=2) printf("4\n");42 else if(mark[3]>=2||mark[3]&&mark[6]) printf("3\n");43 else if(mark[2]>=2||mark[2]&&mark[4]||mark[2]&&mark[6]) printf("2\n");44 else printf("1\n");45 }46 return 0; 47 }
           
          
         
        
       
      

 

 

1003 

 

1004 

看成R和B的两张图。

统计R\斜边上与B/斜边上的连续染色段数即为答案。

1 # include 
      
        2 # include 
       
         3 # include 
        
          4 using namespace std; 5 # define CLR(x) memset(x,0,sizeof(x))  6 char map[55][55]; 7 int R[55][55],B[55][55]; 8  9 int main(void)10 {11     int T; cin>>T;12     while(T--)13     {14         CLR(map); CLR(R); CLR(B);15         int n; scanf("%d",&n);16         for(int i=0;i
         
          =0;j++)40             {41                 if(i-j>=n) continue;42                 if(!flag&&B[i-j][j]) {ans++;flag=1;}43                 if(!B[i-j][j]) flag=0;44             }45         }46         printf("%d\n",ans);47     }48     return 0;49 }
         
        
       
      

 

 

1005 

 

1006 

 

1007 

 

1008 

暴搜可行 证明不会。

l<0跳。l>r-l跳。r>现有答案跳。

搜[l,2*r-l]的时候注意死循环。

1 # include 
      
        2 # include 
       
         3 # include 
        
          4 using namespace std; 5 typedef long long LL; 6 LL ans; 7  8 void dfs(LL l,LL r) 9 {10     if(l==0)11     {12         if(ans==-1) ans=r;13         else ans=min(ans,r);14         return;15     }16     if(l<0) return;17     if(ans!=-1&&r>=ans) return;18     if(r>2*l) return;19     if(r>l) dfs(l,2*r-l);20     dfs(2*l-r-1,r);21     dfs(2*l-r-2,r);22     dfs(l,2*r-l+1);23     return;24 }25 26 int main(void)27 {28     LL l,r;29     while((scanf("%I64d%I64d",&l,&r))!=EOF)30     {31         ans=-1;32         dfs(l,r);33         printf("%I64d\n",ans);34     }35     return 0;36 }
        
       
      

 

 

1009 

 

1010 

按官方题解。

把每条边变成从w大的点到w小的点的有像边。 

以u为min的目标集就是能走到u的点的集合。

花了较长的时间思考这个问题。

换一种说法。

其实就是对于一个已经确定最小值u的目标集S。

点v在S中当且仅当v能通过递减的路到达u。

简要说明一下必要性和充分性。

随手画了个图。

任意取一条链。比方X。它必然有一个端点x1。

只要说明离x1最近的点x2小于x1。然后考虑去掉x1的图。归纳即可得到上述结论。

考虑S中比x1小的最大的点p的位置。

如果x2就是p。那么它比x1小。

如果x2不是p。那么由于x2离x1最近。无论p在什么位置。x2都在p-x1的链上。

根据S的定义。x2小于x1。

反之。如果所有链都是以递减的顺序通向u的。

那么考虑图中的最大点。其必然在一条链的端点。

比方仍取X链。x1是最大点。

最大点给集合带来的约束条件只有一条。

那就是最大点到次大点的路径上的所有点小于最大点。

但是所有点都小于最大点。所以这个条件必然成立。

也就是说原来的点属于S集等价于去掉最大点后的所有点属于S集合。

而去掉x1后的最大点可能是x2或者是其他链的端点。

只要不断从端点去掉最大点。归纳即可证明原来的所有点属于S集。

证明这个之后。树dp即可。

1 # include 
      
        2 # include 
       
         3 # include 
        
          4 # include 
         
           5 # include 
          
            6 using namespace std; 7 # define maxn 500050 8 int w[maxn],dp[maxn]; 9 vector
           
             edge[maxn];10 11 struct V12 {13 int id,w;14 } node[maxn];15 16 bool cmp(V a,V b)17 {18 return a.w>b.w;19 }20 21 int main(void)22 {23 int n;24 while((scanf("%d",&n))!=EOF)25 {26 memset(edge,0,sizeof(edge));27 for(int i=1;i<=n;i++)28 {29 scanf("%d",w+i);30 node[i].id=i;31 node[i].w=w[i];32 }33 for(int i=1;i
            
             w[b]) edge[b].push_back(a);37 else if(w[a]
            
           
          
         
        
       
      

 

 

1011 

签到题。dfs一遍即可。

1 # include 
      
        2 # include 
       
         3 # include 
        
          4 # include 
         
           5 using namespace std; 6 int ind[105],cnt[105]; 7 vector 
          
            edge[105]; 8  9 void dfs(int x)10 {11     cnt[x]=edge[x].size();12     for(int i=0;i