NOIP--螺旋行列(テクニック+シミュレーション)

2857 ワード
思考 シミュレーション+xx
問題C:螺旋行列
時間制限:1 Sec
メモリ制限:128 MB
コミット:132
解決策:49
[提出][状態][討論版][命題者:
admin]
タイトルの説明
n行n列の螺旋行列は、以下の方法で生成することができる.
行列の左上隅(1行目1列目)から、初期に右に移動し、前方が通過していない格子であれば前進し続け、そうでなければ右折し、行列中のすべての格子が通過するまで上記操作を繰り返す.通過順に従って、格子に1,2,3,...,n 2を順次記入し、1つの螺旋行列を構成する.
下図はn=4のときの螺旋行列です.
マトリクスサイズnおよびiおよびjを示します.このマトリクスのi行目j列の数を求めてください.
入力
3つの整数n,i,jを含む合計1行を入力し、2つの整数の間に1つのスペースで区切られ、行列のサイズ、求められる数の行番号、列番号をそれぞれ表します.
1≤n≤30000,1≤i≤n,1≤j≤n
しゅつりょく
出力は、対応するマトリクスのi行目j列目の数を表す整数を含む行である.
サンプル入力
4 2 3

サンプル出力
14

问题解:データ量30000なので、直接シミュレーションしてはいけないので、いくつかのテクニックが必要です.この行列に対して、i、jの数字を直接探せば、私は本当に探しにくいですが、もしそれが最外層にあるなら、探しやすくなり(玉ねぎのように螺旋状に入ると心を剥がす)、このi行j列が最外層でない場合、このn次行列をn-2次行列に変換することができ、このときi行j列がこのときのi-1行j-1列になり、最初の行の最初の列の要素が元のaになる[1][1]+4*n-4、最終的には最外層になってから4つの状況に分けてよく分析すればいいです.
#include
#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
#define FAST_IO ios::sync_with_stdio(false)
const double PI = acos(-1.0);
const double eps = 1e-6;
const int MAX=1e5+10;
const int mod=1e9+7;
typedef long long ll;
using namespace std;
inline ll gcd(ll a,ll b){if(!b)return a;return gcd(b,a%b);}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline ll qpow(ll a,ll b){ll r=1,t=a; while(b){if(b&1)r=(r*t)%mod;b>>=1;t=(t*t)%mod;}return r;}
inline ll inv1(ll b){return qpow(b,mod-2);}
inline ll inv2(ll b){return b==1?1:(mod-mod/b)*inv2(mod%b)%mod;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll r=exgcd(b,a%b,y,x);y-=(a/b)*x;return r;}
inline ll read(){ll x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f;}
 
int main ()
{
    ll n,a,b;
 
    n=read();
    a=read();
    b=read();
 
    ll ans=1;
    while(a!=n && b!=n && a>1 && b>1)
    {
       a--;b--;
       ans+=(4*(n-1));
       n-=2;
    }
 
    if(a==1)
        ans+=b-1;
    else if(a>1 && a!=n)
    {
        if(b==1)
            ans+=(4*n-5-a+2);
        else
            ans+=(n+a-2);
    }
    else
        ans+=(3*n-2-b);
 
    cout<
PHP大数加算
phpのmysql関数