天柱建设局网站,郑州企业网站排行,自己怎么做可以让百度收录的网站,网站建设未来发展前景t宝酱紫喜欢出这种分类讨论的题#xff1f;#xff01;A1. Non-alternating Deck (easy version)给出n张牌#xff0c;按照题目给的顺序分给两人#xff0c;问最后两人手中各有几张牌。思路#xff1a;模拟。AC Code#xff1a;#include bits/stdc.htypedef long…t宝酱紫喜欢出这种分类讨论的题A1. Non-alternating Deck (easy version)给出n张牌按照题目给的顺序分给两人问最后两人手中各有几张牌。思路模拟。AC Code#include bits/stdc.htypedef long long ll;
const int N 1e5 5;
int t, n;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin t;while(t --) {std::cin n;n --;ll cnta 1, cntb 0;int cnt 0, res 0;for(int i 2; n 0; i ) {if(cnt 2) res ^ 1, cnt 0;if(res 0)cntb std::min(n, i), n - std::min(n, i);elsecnta std::min(n, i), n - std::min(n, i);cnt ;}std::cout cnta cntb \n;}return 0;
}A2. Alternating Deck (hard version)在A1的基础上分了两种颜色问最后每人手中每种颜色有几张。思路还是模拟。AC Code#include bits/stdc.htypedef long long ll;
const int N 1e5 5;
int t, n;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin t;while(t --) {std::cin n;int pos 1, cntp 0, cnt 0, res 0;int cntaw 0, cntab 0, cntbw 0, cntbb 0;for(int i 1; i n; i ) {if(cntp pos) {res ;pos ;cntp 0;if(res 1)cnt ^ 1;}if(!cnt) {if(i 1)cntaw ;elsecntab ;}else {if(i 1)cntbw ;elsecntbb ;}cntp ;}std::cout cntaw cntab cntbw cntbb \n; }return 0;
}B. Cake Assembly Line给出一个蛋糕的位置序列和加巧克力的机器头的位置序列调整两条线的相对顺序是否可以满足机器头加入巧克力全部位于蛋糕上的要求。思路从头开始找范围的交集如果交集不为空集就可以满足。当然机器头的半径如果大于蛋糕的半径那一定是不可以的。AC Code#include bits/stdc.htypedef long long ll;
const int N 2e5 5;
int t, n, w, h;
ll a[N], b[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin t;while(t --) {std::cin n w h;for(int i 1; i n; i ) {std::cin a[i];}for(int i 1; i n; i ) {std::cin b[i];}if(w h) {std::cout NO \n;continue;}ll L a[1] - w h, R a[1] w - h;for(int i 2; i n; i ) {ll lb L b[i] - b[i - 1], rb R b[i] - b[i - 1];// std::cout lb rb \n;ll l a[i] - w h, r a[i] w - h;// std::cout l r \n;L std::max(l, lb), R std::min(r, rb);// L std::max(l, L);// R std::min(R, r);// std::cout l r L R \n;}std::cout (L R ? YES : NO) \n;}return 0;
}C. Monsters (easy version)给出一个序列的怪物的生命值有两种操作一是对其中一个怪物打击使得它的生命值-1二是对于所有的怪物进行打击每一个都-1如果在一次打击中有怪物生命值降为0则可以重复该操作。求操作一使用次数最少是多少。思路最优的操作是使得操作数组存在1~x连续序列数字必须从1开始尽可能使得数字变大不能通过一次操作二减去的那只能操作一减去了。AC Code#include bits/stdc.htypedef long long ll;
const int N 2e5 5;
int t, n;
ll a[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin t;while(t --) {std::cin n;for(int i 1; i n; i ) {std::cin a[i];}std::sort(a 1, a 1 n);ll pos 1, ans a[1] - pos;for(int i 2; i n; i ) {if(a[i] pos)continue;pos ;ans (a[i] - pos);}std::cout ans \n;}return 0;
}D. Letter Exchange给出m个有三个字符的字符串每次可以用两个字符串交换字符问最少交换几次可以的使得每个字符串的三个字符都不一样。思路大佬的思路AC Code#include bits/stdc.htypedef long long ll;
const int N 1e5 5;
int t, n;
std::string s;struct node {int a, b;char c, d;
};int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin t;char ch[4] win;const std::arrayint, 3 all1 {1, 1, 1};while(t --) {std::cin n;std::mapstd::arrayint, 3, std::vectorint mp;int sum 0;for(int i 1; i n; i ) {std::cin s;std::arrayint, 3 cnt {};for(auto c : s) {if(c w) cnt[0] ;else if(c i) cnt[1] ;else cnt[2] ;}if(cnt all1) continue;mp[cnt].push_back(i);sum ;}std::vectornode op;while(sum) {int max 0;std::arrayint, 3 p1, p2;for(auto [x1, v1] : mp) {if(v1.empty()) continue;for(auto [x2, v2] : mp) {if(x1 x2) continue;if(v2.empty()) continue;int c 0;for(int i 0; i 3; i ) {if(x1[i] 1 x2[i] 1) c ;else if(x2[i] 1 x1[i] 1) c ;}if(c max) {max c;p1 x1, p2 x2;}}}int t1 mp[p1].back();int t2 mp[p2].back();mp[p1].pop_back();mp[p2].pop_back();char c1, c2;for(int i 0; i 3; i ) {if(p2[i] 2) c2 ch[i], p2[i] --, p1[i] ;else if(p1[i] 2) c1 ch[i], p1[i] --, p2[i] ;}if(p1 ! all1) mp[p1].push_back(t1);else sum --;if(p2! all1) mp[p2].push_back(t2);else sum --;op.push_back({t1, t2, c1, c2});}std::cout op.size() \n;for(auto [a, b, c, d] : op) {std::cout a c b d \n;}}return 0;
}E. Monsters (hard version)与C相同不过区别是要对于每个i输出所需的最少操作一数量。思路我们的操作是将原数组组成一个1递增的数列对于每次向后加入的数如果它比较小那对于现有的数组来说没什么影响但是若是加入的数比较大那就需要考虑它的影响了。但是例如113335来说最后变成的数组为112334而其中第二个数和第四个数对于答案是没有贡献的而去掉重复的元素后前i个数的结果为其中n是数组所能达到的最大的数。引用大佬的结论和证明AC Code#include bits/stdc.htypedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define int long long
const int N 2e5 5;
int t, n;
int a[N];struct SegmentTree {struct node {int l, r, max, add;} tr[N 2];void pushup(int u) {tr[u].max std::max(tr[u 1].max, tr[u 1 | 1].max);}void build(int u, int l, int r) {tr[u] {l, r, -INF, 0};if(l r) {tr[u].max -l;return;}int mid l r 1;build(u 1, l, mid);build(u 1 | 1, mid 1, r);pushup(u);}void pushdown(int u) {if(tr[u].add) {tr[u 1].add tr[u].add;tr[u 1 | 1].add tr[u].add;tr[u 1].max tr[u].add;tr[u 1 | 1].max tr[u].add;tr[u].add 0;}}void modify(int u, int l, int r, int c) {if(tr[u].l l tr[u].r r) {tr[u].max c;tr[u].add c;}else {pushdown(u);int mid tr[u].l tr[u].r 1;if(l mid) modify(u 1, l, r, c);if(r mid) modify(u 1 | 1, l, r, c);pushup(u);}}int query(int u) {if(tr[u].l tr[u].r) return tr[u].l;pushdown(u);if(tr[u 1].max 0) return query(u 1);return query(u 1 | 1);}} ST;signed main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin t;while(t --) {std::cin n;for(int i 1; i n; i ) {std::cin a[i];}ST.build(1, 1, n);int cnt 0, s 0;for(int i 1; i n; i ) {cnt , s a[i];ST.modify(1, a[i], n, 1);if(ST.tr[1].max 0) {int x ST.query(1);ST.modify(1, x, n, -1);cnt --, s - x;}std::cout s - cnt * (cnt 1) / 2 \n[i n];}}return 0;
}
