首页 > ACM题库 > HDU-杭电 > hdu 2687 Matrix Rotation-线段树-[解题报告]C++
2014
02-13

hdu 2687 Matrix Rotation-线段树-[解题报告]C++

Matrix Rotation

问题描述 :

Give you a n*n matrix, if you rotate it 90 degrees, we call it 1-Matrix, if you rotate it 180 degrees, we call it 2-Matrix, etc … This is said if you rotate the Matrix 90*k degrees, then we call it k-Matrix. Now, your task is to calculate all the sum of i-Matrix (0<= i<= k).

输入:

There multiple test cases. Each test case begins with one integer n(1 <= n <= 10), following n lines, each line contains n integers, describe the original matrix, then a single line contains a k
(1 <= k <= 10^8)described above. Process to end of file.

输出:

There multiple test cases. Each test case begins with one integer n(1 <= n <= 10), following n lines, each line contains n integers, describe the original matrix, then a single line contains a k
(1 <= k <= 10^8)described above. Process to end of file.

样例输入:

3
1 2 3
2 3 4
3 4 5 
10

样例输出:

33 32 31
34 33 32
35 34 33 

sl代表当前线段从最右端开始的最大长度,sr代表最左端

s代表当前线段和,ss当前最大字段长

ss的值从三种状态转移而来,ss[rt<<1],ss[rt<<1|1],sl[rt<<1]+sr[rt<<1|1];

即左儿子最大字段长,右儿子最大字段长,抑或由中间向两边延伸的最大字段长

用线段树维护上述变量

#include <stdio.h>
#include <iostream>
using namespace std;
const int maxn=100001;
int n,m;
int s[maxn<<2],sl[maxn<<2],sr[maxn<<2],ss[maxn<<2];
void pushup(int rt)
{
    s[rt]=s[rt<<1]+s[rt<<1|1];
    sl[rt]=max(s[rt<<1|1]+sl[rt<<1],sl[rt<<1|1]);
    sr[rt]=max(s[rt<<1]+sr[rt<<1|1],sr[rt<<1]);
    ss[rt]=max(ss[rt<<1],ss[rt<<1|1]);
    ss[rt]=max(ss[rt],sl[rt<<1]+sr[rt<<1|1]);
}
void init(int rt,int l,int r)
{
    int m=(l+r)>>1;
    if(l!=r)
    {
        init(rt<<1,l,m);
        init(rt<<1|1,m+1,r);
        pushup(rt);
    }
    else
    {
        scanf("%d",&s[rt]);
        sl[rt]=sr[rt]=ss[rt]=s[rt];
    }
}
void change(int rt,int l,int r,int t,int tt)
{
    if(l==t&&r==t)
    {
        sl[rt]=sr[rt]=ss[rt]=s[rt]=tt;
    }
    else
    {
        int m=(l+r)>>1;
        if(m>=t)
            change(rt<<1,l,m,t,tt);
        else
            change(rt<<1|1,m+1,r,t,tt);
        pushup(rt);
    }
}
int main()
{
    int t,tt;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init(1,1,n);
        while(m--)
        {
            scanf("%d%d",&t,&tt);
            change(1,1,n,t,tt);
            printf("%d\n",ss[1]);
        }
    }
}

 

解题转自:http://www.cnblogs.com/acahesky/archive/2013/08/07/3243511.html


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  3. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }