2022 CCPC桂林

gym

A. Lily

标记’L’的两边不能填’C’，其他位置填’C’就行

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 1e6 + 10;

void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = '#' + s;
    int id = 0;
    map<int, int> mp;
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == 'L')
        {
            mp[i + 1] = 1;
            mp[i - 1] = 1;
            mp[i] = 1;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (mp[i])
            cout << s[i];
        else
            cout << 'C';
    }
}

M. Youth Finale

先求出初始逆序对，那么翻转操作后就是总对数减去当前逆序对。用idid来标记第一个位置，对于两个操作，都可以用id+opid+op来表示操作后第一个位置的下标，每次操作后可以修改一下opop为11或者−1-1，来表示正向的方向。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define int ll
const int N = 6e5 + 10;

int n;
int lowbit(int x)
{
    return x & (-x);
}
struct node
{
    int val, id;
    bool operator<(const node &t) const
    {
        if (val == t.val)
            return id > t.id;
        return val > t.val;
    }
} a[N];
int tr[N];
void add(int x, int y)
{
    for (; x <= n; x += lowbit(x))
        tr[x] += y;
}
int getsum(int x)
{
    int ans = 0;
    for (; x; x -= lowbit(x))
        ans += tr[x];
    return ans;
}
int p[N];
void solve()
{
    int m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].val;
        a[i].id = i;
        p[i - 1] = a[i].val;
    }
    ll ans = 0;
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++)
    {
        add(a[i].id, 1);
        ans += getsum(a[i].id - 1);
    }
    cout << ans << endl;

    int op = 1;
    int res = (n * (n - 1)) / 2;
    int id = 0;
    while (m--)
    {
        char c;
        cin >> c;
        if (c == 'S')
        {
            int now = p[id];
            ans = ans - (now - 1) + (n - now);
            id = (id + op + n) % n;
        }
        else
        {
            ans = res - ans;
            op = -op;
            id = (id + op + n) % n;
        }
        cout << ans % 10;
    }
}

C. Array Concatenation

只要一次操作取反，那么接下来的结果就都是等于复制了。而操作后正反次数都是n/2n/2，如果不取反，那么答案就是全是正次数。求出两种的贡献取较大值就可以了。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define int ll

const ll MOD = 1e9 + 7;
ll qpow(ll a, ll b)
{
	if (b <= 0)
		return 1;
	ll ret = 1;
	while (b)
	{
		if (b & 1)
		{
			ret = ret * a % MOD;
		}
		a = a * a % MOD;
		b >>= 1;
	}
	return ret % MOD;
}
void solve()
{
	ll n, m;
	cin >> n >> m;
	ll sum = 0;
	ll sumre = 0;
	ll sum2 = 0;
	for (ll i = 1; i <= n; i++)
	{
		ll x;
		cin >> x;
		sum = (sum + ((n - i + 1) * x % MOD)) % MOD;
		sum2 = (sum2 + (n * x % MOD)) % MOD;
		sumre = (sumre + (i * x % MOD)) % MOD;
	}
	ll pow1 = qpow(2, m - 1), pow2 = qpow(2, m);
	ll ans1 = (((pow2 - 1) * pow1) % MOD * sum2) % MOD; //所有正方形的和
	ll ans2 = (pow1 * (sumre + sum) % MOD) % MOD;		//一半倒置，一半正序
	ll ans3 = (sum * pow2) % MOD;						//都是正序
	ll ans = (ans3 + ans1) % MOD;
	ll anss = (ans2 + ans1) % MOD; //分开求再比大小
	cout << max(ans, anss);
}

E. Draw a triangle

我们设向量AB=(a,b)AB=(a,b)向量AC=(x,y)AC=(x,y)，那么三角形的面积就等于ay−bxay-bx的最小值，根据斐蜀定理可知，一个二元一次方程的解cc为形如ax+byax+by这样的式子中的a,ba,b的最大公因数的倍数，所以三角形面积的最小值就等于aa和−b-b的最大公因数， 然后我们可以通过扩展欧几里得算出向量AC的坐标，然后C的坐标就等于AC的坐标+A的坐标。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define int ll

ll exgcd(ll a, ll b, ll& gcd,ll& x, ll& y)
{//扩展欧几里得
	if (b == 0)
	{
		x = 1, y = 0;
		gcd = a;
	}
	else
	{
		ll g = exgcd(b, a % b, gcd, x, y);
		ll t = y;
		y = x - (a / b) * y;
		x = t;
	}	
	return 0;
}
void solve()
{
	int t;
	cin >> t;
	while (t--)
	{
		ll x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		if (x1 == x2)
		{
			cout << x1 + 1 << ' ' << 0 << endl;
			continue;
		}
		if (y1 == y2)
		{
			cout << 0 << ' ' << y1 + 1 << endl;
			continue;
		}
		ll x = x2 - x1, y = y2 - y1;
		ll x3, y3,gcd;
		exgcd(-y, x,gcd, x3, y3);
		cout << x3 + x1 << ' ' << y3 + y1 << endl;
	}
}

L. Largest Unique Wins

首先第一个人是全押最大的数，最优。然后第二个人，假如他选最大的数，那么他肯定不会让第一个赢。假如他选次大的数，那么他不能保证后来的人会选最大的数，从而让第一个人赢不了。这种情况第二个人可能会输；假如别人选和第二个人一样的数，第二个人也肯定不会赢。那么在选次大不会比选最大更优时，第二个人就会选择最大的数。后面的人就重复这个过程。

所以所有人的逻辑就是：自己不好赢， 那就让别人都别赢。那么就是，m,m,m−1,m−1,m−2........m,m,m-1,m-1,m-2........这样选下去。

