目錄
1,小美的平衡矩陣
2,小美的數組詢問
3,小美的MT
?4,小美的朋友關系
1,小美的平衡矩陣
?【題目描述】
給定一個n*n的矩陣,該矩陣只包含數字0和1。對于 每個i(1<=i<=n),求在該矩陣中,有多少個i*i的區域滿足0的個數等于1的個數???
【題目解析】
示例演示:
?如上圖,1*1的區域結果為0,2*2的區域結果為7。
算法:前綴和+遍歷
題目中給的數據范圍是n<=200,所以可以直接遍歷數組。
維護 一個前綴和數組統計以(x,y)這個點為右下角,以(1,1)這個點為左上角,這個區域中所有元素的和,由于數組中的數要么是0,要么是1,所以前綴和就表示某個區域中1的個數。
有了前綴和數組,就可以快速 求出某個區域中1的個數,如圖:
而這個區域的大小我們是知道的,假設是k,那么這個區域的元素個數就是k*k。如果滿足這個區間中1的個數等于k*k/2,那么說明 這個區間中0和1的個數 相等。而1的個數我們可以通過前綴和來表示。
同時還有一點,如果k為奇數,那么k*k的區域中元素個數一定為奇數 ,所以0和1的個數一定不相等。直接輸出0即可。
?注意:在輸入數據的時候,如果是以整數的形式接受,那么不建議使用cin,因為cin會把第一行的所有數據讀成一個整數。就比如 上面的示例,第一行會被讀成一個整數1010,而我們期望是讀到4個整數的,這是可以使用scanf("%1d",&a),使用 %1d占位符可以確保讀到的第一行是4個整數。
【代碼】
#include <iostream>
#include <vector>
using namespace std;const int N = 205;
int arr[N][N], s[N][N];
//s為前綴和數組
//統計矩形(1,1)到(n,n)中1的數量int main()
{int n = 0;cin >> n;for(int i=1;i<=n;i++)for (int j = 1; j <= n; j++){scanf("%1d", &arr[i][j]);s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + arr[i][j];}cout << 0 << endl;for (int k = 2; k <= n; k++){if (k & 1){cout << 0 << endl;continue;}int ans = 0;for(int i=1;i+k-1<=n;i++)for (int j = 1; j+k-1 <= n; j++){//(i,j)是左上角,需要我們計算出k*k這個區域右下角的坐標int x = i + k - 1;int y = j + k - 1;if (s[x][y] - s[i - 1][y] - s[x][j - 1] + s[i - 1][j - 1] == k * k / 2)ans++;}cout << ans << endl;}return 0;
}
2,小美的數組詢問
?直接遍歷即可?
#include <iostream>
using namespace std;const int N=1e5+10;
int arr[N];
int main()
{int n=0,q=0;cin>>n>>q;long long sum=0,count=0;for(int i=1;i<=n;i++){cin>>arr[i];sum+=arr[i];if(arr[i]==0)count++;}int l,r;while(q--){cin>>l>>r;cout<<sum+count*l<<" "<<sum+count*r<<endl;}return 0;
}
3,小美的MT
統計元字符中 有多少個M和T,再加上最多可以修改 多少個即可。
//小美的MT
#include <iostream>
#include <string>
using namespace std;int main()
{int n = 0, k = 0;cin >> n >> k;string str;cin >> str;int ans = 0;for (int i = 0; i < n; i++){if (str[i] == 'M' || str[i] == 'T')ans++;}if (k > n - ans)cout << n << endl;elsecout << ans + k << endl;return 0;
}
?4,小美的朋友關系
?【題目描述】
總人數為n,編號u和v的人之間存在朋友關系,在這n個人中,存在m個朋友關系。
對于這些關系,進行q次事件,格式為【op,u,v】,其中u和v表示人的編號。op表示要進行哪種操作,當op==1時,u和v的朋友關系淡忘,也就是斷開u和v的朋友關系。當op==2時,表示查詢u和v是否可以建立朋友關系,可以通過第三方或者本來就是朋友關系。
針對每次的op==2操作,返回一個結果Yes or No,表示是否可以建立朋友關系 。
【思路】
這n個人中存在許多的朋友關系,比如編號1-5是朋友,編號6-10是朋友,這兩個關系是獨立的集合,所以可以想到的是使用并查集來記錄朋友關系。
并查集傳送門:
【算法與數據結構】并查集詳解+題目_并查集結構體-CSDN博客
?并查集中的每個集合可以看成是一棵樹,獨立多個集合,就是多個獨立的樹。每個樹的根節點也就是每個集合的父節點。
剛開始我的思路是將這m個朋友關系,使用并查集來存儲。
但是在q次操作中,op=2是查詢是否可以 建立朋友關系的操作,這個簡單,只需判斷這兩個人是否在同一個集合中,也就是這兩個人的父節點是否相同。但是對于op=1刪除朋友關系操作,比較困難,因為并查集擅于進行 添加關系操作的,不好處理刪除節點關系。所以在刪除朋友關系這里出現了問題。
我們可以試著把刪除朋友關系變成添加朋友關系。這樣并查集就可以做了。那么怎么實現呢?
我們可以先將這m個朋友關系用特定的容器存儲下來,首先遍歷q次操作,遇到刪除操作(u,v),在容器中刪除(u,v)。
注意:這里刪除的時候,要刪除的朋友關系是(u,v),有可能存儲的時候,朋友關系是(u,v),也有可能是(v,u),這些都是要刪除的。
遇到op=2時,不進行操作。一次操作完成后,將該次操作用數組記錄下來【op,u,v】。
順序遍歷完后,此時將容器中剩余的朋友關系,構建并查集。?然后逆序遍歷記錄操作的數組,遇到op=1時,就添加朋友關系,遇到op=2時,就查詢朋友關系,判斷父節點是否相等即可。
?【代碼】
//小美的朋友關系
#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int N = 1e5;//總人數,初始的朋友關系數,事件數量
int n, m, q;
vector<int> parent;//并查集
set<pair<int, int>> st;//存儲初始的朋友關系
//存儲事件
struct node
{int op, u, v;
}arr[N+5];
//找父節點,路徑壓縮
int find(int x)
{if (parent[x] != x)parent[x] = find(parent[x]);return parent[x];
}
//合并
void unite(int x, int y)
{int rootX = find(x);int rootY = find(y);if (rootX == rootY)return;parent[rootX] = rootY;
}
int main()
{cin >> n >> m >> q;//初始化并查集parent.resize(n + 1);for (int i = 1; i <= n; i++)parent[i] = i;//存儲關系int op,u, v;while (m--){cin >> u >> v;st.insert({ u,v });}int num = 0;while (q--){cin >> op >> u >> v;//處理刪除操作if (op == 1){if (st.find({ u,v }) != st.end())st.erase({ u,v });else if (st.find({ v,u }) != st.end())st.erase({ v,u });elsecontinue;//說明u和v表示朋友關系,此次刪除操作無意義,不需要存儲下來}//記錄操作arr[num++] = { op,u,v };}//刪除關系完成后,剩余的元素是沒有進行操作的//構建并查集for (auto [u, v] : st)unite(u, v);vector<bool> ans;//記錄最終結果//逆序遍歷操作//如果是刪除就進行合并//如果是查詢就進行判斷是否在同一個集合for (int i = num - 1; i >= 0; i--){op = arr[i].op, u = arr[i].u, v = arr[i].v;if (op == 1){//合并unite(u, v);}else{//判斷ans.emplace_back(find(u) == find(v));}}for (int i = ans.size() - 1; i >= 0; i--)if (ans[i])cout << "Yes" << endl;elsecout << "No" << endl;return 0;
}
上述代碼是使用vector來實現并查集的,題目中的數據范圍n是1e9,如果使用vector,就需要開辟1e9個空間,會超出內存限制。所以這里實現并查集的時候,需要使用map來替代。存儲當前節點和它的父節點。具體原因,看下方:
初始時,每個節點的父節點就是自己本身。比如mp[1]=1。
當我們逆序遍歷時,當遇到op=2,查詢朋友關系時,給的兩個朋友編號u和v,之前可能沒初始化。比如n=10,給了3個朋友關系(1,3),(3,2),(4,6),當我們查詢的時候,可能查詢的是(5,7),這兩個節點沒有初始化,也就是mp[5]=0,mp[7]=0,可以發現這兩個節點的父節點都是0,如果直接判斷,得到的結果是可以構成朋友關系,但本質是不能構成朋友關系的。
也可以看下方代碼的初始化部分,我們只初始化了存在朋友關系的節點,其他的節點沒有初始化,他們的父節點默認就是0。如果我們開始將所有節點都初始化好,那么就會超出內存限制,那么就和使用vector一樣了,甚至占用的內存比vector還要大,所以我們不能一次性就初始還所有節點。而是當遇到一個沒初始化的節點,就初始化即可。
所以在查詢操作的時候,如果mp[u]=0,或者mp[v]=0,就把這兩個值做一下初始化mp[u]=u或者mp[v]=v,這樣在判斷的時候就不會出錯了。
而如果使用的是vector來表示并查集,是不需要考慮這個問題的,因為vector會開辟n個空間,將所有人都初始化好,父節點就是自己。而使用map來存儲,只會存儲存在朋友關系的節點,如果出現一個新的節點,需要我們自己再初始化。這也就是map不會超出內存限制而vector會超出內存限制的原因。
?【代碼】
//小美的朋友關系
#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
const int N = 1e5;//總人數,初始的朋友關系數,事件數量
int n, m, q;
map<int,int> parent;//并查集
set<pair<int, int>> st;//存儲初始的朋友關系//存儲事件
struct node
{int op, u, v;
}arr[N + 5];
//找父節點,路徑壓縮
int find(int x)
{if (parent[x] != x)parent[x] = find(parent[x]);return parent[x];
}
//合并
void unite(int x, int y)
{int rootX = find(x);int rootY = find(y);if (rootX == rootY)return;parent[rootX] = rootY;
}
int main()
{cin >> n >> m >> q;//初始化并查集和關系集合int op, u, v;for (int i = 0; i < m; i++){cin >> u >> v;parent[u] = u;parent[v] = v;st.insert({ u,v });}int num = 0;while (q--){cin >> op >> u >> v;//處理刪除操作if (op == 1){if (st.find({ u,v }) != st.end())st.erase({ u,v });else if (st.find({ v,u }) != st.end())st.erase({ v,u });elsecontinue;//說明u和v表示朋友關系,此次刪除操作無意義,不需要存儲下來}//記錄操作arr[num++] = { op,u,v };}//刪除關系完成后,剩余的元素是沒有進行操作的//構建并查集for (auto [u, v] : st)unite(u, v);vector<bool> ans;//記錄最終結果//逆序遍歷操作//如果是刪除就進行合并//如果是查詢就進行判斷是否在同一個集合for (int i = num - 1; i >= 0; i--){op = arr[i].op, u = arr[i].u, v = arr[i].v;if (op == 1){//合并unite(u, v);}else{//parent[u]==0,說明該節點第一次出現,初始化為uif (parent[u] == 0)parent[u] = u;if (parent[v] == 0)parent[v] = v;//判斷ans.emplace_back(find(u) == find(v));}}for (int i = ans.size() - 1; i >= 0; i--)if (ans[i])cout << "Yes" << endl;elsecout << "No" << endl;return 0;
}