hdu5892Resident Evil

2167 ワード

オンライン judge Hdu データ構造ツリー配列その他プレフィックスと数学叱責を許す

リンク:http://acm.hdu.edu.cn/showproblem.php?pid=5892
題意:所与のnとmはn*nのマトリクスとmの操作を表し、操作1:左上角の位置[x 1,y 1]と右下角の位置[x 2,y 2]を与え、次に所与のkはk対[a,b]を表し、次にこの所与のマトリクスに各格子にb個のa類物品を添加する.操作2:左上隅位置[x 1,y 1]と右下隅位置[x 2,y 2]を与え、この行列におけるすべての物品のパリティを求める.
分析:まず物品が50種類しかないため,状態圧縮とマトリクスの反発問題は容易に考えられる.問題を[1,1]~[x,y]を求める行列におけるパリティの場合に変換したが,操作1の影響を自分で図面で見ると,1行または1列離れた点だけが役に立つことが分かった.まずこの問題を簡略化してみましょう.もし1次元であればどう処理しますか.区間追加、区間クエリー.区間追加を単点追加にすることができ、区間[x,y]に1つのアイテムを追加すると、奇数の場合、x,x+2,x+4...これらの間隔の位置にのみ影響があることがわかります.ここでは、パリティの2つの位置を2つの配列に分解して維持すればよいと考えられ、接頭辞和は異ならないことが考えられます.そして問題を2次元に戻し,[1,1]~[x,y]のxとyのパリティに基づいて行列を4つに分けることができ,対応する行列を維持するたびにすればよい.まだわからない場合はコードを参考にしましょう.
コード:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int N=1510;
const int M=50010;
const int mod=1000000007;
const int MOD1=1000000007;
const int MOD2=1000000009;
const double EPS=0.00000001;
typedef long long ll;
const ll MOD=1000000007;
const int INF=1000000010;
const ll MAX=1ll<<55;
const double eps=1e-5;
const double inf=~0u>>1;
const double pi=acos(-1.0);
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
int mx;
char s[3];
ll B,t[55],f[2][2][N][N];
ll getans(int x,int y) {
    int one=x&1,two=y&1;ll ret=0;
    int i,j,X=x/2+one,Y=y/2+two;
    for (i=X;i;i-=i&-i)
        for (j=Y;j;j-=j&-j) ret^=f[one][two][i][j];
    return ret;
}
void add(int x,int y) {
    int one=x&1,two=y&1;
    int i,j,X=x/2+one,Y=y/2+two;
    for (i=X;i<=mx;i+=i&-i)
        for (j=Y;j<=mx;j+=j&-j) f[one][two][i][j]^=B;
}
int main()
{
    int i,j,k,n,m,x,y,x1,y1,x2,y2;
    for (i=0;i<=50;i++) t[i]=1ll<

Java操作mongodeDB 2.6の一般的なAPIの使い方

N個の重複しない乱数を生産する(一つの配列からN個の要素をランダムに取る)