倪文迪陪你学藍橋杯2021冬休み毎日一題:1.19日(2018省試合A組第7題)

2021年冬休み毎日1題、2017~2019年の省試合本題.本文の内容は倪文迪(華東理工大学コンピュータ学部ソフトウェア192クラス)と羅勇軍先生から提供された.次の毎日の問題は、新しいブログを送ります.毎日ブログのブルーブリッジカップのコラムを見てください.https://blog.csdn.net/weixin_43914593/category_10721247.html
C++、Java、Pythonの3言語のコードを提供します.
文書ディレクトリ

1、題名説明

2、題解

2.1一次元差分+二分法

2.2二次元差分、三次元差分

3、C++コード

4、ノックとテスト

4.1 pythonで暴力法のノックコード

を書く

4.2 pythonでテストデータ

を生成する

5、ビートテスト

2018省試合A組第7題「三体攻撃」、タイトルリンク:http://oj.ecustacm.cn/problem.php?id=1364 https://www.dotcpp.com/oj/problem2275.html
1、テーマの説明
Aを1つ作る.× B × C A×B×C A×B×C、すなわちA層B行C列の立方体であり、i層j行k列(戦艦(i,j,k)(i,j,k)(i,j,k))の生命値はd(i,j,k)d(i,j,k)d(i,j,k)である.  三体人隊はm輪の「立方体攻撃」を開始し、攻撃のたびに小さな立方体のすべての戦艦に同等のダメージを与えた.具体的には、第tラウンド攻撃は、7つのパラメータl a t, r a t, l b t, r b t, l c t, r c t, h t la_t, ra_t, lb_t, rb_t, lc_t, rc_t, h_t lat, rat, lbt, rbt, lct, rct, ht記述,すなわちi 96[la_t, ra_t],j ∈ [lb_t, rb_t],k ∈ [lc_t, rc_t]i ∈ [lat, rat],j ∈ [lbt, rbt],k ∈ [lct, rct]の戦艦(i, j, k)(i, j, k)(i, j, k)はh t h_t htのダメージを受ける.1つの戦艦が累積した総ダメージがその防御力を超えると、この戦艦は爆発する.  は最初の爆発した戦艦がどの攻撃後に爆発したのかを聞く. データ規模:A×   B   ×   C   ≤   1 0 6 ,   m   ≤   1 0 6 ,   0   ≤   d ( i ,   j ,   k ) ,   h t   ≤   1 0 9 A × B × C ≤ 10^6, m ≤ 10^6, 0 ≤ d(i, j, k), h_t ≤ 10^9 A × B ×ジルコニウムCジルコニウム≦ジルコニウム106,ジルコニウムmジルコニウム≦ジルコニウム106,ジルコニウム0ジルコニウム≦ジルコニウムd(i,ジルコニウムj,ジルコニウムk),ジルコニウムhtジルコニウム109.ジルコニウム時間制限:2 s.ジルコニウムメモリ制限:256 M.
2、問題解
  (比较深入地搞过算法竞赛的队员一看就知道,这是一个三维差分的模板题.)
まずデータ規模を見てみると、n=1 0 6 n=10^6 n=106点、m=1 0 6 m=10^6 m=106回の攻撃があり、暴力で攻撃するたびに各点の生命値を統計すると、複雑度はO(mn)O(mn)O(mn)O(mn)O(mn)はい、タイトルの期限は2 sで、必然的にタイムアウトします.
2.1一次元差分+二分法
  1次元、すなわちすべての戦艦が1本の線に並ぶ.  は毎回1つの区間内のすべての要素(戦艦生命値)から同じh t h_t ht値を減算し、古典的な「1次元区間修正問題」であり、「差分グループ」でデータを処理することができる. 注:「差分グループ」の概念は、博文樹状配列の「4.区間修正+単点照会」を参照してください.、「5、差分グループ」での説明.「差分グループ」を完全に理解してから下を見てください..m回の修正の総複雑度はO(m)のみです.  しかし、光用差分グループでは問題を解決できません.差分グループで区間内の各要素が0より小さいかどうかを問い合わせるため、差分グループで区間内の各要素の値を計算する必要があり、複雑度はO(n)です.合わせた総複雑度はO(mn)ですはい、実は暴力法の複雑さと同じです.2回以内にこの臨界点を見つけると、これが答えです.具体的な操作手順は、× B ×キュウC個の点(戦艦)の生命値;m回の修正を格納する.キュウ2、1回目の二分は、最大のmから:m回の修正をした後に負の値が発生するかどうかを判断する.過程は:まずm回の差分修正をして、差分数グループを得て、複雑度O(m);それからこの差分配列に基づいて各戦艦の値を計算して、負の数、複雑度O(n)があるかどうかを見る.総複雑度O(m+n).  3、以上の二分操作を繰り返して、臨界修正の回数を見つけるまで.  は全部でO(logm)次二分をして、総複雑度O(m+n)logm)、完璧に符号化任務を完成して、AC!
