首页 > ACM题库 > HDU-杭电 > HDU 1759 Matrix Revolution-线段树[解题报告] C++
2013
12-23

HDU 1759 Matrix Revolution-线段树[解题报告] C++

Matrix Revolution

问题描述 :

Lele 现在不仅会整数A+B,A*B,还会矩阵A+B,矩阵A*B。

一天,Lele在百无聊赖的时候,突然想起一个很无聊的问题。
对于给定的一个矩阵A,A+A^2+A^3+…+A^K 是多少呢?
其中A^2 表示两个矩阵的乘积A*A,A^3表示三个矩阵的乘积A*A*A,依此类推。

由于这个计算结果太大了,Lele无法把整个结果写出来,但是,他还是想请你告诉他,结果矩阵中到底有多少个非零元素。

输入:

本题目包含多组测试,请处理到文件结束。
在每个测试数据的第一行,有三个整数N,M,和K(0<N<1000,0<=M<10*N,N<K<10^100),其中N代表矩阵A的大小是N*N,K是题目中所描述的K。
接下来有M行,每行有三个整数a,b,c(0<=a,b,<N 且a!=b,0<c<10^9)表示矩阵中第a行第b列的值为c。(矩阵的行数和列数都是从0开始计数)

你可以假定矩阵中主对角线上的数都是1,其余没有提到的元素都是0。

输出:

对于每一组测试数据,请在一行里输出结果矩阵里的非0元素的个数。

样例输入:

3 4 4
1 2 1
2 1 1
0 1 1
0 2 1

样例输出:

7

Hint
Huge input,the C function scanf() will work better than cin

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1754

存四个变量,两个边界一个sum存其成绩,max存这段的最值。在更新成绩时 父节点的max要同时更新。

#include <iostream>
 #include <cstdio>
 #include <cstring>
 using namespace std;
 #define L(x)(x<<1)
 #define R(x)(x<<1|1)
 #define MID(x,y) ((x+y)>>1)
 const int MAX=200005;
 struct Tnode{
 int sum,left,right,max;
 }node[MAX*4];
 int num[MAX];
 void init()
 {
     memset(node,0,sizeof(node));
 }
 void Build(int t,int l,int r)
 {
     node[t].left=l;
     node[t].right=r;
     if(l+1==r)
     {
         node[t].sum=num[l];
         node[t].max=num[l];
         return ;
     }
     int mid=MID(l,r);
     Build(L(t),l,mid);
     Build(R(t),mid,r);
     node[t].max=(node[L(t)].max>node[R(t)].max)?node[L(t)].max:node[R(t)].max;
 }
 void update(int t,int l,int r,int sum)
 {
     if(node[t].left==l&&node[t].right==r)
     {
         node[t].sum=sum;
         node[t].max=sum;
         return ;
     }
     int mid=MID(node[t].left,node[t].right);
     if(l>=mid) update(R(t),l,r,sum);
     else if(r<=mid) update(L(t),l,r,sum);
     else {
         update(L(t),l,mid,sum);
         update(R(t),mid,r,sum);
     }
     //if(node[t].max<sum)node[t].max=sum;
     node[t].max=(node[L(t)].max>node[R(t)].max)?node[L(t)].max:node[R(t)].max;
 }
 int query(int t,int l,int r)
 {
     int gg,mm,tt;
     if( node[t].left == l && node[t].right == r )
         return node[t].max;
     int mid = MID(node[t].left,node[t].right);
     if( l >= mid )
         return query(R(t),l,r);
     else
         if( r <= mid )
             return query(L(t),l,r);
         else
         {
             gg=query(L(t),l,mid);
             mm=query(R(t),mid,r);
             if(gg>mm)tt=gg;
             else tt=mm;
             return tt;
         }
 
 }
 int main()
 {
      int ind = 1,m,n,x,y;
      char s[10];
 
     while(scanf("%d%d",&n,&m)!=EOF)
     {
         for(int i=0; i<n; i++)
             scanf("%d",&num[i]);
         init();
         Build(1,0,n+1);
 
         while(m--)
         {
             scanf("%s%d%d",s,&x,&y);
 
             if(s[0] =='U' )
                 update(1,x-1,x,y);
             else
                 printf("%d\n",query(1,x-1,y));
         }
     }
 return 0;
 }

 

解题报告转自:http://www.cnblogs.com/zhaoguanqin/archive/2012/02/27/2370185.html


  1. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  2. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。