Codeforces Round 1027 (Div. 3)

A. Square Year

题目大意：拆分完全平方数。

【解题】：如果是完全平方数输出0 + 平方根就行，不是就输出-1。

code:

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
typedef long long LL;
#define endl '\n'
void solve() 
{
    string s; cin >> s;
    int t = stoi(s);
    int sq = sqrt(t);
    if(sq * sq != t) cout << -1 << endl;
    else 
    {
        cout << 0 << " " << sq << endl;
    }
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
	cin >> T;
	while(T--)
	{
        solve();
	}
	return 0;
}

B. Not Quite a Palindromic String

题目大意：给定一个偶数长度的01序列s，如果si == sn - i+ 1，则称为一对好的索引，问我们能否通过重新调整顺序使得可以构造出一个正好为k对好索引的字符串呢。

【解题】：我们不难发现好索引对的下限minc是尽可能使01配对得来的；上限maxc是通过尽可能00 11 配对得来的。所以k只要在上下限之内就可以，但需要注意k是从下限每次变动两对得来的，因此还要满足k - minc是2的倍数。

code：

#include <iostream>
using namespace std;
typedef long long LL;
#define endl '\n'
void solve() 
{
    int n, k; cin >> n >> k;
    string s; cin >> s;
    int cnt1 = 0, cnt0 = 0;
    for(int i = 0; i < n; i++)
        if(s[i] == '1') cnt1++;
        else cnt0++;
    int minc = abs(cnt1 - cnt0) / 2;
    int maxc = cnt1 / 2 + cnt0 / 2;
    if(k >= minc && k <= maxc && (k - minc) % 2 == 0) cout << "YES" << endl;
    else cout << "NO" << endl;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
	cin >> T;
	while(T--)
	{
        solve();
	}
	return 0;
}

C. Need More Arrays

题目大意：给定非递减顺序排序数组a，我们对数组a进行一下操作：

• a1 被写入新数组；
• 如果是 a1+1<a2 ，那么 a2 将被写入一个新数组；否则 a2 将被写入与 a1 相同的数组；
• 如果是 a2+1<a3 ，那么 a3 会被写入到一个新数组中；否则， a3 会被写入到与 a2 相同的数组中；
• ...

现在我们可以提前从a中删除任意个数的元素，使得通过上述操作得到的数组数量最多。

【解题】：a是非递减排序的，我们首先考虑是否删除a[1]，可以达到最优解，很明显a[1]一定不可以删除，原因是：a[1]一定会形成一个新的数组，而a[2] >= a[1]，而在删除a[1]，的情况下指挥影响a[2]，这就导致了删除a[1]，一定会少形成一个新数组。

对于a[i]只会影响a[i + 1]，对于一个需要放到与前面元素同一个数组的a[i]来讲：不删可能导致a[i + 1]和a[i]都被放到了与a[i - 1]相同的集合内；删除可能会使a[i + 1] 与a[i - 1] 分开，而删除有对后面没影响。所以最有的贪心策略就是：对于需要放到与前一个元素同一个集合的元素我们就删掉。

code：

#include <iostream>
using namespace std;
typedef long long LL;
#define endl '\n'
void solve() 
{
    int n; cin >> n;
    int cnt = 1;
    int pre; cin >> pre;
    for(int i = 2; i <= n; i++)
    {
        int x; cin >> x;
        if(x - pre > 1) 
        {
            cnt++;
            pre = x;
        }
    }
    cout << cnt << endl;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
	cin >> T;
	while(T--)
	{
        solve();
	}
	return 0;
}

D. Kirei Attacks the Estate

题目大意：给定一个非常大的棋盘，棋盘内有许多怪兽，可以先移动一个怪兽的位置到任意空格置，随后我们需要选择一个矩形包含所有的怪兽，输出最小矩形的大小。

【解题】：不难发现：矩形的大小是由边界点决定的，所以我们以此尝试移动上下左右边界点，就行。但需要注意要是移动边界点没有位置放需要新开一行或一列。

code：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
#define endl '\n'

const int N = 2e5 + 10;
struct node
{
    LL x, y;
}a[N], b[N];
int n; 
bool cmp1(node& a, node& b)
{
    return a.x < b.x;
}

bool cmp2(node& a, node& b)
{
    return a.y < b.y;
}

LL calc()
{
    LL ans = 4e18;
    LL r = 0, l = 2e9, d = 2e9, u = 0;
    for(int i = 2; i <= n; i++)
    {
        LL x = a[i].x, y = a[i].y;
        l = min(l, x); r = max(r, x);
        d = min(y, d); u = max(u, y);
    }
    LL ret = (abs(r - l) + 1) * (abs(u - d) + 1);
    if(ret == n - 1) ret += min(abs(r - l) + 1, abs(u - d) + 1);
    ans = min(ans, ret);
    r = 0, l = 2e9, d = 2e9, u = 0;
    for(int i = 1; i <= n - 1; i++)
    {
        LL x = a[i].x, y = a[i].y;
        l = min(l, x); r = max(r, x);
        d = min(y, d); u = max(u, y);
    }  
    ret = (abs(r - l) + 1) * (abs(u - d) + 1);
    if(ret == n - 1) ret += min(abs(r - l) + 1, abs(u - d) + 1);
    ans = min(ans, ret);
    r = 0, l = 2e9, d = 2e9, u = 0;
    for(int i = 1; i <= n - 1; i++)
    {
        LL x = b[i].x, y = b[i].y;
        l = min(l, x); r = max(r, x);
        d = min(y, d); u = max(u, y);
    }  
    ret = (abs(r - l) + 1) * (abs(u - d) + 1);
    if(ret == n - 1) ret += min(abs(r - l) + 1, abs(u - d) + 1);
    ans = min(ans, ret);
    r = 0, l = 2e9, d = 2e9, u = 0;
    for(int i = 2; i <= n; i++)
    {
        LL x = b[i].x, y = b[i].y;
        l = min(l, x); r = max(r, x);
        d = min(y, d); u = max(u, y);
    }  
    ret = (abs(r - l) + 1) * (abs(u - d) + 1);
    if(ret == n - 1) ret += min(abs(r - l) + 1, abs(u - d) + 1);
    ans = min(ans, ret);    
    return ans;
}

