Mirko在一家大型IT公司暑假實習。 該公司構建了一個由N行和M列組成的大型數據庫。

在他第一天，Mirko收到了Q個查詢。 每個查詢由M個數字組成。

然而，一些數字在傳輸過程中丟失，所以它們用-1表示。 Mirko想知道數據庫中有多少行對應于查詢，即數據庫的行數與查詢相同，不包括-1。

例如，如果查詢是-1 3 2的形式，那么我們需要統計滿足，第一列是任何數字，第二列中的數字為3 ，第3列中的數字2。

由于他剛開始實習，Mirko需要你的幫助。 幫助他并回答查詢！

輸入

第一行輸入包含數據庫的大小N（1≤N≤1e3）和M（1≤M≤1e3）。

以下N行中的每一行包含M數字A ij（1≤Aij≤10^6），數據庫的內容。

以下行包含Q（1≤Q≤50），查詢次數。

以下Q行中的每一行包含M個數字Bij（Bij = -1 或1≤Bij≤10^6），表示第i個查詢的描述。

輸出

輸出必須包含Q行，每行包含X，表示第i個查詢的答案。

樣例略

題解：

初次寫題解，不喜勿噴。本題就是一道帶有一定思維難度的模擬，因為數據較小，所以普及提高還可以出，（Q<=1000時，用分塊FFT搞定，這個至少 省選（也可能是國賽才有，畢竟還沒考過））。直接按照題意寫會TLE，所以需要注意一些細節。

首先是在每個查詢的位置，這是本題主要卡時間的地方，至少我在SDOJ上被卡掉了20分（類樂多賽制），我們在這里只需要一個二層循環實現，但很容易寫出一個來標記，一個來查找這種思維簡單但十分費事的算法。所以應該按照題目給出的每組數據，從前到后掃描，匹配每個位置，遇到-1就continue，同時用一個變量來記錄方案數，我用的是ans。這個ans有個很巧妙的設計，就是在開始時，將ans初始化為N，就是行數（因為是查詢是詢問有多少行），然后一旦失配，就break，并將ans--。

題解說完了，上代碼：

#include<bits/stdc++.h> using namespace std; const int N=1005; int n,m,a[N][N],b[N]; int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);int Q;scanf("%d",&Q);while(Q--){for(int i=1;i<=m;i++)scanf("%d",&b[i]);int ans=n;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(b[j]==-1)continue;else{if(a[i][j]==b[j])continue;else{ans--;break;}}}}cout<<ans<<endl;}return 0; }

轉載于:https://www.cnblogs.com/Neonen/p/9832504.html

總結

以上是生活随笔為你收集整理的我的做题日志（1），来源：COCI2017，SDOJ的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。