贝茜和她的朋友们正在玩奶牛杀。在这款游戏中，贝茜本色出演奶牛，她的 n n n 1 1 1 n n n i i i a i a_i a i b i b_i b i i i i i m o d n + 1 i \bmod n+1 i mod n + 1 i i i 0 0 0 i m o d n + 1 i\bmod n+1 i mod n + 1 b i b_i b i 0 0 0
需要注意的是，本游戏并无缩圈环节，若第 i m o d n + 1 i \bmod n+1 i mod n + 1 i i i
在奶牛杀中，没有投票环节，只有贝茜每晚上袭击一个猎人，造成 1 1 1
第一行一个正整数 n n n
接下来的 n n n a i , b i a_i,b_i a i , b i i i i
输出一个正整数，表示贝茜最快需要多少个晚上获得胜利。
3
6
最佳策略是连续 2 2 2 2 2 2 3 3 3 3 3 3 1 1 1 3 3 3 4 4 4 1 1 1
对于 10 % 10\% 10% n ≤ 10 n\leq 10 n ≤ 10 对于另外 10 % 10\% 10% n ≤ 100 n\leq 100 n ≤ 100 对于另外 20 % 20\% 20% n ≤ 1000 n\leq 1000 n ≤ 1000 对于另外 20 % 20\% 20% b i ≤ a i m o d n + 1 b_i\leq a_{i\ mod\ n+1} b i ≤ a i m o d n + 1 对于 100 % 100\% 100% n ≤ 3 ∗ 1 0 5 , 1 ≤ a i , b i ≤ 1 0 12 n\leq 3*10^5,1\leq a_i,b_i\leq 10^{12} n ≤ 3 ∗ 1 0 5 , 1 ≤ a i , b i ≤ 1 0 12 给定 n n n a i a_i a i n n n b i b_i b i
为了方便，我们把每个人的下一个人记为 n x t i nxt_i n x t i p r e i pre_i p r e i
假设我们从第 k k k a k a_k a k
那么显然以第 k k k
− max { b p r e k − a k , 0 } + a k + ∑ i = 1 n max { b p r e i − a i , 0 } -\max{ \{b_{pre_k} - a_k, 0\} } + a_k+ \sum \limits_{i = 1}^{n} \max{ \{b_{pre_i} - a_i, 0\} } − max { b p r e k − a k , 0 } + a k + i = 1 ∑ n max { b p r e i − a i , 0 }
那么计算出 s u m = ∑ i = 1 n max { b p r e i − a i , 0 } sum = \sum \limits_{i = 1}^{n} \max{ \{b_{pre_i} - a_i, 0\} } s u m = i = 1 ∑ n max { b p r e i − a i , 0 }
总的时间复杂度为 O ( n ) O(n) O ( n )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include <bits/stdc++.h> namespace solution{ typedef long long LL; const int MAXN = 3e5 + 5 ; const LL INF = 0x3f3f3f3f3f3f3f3f LL; int n; LL sum = 0 ; LL ans = INF; LL a[MAXN], b[MAXN], c[MAXN]; int main () { freopen ("doge.in" , "r" , stdin); freopen ("doge.out" , "w" , stdout); scanf ("%d" , &n); for (int i = 1 ; i <= n; i++) { scanf ("%lld%lld" , &a[i], &b[i]); } for (int i = 1 ; i <= n; i++) { c[i % n + 1 ] = std::max (0LL , a[i % n + 1 ] - b[i]); sum += c[i % n + 1 ]; } for (int i = 1 ; i <= n; i++) { ans = std::min (ans, sum - c[i] + a[i]); } printf ("%lld\n" , ans); return 0 ; } } int main () solution::main (); return 0 ; }
约翰要给他的奶牛们备餐，有 n n n a i a_i a i
奶牛们对食物的要求也很高，他们要求从准备的食物中任选两个计算他们满意度的异或，如果小于他们的忍耐度 x x x
约翰想问问你，在所有 2 n − 1 2^n-1 2 n − 1 x x x 998244353 998244353 998244353
如果子序列只有一个元素，约翰认为一定是合法的。
第一行包含两个非负整数 n , x n,x n , x
第二行包含 n n n a 1 , a 2 , . . . a n a_1,a_2,...a_n a 1 , a 2 , ... a n
输出一个非负整数，表示方案数模 998244353 998244353 998244353
3 0 0 1 2
7
所有的 2 3 − 1 2^3-1 2 3 − 1
3 2 0 1 2
5
由于 0 ⨁ 1 = 1 < 2 0 \bigoplus 1=1<2 0 ⨁ 1 = 1 < 2 { 0 , 1 } \{0,1\} { 0 , 1 } { 0 , 1 , 2 } \{0, 1, 2\} { 0 , 1 , 2 }
7 4 11 5 5 8 3 1 3
35
不保证 a i a_i a i 5 5 5 3 3 3
对于 100 % 100\% 100% 1 ≤ n ≤ 3 ∗ 1 0 5 1\leq n \leq 3*10^5 1 ≤ n ≤ 3 ∗ 1 0 5 0 ≤ a i , x < 2 60 0\leq a_i,x< 2^{60} 0 ≤ a i , x < 2 60 约翰最近迷恋上了《只狼：影逝二度》，于是他决定拿奶牛试试手。
具体来说，有 n n n x i x_i x i [ l i , r i ] [l_i,r_i] [ l i , r i ]
刚开始所有奶牛都是未警戒的状态。约翰可以偷袭并瞬间杀死一个未警戒状态的奶牛 i i i x i ∈ [ l j , r j ] x_i\in[l_j,r_j] x i ∈ [ l j , r j ] j j j
约翰有一次复活机会，复活后仍然活着的奶牛会恢复到未警戒状态和原来的位置。但是如果复活后偷袭被别的奶牛再次被发现就会失败。
约翰有 T T T
输入的第一行包含一个正整数 T T T
接下来连续输入 T T T
每张地图的第一行包含一个正整数 n n n
此后的 n n n x i , l i , r i x_i, l_i, r_i x i , l i , r i i i i x 1 < x 2 < . . . < x n x_1 < x_2 < ... < x_n x 1 < x 2 < ... < x n
输出 T T T Yes 或 No，分别表示约翰是否可以通过这张地图。
2
Yes
对于第一张地图，约翰可以首先对第二个奶牛（位置为 6）发动偷袭，并会被第三个奶牛杀死。在复生后，他可以按照三，一，四的顺序分别杀死剩余的三个奶牛，并且不会引起敌人的警觉。
对于 100 % 100\% 100% 1 ≤ T ≤ 1 0 5 , 1 ≤ n ≤ 1 0 6 , ∑ n ≤ 3 ∗ 1 0 6 , 1 ≤ l i ≤ x i ≤ r i ≤ 1 0 9 , 1 ≤ x 1 < x 2 < . . . < x n ≤ 1 0 9 1\leq T\leq 10^5,1\leq n \leq 10^6,\sum n\leq 3*10^6,1\leq l_i\leq x_i\leq r_i\leq 10^9,1\leq x_1<x_2<...<x_n\leq 10^9 1 ≤ T ≤ 1 0 5 , 1 ≤ n ≤ 1 0 6 , ∑ n ≤ 3 ∗ 1 0 6 , 1 ≤ l i ≤ x i ≤ r i ≤ 1 0 9 , 1 ≤ x 1 < x 2 < ... < x n ≤ 1 0 9
给定 n n n x i , l i , r i x_i, l_i, r_i x i , l i , r i x i x_i x i l j , r j l_j, r_j l j , r j
简化题意，可以通过相互包含的关系建出一张有向图，图上有环时则无法处理，只能将某个区间删除掉
那么可以通过枚举环上的点删除，拓扑排序判断图中是否还有其他环的方法来解决，时间复杂度为 O ( n 3 ) O(n ^ 3) O ( n 3 )
可以发现如下性质：图中如果存在环，那么必定存在二元环，
以三元环为例，假设图中有三元环 a , b , c a, b, c a , b , c x a < x b < x c x_a < x_b < x_c x a < x b < x c b b b a a a c c c b b b a a a b b b c c c
那么现在的问题就变成了在图中找二元环的问题
首先可以在图中找出任意一对二元环，对环上的两个点枚举删除，判断图中是否还有其他二元环
判断二元环时可以从左向右枚举每个点，同时维护一个栈，栈中的元素从栈底到栈顶 x x x r r r x x x r r r i i i r r r i i i r r r i i i
下面考虑证明正确性
假设图中存在二元环 a , b a, b a , b a x < b x a_x < b_x a x < b x a l ≤ b x ≤ a r a_l \le b_x \le a_r a l ≤ b x ≤ a r
枚举到 b b b a a a b b b a a a a , b a, b a , b c c c 枚举到 b b b a a a c c c a a a c c c 故若图中有环，那么该算法一定可以找到
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #include <bits/stdc++.h> namespace solution{ typedef long long LL; const int MAXN = 3e6 + 5 ; int t; LL n; LL a[MAXN]; struct Node { LL l, x, r; }; Node node[MAXN]; auto find (int pos) { std::stack<int > stk; for (int i = 1 ; i <= n; i++) { if (i == pos) { continue ; } while (!stk.empty ()) { int u = stk.top (); if (node[i].l <= node[u].x && node[u].x <= node[i].r && node[u].l <= node[i].x && node[i].x <= node[u].r) { return std::make_pair (i, u); } if (node[u].r > node[i].r) { break ; } stk.pop (); } stk.push (i); } return std::make_pair (0 , 0 ); } int main () { freopen ("sekiro.in" , "r" , stdin); freopen ("sekiro.out" , "w" , stdout); scanf ("%d" , &t); while (t--) { scanf ("%lld" , &n); for (int i = 1 ; i <= n; i++) { scanf ("%lld%lld%lld" , &node[i].x, &node[i].l, &node[i].r); } auto t = find (0 ); if (t == std::make_pair (0 , 0 ) || find (t.first) == std::make_pair (0 , 0 ) || find (t.second) == std::make_pair (0 , 0 )) { puts ("Yes" ); } else { puts ("No" ); } } return 0 ; } } int main () solution::main (); return 0 ; }