A
计数DP
1表示看到白天，0表示看到晚上，-1表示看到不确定。给个序列，问所有把-1变成0或1的方案中，白天天数的和？
首先如果只是求方案数是好求的，但是这里每个方案都有贡献，要求的是所有方案的贡献和。这种一般就维护两个dp数组，一个是贡献和，一个是方案数，方案数正常转移，什么时候能产生贡献了，再把方案数加入答案。
这里能产生贡献的地方就是前一个时0，当前是1，这意味着开始了新的一个白天，我们把计算出来的方案数加上
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
const long long mod=998244353;
long long n,t;
long long a[N],dp[N][5],f[N][5];
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=0;i<=n;i++){
for(int j=0;j<=1;j++)dp[i][j]=f[i][j]=0;
}
f[0][0]=1;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
if(a[i]==1){
dp[i][1]=(dp[i-1][0]+dp[i-1][1]+f[i-1][0])%mod;
f[i][1]=(f[i-1][0]+f[i-1][1])%mod;
}
else if(a[i]==0){
dp[i][0]=(dp[i-1][0]+dp[i-1][1])%mod;
f[i][0]=(f[i-1][0]+f[i-1][1])%mod;
}
else {
dp[i][1]=(dp[i-1][0]+dp[i-1][1]+f[i-1][0])%mod;
dp[i][0]=(dp[i-1][0]+dp[i-1][1])%mod;
f[i][1]=f[i][0]=(f[i-1][0]+f[i-1][1])%mod;
}
}
printf("%lld\n",(dp[n][0]+dp[n][1])%mod);
}
return 0;
}
F
贪心，模拟
一个环上多个起火点，每秒会往相邻一个格子蔓延，t秒后消防队才回来，你可以选一个点的树提前消灭掉，这样火就不能从这一点蔓延了，问最优情况下，消防队来的时候还剩多少点没着火？
多个起火点？环？不好想？
先简单点，一条链上，只有一个起火点，那显然我们只可能在起火点两侧选一个点阻断，这样能救的点是最多的，至于选哪个点，要看哪边的树多。
多个点？可能的答案点仍然是每个初始起火点的左右两侧，具体选哪个，看所有连续0段的长度，应该选最长的0段的端点，这样可能救的树最多
环怎么办？因为至少有一个起火点，也就是1，那么我们不妨从第一个1开始考虑，这个1左侧的0，可以接到最右侧，因为这是环。
如何计算答案，找到最长0后，除了这一段答案都是，也就是长度
的0被从两端开始烧了
秒，剩下这么多，可能是负数，要和0取max。最长0这一段，有一个端点来的火被我们阻断了，相当于只从一端开始着火，
即可，仍然和0取max
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5;
const long long mod=998244353;
int T;
signed main(){
cin>>T;
while(T--){
int n,t;
cin>>n>>t;
string s;
cin>>s;
s=' '+s;
int pre=0;
for(int i=1;i<=n;i++){
if(s[i]=='1'){
break;
}
else{
pre++;
}
}
for(int i=0;i<pre;i++){
s+='0';
}
int ans=0;
int len=0;
int mx=0;
for(int i=pre+1;i<=n+pre;i++){
if(s[i]=='0'){
len++;
}
else{
mx=max(mx,len);
ans+=max(0ll,len-2*t);
len=0;
}
}
ans+=max(0ll,len-2*t);
mx=max(mx,len);
ans-=max(0ll,mx-2*t);
ans+=max(0ll,mx-t-1);
cout<<ans<<'\n';
}
return 0;
}
G
几何
给一个凸多边形，饶益格中心转，问最多转多少角度后，扫过的面积不再增大？
旋转问题一个关键点是考虑中心在多边形的内外。
如果在多边形内，可以看成多个半径在画圆，那么面积增长取决于最长半径什么时候画出一个完整圆，如果最长半径还没画完，即使小半径画完一圈了，面积仍然在增长。最长半径只有一个的话就是画一圈，如果有多个的话，手玩可以发现就是这些半径之间的最大夹角，因为一块转动的话，大夹角扫过了，小夹角肯定也扫过了。找到最大半径，极角序排序然后扫一遍，计算相邻的差值即可，注意这是个循环数组，第一个和最后一个也构成一个角。不过点给出的顺序就是逆时针了，也不用极角序排序了。
如果中心在多边形外部，关于最大半径的讨论还是一样的，但是最小半径也会产生影响，因为旋转时画的是个圆环，外圈边界时最大半径决定的，内圈半径是最小半径决定的，所以我们还要看最小半径有几个。
关键点来了，最小半径，也就是距离旋转中心最近的点一定只有一个，不信可以手玩，因为这是凸多边形，（凹多边形可能有多个）。那么根据我们上面对于最大半径的讨论，只有一个的话肯定要转一整圈，答案永远是2pi
实现上的一个坑点是给出点，怎么求和x正方向的夹角？这可以用atan函数，但是注意值域。需要加个偏移量。另外跨一四象限的夹角计算也需要偏移量，无脑办法就是大于2pi小于0，都无脑加减2pi
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = ll;
constexpr long double PI = acos(-1);
constexpr double eps = 1e-8;
struct P {
db x, y;
P(db x = 0, db y = 0) : x(x), y(y) {}
P operator-(const P &o) const { return P(x - o.x, y - o.y); }
db operator*(const P &o) const { return (x * o.x + y * o.y); }
db operator^(const P &o) const { return x * o.y - y * o.x; }
long double theta() {
long double res = atan2((long double)y, (long double)x);
if (res < 0) res += 2 * PI;
return res;
}
};
db abs2(const P &p) { return p * p; }
using Poly = vector<P>;
bool contain(const Poly &g, const P &p) {
bool inPoly = false;
for (size_t i = 0; i < g.size(); i++) {
P a = g[i] - p, b = g[(i + 1) % g.size()] - p;
if (abs(a ^ b) == 0 and a * b <= 0) return true;
if (a.y > b.y) swap(a, b);
if (a.y <= 0 and 0 < b.y and (a ^ b) > 0) inPoly = !inPoly;
}
return inPoly;
}
long double calc(vector<long double> &a) {
if (a.size() == 1) {
return 2 * PI;
}
long double ans = 0;
for (size_t i = 0; i + 1 < a.size(); i++) {
long double tmp = a[i + 1] - a[i];
while (tmp < 0) tmp += 2 * PI;
while (tmp > 2 * PI) tmp -= 2 * PI;
ans = max(ans, tmp);
}
long double tmp = a.front() + 2 * PI - a.back();
while (tmp < 0) tmp += 2 * PI;
while (tmp > 2 * PI) tmp -= 2 * PI;
ans = max(ans, tmp);
return ans;
}
void solve() {
ll n, x, y;
cin >> n >> x >> y;
P c(x, y);
Poly g(n);
ll maxD = 0;
ll minD = LONG_LONG_MAX;
for (int i = 0; i < n; i++) {
cin >> g[i].x >> g[i].y;
g[i] = g[i] - c;
maxD = max(maxD, abs2(g[i]));
minD = min(minD, abs2(g[i]));
}
vector<long double> a, b;
a.reserve(n);
b.reserve(n);
for (int i = 0; i < n; i++) {
if (abs2(g[i]) == maxD) {
a.push_back(g[i].theta());
}
if (abs2(g[i]) == minD) {
b.push_back(g[i].theta());
}
}
long double ans;
if (contain(g, P(0, 0))) {
ans = calc(a);
} else {
ans = 2*PI;
}
cout << fixed << setprecision(15) << ans << "\n";
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
solve();
}
}
H
李超线段树 最短路
一张图，每条边每次升级可以边权减去，现在给k次机会升级，问1-n最短路？
注意到满足每条边都有，也就是升级次数全用在这一条边上也不会浪费。所以一定存在一个最优解，k次升级都用在了同一个边上。那么我们可以枚举用在了哪条边上，如果用在了
边上，那么此时的最短路就是
。
那么可以先预处理出来1和n出发到所有点的最短路，原式可以转化为,有多个k的询问，每次询问要在m个这样的式子里取最小值。
这是啥？你把每个式子看成一个直线，这就是多条直线，在给定x坐标处的最小值？李超树板子即可。
注意这里是直线，直接把插入区间等于李超树定义域即可，或者只要线段定义域比k范围大即可
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define per(i, b, a) for(int i = b; i >= a; i--)
#define endl "\n"
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pll = pair<ll, ll>;
using graph = vector<vector<pll>>;
using ugraph = vector<vector<int>>;
constexpr int MAXN = 2E5 + 5;
constexpr double eps = 1E-8;
constexpr ll INF = 1E18;
vector<ll> dijkstra(graph &g, ll s) {
vector<ll> dist(g.size(), INF);
priority_queue<pll, vector<pll>, greater<pll>> pq;
dist[s] = 0;
pq.emplace(0, s);
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (dist[u] < d) continue;
for (auto [w, v] : g[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.emplace(dist[v], v);
}
}
}
return dist;
}
struct LiChao {
struct Line {
ll k, b;
ll eval(ll x) const { return k*x + b; }
};
struct Node {
Line ln;
Node *l, *r;
Node(Line v): ln(v), l(nullptr), r(nullptr) {}
};
ll L, R;
Node* root;
LiChao(ll _L, ll _R): L(_L), R(_R), root(nullptr) {}
void insert(Line nw, ll l, ll r, Node*& o, ll seg_l, ll seg_r) {
if (!o) { o = new Node(nw); return; }
ll m = (l + r) >> 1;
// 如果线段完全不在当前区间
if (seg_r < l || seg_l > r) return;
// 如果线段完全覆盖当前区间
if (seg_l <= l && r <= seg_r) {
bool left = nw.eval(l) < o->ln.eval(l);
bool mid = nw.eval(m) < o->ln.eval(m);
bool right = nw.eval(r) < o->ln.eval(r);
if (left && right) {
swap(nw, o->ln);
return;
}
if (!left && !right) return;
if (mid) swap(nw, o->ln);
if (left != mid) insert(nw, l, m, o->l, seg_l, seg_r);
if (right != mid) insert(nw, m+1, r, o->r, seg_l, seg_r);
return;
}
// 线段部分覆盖当前区间
if (seg_l <= m) insert(nw, l, m, o->l, seg_l, seg_r);
if (seg_r > m) insert(nw, m+1, r, o->r, seg_l, seg_r);
}
void add_segment(ll k, ll b, ll left, ll right) {
insert({k, b}, L, R, root, left, right);
}
ll query(ll x, ll l, ll r, Node* o) const {
if (!o) return LLONG_MAX;
ll m = (l + r) >> 1, res = o->ln.eval(x);
if (l == r) return res;
return min(res, x <= m ? query(x, l, m, o->l)
: query(x, m+1, r, o->r));
}
ll get(ll x) const {
return query(x, L, R, root);
}
};
void solve() {
int n, m; cin >> n >> m;
vector<tuple<int, int, ll, ll>> edges(m);
graph g(n + 1), h(n + 1);
for (auto &[u, v, t, w] : edges) {
cin >> u >> v >> t >> w;
g[u].emplace_back(t, v);
h[v].emplace_back(t, u);
}
auto d1 = dijkstra(g, 1);
auto d2 = dijkstra(h, n);
vector<ll> dist(m);
for (int i = 0; i < m; i++) {
auto &[u, v, t, w] = edges[i];
dist[i] = d1[u] + d2[v] + t;
}
// min{dist_i - w_i * k}
LiChao seg(0, 1'000'000'000);
for (int i = 0; i < m; i++) {
auto &[u, v, t, w] = edges[i];
seg.add_segment(-w, dist[i],1,100'000'000);
// seg.add(-w,dist[i]);
}
int q; cin >> q;
for (int i = 0; i < q; i++) {
int k; cin >> k;
cout << seg.get(k) << "\n";
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T; cin >> T;
for (int ttt = 1; ttt <= T; ++ttt) {
solve();
}
return 0;
}
L
图论 数学
偶数个人，每个人都有喜欢的人，每个人喜欢的人互不相同。两个人可以结婚条件是至少一个人喜欢另一个人。现在要删掉两个人，删掉之后剩余人都能结婚，问多少种结婚方案，注意不是删除方案，同一个删除方案可能结婚方式不同
喜欢虽然是单向的，但只要一个人喜欢另一个人就可以结婚，在结婚的意义上这其实是个无向图，a喜欢b，ab就可以结婚，有一个无向边。注意到n个人n条边，这是个类似基环森林。并且每个人喜欢的人互不相同，所以环上不能长出来树，如果环上点能长出树，说明要么根由两个人喜欢，要么他喜欢两个人，都是不可能的。
所以构成的图就是一堆环。
我们要删除点，注意到长度为偶数的环删掉奇数个点无解，剩下奇数个人肯定有个人没法结婚，所以要么不删要么删除两个。长度为奇数的环需要删掉奇数个点，也就是必须删除一个点。
可以看到奇数环必须删点，而我们只有两次机会，所以奇数环个数决定了是否有解。 如果奇数环有超过2个就无解，
恰好两个就把两次机会分别给这两个环，每个奇数环上所有点都可以删除，方案数是两个奇环大小乘积，剩余偶数环不删，但是每个长度不为2的偶数环的结婚方案也有两种，所以还要乘上,
是长度不为2的偶数环个数。
恰好一个奇数环，用来一个名额，但是剩下一次机会只能去删偶数环了，而偶数环不能删1个，所以此时也无解。
0个奇数环，两次机会可以给一个偶数环，枚举给哪个，这些方案之间是加法。确定一个环了，删除两个位置后得到俩链，这俩链必须都是偶数长度，否则会有人无法结婚，删除方案可以考虑容斥。然后剩余没删除的偶数环算法还是，这里需要考虑这个枚举的环是不是长度大于2，是的话
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define per(i, b, a) for(int i = b; i >= a; i--)
#define endl "\n"
#define int long long
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
using ugraph = vector<vector<int>>;
constexpr int MAXN = 2E5 + 5;
constexpr double eps = 1E-8;
constexpr ll INF = 1E18;
const int mod=998244353;
constexpr int B = 63;
int p2[505050];
void solve() {
int n;
cin>>n;
vector<int>f(n+1),sz(n+1,1);
for(int i=1;i<=n;i++){
f[i]=i;
}
auto &&find=[&](auto &&find,int x)->int{
if(f[x]==x)return x;
return f[x]=find(find,f[x]);
};
for(int i=1;i<=n;i++){
int x;
cin>>x;
int f1=find(find,i),f2=find(find,x);
if(f1!=f2){
f[f1]=f2;
sz[f2]+=sz[f1];
}
}
int cnt0=0,cnt1=0,cnt2=0;
vector<int>a,b;
for(int i=1;i<=n;i++){
if(find(find,i)==i){
if(sz[i]%2)cnt1++,a.push_back(sz[i]);
else{
cnt0++;
if(sz[i]>2){
cnt2++;
}
b.push_back(sz[i]);
}
}
}
if(cnt1==0){
int ans=0;
for(int x:b){
int t=x*(x-1)/2;
t%=mod;
t-=x/2*(x/2-1);
t=(t%mod+mod)%mod;
int c=cnt2;
if(x>2){
c--;
}
t=t*p2[c]%mod;
ans=(ans+t)%mod;
}
cout<<ans<<'\n';
}
else if(cnt1==2){
int ans=a[0]*a[1]%mod;
ans=ans*p2[cnt2]%mod;
cout<<ans<<'\n';
}
else{
cout<<0<<'\n';
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
p2[0]=1;
for(int i=1;i<=500000;i++){
p2[i]=p2[i-1]*2%mod;
}
int T; cin >> T;
for (int ttt = 1; ttt <= T; ++ttt) {
solve();
}
return 0;
}
京公网安备 11010502036488号