【BZOJ】2321:[BeiJing 2011合宿]星器(数学+特殊なテクニック)

 http://www.lydsy.com/JudgeOnline/problem.php?id=2321
全く思いもよらなかった.
第一眼は爆捜だと思っていたが、データの範囲を見て断固として放棄した.2番目の目は、ネットワーク・フロー(行列操作のみなので、ポイントに接続して容量を設定するなど面倒なものを最大ストリームにします)、モデリングが面倒だと思って諦めます.
数学...
まず、本題には次のような性質があります.
答えは移動方法とは関係ありません(行列制限があり、2つが同時に同業者で同列に移動するため、この行のこの列に点が終点であれば、どのように積算しても、到達できる点からここまでの距離と等しい)
これにより、答えを迂回することができます.
長方形を見てみましょう
0 0 0 1
0 0 0 0
1 0 0 0
私たちは左下から右上に行きます(本題では必ず左下が左上か右下に着いてから右上に行きます)
距離は同じです.のこのように統合された答えと同じです.
長方形では対角線の距離は変わりません..
そして私たちはその性質を十分に掘り起こさなければならない.
この矩形を各点に置くと,元の矩形の左上隅から各点までの行列が
 
そしてネット上の問題解があります.
まず,2つの点(i,j),(i,k)が中間に1格移動し,k>j+1であると仮定すると,得られる価値はk−jであり,このようにして,各点の各星のエネルギーをa[(i,j)]=i*i+j*jと定義し,この2つの点からのエネルギーをi*i+j*j+i*i+kとし,移動後,2つの点を(i,j+1),(i,k−1),このときのエネルギーをi*i+i+(j+1)*(j+1)+i*i+(k−1),このときのエネルギー差は2*k-2*jであり,獲得価値の2倍であり,すべての価値獲得に対してこのような方法が採用できるため,開始局面のエネルギーと,終了局面のエネルギーと,減算>>1が答えである.
このようにした原因は私が言ったことです.
 

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << #x << " = " << x << endl

#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }



int main() {

	long long ans=0, n, m;

	read(n); read(m);

	for1(i, 1, n) for1(j, 1, m) ans+=(long long)(i*i+j*j)*getint();

	for1(i, 1, n) for1(j, 1, m) ans-=(long long)(i*i+j*j)*getint();

	printf("%lld", ans>>1);

	return 0;

}

 
 
 
 
Description
Magic Landの時間はまた何世紀も経った......
今、人々は伝説について話しています.昔、彼らの祖先は東方にある島に来ました.そこはまるで別の世界です.分析と構造に長けたMagic Landの人々は、そこの人々がどのように正確な実験と計算を借りて魔法を駆動し、操作しないのか分からない.
偶然、魔法使い(Magician)がMagic Landに来て、帰る時に不思議な箱を残して、星器(Casket of star)と呼ばれています.
この箱が何をしているのか分からないが、大量の実験と計算を経て、人々はすでにそのいくつかの事実を知っている.
1.星器の中にNがある×M個の領域は、N行とM列に分かれた格子と見なすことができ、各領域にはいくつかの単位の「星」と呼ばれるオブジェクトがあり、このオブジェクトの最小単位が決定されているので、この数は常に整数である.
2.魔法使いは、星器の同じ行または同じ列にある隣接しない(共通のエッジがある領域を隣接と呼ぶ)2つの領域の各1単位の「星」を駆動し、それぞれ中心に1格移動させることができる.
3.毎回2の方法で「星」を駆動すると、魔力が発生し、魔法使いはこの魔力の一部を得る.魔力の量はこの2つの領域の間に隔てられた領域数に等しい.
これでNを1つ使うことができます×Mの数表は星器の状態を表し、例えばN=2、M=3の場合:
2
0
1
 
 
1
2
0
5
1
4
 
 
5
1
4
星器が左図の状態である場合、1行目の1番目と3番目の領域の「星」(太字の数字に対応する領域)を操作することで、右図に示す状態になり、同時に1単位の魔力が発生する(この2つの領域の間にちょうど1つの領域が隔てられているため).
さらなる研究を経て,この星器の最初の状態(Ini)と最終的に彼らに得られた時の状態(Fin)が知られた.
星器が所有者にどれだけの魔力を提供したかを知りたい.すなわち、一連の上述の操作によって初期状態(Ini)から最終状態(Fin)に変化し、どれだけの魔力が発生するか.
注意しなければならないのは、操作中に各領域内の「星」の数が負ではないことです.つまり、その領域に「星」がなければ、もちろん操作を続けることはできません.
 
Input
最初の行には、2つの正の整数N、Mがスターのサイズを表します.
次のN行は,各行にM個の自然数:Iniijを含み,初期状態(Ini)を描いた.
1つの空の行の後のN行では、各行はM個の自然数:Finijを含み、終態(Fin)を描いている.
 
Output
発生する魔力を表す正の整数を出力します.
 
Sample Input
【入力サンプル1】
5 5
1 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 1 0 1 1
1 0 0 0 0
0 0 0 0 0
0 0 0 0 1
2 0 0 0 1
0 0 2 0 0
0 0 0 0 0
【入力サンプル2】
1 4
10 20 30 40
0 0 100 0
Sample Output
【出力サンプル1】
7
【様式1解釈】
唯一の操作方法は次のとおりです.
5列目の2つの「星」を1回操作し、魔力2を発生させる.
1列目の2つの「星」を2回操作し、魔力3+1を生成する.
4行目の2つの「星」を1回操作し、魔力1を発生させる.
全部で7ユニットの魔力を生み出す.
【出力サンプル2】
50
HINT
【データ規模と約定】40%のデータのうちN≦2、例えばサンプル2;
100%のデータでは1≦N,M≦200,Iniij,Finij≦1000であった.
すべてのデータは、星が初期状態から最終状態に変化するように少なくとも1つの操作方法が存在することを保証し、同時に初期状態と最終状態が完全に同じではないことを保証する.
Source