codeforces div2 870
#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
using bs = bitset<N>;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> m >> n;
vector<vector<int>> a(n, vector<int>(m + 1));
for(int i = 0;i < n;i ++) cin >> a[i][m];
for(int j = 0;j < m;j ++)
for(int i = 0;i < n;i ++)
cin >> a[i][j];
//先排序是为了保证能拓扑序,接下来好使用LIS的思想
sort(a.begin(), a.end());
vector<int> idx(n);
vector<bs> lower(n);
for(int i = 0;i < n;i ++) lower[i].set();
iota(idx.begin(), idx.end(), 0);
//预处理每一列向量,找出比向量j严格大于的向量,用bitset存储
for(int i = 0;i < m;i ++){
//对下标排序
sort(idx.begin(), idx.end(), [&](int x, int y) -> auto {
return a[x][i] < a[y][i];
});
bs cur = 0;
int p = 0;
for(int j = 0;j < n;j ++){
while(a[idx[p]][i] < a[idx[j]][i]) cur.set(idx[p ++], 1);
//对每一行取交集就是比这一列大的
lower[idx[j]] &= cur;
}
}
vector<long long> f(n);
for(int i = 0;i < n;i ++){
f[i] = a[i][m];
for(int j = 0;j < i;j ++)
if(lower[i][j]) f[i] = max(f[i], f[j] + a[i][m]);
}
cout << *max_element(f.begin(), f.end()) << endl;
return 0;
}
codeforces div3 874
E. Round Dance
找长度为2的环、大于2的环。发现跟有环相关看看能不能有强连通分量的tarjan算法,这题是可以的
如何把题目抽象成是找环非常关键
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int T, n;
int stk[N], low[N], dfn[N], top, timestamp;
bool in_stk[N];
vector<vector<int>> g(N);
int id[N], sz[N], scc_cnt;
void tarjan(int u){
low[u] = dfn[u] = ++ timestamp;
stk[++ top] = u, in_stk[u] = true;
for(auto j : g[u]){
if(!dfn[j]){
tarjan(j);
low[u] = min(low[u], low[j]);
}else if(in_stk[j]) low[u] = min(low[u], dfn[j]);
}
if(low[u] == dfn[u]){
int y;
++ scc_cnt;
do{
y = stk[top --];
id[y] = scc_cnt;
in_stk[y] = false;
sz[scc_cnt] ++;
}while(y != u);
}
}
void solve(){
cin >> n;
for(int i = 1;i <= n;i ++) g[i].clear();
timestamp = 0, top = 0, scc_cnt = 0;
memset(sz, 0, sizeof sz);
memset(low, 0, sizeof low), memset(dfn, 0, sizeof dfn);
for(int i = 1;i <= n;i ++){
int a;
cin >> a;
g[i].push_back(a);
}
for(int i = 1;i <= n;i ++)
if(!dfn[i]) tarjan(i);
int cnt1 = 0, cnt2 = 0;//1代表长度为2的环,2代表长度大于2的环
for(int i = 1;i <= scc_cnt;i ++)
if(sz[i] == 2) cnt1 ++;
else if(sz[i] > 2) cnt2 ++;
if(cnt1) cout << 1 + cnt2 << " " << cnt1 + cnt2 << endl;
else cout << cnt2 << " " << cnt1 + cnt2 << endl;
}
int main(){
cin >> T;
while(T --){
solve();
}
return 0;
}
LeetCode 347周赛
T4 2713. 矩阵中严格递增的单元格数
由于题目中说了,一个点只能向严格大于他的点移动,这就暗示了这个图是一个DAG(有向无环图),再结合题目要求我们算的是最大路径,我们直接可以动态规划求最大路径。按每个点数值从小到大计算,保证无后效性(也就是按拓更新)。还有个难点就是如何计算转移,一个点只能是从他那一列那一行的点转移过来,如果我们要找最大值,那么就得一个个遍历过去,时间复杂度就不满足了题目要求了。由于我们不关心状态是由哪个点转移过来的,所以我们只需要记录要计算的那个点的行f[i][j]和列f[i][j]的最大值就行了。
class Solution {
public:
int maxIncreasingCells(vector<vector<int>>& mat) {
int n = mat.size(), m = mat[0].size();
map<int, vector<pair<int, int>>> mp;
for(int i = 0;i < n;i ++)
for(int j = 0;j < m;j ++)
mp[mat[i][j]].push_back({i, j});
//记录每一行每一列的最大值,可以思考一下初始值为什么设置为0
vector<int> row_max(n, 0);
vector<int> col_max(m, 0);
vector<vector<int>> f(n, vector<int>(m, 0));
for(auto [k, v] : mp){
for(auto [x, y] : v)
f[x][y] = max(row_max[x], col_max[y]) + 1;
//这里是一个细节,值相同的点要一起计算完再更新每一行每一列的最大值
//可以思考一下为什么
for(auto [x, y] : v)
row_max[x] = max(row_max[x], f[x][y]),
col_max[y] = max(col_max[y], f[x][y]);
}
int res = 0;
for(int i = 0;i < n;i ++)
for(int j = 0;j < m;j ++) res = max(res,f[i][j]);
return res;
}
};
1272F. Two Bracket Sequences
这题的做法需要先知道 最短公共超序列 ,这题跟这个最短公共超序列非常的相似,由于递推没想明白就按照灵神的思路写了一版记忆化搜索。同时这题还需要加一个维度,f[i][j][k]表示i~n j~m 然后左括号和右括号只差为k的最短公共超序列,相当于记忆化中的memo数组,不过就是把memo数组的含义解释一下。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 210, INF = 1e9;
int T, n;
int f[N][N][2 * N];
void solve(){
string s, t;
cin >> s >> t;
int n = s.length(), m = t.length();
s = s + " ", t = t + " ";
//f[i][j][k]表示s中i后面和t中j后面个并且左括号为k个的最短超序列
for(int i = 0;i < N;i ++)
for(int j = 0;j < N;j ++)
for(int k = 0;k < N * 2;k ++)
f[i][j][k] = -1;
//这个不能忘了,没写就回溯不了
f[n][m][0] = 0;
function<int(int, int, int)> dfs = [&](int i, int j, int k) -> auto {
if(k > n + m)
return INF;
if(i == n && j == m && k == 0)
return 0;
if(f[i][j][k] != -1)
return f[i][j][k];
int res = INF;
//这个地方一定不能漏了,会栈溢出
f[i][j][k] = INF;
res = dfs(i + (s[i] == '('), j + (t[j] == '('), k + 1) + 1;
if(k > 0)
res = min(res, dfs(i + (s[i] == ')'), j + (t[j] == ')'), k - 1) + 1);
f[i][j][k] = res;
return res;
};
dfs(0, 0, 0);
int i = 0, j = 0, k = 0;
string res;
while(true){
if(i == n && j == m && k == 0) break;
if(f[i][j][k] == f[i + (s[i] == '(')][j + (t[j] == '(')][k + 1] + 1){
res += '(';
i = i + (s[i] == '(');
j = j + (t[j] == '(');
k ++;
}else if(f[i][j][k] == f[i + (s[i] == ')')][j + (t[j] == ')')][k - 1] + 1){
res += ')';
i = i + (s[i] == ')');
j = j + (t[j] == ')');
k --;
}
}
cout << res << endl;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
T = 1;
while(T --){
solve();
}
return 0;
}}