Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:这题如果M,N可能很大怎么办?

Posted by Liuzhaoliang at 2014-08-14 11:21:42 on Problem 3752
In Reply To:这题如果M,N可能很大怎么办? Posted by:wcfairytale at 2011-10-16 22:51:26
> 题目可没规定数据范围哟
我YY出一个方法来通过(i,j)直接计算字母。不用填充矩阵。
思路是找出(i,j)在第几个环里。还有在这个环的偏移。

#include<iostream>
#include<vector>
#include<string.h>
#include<stdio.h>
#include<stack>
#include<algorithm>
#include<stdlib.h>
#include<queue>
#include<utility>
using namespace std;
int N,M;
int get_total(int m){
    if(m==0) return 0;
    else return 2*m*(M+N)+4*m - 8*m*(m+1)/2;
}
int get(int i,int j){
    int m = min(i,j);
    m = min(m,M+1-i);
    m = min(m,N+1-j);
    int off = get_total(m-1);
    int X = M-2*(m-1), Y = N-2*(m-1);
    int dx = i-m, dy = j-m;
    if(dx==0) return off+dy+1;
    if(dy==0) return off+2*(X+Y)-4-dx+1;
    if(dy==Y-1) return off+Y + dx;
    return off+Y + Y - dy + X-2;
    
}
int main(){
    cin>>M>>N;
    for(int i=1;i<=M;i++){
        for(int j=1;j<=N;j++){
            printf("   %c",(get(i,j)-1)%26+'A');
        }
        cout<<endl;
    }
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator