2014
02-13

# 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]);
}
}
}

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;
}