Codeforces Round #786

A. Number Transformation

题意：给你一个x一个y，求出x乘a次b得到y。输出a和b，无解的话输出0 0

#include 
#include 
#include 
#include 
#include 
#include 

#define endl '\n'

using namespace std;

const int N = 1e5 + 10;

void solve()
{
	int x, y;
	cin >> x >> y;
	if (y % x == 0)
	{
		cout << 1 << ' ' << y / x << endl;
	}
	else
	{
		cout << 0 << ' ' << 0 << endl;
	}
}

int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		solve();
	}
	return 0;
}

B. Dictionary

题意：有650个字符串，输出当前给的字符串是第几个。

#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define endl '\n'

using namespace std;

const int N = 1e5 + 10;

unordered_map<string, int> st;

void solve()
{
	string s;
	cin >> s;
	int res = 25 * (s[0] - 'a');
	if (s[1] < s[0])
	{
		res += s[1] - 'a';
	}
	else
	{
		res += s[1] - 'a' - 1;
	}
	cout << res + 1 << endl;
}

int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		solve();
	}
	return 0;
}

C. Infinite Replacement

题意：给出一个只包含a的字符串，然后给出另外一个字符串b，可以用b字符串换掉源串中的’a’，求能出现多少种字符串。

思路：求出原串的长度n，如果b串长度为1，那么判断b是不是a,

如果是，那么结果为1，否则结果为2ⁿ，如果b串长度不为1，判断b串中是否有‘a’，如果有那个结果-1，否则结果也是 2ⁿ。

#include 
#include 
#include 
#include 
#include 
#include 

#define endl '\n'

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

ll ksm(ll a, int b)
{
	ll res = 1;
	while (b)
	{
		if (b & 1)
			res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}

void solve()
{
	string a;
	string b;
	cin >> a >> b;
	bool flag = false;
	for (int i = 0; i < b.size(); i++)
	{
		if (b[i] == 'a')
		{
			flag = true;
		}
	}
	if (b.size() >= 2 && flag)
	{
		cout << -1 << endl;
	}
	else
	{
		if (b == "a")
		{
			cout << 1 << endl;
			return;
		}
		int num = a.size();
		cout << ksm(2, num) << endl;
	}
}

int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		solve();
	}
	return 0;
}

D. A-B-C Sort

题意：给一个原始数组，然后这个数组每次将最后一个数移动到b数组中间，如果b数组是奇数长度，那么可以放到中间数的左或右边。a数组为空时，将b数组中间的那个数放到c后面。求这样下来c能否是有序的。

思路：整体看下来就是只有连续两个数之间是可以有交换的关系，而且是倒数第一个和倒数第二个数，倒数第三个数和倒数第四个数。那么可以倒着每两个数之间排序，最后判断是否有序即可。

#include 
#include 
#include 
#include 
#include 
#include 

#define endl '\n'

using namespace std;

const int N = 2e5 + 10;

int a[N];

void solve()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (int i = n - 2; i >= 0; i -= 2)
    {
        if (a[i + 1] < a[i])
        {
            swap(a[i + 1], a[i]);
        }
    }
    if (is_sorted(a, a + n))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

E. Breaking the Wall

题意：可以打一个位置的墙，打的位置掉两点血，旁边的两片墙掉一点，问把任意两面墙打掉需要最少多少下
思路：暴力找下三种情况，隔一扇墙，连续两扇，互不相关的两扇。然后求最小的值。

#include 
#include 

using namespace std;

const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;

int check1(int a, int b) // a b
{
	if (a < b)
	{
		swap(a, b);
	}
	if(b * 2 < a)
	{
		return (a + 1) / 2;
	}
	int res = a - b;
	a -= (a - b) * 2;
	res += a / 3 * 2;
	if (a % 3 == 1)
	{
		res += 1;
	}
	else if (a % 3 == 2)
	{
		res += 2;
	}
	return res;
}

int check2(int a, int b) // a x b
{
	if (a < b) swap(a, b);
	int res = b;
	res += (a - b + 1) / 2;
	return res;
}

int a[N];

int main()
{
	int res = INF;
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	for (int i = 1; i < n; i++)
	{
		res = min(res, check1(a[i], a[i + 1]));
	}
	for (int i = 2; i < n; i++)
	{
		res = min(res, check2(a[i - 1], a[i + 1]));
	}
	sort(a + 1, a + n + 1);
	res = min(res, (a[1] + 1) / 2 + (a[2] + 1) / 2);
	cout << res << endl;
	return 0;
}

这个判断写麻烦了，直接加2除以三就行了
因为两个连续的可以每次攻击不亏损伤害（3点），最后一次亏损的加2再算就行
太菜了