| 😊 | Powered By HeartFireY | MINIEYE Contest 1 Solution |
A.Mod, Or and Everything
Problem Description
You are given an integer .
You are required to calculate .
The “or” operation means “bitwise OR”.
Input
The first line contains an integer representing the number of test cases.
For each test case, there is an integer in one line.
Output
For each test case, print the answer in one line.
Solution
| 😀 算法标簽：打表找規律 |
讀完題還是沒有思路，遂打表~，找規律，打表程式和資料：
打到，規律特别明顯，遂打到驗證，發現規律成立：
然後寫了一發AC。但是這跟題目描述究竟有何聯系呢？可以對任意值而言：對其從取模，那麼除去他二進制最高非0位，其模數取遍各位為1的情況(可以打表驗證)，那麼通過題目的按位取或方式得出的結果所有位全為，正好解釋了這個規律。
（其實沒必要用快速幂 \doge）
#include <bits/stdc++.h>
#define
#define
using namespace std;
ll binpow(ll a, ll b) {
ll res = 1;
while (b > 0) {
if (b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
signed main(){
int t = 0; cin >> t;
while(t--){
int n = 0, cnt = 0, ans = 0; cin >> n;
n -= 1;
while(n){
n >>= 1;
cnt++;
}
for(int i = 0; i < cnt - 1; i++) ans += binpow(2, i);
cout << ans << endl;
}
return 0;
} E.Minimum spanning tree
Problem Description
Given points, numbered from to , the edge weight between the two points and is . Please find the minimum spanning tree formed by them.
A minimum spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible.
is the smallest positive integer that is divisible by both and .
Input
The first line contains a single integer
The only line of each test case contains one integers
Output
For each test case, print one integer in one line, which is the minimum spanning tree edge weight sum.
Solution
| 😀 算法标簽：字首和、素數篩、思維/規律 |
題目給定個點，從編号，任意兩點間的均有一條邊，其邊權為兩點編号的最小公倍數，求該圖的MST。
首先明确資料範圍，顯然不是一道跑最小生成樹算法的題。那麼考慮規律。
根據題目條件：邊權為兩點的最小公倍數，那麼我們可以對點進行分類：①.質數點 ②.合數點
對于任意兩個質數點，其最小公倍數必然為兩質數點乘積，那麼為了使邊權最小，可以讓所有的質數點()全部向連線，可保證所有質數點間邊權最小。
而對于合數點，則向其約數點連邊。此時可保證邊權最小。
如此可得總邊權和為 質數的和*2+合數的和。
注意開long long！
#include <bits/stdc++.h>
#define
using namespace std;
const int N = 10000010;
int isp[N], prime[N], a[N], cnt = 0;
void init(){
for(int i = 2; i < N; i++){
if(!isp[i]) prime[++cnt] = i;
for(int j = 1; j <= cnt && i * prime[j] < N; j++){
isp[prime[j] * i] = 1;
if(i % prime[j] == 0) break;
}
}
}
signed main(){
init();
for(int i = 3; i <= N - 10; i++){
if(isp[i]) a[i] = a[i - 1] + i;
else a[i] = a[i - 1] + 2 * i;
}
int t = 0; cin >> t;
while(t--){
int n = 0; cin >> n;
cout << a[n] << endl;
}
return 0;
} F.Xor sum
Problem Description
Given a sequence of integers of length n, find the shortest consecutive subsequence witch XOR sum not less than k.
If there are multiple consecutive subsequences of the same length, print the consecutive subsequence with the smallest left end point.
If there are no consecutive subsequence witch XOR sum not less than k, just print “-1”.
Input
The first line contains a single integer t (t<=100) representing the number of test cases in the input. Then t test cases follow.
The first line of each test case contains two integers n (1<=n<=100000) and k (0<=k<2^30), representing the length of sequence.
The second line of each test contains n integers ai (0<=ai<2^30), representing the integers in sequence.
The number of test witch n>1000 does not exceed 5.
Output
For each test case, print two integers in one line, representing the left end point and right end point of the consecutive subsequence.
If there are no consecutive subsequence witch XOR sum not less than k, print “-1” in one line.
Solution
| 😀 算法标簽：0-1 Trie |
給定一個長度為的序列，求一段最短的連續子序列滿足異或和大于等于。
序列長度範圍 ，考慮使用複雜度及以下的算法解決。
首先我們需要知道：對于字首異或和，如果要求一段區間的字首異或，有
那麼對于本題，我們對整個序列求字首異或，則問題轉為求序列内兩個距離最近的數，使得他們的異或值不小于。
對于轉化後的問題可以使用
0-1字典樹
解決。
接下來對如何使用
0-1字典樹
解決這個問題進行分析：
首先，我們采用類似線上處理的方式，邊求異或字首邊更新最優解，這樣相當于固定第二個數(也就是原題區間右端點)，來求最優的第一個數(也就是原題區間左端點)。
- 首先讀入目前值，求到目前值位置的異或字首；
- 判斷：如果目前的異或字首，且目前區間長度(即為)記錄的最短區間長度，則更新一次最優解；
- 求位于~目前範圍内滿足異或字首的最大數(即為原題區間左端點)，再次判斷是否需要更新最優解；
- 将目前異或字首插入到字典樹中。
先對字典樹的插入過程進行分析：
和普通字典樹一樣，我們使用一個數組，由于僅有兩個字元，是以數組第二次元隻需要兩個空間，用于表示連接配接目前節點和子節點兩條邊，那麼數組的使用方法可以表示為：
那麼構造數組的過程就可以得出了：
- 首先判斷對于待插入位，目前節點是否已經被插入過，如果被插入過，則向子節點繼續走
- 如果沒有插入過，那麼建立節點，同時初始化兩條邊指向的節點為空，記錄新子節點位置，向新子節點走
此外，由于我們要求最大異或值的下标，是以還需要一個額外的數組存一下下标：設表示編号為的節點對應的序列下标。由于我們要找的是盡可能大的"左端點"，是以我們對于下标的存儲政策是"新覆寫舊"。這裡需要讀者重點了解一下。
我們繼續對查找區間左端點的過程進行分析：字典樹上自根節點到葉節點的每條路徑均表示一個二進制數，我們從根節點開始(也就是最高位開始)，将待異或值對應位取出與之進行異或，加和後(此處由于是數位異或，是以是累加)，繼續遞歸向子節點移動。這個過程實際就是個DFS。
對于遞歸的終止條件我們需要注意：我們沒有必要累加至葉節點，而隻需要在周遊過程中進行判斷：如果截至目前數位，先前數位相異或後累加的值已經大于等于，再向下累加一定還是大于等于，那麼我們直接傳回目前節點的編号即可。
此外，還要再對遞歸過程進行剪枝，如果截至目前數位，假設目前位到最低為全部為，将截至目前的高位異或累加值加上到低位全為仍不滿足大于等于，那麼無論怎麼向低位求異或累加也不可能再出現再高的情形，此時直接傳回表示不滿足條件即可。
搜尋的過程是比較簡單的，隻需要從目前節點開始，向左右兩條邊走，分别求出兩個數目前位的異或值，累加至和中，向低位移動即可。
AC CODE
#include <bits/stdc++.h>
using namespace std;
const int NN = 31 * (1e5 + 10);
int trie[NN][2], ser[NN], tmp[31], tot = 0;
inline void insert(int x, int pos){
for(int i = 30; i>= 1; i--) tmp[i] = x & 1, x >>= 1;
int now = 0;
for(int i = 1; i <= 30; i++){
ser[now] = pos;
if(trie[now][tmp[i]]) now = trie[now][tmp[i]];
else{
trie[now][tmp[i]] = ++tot;
trie[tot][0] = trie[tot][1] = 0;
now = tot;
}
}
ser[now] = pos;
}
int query(int r, int k, int now, int sum, int bit){
if(sum >= k) return ser[now];
if(sum + (1 << (bit + 1)) <= k) return 0;
int ans = 0, temp = 0;
if(trie[now][0]){
temp = r & (1 << bit);
ans = max(ans, query(r, k, trie[now][0], sum + temp, bit - 1));
}
if(trie[now][1]){
temp = r & (1 << bit) ^ (1 << bit);
ans = max(ans, query(r, k, trie[now][1], sum + temp, bit - 1));
}
return ans;
}
signed main(){
ios_base::sync_with_stdio(false);
int t = 0; cin >> t;
while(t--){
int n, k; cin >> n >> k;
trie[0][0] = trie[0][1] = 0;
for (int i = 0; i <= tot; i ++) ser[i] = 0;
tot = 0;
//memset(trie, 0, sizeof(trie));
//memset(ser, 0, sizeof(ser));
//memset(fa, 0, sizeof(fa));
int ans = n + 1, l = -1, r = -1, sum_all = 0;
for(int i = 1; i <= n; i++){
int x; cin >> x;
sum_all ^= x;
if(sum_all >= k && ans > i) ans = i, l = 1, r = i;
int d = query(sum_all, k, 0, 0, 29);
if(d > 0 && ans > i - d) ans = i - d, l = d + 1, r = i;
insert(sum_all, i);
}
if(ans == n + 1) cout << -1 << endl;
else cout << l << ' ' << r << endl;
}
return 0;
} H.Maximal submatrix
Problem Description
Given a matrix of n rows and m columns,find the largest area submatrix which is non decreasing on each column
Input
The first line contains an integer T(1≤T≤10)T(1≤T≤10)representing the number of test cases.
For each test case, the first line contains two integers n,m(1≤n,m≤2∗103)n,m(1≤n,m≤2∗103)representing the size of the matrix
the next n line followed. the i-th line contains mm integers vijvij(1≤vij≤5∗103)(1≤vij≤5∗103)representing the value of matrix
It is guaranteed that there are no more than 2 testcases with n∗m>10000
Output
For each test case, print a integer representing the Maximal submatrix
Solution
| 😀 算法标簽：懸線法 |
聽隊友說是懸線的闆子題…
首先分析一下思路：大小關系隻針對縱向而言，那麼想到轉化為0-1矩陣，但後跑懸線法闆子即可。這裡放個參考标程的代碼，自己寫的不堪入目。。。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3;
int a[N][N], b[N][N];
int h[N];
int que[N];
signed main(){
int t; cin >> t;
while (t--){
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin >> a[i][j];
b[i][j] = 0;
if (i > 1) b[i][j] = (a[i][j] >= a[i - 1][j]);
}
}
for (int i = 1; i <= m; i++) h[i] = 0;
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++){
if (b[i][j] == 0) h[j] = 1;
else h[j]++;
}
int tot = 0;
h[m + 1] = 0;
for (int j = 1; j <= m + 1; j++){
while (tot && h[que[tot]] > h[j]){
ans = max(ans, (j - que[tot - 1] - 1) * h[que[tot]]);
tot--;
}
que[++tot] = j;
}
}
cout << ans << endl;
}
} I.KD-Graph
Problem Description
Let’s call a weighted connected undirected graph of nn vertices and m edges KD-Graph, if the
following conditions fulfill:
* nn vertices are strictly divided into KK groups, each group contains at least one vertice
* if vertices pp and qq ( pp ≠ qq ) are in the same group, there must be at least one path between pp and qq meet the max value in this path is less than or equal to DD.
* if vertices pp and qq ( pp ≠ qq ) are in different groups, there can’t be any path between pp and qq meet the max value in this path is less than or equal to DD.
You are given a weighted connected undirected graph GG of nn vertices and mm edges and an integer KK.
Your task is find the minimum non-negative DD which can make there is a way to divide the nn vertices into KK groups makes GG satisfy the definition of KD-Graph.Or −1−1 if there is no such DD exist.
Input
The first line contains an integer TT (1≤ TT ≤5) representing the number of test cases.
For each test case , there are three integers n,m,k(2≤n≤100000,1≤m≤500000,1≤k≤n)n,m,k(2≤n≤100000,1≤m≤500000,1≤k≤n) in the first line.
Each of the next mm lines contains three integers u,vu,v and cc (1≤v,u≤n,v≠u,1≤c≤109)(1≤v,u≤n,v≠u,1≤c≤109) meaning that there is an edge between vertices uu and vv with weight cc.
Output
For each test case print a single integer in a new line.
Solution
| 😀 算法标簽：并查集 |
給定邊集，要求劃分為組，求一個，使得同一組的頂點間的路徑最大值小于等于。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e6 + 10;
struct edge{
int u, v, c;
const bool operator<(const edge &a){ return c < a.c; }
}edgeset[maxn];
int fa[maxn];
inline void init(int n){
for(int i = 0; i <= n + 10; i++) fa[i] = i;
}
inline int find(int x){
while(x != fa[x]) x = fa[x] = fa[fa[x]];
return x;
}
signed main(){
ios_base::sync_with_stdio(false);
int t = 0; cin >> t;
while(t--){
int n, m, k; cin >> n >> m >> k;
for(int i = 1; i <= m; i++) cin >> edgeset[i].u >> edgeset[i].v >> edgeset[i].c;
init(n);
sort(edgeset + 1, edgeset + 1 + m);
int ans = INT_MAX, flag = 1, cnt = n;
if(k == n) ans = 0;
for(int i = 1; i <= m; i++){
if(!ans) break;
int uu = edgeset[i].u, vv = edgeset[i].v, cc = edgeset[i].c;
int fu = find(uu), fv = find(vv);
if(fu == fv) continue;
else{
if(cnt - 1 == k) ans = cc;
else if(cnt - 1 < k){
if(cc <= ans) flag = 0;
break;
}
}
fa[fu] = fv;
cnt--;
}
if(!flag || ans == INT_MAX) cout << -1 << endl;
else cout << ans << endl;
}
return 0;
} ![筆試面試題目：滑動視窗(二)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)