本文主要是介绍Educational Codeforces Round 161 (Rated for Div. 2)A~E，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A. Tricky Template
问能否构造一个匹配串能和a、b匹配却不能和c匹配。
如果a和b某一位置上字母相同且和c这一位置上字母不同的话一定能构造出来
还有如果a、b、c某一位置上字母都不同的话匹配串放c这一位置上的大写字母也一定能构造出来
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef long long ll;void solve()
{int n;cin >> n;string a, b, c;cin >> a >> b >> c;int f = 0;for(int i = 0; i < n; i ++){if(a[i] == b[i] && a[i] != c[i]){f = 1;break;}if(a[i] != b[i] && a[i] != c[i] && b[i] != c[i]){f = 1;break;}}if(f)cout << "YES" << endl;else cout << "NO" << endl;
}int main()
{IOSint _;cin >> _;while(_ --){solve();}return 0;
}B. Forming Triangles
组成三角形只有两种情况：
1.三条边等长
2.两条边等长，第三条边比另外两条边短
没有其他情况了
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef long long ll;const int N = 300010;int a[N];ll C(ll A, ll B)
{if(A < B)return 0;if(B == 2){ll res = A * (A - 1) / 2;return res;}ll res = A * (A - 1) * (A - 2) / 6;return res;
}void solve()
{int n;cin >> n;for(int i = 0; i <= n; i ++)a[i] = 0;for(int i = 0; i < n; i ++){int x;cin >> x;a[x] ++;}ll ans = 0, cnt = 0;for(int i = 0; i <= n; i ++){ans += C(a[i], 3) + cnt * C(a[i], 2);cnt += a[i];}cout << ans << endl;
}int main()
{IOSint _;cin >> _;while(_ --){solve();}return 0;
}C. Closest Cities
前缀和，只要计算每两个城市之前的往返费用即可
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef long long ll;const int N = 100010;int x[N];
int a[N], b[N];void solve()
{int n;cin >> n;for(int i = 0; i <= n; i ++)a[i] = b[i] = 0;for(int i = 1; i <= n; i ++)cin >> x[i];a[1] = 1, b[n] = 1;for(int i = 2; i < n; i ++)//1 - n-1{if(x[i + 1] - x[i] < x[i] - x[i - 1])a[i] = 1;else a[i] = x[i + 1] - x[i];}for(int i = n - 1; i > 1; i --)//2 - n{if(x[i] - x[i - 1] < x[i + 1] - x[i])b[i] = 1;else b[i] = x[i] - x[i - 1];}for(int i = 1; i <= n; i ++){a[i] += a[i - 1];b[i] += b[i - 1];}int Q;cin >> Q;while(Q --){int l, r;cin >> l >> r;if(l < r)//[l, r-1]{cout << a[r - 1] - a[l - 1] << endl;}else//[r+1, l]{cout << b[l] - b[r] << endl;}}
}int main()
{IOSint _;cin >> _;while(_ --){solve();}return 0;
}D. Berserk Monsters
不难想到最多会删n次，和建立链表
但难点在如何快速地实现删这n次，暴力做法在n方，明显不可取
但有一个性质是下一轮新删的点必然是由这一轮删的点影响的，根据这个性质和set的排序，可以把时间复杂度降到nlogn，可取
可以把每个点和它本轮收到的实际伤害存到set中，每一次取<0的点，然后再把这些点影响到的点更新一下即可
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef long long ll;
typedef pair<int, int> PII;const int N = 300010;int n;
int a[N], d[N];
int l[N], r[N];
bool st[N];
set<PII> S;int get(int x)
{return d[x] - a[l[x]] - a[r[x]];
}void del(int x)
{if(l[x] && !st[l[x]])S.erase({get(l[x]), l[x]});//把左右更新一下，原来的存在的话就把原来的删了 if(r[x] && !st[r[x]])S.erase({get(r[x]), r[x]});l[r[x]] = l[x];r[l[x]] = r[x];if(l[x] && !st[l[x]])S.insert({get(l[x]), l[x]});if(r[x] && !st[r[x]])S.insert({get(r[x]), r[x]});
}void solve()
{S.clear();cin >> n;for(int i = 1; i <= n; i ++)cin >> a[i];for(int i = 1; i <= n; i ++)cin >> d[i];for(int i = 1; i <= n; i ++){l[i] = i - 1, r[i] = i + 1;st[i] = false;}r[n] = 0;//a[n + 1] = 0;for(int i = 1; i <= n; i ++){S.insert({get(i), i});}for(int i = 1; i <= n; i ++){vector<int> res;while(!S.empty() && S.begin()->first < 0){int t = S.begin()->second;res.push_back(t);S.erase(S.begin());st[t] = true;}for(auto x : res){del(x);}cout << res.size() << ' ';}cout << endl;
}int main()
{IOSint _;cin >> _;while(_ --){solve();}return 0;
}E. Increasing Subsequences
构造题，看到的时候觉得应该可以往二进制角度去想
不考虑空序列的话，[0]是有1个上升子序列，[0 1]有三个子序列，增加了2个，这2个是[1]自身的一个和将[0]的所有上升子序列接到[1]前面,总共有两个
[0 1 2]是7个，增加了4个，分别是[2]的1个和[0 1]的3个接到[2]前面新生成的3个
以此类推0 1 2 3 4.....，分别依次增加8个、16个、32个.....
如果在[0 1 2 3 4]后再加一个2的话，依旧是增加了4个，按照先递增再递减的顺序是不会对彼此产生影响的。
这样就符合了二进制的条件。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef long long ll;const int N = 210;ll a[N];void solve()
{ll x;cin >> x;x --;vector<int> ans;for(int i = 0; ; i ++){if(a[i] <= x && a[i + 1] > x){for(int j = 0; j <= i; j ++)ans.push_back(j);x -= a[i];break;}}for(int i = 62; i >= 0; i --){if(x >> i & 1)ans.push_back(i);}cout << ans.size() << endl;for(auto xx : ans)cout << xx << ' ';cout << endl;
}int main()
{IOSa[0] = 1;int i = 1;for(i = 1; i <= 61; i ++){a[i] = a[i - 1] * 2 + 1;}int _;cin >> _;while(_ --){solve();}return 0;
}这篇关于Educational Codeforces Round 161 (Rated for Div. 2)A~E的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
