Codeforces Round #715 (Div. 2) A ~ D
2021/4/18 18:27:03
本文主要是介绍Codeforces Round #715 (Div. 2) A ~ D,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
个人博客版:http://www.noobzyk.top/?p=692
A. Average Height
分析
堪比div3 A的水题
代码
/** * @file :vsDebug2.cpp * @brief : * @date :2021-04-16 * @Motto :Love Sakurai Yamauchi Forever */ #include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <stack> #include <vector> #include <map> #include <set> #include <unordered_map> #include <deque> #include <cmath> #include <algorithm> #define mem(a) memset(a, 0, sizeof(a)) #define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) //#define int long long const int inf = 0x3f3f3f3f; typedef long long ll; using namespace std; const int maxn = 2005; int main() { IOS; int t; cin >> t; while(t--) { int n; cin >> n; vector<int> odd, even; int x; for(int i = 0; i < n; ++i){ cin >> x; if(x & 1) odd.push_back(x); else even.push_back(x); } for(int i = 0; i < odd.size(); ++i) cout << odd[i] << ' '; for(int i = 0; i < even.size(); ++i) cout << even[i] << ' '; cout << endl; } return 0; }
B. TMT Document
题意
给一个只含有T,M的字符串,问是否可以分割成若干个不相交的“TMT"子序列。
例如,TMTMTT可以划分成两个TMT(TMTMTT).
分析
首先,为确保数据合法,保证T的总个数是M的两倍.
然后,从左往右看,保证字符串所有前缀都满足T的数目不小于M的,这样就能保证“TM”序列总是可以划分的。
由于是对称的,再从右往左看,保证“MT”序列总可以划分,即保证了“TMT"总可以划分。
代码
/** * @file :vsDebug2.cpp * @brief : * @date :2021-04-16 * @Motto :Love Sakurai Yamauchi Forever */ #include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <stack> #include <vector> #include <map> #include <set> #include <unordered_map> #include <deque> #include <cmath> #include <algorithm> #define mem(a) memset(a, 0, sizeof(a)) #define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) //#define int long long const int inf = 0x3f3f3f3f; typedef long long ll; using namespace std; int main() { IOS; int t; cin >> t; while(t--) { int n; cin >> n; string s; cin >> s; int T = 0, M = 0; bool flag = 1; for(int i = 0; i < s.size(); ++i){ if(s[i] == 'T') T++; else if(s[i] == 'M'){ M++; if(T < M){ flag = 0; break; } } } if(T != 2 * M) flag = 0; if(!flag){ cout << "NO" << endl; continue; } T = 0, M = 0; for(int i = n - 1; i >= 0; --i){ if(s[i] == 'T') T++; else if(s[i] == 'M'){ M++; if(T < M){ flag = 0; break; } } } if(!flag) cout << "NO" << endl; else cout << "YES" << endl; } return 0; }
C.The Sports Festival
题意
给定一组数,现在将这些数按某种顺序加入。设置一个初始值为0的值 x x x.
每加入一个数, x x x加上当前加入的所有数的最大值-最小值。
问怎么排加入的顺序来保证最后得到的 x x x最小,输出最小 x x x即可。
分析
首先要贪心分析一波:
当序列中的数都是一样的时候, x x x每次都只能加0;如果不一样,保证尽量接近, x x x每次加的值也会较小。
所以,我们先将原输入序列排个序。
接下来是区间DP.
设
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]表示区间
{
i
,
j
}
\{i,j\}
{i,j}得到的最小
x
x
x,则:
d
p
[
i
]
[
j
]
=
m
i
n
(
d
p
[
i
+
1
]
[
j
]
,
d
p
[
i
]
[
j
−
1
]
)
+
a
[
j
]
−
a
[
i
]
dp[i][j]=min(dp[i+1][j], dp[i][j-1])+a[j]-a[i]
dp[i][j]=min(dp[i+1][j],dp[i][j−1])+a[j]−a[i]
因为已经排好序,所以当前最大值减最小值就是
a
[
j
]
−
a
[
i
]
a[j]-a[i]
a[j]−a[i].
之后按长度动规, d p dp dp复杂度为 O ( n 2 ) O(n^2) O(n2),总复杂度为 O ( n 2 + n l o g n ) = O ( n 2 ) O(n^2+nlogn)=O(n^2) O(n2+nlogn)=O(n2).
代码
/** * @file :vsDebug2.cpp * @brief : * @date :2021-04-16 * @Motto :Love Sakurai Yamauchi Forever */ #include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <stack> #include <vector> #include <map> #include <set> #include <unordered_map> #include <deque> #include <cmath> #include <algorithm> #define mem(a) memset(a, 0, sizeof(a)) #define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) #define int long long const int inf = 0x3f3f3f3f; typedef long long ll; using namespace std; signed main() { IOS; int sum = 0; int n; cin >> n; int a[n]; for(int i = 0; i < n; ++i){ cin >> a[i]; } sort(a, a + n); int dp[n][n]; memset(dp, 0, sizeof(dp)); for(int l = 2; l <= n; ++l){ for(int i = 0, j = i + l - 1; j < n; ++i, ++j){ dp[i][j] = min(dp[i][j - 1], dp[i + 1][j]) + a[j] - a[i]; } } cout << dp[0][n - 1] << endl; return 0; }
D. Binary Literature
其他
CF官方的解法真的妙~~~~~~~~~~~~~~~~啊
题意
给定一个数字 n n n,然后给出3个长度为 2 n 2n 2n的01字符串,现在要你构造一个长度不超过 3 n 3n 3n的字符串,要求至少有2个给出的01串是这个字符串的子序列(不是子串!)
另外,可以证明,这样的构造总是存在的。
分析
三指针做法,初始依次指向各个01字符串的开头。另外,新建一个字符串 s s s.
由于为01字符串,故3个指针指向的位置至少有2个的字符是一样的,将这个字符加入 s s s,并将这两个指针右移一位,剩下的一个指针不动。
如果有一个指针 p p p移动到了终点,那么现在进一步分析:
- 此时字符串 s s s已经完全包含了 p p p所在的字符串, p p p所在字符串已经可以是 s s s的子序列了。
- 由于每次移动都是移动2个指针,故所有指针移动了4n次,其中 p p p移动了 2 n 2n 2n次,那么剩下两个指针一共移动了 2 n 2n 2n次。也可以得到 s s s当前长度为 2 n 2n 2n.
- 剩下两个指针至少移动了 n n n次,那么至少有一个指针,其剩余未匹配的字符数小于等于 n n n个,把这些字符加入 s s s,就保证了该01串也是 s s s的子序列,且长度一定不超过 3 n 3n 3n!
/** * @file :vsDebug2.cpp * @brief : * @date :2021-04-16 * @Motto :Love Sakurai Yamauchi Forever */ #include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <stack> #include <vector> #include <map> #include <set> #include <unordered_map> #include <deque> #include <cmath> #include <algorithm> #define mem(a) memset(a, 0, sizeof(a)) #define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) //#define int long long const int inf = 0x3f3f3f3f; typedef long long ll; using namespace std; int p[3] = {0}; string s[3]; int main() { IOS; int t; cin >> t; while(t--) { memset(p, 0, sizeof(p)); int n; cin >> n; string u; cin >> s[0] >> s[1] >> s[2]; while(p[0] < 2 * n && p[1] < 2 * n && p[2] < 2 * n){ if(s[0][p[0]] == s[1][p[1]]){ u += s[0][p[0]]; p[0]++, p[1]++; } else if(s[0][p[0]] == s[2][p[2]]){ u += s[0][p[0]]; p[0]++, p[2]++; } else if(s[1][p[1]] == s[2][p[2]]){ u += s[1][p[1]]; p[1]++, p[2]++; } } string u1, s1; if(p[0] == 2 * n){ while(p[1] < 2 * n){ u1 += s[1][p[1]++]; } while(p[2] < 2 * n){ s1 += s[2][p[2]++]; } } else if(p[1] == 2 * n){ while(p[0] < 2 * n){ u1 += s[0][p[0]++]; } while(p[2] < 2 * n){ s1 += s[2][p[2]++]; } } else if(p[2] == 2 * n){ while(p[1] < 2 * n){ u1 += s[1][p[1]++]; } while(p[0] < 2 * n){ s1 += s[0][p[0]++]; } } if(u1.size() + u.size() <= 3 * n) cout << u + u1 << endl; else cout << u + s1 << endl; } return 0; }
这篇关于Codeforces Round #715 (Div. 2) A ~ D的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-21LangChain4j支持的API类型
- 2024-09-21企业如何判断自身的 CRM 系统需要多大的服务器配置?
- 2024-09-21拼接的xml报文,尖括号都被转移成了< 是什么原因-icode9专业技术文章分享
- 2024-09-21Svg Sprite Icon教程:从入门到实践
- 2024-09-21Svg Sprite Icon实战:从入门到上手
- 2024-09-20构建一个多PDF RAG聊天机器人:使用Langchain和Streamlit及代码
- 2024-09-20whatsapp webhook 回调的签名验证偶尔会失败是什么原因-icode9专业技术文章分享
- 2024-09-19Excel数据导出课程:初学者必备教程
- 2024-09-19Excel数据导入课程:新手入门指南
- 2024-09-19RBAC的权限管理入门教程