2026-01-03

CF

Problem - 1851E - Codeforces

拓扑排序模板题
题意： 题目很长，要好好理解，简单说就是计算药品的最少花费，每个药品有可能

• 无限供应（花费0）
• 成本价格购买（c[i]）
• 由一些药品混合得到
  所以用拓扑排序，用拓扑排序时要先思考题目有没有环存在

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
int c[N], in[N];
LL f[N], sum[N];
vector<int> e[N];
bool vis[N];void solve()
{int n, k;cin >> n >> k;for (int i = 0; i <= n;i++){//初始化，不要漏掉e[i].clear();vis[i] = 0;in[i] = 0;f[i] = 0;sum[i] = 0;//注意}for (int i = 1; i <= n; i++){cin >> c[i];}for (int i = 1,x; i <= k;i++){cin >> x;vis[x] = 1;}for (int i = 1; i <= n;i++){int m;cin >> m;for (int j = 0; j < m;j++){int u;cin >> u;e[u].push_back(i);in[i]++;}}//拓扑排序queue<int> q;for (int i = 1; i <= n;i++){if(in[i]==0)q.push(i);}for (int i = 1; i <= n;i++){if(vis[i]){f[i] = 0;}else{f[i] = c[i];}}while(!q.empty()){int u = q.front();q.pop();for (int i = 0; i < e[u].size();i++){int v = e[u][i];sum[v] += f[u];in[v]--;if(in[v]==0){q.push(v);f[v] = min(f[v], sum[v]);}}}for (int i = 1; i <= n;i++){cout << f[i] << " ";}cout << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}

Problem - 5C - Codeforces（dp好题）

括号匹配，计算最大长度
用dp解决
注意：找不到的时候是输出"0 1"
主要代码：

dp[i] = i - st.top() + 1 + dp[st.top() - 1];
cnt[dp[i]]++;

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=1e6+10;
stack<int> st;
int dp[N],cnt[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);string s;cin >> s;int n = s.size();s = " " + s;for (int i = 1; i <= n;i++){if(s[i]=='(')st.push(i);else if(!st.empty()){dp[i] = i - st.top() + 1 + dp[st.top() - 1];cnt[dp[i]]++;st.pop();}}cnt[0] = 1;for (int i = n; i>=0;i--){if(cnt[i]){cout << i << " " << cnt[i] << endl;return 0;}}
}

Problem - 166E - Codeforces（dp）

![[Pasted image 20260103104946.png]]
算在顶端的方案数 \(f\) 和不在顶端的一点 \(g\)
\(f_i=3\times g_{i-1},g_i=f_{i-1}+2*\times g\)
对于 \(f\)，即为\(A,B,C\) 任意一点到 \(D\) 的方案数，因为对称，求一个即可
对于 \(g\)，即为从 \(D\) 到\(A\) (假设一点)，然后加上从 \(B,C\) 两点到\(A\) 的方案数

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 1e9+7;
const int N=2e5+10;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;LL f = 0, g = 1;for (int i = 2; i <= n;i++){LL tmp = f;f = 3 * g % mod;g = tmp%mod + 2 * g % mod;}cout << f % mod << endl;
}