本文主要是介绍Educational Codeforces Round 161 (Rated for Div. 2)（A - E），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
比赛地址 :
https://codeforces.com/contest/1922
A. Tricky Template
直接根据题意就能够发现 :
遍历每一个位置 i : 如果能够发现 c[i]!=a[i] && c[i]!=b[i] , 就直接返回true；
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define lowbit(x) (x&(-x))
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define int long long
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;using namespace std;inline void solve(){int n ; cin >> n ;string a,b,c;cin >>a>>b>>c;bool tag = false ;for(int i=0;i<n;i++){if(c[i]!=a[i] && c[i]!=b[i]){tag = true;break ;}}if(tag) cout << "Yes" <<endl;else cout << "No" <<endl;
}signed main()
{IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}B. Forming Triangles
B 题的话要用到组合数的思想 ，和 三角形的知识 ;
首先看题 : 对于每一条边都是2^ai,分析一下的话，如果三条边的长度都不相等的话，那么就一定不可能构造出一个三角形 ；
例如 分别为i-1 , i , i+1 的三个边的长度就是a = 2^i-1 , b = 2 ^ i , c = 2 ^ i + 1 , 那么无论如何都会出现 a + b < c 的情况，因为a < c-b = b , 如果间隔再取大一点的话，那就更不可能满足了；
有了以上分析之后，可以得出只有可能是等边或者等腰三角形满足题目条件 ;
那么就先排序，然后依据每个相等长度木棒数量len进行分析即可:
if(len>=3){//等边 ans += 1LL * (len) * (len-1) * (len-2) / 6 ;}
if(len>=2){// 等腰ans += 1LL * (len) * (len-1) / 2 * (i-1) ;}详细请看代码 :
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define lowbit(x) (x&(-x))
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define int long long
typedef long long LL;
const int mod = 1e9 + 7;
const int N = 3e5 + 10;using namespace std;int a[N] ;inline void solve() {int n ; cin >> n;for(int i=1;i<=n;i++) cin >> a[i];if(n<3){cout << 0 << endl;return ;}sort(a+1,a+1+n) ;// abbint ans = 0 ;for(int i=1;i<=n;i++){int j = i + 1;while(j<=n && a[j]==a[i]) j++;int len = j - i ;if(len>=3){//等边 ans += 1LL * (len) * (len-1) * (len-2) / 6 ;}if(len>=2){ans += 1LL * (len) * (len-1) / 2 * (i-1) ;}i = j - 1 ;}cout << ans << endl;return ;
}signed main()
{IOSint _ = 1;cin >> _;while (_--) solve();return 0;
}C. Closest Cities
此题采用类似于前缀和的思想来解决，先预处理好两个数组st,ed，其中st[i]表示由1城市到i城市的最小花费，ed[i]表示从n城市到i城市的最小花费；
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 1e5 + 10 ;
typedef long long LL ;
LL a[N] , st[N] , ed[N];void solve() {int n ; cin >> n ;for(int i=1;i<=n;i++) cin >> a[i] ;// st[i]表示从1到i的最小花费 st[1] = ed[n] = 0 ;st[2] = 1 ;// 1 到 2 城市 一定是 1 for(int i=3;i<=n;i++){// i-1 到 i int l = a[i-1] - a[i-2];int r = a[i] - a[i-1];if(l<r) st[i] = st[i-1] + r ;else st[i] = st[i-1] + 1 ;} ed[n-1] = 1;for(int i=n-2;i>=1;i--){// i+1 到 i int l = a[i+1] - a[i];int r = a[i+2] - a[i+1];if(l<r) ed[i] = ed[i+1] + 1;else ed[i] = ed[i+1] + l;}int m ; cin >> m;while(m--){int x,y;cin >> x >> y;if(x < y) cout << st[y] - st[x] << endl;else cout << ed[y] - ed[x] << endl;}return ;
}int main() {ios_base::sync_with_stdio(false);cin.tie(NULL);int _ = 1;cin >> _;while (_--) solve();return 0;
}D . Berserk Monsters
首先我们可以看出，当所有怪物在一轮中全部活了下来，那么显然，下一轮还是所有怪物都活着，那么实际上也说明了一个问题，只有上一轮死去了怪物，死去的怪物的左右会改变，也就是它们受到的伤害会变得不一样，产生新的怪物;
我们需要注意，只有上轮怪物死掉得左右需要再次算一遍；
这样得操作很类似于一个链表 , o(1) ;
我们可以记录左右 ， 然后模拟链表 ;
当然我们可以简单一点，我们可以搞一个set,用于计算目前得左右点，O(logn)
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define lowbit(x) (x&(-x))
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define int long long
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;using namespace std;inline void solve(){int n ; cin >> n ;vector<int> a(n+1);// 记录攻击vector<int> d(n+1);// 记录防御 vector<int> l(n+1);// 记录左边 vector<int> r(n+1);// 记录右边 for(int i=1;i<=n;i++) cin >> a[i-1] ;for(int i=1;i<=n;i++) cin >> d[i-1] ;a[n] = 0 ;// 创造一个新点 ， 不算人 ， 也没有攻击力d[n] = 0 ;// int de[n+1] ;// de数组 : 记录一个点是否死掉，防止重复计算for(int i=0;i<=n;i++){l[i] = n ;r[i] = n ;de[i] = 0 ;}for(int i=0;i<n;i++){// 初始化 链表 的 左右连接if(i-1>=0) l[i] = i - 1 ;if(i+1<=n-1) r[i] = i + 1 ;}queue<int> q ;// 写一个队列 ， 记录哪些点可能被删除 ; for(int i=0;i<n;i++){q.push(i);}vector<int> ans(n);int cnt = 0 ;while(1){int len = q.size() ;int zhi = 0 ; // 记录这轮死了多少怪物 vector<int> drr ; // 记录目前删掉哪些点 ， 后面会进行链表的从新连接while(len--){int z = q.front();q.pop() ;if(z==n) continue ;if(de[z]>=1) continue;if(a[l[z]]+a[r[z]]>d[z]){// 当左右能够杀死这个点 drr.push_back(z);// 加到本轮能够删除的点 de[z]++;// 已经死掉的标记 zhi++;}} if(zhi==0) break;// 如果没点死掉，那么就不用再算了 set<int> st ;// 找到目前可能还会被杀死的怪物 for(auto x : drr){if(l[x]>=0){r[l[x]] = r[x];// 链表的连接 if(de[l[x]]>=1) continue;else st.insert(l[x]);// 如果有怪物没死 }if(r[x]<=n-1){l[r[x]] = l[x] ;// 链表的连接if(de[r[x]]>=1) continue;else//同理st.insert(r[x]); }}for(auto x : st){q.push(x);// 添加进队列 , 新的可能被杀死的怪物 }ans[cnt++] = zhi;// 记录一下本轮答案 }for(int i=cnt ;i<n;i++) ans[i] = 0 ;for(int i=0;i<n;i++) cout << ans[i] << " " ;cout << endl ;return ;
}signed main()
{IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}E. Increasing Subsequences
思路如下 :
// 构造 , 位运算
// 设数组 a 有 x 个递增的子序列
// 在数组的末尾添加一个新的最小值，ans = x + 1 ;
// 在数组末尾添加一个新的最大值，新数组中的ans = 2 * x ;
// 那么分奇偶 , 使用递归函数f(x) , 他返回正好有x个递归子序列的数组。
// 对于奇数 x : f(x) = f(x-1) + min,这里+表示向数组末尾添加一个最小的元素
// 对于偶数 x : f(x) = f(x/2) + max
// 估计元素数量 :
代码 :
#include <bits/stdc++.h>using namespace std;vector<int> f(long long x) {vector<int> res;if (x == 2) {res.push_back(0);} else if (x & 1) {res = f(x - 1);res.push_back(*min_element(res.begin(), res.end()) - 1);} else {res = f(x / 2);res.push_back(*max_element(res.begin(), res.end()) + 1);}return res;
}int main() {int t;cin >> t;while (t--) {long long x;cin >> x;auto ans = f(x);cout << ans.size() << '\n';for (int i : ans) cout << i << ' ';cout << '\n';}
}这篇关于Educational Codeforces Round 161 (Rated for Div. 2)（A - E）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