nn为偶数可以完全抵消掉，没有人赢；奇数呢？不可避免最后一个人可能会赢，但是这样他相应赢的最少。这是其他人所能得到的最好结果了。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define int ll
const int N = 1e6 + 10;

void solve()
{
	int n, m;
	cin >> n >> m;
	int mm = m;
	vector<int> ans(m + 100, 1);
	for (int i = 1; i <= n; i += 2)
		ans[i] = ans[i + 1] = max(1ll, m--);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= mm; j++)
		{
			if (ans[i] == j)
				cout << 1 << " ";
			else
				cout << 0 << " ";
		}
		cout << endl;
	}
}

G. Group Homework

最大值要是是找两条不相交的链，要么是只有一个交点，也就是某个结点四条子链的和的最大值，两种情况取较大值就是答案。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define int ll
const int N = 2e5 + 10;

//维护每个点的四条前大的链，最大的四条链值为ans
int w[N];
vector<int> e[N];
int ans = 0;
int d[N];
struct ma
{
	int m1, m2, m3, m4;
} M[N];
void dff(int u, int fa, ll pre)
{
	for (auto v : e[u])
	{
		if (v == fa)
			continue;
		if (d[v] >= M[u].m1)
		{
			M[u] = {d[v], M[u].m1, M[u].m2, M[u].m3};
		}
		else if (d[v] >= M[u].m2)
		{
			M[u] = {M[u].m1, d[v], M[u].m2, M[u].m3};
		}
		else if (d[v] >= M[u].m3)
		{
			M[u] = {M[u].m1, M[u].m2, d[v], M[u].m3};
		}
		else if (d[v] > M[u].m4)
			M[u].m4 = d[v];
	}
	for (auto v : e[u])
	{
		if (v == fa)
			continue;
		if (d[v] == M[u].m1)
			dff(v, u, max(M[u].m2, pre) + w[u]);
		else
			dff(v, u, max(M[u].m1, pre) + w[u]);
	}
	ans = max(ans, max(pre, M[u].m4) + M[u].m3 + M[u].m2 + M[u].m1);
}

//查找树中不相交的两条路径和最大，为dp[1]
int dp[N], f[N], g[N];
void dfs(int u, int fa)
{
	dp[u] = f[u] = g[u] = d[u] = w[u];
	ll maxx = 0;
	for (auto v : e[u])
	{
		if (v == fa)
			continue;
		dfs(v, u);
		dp[u] = max({dp[u], dp[v], g[u] + d[v], f[u] + f[v], g[v] + d[u]});
		f[u] = max({f[u], f[v], d[v] + d[u]});
		g[u] = max({g[u], g[v] + w[u], d[v] + w[u] + maxx, d[u] + f[v]});
		d[u] = max(d[u], d[v] + w[u]);
		maxx = max(maxx, f[v]);
	}
}

void solve()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> w[i];
	for (int i = 1; i < n; i++)
	{
		int u, v;
		cin >> u >> v;
		e[u].push_back(v), e[v].push_back(u);
	}
	if (n == 1)
	{
		cout << 0 << endl;
		return;
	}
	dfs(1, 0);
	dff(1, 0, 0);
	cout << max(ans, dp[1]) << endl;
}

J. Permutation Puzzle

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'

//区间段按照右端点从小到大排序
struct node
{
    int l, r, id;
    bool operator<(const node &x) { return l < x.l; }
};

void solve()
{
    int n, m, k;
    cin >> n >> m;
    vector<int> e[n + 1], g[n + 1];
    vector<int> in1(n + 1, 0), in2(n + 1, 0), w(n + 1, 0);
    vector<node> a(n + 1);

    for (int i = 1; i <= n; i++)
    {
        cin >> w[i];
        if (w[i] != 0)
            a[i] = {w[i], w[i], i}; //初始化能选区间
        else
            a[i] = {1, n, i};
    }
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        in1[y]++; //正向建有向图
        g[y].push_back(x);
        in2[x]++; //反向建有向图
    }

    auto top1 = [&]()
    {
        queue<int> q;
        for (int i = 1; i <= n; i++)
            if (in1[i] == 0)
                q.push(i);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (auto v : e[u])
            {
                a[v].l = max(a[v].l, a[u].l + 1); //求最小，保留符合的中的最大值
                if (--in1[v] == 0)
                    q.push(v);
            }
        }
    };
    auto top2 = [&]()
    {
        queue<int> q;
        for (int i = 1; i <= n; i++)
            if (in2[i] == 0)
                q.push(i);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (auto v : g[u])
            {
                a[v].r = min(a[v].r, a[u].r - 1); //求最大，保留符合的中的最小值
                if (--in2[v] == 0)
                    q.push(v);
            }
        }
    };

    top1(); //正向拓扑找出约束最小值
    top2(); //逆序拓扑找出约束最大值
    for (int i = 1; i <= n; i++)
    {
        if (a[i].l > a[i].r)
        {
            cout << -1 << endl;
            return;
        }
    }

    //对于多个位置能选答案的区间，贪心选择右端点最小的，因为备选数从小到大枚举，右端点更大的一定比小的选择多
    sort(a.begin() + 1, a.begin() + 1 + n);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    vector<int> ans(n + 1, 0);
    for (int i = 1, j = 1; i <= n; i++)
    {
        //先把可能选择当前数的区间塞进去
        while (j <= n && a[j].l <= i)
            q.push({a[j].r, a[j].id}), j++;
        if (q.empty() || q.top().first < i)
        {
            cout << -1 << endl; //右端点最小的也无法满足，那么不存在答案
            return;
        }
        int x = q.top().second;
        q.pop();
        ans[x] = i;
    }
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    cout << endl;
}