200天1000题 （DAY 7）
目前总题数： 32
目前CF分数： 1325
T1 (Codeforces Edu.#130 Div. 2)C. awoo's Favorite Problem
/*
题目大意：
给你两个字符串 s，t
你可以对s进行如下操作任意次：
1. 把s中某个字串"ab"变为"ba"
2. 把s中某个字串"bc"变为"cb"
问，是否能够在任意次操作后使得s==t
*/
/*
题解：
首先应该关注到这两个操作 "ab"变"ba" ,"bc"变"cb"
这意味这 a和c的相对位置是不可变的
而b则是可以“出现在”任意位置
所以我们首先要判断一下 去除掉 b后的s和t是否相同
如果不同那么就肯定不能
如果同，我们观察到，a永远只能从左边的位置变到右边的位置，c则是只能从某个右边的位置变到左边的位置
所以我们可以开几个数组分别记录一下s中c，a的下标以及t中c，a的下标
判断是否符合上述规则，如果不符合，直接输出NO
符合上述所有规则，那么就是可以的
*/
inline void sensei()
{
int n;
cin >> n;
string s, t;
cin >> s >> t;
string c, d;
c = d = "";
for (auto &i : s) {
if (i == 'a') c += "a";
if (i == 'c') c += "c";
}
for (auto &i : t) {
if (i == 'a') d += "a";
if (i == 'c') d += "c";
}
if(d!=c){
cout << "NO" << endl;
return ;
}
vector<int> sa,sc,ta,tc;
for(int i=0;i<s.size();i++){
if(s[i] == 'a') sa.pb(i);
if(s[i] == 'c') sc.pb(i);
if(t[i] == 'a') ta.pb(i);
if(t[i] == 'c') tc.pb(i);
}
if(sa.size()!=0){
for(int i=0;i<sa.size();i++){
if(sa[i] > ta[i]) {
cout << "NO" << endl;
return ;
}
}
}
if(sc.size()!=0){
for(int i=0;i<sc.size();i++){
if(sc[i] < tc[i]){
cout << "NO" << endl;
debug("haha");
return ;
}
}
}
cout << "YES" << endl;
}
signed main()
{
#ifndef LOCAL
fuckios
#endif
int t;
cin >> t;
while (t --) {
sensei();
}
return 0;
}
T2. (Codeforces Edu#99 Div. 2) C. Ping-pong
/*
题目大意：
给你两个数字a，b
表示alice的体力和bob的体力
他们要进行乒乓球比赛
第一轮中 alice 先发球
在每一轮比赛中，每个人可以选择回球或者不回球
不回球者输掉这轮比赛，回球者体力减1
每轮的胜利者下一轮接着发球
问如果他们以最优的策略进行游戏，那么他们的最大得分分别是多少？
题解：
观察可得 alice最多赢得体力-1分
bob最多可赢得b分
*/
inline void sensei()
{
int a,b;
cin >> a >> b;
cout << a-1 << ' ' << b << endl;
}
signed main()
{
#ifndef LOCAL
fuckios
#endif
int t;
cin >> t;
while(t --){
sensei();
}
return 0;
}
T3 (Codeforces #792 DIV.1+DIV.2） C. Column Swapping
/*
暴力，就是代码容易写假（）
*/
const int N = 1e6 + 10;
inline void sensei()
{
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> g[i][j];
}
}
set<int> pos;
vector<int> npos;
for (int i = 1; i <= n and npos.empty(); i++) {
vector<int> alls = g[i];
sort(alls.begin() + 1, alls.begin() + 1 + m);
for (int j = 1; j <= m; j++) {
if (alls[j] != g[i][j]) {
pos.insert(j);
npos.push_back(j);
}
}
}
if (npos.size() > 2) {
cout << -1 << endl;
return ;
}
if (npos.size() == 0 ) {
cout << 1 << ' ' << 1 << endl;
return ;
}
if (npos.size() == 1) {
cout << npos[0] << ' ' << npos[0] + 1 << endl;
return ;
}
debug(npos[0]);
debug(npos[1]);
if (pos.size() == 2) {
for (int i = 1; i <= n; i++) {
swap(g[i][npos[0]], g[i][npos[1]]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m-1;j++){
if(g[i][j] > g[i][j+1]){
cout << "-1" << endl;
return ;
}
}
}
cout << npos[0] << ' ' << ' ' << npos[1] << endl;
}
signed main()
{
#ifndef LOCAL
fuckios
#endif
int t;
cin >> t;
while (t --) {
sensei();
}
return 0;
}
T4 (Codeforces #758 DIV1+ DIV2) B. Build the Permutation
/*
题意：
给你三个数字 n，a，b
要求你构造出 任意一个长度为n，有a个局部最大，b个局部最小的序列
局部最大： 对于a[i] 有 a[i-1] < a[i] > a[i+1]
局部最小， 对于a[i] 有 a[i-1] > a[i] < a[i+1]
如果这样的序列不存在，则输出-1
*/
/*
首先观察得出
如果a和b相差大于1 则必定不可能
其次 a+b也必须小于n-2
后面就是构造了，详细见代码
*/
inline void sensei()
{
int n, a, b;
cin >> n >> a >> b;
if (abs(a - b) > 1) {
cout << -1 << endl;
return ;
}
if (a + b > (n - 2)) {
cout << -1 << endl;
return ;
}
vector<int> ans(n + 1, 0);
for (int i = 1; i <= n; i++) ans[i] = i;
if (a == b) {
for (int i = 1; i <= a; i++)
swap(ans[i * 2], ans[i * 2 + 1]);
} else if (a > b) {
for (int i = 1; i <= a; i++) {
swap(ans[i * 2], ans[i * 2 - 1]);
}
} else {
for (int i = 1; i <= b; i++) {
swap(ans[i * 2], ans[i * 2 - 1]);
}
}
if(a - b == 1){
for(int i=1;i<=n;i++){
ans[i] = -ans[i]+n+1;
}
}
for(int i=1;i<=n;i++){
cout << ans[i] << " \n"[i==n];
}
}
signed main()
{
#ifndef LOCAL
fuckios
#endif
int t;
cin >> t;
while (t --) sensei();
return 0;
}