void solve() 
{
    cin >> n;;

    for(int i = 1; i <= n; i++) 
    {
        cin >> a[i].x >> a[i].y;
        b[i].x = a[i].x;
        b[i].y = a[i].y;
    }
    if(n == 1)
    {
        cout << 1 << endl;
        return;
    }
    sort(a + 1, a + 1 + n, cmp1);
    sort(b + 1, b + 1 + n, cmp2);
    cout << calc() << endl;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
	cin >> T;
	while(T--)
	{
        solve();
	}
	return 0;
}

E. Kirei Attacks the Estate

题目大意：给定一棵树，每个节点有对应权值，要求我们输出每个节点的最大交替和。

节点交替和定义：以该节点为叶节点往上走，加上与该节点距离为偶数节点权值，减去距离为奇数节点权值（大家还是去看人家的定义把吧），这一系列和的最大值。

【解题】：其实我们可以做树上前缀和（交替和），要让该节点的交替和最大就要让它减去一个它前面最小的一个字段（类似于最大字段和）。但是要注意，如果该节点的层数为奇数，那么该节点在做前缀交替和的时候是减，而事实上是加，所有它的前面的值都应该是负的，我们还是常做前缀，输出的时候要输出该节点的前缀交替和减去一个它上面最大的一个前缀交替和的相反数。

code：

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL a[N];
vector<int> edg[N];
// pre_max - 该节点前面最大的前缀交替和
// pre_min - 该节点前面最小的前缀交替和
// sum - 根节点到该节点的前缀交替和
// dep - 该节点的深度
LL pre_max[N], pre_min[N], dep[N], sum[N];
void dfs(int child, int fa)
{
    dep[child] = dep[fa] + 1;
    if(dep[child] % 2) sum[child] = sum[fa] + a[child]; 
    else sum[child] = sum[fa] - a[child];
    pre_max[child] = max(sum[child], pre_max[fa]);
    pre_min[child] = min(sum[child], pre_min[fa]);
    for(auto v : edg[child])
    {
        if(v == fa) continue;
        else dfs(v, child);
    }
}

void solve()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i++) 
    {
        pre_max[i] = pre_min[i] = dep[i] = sum[i] = 0;
        edg[i].clear();
        cin >> a[i];
    }
    for(int i = 1; i < n; i++)
    {
        int x, y; cin >> x >> y;
        edg[x].push_back(y);
        edg[y].push_back(x);
    }
    dep[1] = 1;
    dfs(1, -1);
    for(int i = 1; i <= n; i++) 
    {
        // 奇数正常输出前缀减一个最小的
        if(dep[i] % 2) cout << sum[i] - pre_min[i] << " ";
        // 偶数输出前缀减一个最大的的相反数
        else cout << -(sum[i] - pre_max[i]) << " ";
    }
    cout << endl;
}

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

F. Small Operations

题目大意：给定三个数x，y，k。可以进行下列操作：

• 选一个a ，1 <= a <= k ，让x = x * a
• 选一个a ，1 <= a <= k 且 x % a = 0，让x = x / a

问最小的操作次数使得x = y，如果x 不能变成y输出-1

【解题】：其实不难想到，先把x变成gcd(x, y)，然后再从gcd(x, y) 变成y。

问题是怎么求x变成gcd(x, y)的最小次数，他俩之间的倍数是t，就是不断进行操作二，其实就是不断选取1-k的因数累乘凑出t的最少因数个数。这里题解使用dp做的，我cy下来了但不是很懂。

从gcd(x, y) 变成y其实也是凑倍数t，只不过进行的是操作一。

code：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
#define endl '\n'

LL gcd(LL a, LL b)
{
    return b == 0 ? a : gcd(b, a % b);
}

LL get_ans(LL x, LL k)
{
    if(x == 1) return 0;
    vector<int> fac;
    for(int i = 1; i * i <= x; i++)
    {
        if(x % i == 0) 
        {
            fac.push_back(i);
            if(x / i != i) fac.push_back(x / i);
        }
    }
    sort(fac.begin(), fac.end());
    int n = fac.size();
    vector<int> dp(n, 100);
    dp[0] = 0;
    for(int i = 1; i < n; i++)
    {
        for(int j = i - 1; j >= 0; j--)
        {
            if(fac[i] / fac[j] > k) break;
            else
            {
                if(fac[i] % fac[j] == 0) 
                    dp[i] = min(dp[i], dp[j] + 1);
            }
        }
    }
    return dp[n - 1] == 100 ? -1 : dp[n - 1];
}

void solve() 
{
    LL x, y, k; cin >> x >> y >> k;
    LL g = gcd(x, y);
    LL ans = 0;
    x = x / g;
    y = y / g;
    LL ax = get_ans(x, k);
    LL ay = get_ans(y, k);
    if(ax == -1 || ay == -1) cout << -1 << endl;
    else cout << ax + ay << endl;

}


int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
	cin >> T;
	while(T--)
	{
        solve();
	}
	return 0;
}