Aising Programming Contest 2022(AtCoder Beginner Contest 255)
2022/6/12 23:20:12
本文主要是介绍Aising Programming Contest 2022(AtCoder Beginner Contest 255),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Aising Programming Contest 2022(AtCoder Beginner Contest 255)
E
题意
给一个数组 \(S\) 满足 \(S_i = a_i + a_{i + 1}\) ,\(0 < i < n\) 。给一个好数集合 \(X\) 要求用 \(S\) 构造出来的数组 \(a\) 中含最多的好数。
思路
当确定 \(a\) 中任意一个元素整个数组就确定了。最暴力的方法枚举所有情况,显然T了。
这里用了一个第一次见的思路,还挺新奇的。
不妨设 \(a_1 = x\) ,那么 \(a_i = -x + b\) 或 \(a_i = x + b\) 。\(x\) 就是可解的,当 \(x = b - c_j\) 或 \(x = c_j - b\) 时对答案有贡献,其中 \(c_j\) 是集合 \(X\) 中的任意数。所以对每个数都可以推出有贡献的 \(x\) 的取值,统计那个出现最多的 \(x\) 就是对答案最大的贡献。
感觉核心思想就是用一个数 \(x\) 表示序列的状态,然后对每个数字都贪心的找对答案有最大贡献的取值,如果不同数字的的取值都可以对应到 \(x\) 上,那么它们就可以同时满足。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<set> #include<queue> #include<map> #include<string> #include<random> #include<iomanip> #define yes puts("yes"); #define inf 0x3f3f3f3f #define ll long long #define linf 0x3f3f3f3f3f3f3f3f #define ull unsigned long long #define endl '\n' #define int long long #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) using namespace std; mt19937 mrand(random_device{}()); int rnd(int x) { return mrand() % x;} typedef pair<int,int> PII; const int MAXN =10 + 2e5 ,mod=1e9 + 7; void solve() { int n,m; cin >> n >> m; vector<int> s(n + 1),a(m + 1); rep(i,1,n - 1) cin >> s[i]; rep(i,1,m) cin >> a[i]; map<int,int> mp; int k = 1, b = 0;// a1 + a2 = s1 a2 = s1 - x a1 = x s1 - c1 rep(i,1,m) mp[k * (a[i] - b)] ++; rep(i,2,n) { k *= -1; b = s[i - 1] - b; rep(i,1,m) mp[k * (a[i] - b)] ++; } int ans = 0; for(auto [x,c] : mp) ans = max(ans, c); cout << ans; } signed main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //int T;cin>>T; //while(T--) solve(); return 0; }
F
题意
给二叉树的先序遍历和中序遍历,求这棵树,如果这棵树不存在或根不为 \(1\) 。输出\(-1\)。
思路
数据结构作业题,思路略了
代码实现上,核心思路是把先序当时间戳,不断切割中序序列,在一段区间中时间戳最小的就是根节点。递归找下去。
最后检查一下跑出来的树是否合法。
中间要查区间最小,得st表查一查(感觉写麻烦了,先这样吧)
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<set> #include<queue> #include<map> #include<string> #include<random> #include<iomanip> #define yes puts("yes"); #define inf 0x3f3f3f3f #define ll long long #define linf 0x3f3f3f3f3f3f3f3f #define ull unsigned long long #define endl '\n' // #define int long long #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) using namespace std; mt19937 mrand(random_device{}()); int rnd(int x) { return mrand() % x;} typedef pair<int,int> PII; const int MAXN =10 + 2e5 ,mod=1e9 + 7; template<typename T> struct ST{ ST(vector<T> a, int n){ // cope with in [0,n] siz = n; maxv.resize(n+1); minv.resize(n+1); int t = __lg(n) + 1; for(int i= 0;i<=n;i++) maxv[i].resize(t), minv[i].resize(t); for(int i = 0; i <= n; i++) maxv[i][0] = minv[i][0] = a[i]; for(int j = 1; j < t; j++) { for(int i = 0; i <= n - (1<<j)+1; i++) { maxv[i][j] = max(maxv[i][j-1], maxv[i+(1 << (j-1))][j-1]); minv[i][j] = min(minv[i][j-1], minv[i+(1 << (j-1))][j-1]); } } } T getmax(int l,int r){ int k = __lg(r-l+1); return max(maxv[l][k],maxv[r-(1<<k)+1][k]); } T getmin(int l,int r){ int k = __lg(r-l+1); return min(minv[l][k],minv[r-(1<<k)+1][k]); } private: int siz = 0; vector<vector<T>> maxv, minv; }; void solve() { int n; cin >> n; vector<int> a(n + 1),b(n + 1); rep(i,1,n) cin >> a[i]; rep(i,1,n) cin >> b[i]; vector<int> vec(n + 1); rep(i,1,n) vec[a[i]] = i; vector<int> tim(n + 1),val(n + 1),p(n + 1); rep(i,1,n) tim[i] = vec[b[i]], val[tim[i]] = b[i],p[b[i]] = i; ST stt(tim,n + 1); vector<PII> ans(n + 1); bool ok = 1; function<int(int,int)> dfs = [&](int l,int r) { if(l > r) return 0; int mintim = stt.getmin(l,r); int rt = val[mintim]; ans[rt].first = dfs(l,p[rt] - 1); ans[rt].second = dfs(p[rt] + 1,r); return rt; }; dfs(1,n); vector<int> P,I; function<void(int)> dfs2 = [&](int u) { if(!u) return; auto [lc,rc] = ans[u]; P.push_back(u); dfs2(lc); I.push_back(u); dfs2(rc); }; dfs2(a[1]); rep(i,1,n) { if(a[i] != P[i - 1]) ok = 0; if(b[i] != I[i - 1]) ok = 0; } if(!ok || a[1] != 1) cout << -1; else rep(i,1,n) cout << ans[i].first << " " << ans[i].second << "\n"; } signed main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //int T;cin>>T; //while(T--) solve(); return 0; }
G
博弈 ?不会博弈(
Ex
题意
用 \(n\) 棵树,第 \(i\) 棵树每天长 \(i\) 个果子。一开始树上都没有果子
有 \(q\) 次询问,每次询问将区间 \([l,r]\) 范围内的果子收获,输出收获的果子数量。
思路
有推平操作考虑珂朵莉树。发现在推平过程中可以通过维护上次收获时间把答案算出来(等差数列求个和)
注意数据范围很大,取模运算时小心越界。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<set> #include<queue> #include<map> #include<string> #include<random> #include<iomanip> #define yes puts("yes"); #define inf 0x3f3f3f3f #define ll long long #define linf 0x3f3f3f3f3f3f3f3f #define ull unsigned long long #define endl '\n' #define int long long #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) using namespace std; mt19937 mrand(random_device{}()); int rnd(int x) { return mrand() % x;} typedef pair<int,int> PII; const int MAXN =10 + 2e5 ,mod=998244353; int inv2; int ksm(int a,int b) { int ans = 1; while(b) { if(b & 1) ans = ans * a % mod; a = a * a % mod; b >>= 1; } return ans; } struct Node { int l,r; int timer; Node(int L): l(L){} Node(int L,int R,int tim): l(L),r(R),timer(tim){} bool operator<(const Node &o) const {return l < o.l;} }; set<Node> s; #define IT set<Node>::iterator IT split(int pos) { // [l,p - 1][p,r] IT it = s.lower_bound(Node(pos)); if(it != s.end() && it->l == pos) return it; it --; int L = it->l, R = it->r; auto tim = it->timer; s.erase(it); s.insert(Node(L,pos - 1,tim)); return s.insert(Node(pos,R,tim)).first; } int assign(int l,int r,int d) { IT end = split(r + 1), beg = split(l); int ans = 0; for(auto it = beg;it != end;it ++) { int tim = it->timer,L = it->l, R = it->r; L %= mod, R %= mod; ans = (ans + ((d - tim) % mod + mod) % mod * (L + R) % mod * (R - L + 1) % mod * inv2 % mod) % mod; } s.erase(beg,end); s.insert(Node(l,r,d)); while(ans < 0) ans += mod; return ans; } void solve() { inv2 = ksm(2,mod - 2); int n,q; cin >> n >> q; s.insert(Node(1,n,0)); s.insert(Node(0,0,0)); s.insert(Node(n + 1,n + 1,0)); while(q --) { int d,l,r; cin >> d >> l >> r; cout << assign(l,r,d) << endl; } } signed main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //int T;cin>>T; //while(T--) solve(); return 0; }
这篇关于Aising Programming Contest 2022(AtCoder Beginner Contest 255)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升