2.2 2 D差分、3 D差分
 同理には2次元差分と3次元差分がある.2次元差分には4つの区間端点があり、3次元差分には8つの区間端点がある.複雑度もO((m+n)logm)のですが、定数は4倍、8倍大きくなります.  羅先生はまだ2次元と3次元の差分の解析を書いていません.以下の博文を参考にすることができます:  2次元の差分:https://blog.csdn.net/justidle/article/details/104506724 3 D差分:https://blog.csdn.net/weixin_44716674/article/details/105577862 https://blog.csdn.net/weixin_43738764/article/details/105553072「この問題は主に3次元差分と2点を考察する.我々は2次元差分を処理したことがあり、局部の単点の修正と接頭辞の和を求めることによってある特定の時刻の状態を比較的に効率的に解くことができる.3次元差分は対応する立方体の8つの点を修正することであり、原理は類似している.本題の2点は負の値が現れたidであり、我々は初めて負の値が現れたidを解くだけであるで行ないます.」
3、C++コード
下のC++コードは上の解釈をはっきりと再現しています.疑問があれば、コメントを見てください.

//cpp      good.cpp
#include
using namespace std;
int A,B,C,n,m;
int d[1000005];   //       
int D[1000005];   //      （  ）；              
int lat[1000005],rat[1000005];  //    
int lbt[1000005],rbt[1000005];
int lct[1000005],rct[1000005];
int ht[1000005];
int num(int i,int j,int k) {
         //   ：  ，     [i][j][k]     ((i-1)*B+(j-1))*C+(k-1)+1
    if (i>A || j>B || k>C) return 0;
    return ((i-1)*B+(j-1))*C+(k-1)+1;
}
bool check(int x) {
                   //    x           
    for (int i=1; i<=n; i++) D[i]=0;
    for (int i=1; i<=x; i++) {
         //      ：   8     
        D[num(lat[i],  lbt[i],  lct[i])]   += ht[i];
        D[num(rat[i]+1,lbt[i],  lct[i])]   -= ht[i];
        D[num(lat[i],  rbt[i]+1,lct[i])]   -= ht[i];
        D[num(lat[i],  lbt[i],  rct[i]+1)] -= ht[i];
        D[num(rat[i]+1,rbt[i]+1,lct[i])]   += ht[i];
        D[num(lat[i],  rbt[i]+1,rct[i]+1)] += ht[i];
        D[num(rat[i]+1,lbt[i],  rct[i]+1)] += ht[i];
        D[num(rat[i]+1,rbt[i]+1,rct[i]+1)] -= ht[i];
    }
    for (int i=1; i<=A; i++)
        for (int j=1; j<=B; j++)
            for (int k=1; k<C; k++)
                D[num(i,j,k+1)] += D[num(i,j,k)];  //               

    for (int i=1; i<=A; i++)
        for (int k=1; k<=C; k++)
            for (int j=1; j<B; j++)
                D[num(i,j+1,k)] += D[num(i,j,k)];

    for (int j=1; j<=B; j++)
        for (int k=1; k<=C; k++)
            for (int i=1; i<A; i++)
                D[num(i+1,j,k)] += D[num(i,j,k)];

    for (int i=1; i<=n; i++)
        if (D[i]>d[i])
            return true; //        
    return false;
}
int main() {
     
    scanf("%d%d%d%d", &A, &B, &C, &m);
    n=A*B*C;
    for (int i=1; i<=n; i++) scanf("%d", &d[i]);
    for (int i=1; i<=m; i++) scanf("%d%d%d%d%d%d%d",&lat[i],&rat[i],&lbt[i],&rbt[i],&lct[i],&rct[i],&ht[i]);

    int L=1,R=m;      //       
    while (L<R) {
          // m    ，     
        int mid=(L+R)>>1;
        if (check(mid)) R=mid;
        else L=mid+1;
    }
    printf("%d
", R);  //     
    return 0;
}

4、ノックとテスト
  ちょうどこのテーマでノックとテストを練習します. 参考博文:Pythonのコンテストでの応用-テストデータの構造と対拍https://blog.csdn.net/weixin_43914593/article/details/111385152
4.1 pythonで暴力法のノックコードを書く
暴力コードは書きやすいです.次のコードはbaoli.pyと名付けられています.

A,B,C,m = map(int,input().split())

ship=[]
for i in range(A):
    sublist=[]
    for j in range(B):
        sublist.append([0]*C)
    ship.append(sublist)
    
life=list(map(int,input().split()))
v=0
for i in range(A):
    for j in range(B):
        for k in range(C):
            ship[i][j][k]=life[v]  #     
            v += 1
num = m
for attacknum in range(1,m+1):
    la, ra, lb, rb, lc, rc, ht = map(int,input().split())
    for i in range(la-1,ra):
        for j in range(lb-1,rb):
            for k in range(lc-1,rc):
                ship[i][j][k] -= ht
                if ship[i][j][k]<0:
                    print(attacknum)
                    exit()

4.2 pythonでテストデータを生成する
  pyファイルを作成し、問題のフォーマットに従ってテストデータを生成します.ファイル名はtest.pyです. コードは書きやすく、パラメータは設定しにくいです.読者がパラメータを設定する方法の心得があれば、教えてください.共有してください.

#test.py
from random import *
N = 1e4                       #         
HT = 1e9                      

A = randint(1,N)
B = randint(1,N//A)
C = randint(1,N//A//B)
m = randint(1,N)
print( A,B,C,m)               #   

for i in range(A*B*C-1):      #   
  print (randint(HT//1000,HT),end=' ')    #       
print (randint(HT//1000,HT))

for i in range(m):                #  m ，  7 
    lat = randint(1,A)
    rat = randint(lat,A)          #  ：rat lat 
    lbt = randint(1,B)
    rbt = randint(lbt,B)
    lct = randint(1,C)
    rct = randint(lct,C)
    ht  = randint(1,HT/100000)     #       
    print (lat,rat,lbt,rbt,lct,rct,ht)

5、ビートテスト
 本機はwindowsの下でテストする.循環テスト対拍のbatファイルを書く.aa.batと名付けられた.その仕事は、まずtest.pyでテストデータを生成し、data.inファイルに保存することである. は対拍コードtest.pyを実行し、入力データを読み、出力データをファイルpy.outに出力する. はコードgood.cppを実行し、ファイルgood.outに出力する9142.2つの出力fcとpy.outが完全に一致しているかどうかをgood.outコマンドで比較します.

@echo off
set path=C:\MinGW\bin
g++ -o good.exe good.cpp
:loop
set path=C:\Users\hp\AppData\Local\Programs\Python\Python39
python test.py >data.in
good.exe <data.in >good.out
python baoli.py <data.in >py.out
set path=C:\Windows\System32
fc py.out good.out
good.exe <data.in
if errorlevel == 1 pause
goto loop

  答えを見極めるために、テストごとの出力も印刷されました.windowsのpathでpathを実行し、結果は以下の通りです.

D:\cpp>aa.bat
       py.out   GOOD.OUT
FC:      

686
       py.out   GOOD.OUT
FC:      

995
       py.out   GOOD.OUT
FC:      

1597
       py.out   GOOD.OUT
FC: