（反悔贪心，Rating 1600）：CF 1526C2 - Potions (Hard Version)
反悔贪心模板题，从前往后拿，每取走一个物品，就将这个物品放入优先队列
如果现在总和小于零，则在优先队列中删去一个最小的。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;void solve(){int n;cin>>n;int sum=0;priority_queue<int,vector<int>,greater<int>> q;for(int i=1;i<=n;i++){int val;cin>>val;sum+=val;q.push(val);while(sum<0){sum-=q.top();q.pop();}}cout<<q.size();}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;// cin>>ct;while(ct--){solve();}
}
(奇偶与离散介值，Rating 1700）：CF 1695C - Zero Path
妙妙题，带了一点 DP
先判断 \(n+m-1\) 的寄偶性，如果是奇数，则不可能凑出 0
然后再用 DP 的方式，找到从 \((1,1)\) 到 \((n,m)\) 的最大最小值
如果最大值大于等于零，且最小值小于等于零，则这两条路径之间一定能调整出来一条恰好为零的路径
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;void solve(){int n,m;cin>>n>>m;vector g(n+1,vector<int>(m+1));vector f1(n+1,vector<int>(m+1,-inf));vector f2(n+1,vector<int>(m+1,inf));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>g[i][j];if(i==1 && j==1){f1[i][j]=g[i][j];f2[i][j]=g[i][j];continue;}f1[i][j]=g[i][j]+max(f1[i-1][j],f1[i][j-1]);f2[i][j]=g[i][j]+min(f2[i-1][j],f2[i][j-1]);}}if((n+m-1)&1){cout<<"NO\n";return;}if(f1[n][m]>=0 && f2[n][m]<=0){cout<<"YES\n";}else cout<<"NO\n";
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;cin>>ct;while(ct--){solve();}
}
（正难则反与连通块，Rating 1500）：CF 1139C - Edgy Trees
将红色边视为连通，可以将所有用红色边相连的点，视为一个联通块中的点。
题意即为，选出 \(k\) 个点（可重复），使得这 \(k\) 个点不在一个联通块内
所以可以先计算出从 \(n\) 个点里选 \(k\) 个点的方案数，再减去所有从单个联通块里选 \(k\) 个点的方案数
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 1e9+7;class DSU{public:vector<int> fa,sz;int setCount;int n;DSU(){}DSU(int n){init(n);}void init(int n){fa.resize(0);fa.resize(n+1);sz.resize(0);sz.resize(n+1,1);this->n=n;setCount=n;iota(fa.begin(), fa.end(), 0);}int find(int x) {if(fa[x] == x) return x;return fa[x] = find(fa[x]);} void unite(int x, int y) {x = find(x),y = find(y);if(x == y) return;if(sz[x] <= sz[y] ) swap(x, y);fa[y] = fa[x];sz[x] += sz[y];--setCount;}
};int qmi(int a,int b,int p){int res=1;while(b){if(b&1) res=res*a%p;a=a*a%p;b>>=1;}return res;
}void solve(){int n,k;cin>>n>>k;DSU dsu(n);for(int i=1;i<n;i++){int u,v,x;cin>>u>>v>>x;if(x==0){dsu.unite(u,v);}}int ans=qmi(n,k,mod);for(int i=1;i<=n;i++){if(dsu.fa[i]==i){ans=(ans-qmi(dsu.sz[i],k,mod))%mod+mod;}ans%=mod;}cout<<ans;}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;// cin>>ct;while(ct--){solve();}
}