Aug.Day04 8.8总结

#A.多项式输出

本题的题面初一看似乎有些复杂，特别是开头的式子：

$$f (x) = a_nx^n + a_{n - 1}x^{n-1} + \cdot \cdot \cdot + a_1x + a_0 \\ a_n \ne 0$$

不过不慌，我们结合下面的样例来看。

输入：5 \n 100 -1 1 -3 0 10。

输出：100x^5-x^4+x^3-3x^2+10。

我们需要按顺序解决各个问题，用一个 ans 存答案（字符串）。首先是符号的问题，首先判断当前是不是第一个元素且为整数，如果是则不作输出，否则如果是非首元素正数则ans += '+'，否则只要是负数那么ans += '-'。

接下来解决系数的问题，首先可以发现要求中“多项式中只包含系数不为 $0$ 的项”，那么如果当前输入系数为 $0$，则直接跳过，否则再判断系数绝对值是否为 $1$，是则直接跳到次数部分（但这里要特别注意当次数为 $0$ 时要加上 '1'），否则 ans += 系数。

最后解决次数，这里发现可以将外层循环改成 while (n --)，这样就可以每次拿 n 当次数（n 要先 + 1），如果 n > 1，那么让 ans 先加上 "x^" 再加上 to_string (n)，如果 n == 1，那么 ans += 'x'，最后如果 n == 0 则不做处理。

Code:

#include <bits/stdc++.h>
using namespace std;
string ans;
bool isp;
int n;

int main ()
{
	freopen ("poly.in", "r", stdin);
	freopen ("poly.out", "w", stdout);
    cin >> n; n ++;
    while (n --)
    {
        string s; cin >> s;
        int k = stoi (s);
        if (! k) continue;
        if (k < 0) ans += '-';
        if (isp && k > -1) ans += '+';
        if (abs (k) != 1) ans += to_string (abs (k));
        if (abs (k) == 1 && n == 0) ans += '1';
        if (n > 1) ans += "x^" + to_string (n);
        if (n == 1) ans += "x";
        isp = true;
    }
    cout << ans;
    return 0;
}

感受与学习：本题我知道了在做一道看起来十分复杂的题时，应该理清步骤，多打草稿，明确先干什么，再干什么。

错误原因：无。

---

#B.潜伏者

本题是一道十分简单的字符串处理题，需要用两个 map，一个是从密文映射到明文（sta），一个从明文映射到密文（os）。一开始将所有的映射表的值都设为 '@'，在循环的过程中如果发现当前明文已经对应了一个密文且对应的不是当前密文，那么直接输出 "Failed" 并结束程序，从密文到明文也同样处理。

循环完后将 $26$ 个字母遍历一遍，如果发现哪个字符没有在原文里出现过，那么直接输出 "Failed" 并结束，最后还没有结束说明符合条件可以输出。

Code:

#include <bits/stdc++.h>
using namespace std;
unordered_map <char, char> sta;
unordered_map <char, char> os;
string ori, now, pw;
int cnt;

int main ()
{
	freopen ("spy.in", "r", stdin);
	freopen ("spy.out", "w", stdout);
    cin >> ori >> now >> pw;
    for (int i = 0; i < ori.size (); i ++)
    {
        sta[ori[i]] = '@';
        os[ori[i]] = '@';
    }
    for (int i = 0; i < ori.size (); i ++)
    {
        if (sta[ori[i]] != '@' && sta[ori[i]] != now[i])
        {
            cout << "Failed";
            return 0;
        }
        if (os[now[i]] != '@' && os[now[i]] != ori[i])
        {
        	cout << "Failed";
        	return 0;
		}
        sta[ori[i]] = now[i];
        os[now[i]] = ori[i];
    }
    for (int i = int ('A'); i <= int ('Z'); i ++)
    	if (sta[char (i)] == '@')
    	{
    		cout << "Failed";
    		return 0;
		}
    for (int i = 0; i < pw.size (); i ++) cout << sta[pw[i]];
    return 0;
}

感受与学习：本题中我明白了在做模拟时要将所有可能都列出来并思考解决方法。

错误原因：只想到了一个原文对应两个密文，没有想到一个密文对应两个原文，思考方向不全面，做完这道题就匆匆忙忙去做下一道题了，并且也没有花足够的时间检查。

---

#C.细胞分裂

本题是一道偏数学的模拟，需要考虑如何才能使 $m_1^{m_2}$ 变为 $S_i^x$ 的倍数。

首先需要一个前置数学小芝士：

​ 如果 $x$ 拥有 $y$ 的全部质因数，我们将 $x$ 中的任意一个质因数 $p_i$ 在 $x$ 的因数中的个数记为 $f (x_{p_i})$。那么如果对于 $y$ 的所有质因数 $p'_i (i \in [2, y])$ 而言，如果所有 $f (x_{p'_i}) \ge f (y_{p'_i})$，说明 $y$ 的所有质因子在 $x$ 中的个数都比在 $y$ 中多或相等，那么 $x$ 即为 $y$ 的倍数。

所以对于这道题而言，我们需要统计最小的 $S_i$ 的变换次数 ans，我们只需一开始统计 $m_1^{m_2}$ 的质因子个数（记得每个质因子个数都要乘上 $m_2$）并用一个 k 表示每个 $S_i$ 变换的次数，然后每输入一个 $S_i$ 就用 $m_1^{m_2}$ 的所有质因子去除它并统计这些质因子在 $S_i$ 中出现的次数，如果每次 $m_1^{m_2}$ 的当前质因子个数大于等于在 $S_i$ 中出现的次数，那么就更新 k 为 k 和 向上取整 (当前质因子在m1^m2中出现的次数 / 当前质因子在s[i]中出现的次数)，向上取整的原因是因为……呃，举个例子吧，例如：

$$m_1^{m_2} = 12, S_i = 24 \to \\ \operatorname {GetDiviors (12)} = 2 \times 2 \times 3 \\ \operatorname {GetDiviors (24)} = 2 \times 2 \times 2 \times 3 \\ \lceil \frac{3}{2} \rceil \ = \ 2, \lceil \frac{1}{1} \rceil \ = \ 1$$

其中最大的个数是 $2$，如果不向上取整，那么就会判定为 $1$，可是 $12^1 = 12$，并不是 $24$ 的倍数，所以为避免误差，所以采用向上取整。

Code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
map <int, int> pms;
int n, m1, m2, ans = 2e9;

signed main ()
{
	freopen ("cell.in", "r", stdin);
	freopen ("cell.out", "w", stdout);
    cin >> n >> m1 >> m2;
    for (int i = 2; i <= m1 / i; i ++)
    {
        if (! (m1 % i))
        {
            int cnt = 0;
            while (! (m1 % i))
            {
                cnt ++;
                m1 /= i;
            }
            pms[i] = cnt * m2;
        }
    }
    if (m1 > 1) pms[m1] = m2;
    while (n --)
    {
    	int s; cin >> s;
    	int k = 0; bool l = true;
    	for (auto itr : pms)
    	{
    		int prm = itr.first, num = itr.second;
    		if (s % prm)
			{ l = false; break; }
    		int cnt = 0;
    		while (! (s % prm))
    		{
    			cnt ++;
    			s /= prm;
			}
			k = max (k, (int)(ceil (num * 1.0 / cnt)));
		}
		if (l) ans = min (ans, k);
	}
	cout << (ans == 2e9 ? -1 : ans);
    return 0;
}