ARC168

前言

输输输，只有 A、B、D 只有独立做出来了。C 想到了的 idea，但是指数是 6 次方级别的，没敢写。E 看出来了是 wqs 二分，但是找不到凸，F 根本不可做。麻了。

[ARC168A]

传送门 link

这种题放在 A 就别瞎想，简单问题简单解决，双指针扫一遍即可。

int n;
string s;
int ans;

signed main()
{
    cin >> n >> s;
    
    for (rint i = 0, j = 0; i < n - 1; i++)
	{
    	if (s[i] != '>') continue;
		j = max(i, j);
		bool flag = 0;
		while (s[j] == '>') j++, flag = 1;
		j -= flag;
		ans += j - i + 1;
	}
	
	cout << ans << endl;
	
	return 0;
}

[ARC168B] Arbitrary Nim

传送门 link

比较板子的一个 nim 博弈

先判一手有没有必胜策略，如果有，考虑如何维护答案。镜子影像思想，先将出现两次的数给消掉，通过模仿对方的行为消除这两堆。保证最大的一堆用两步消掉。对最大的一堆异或记录即可。

multiset<int> s;
int n, t;

signed main()
{
	cin >> n;
	
	for (rint i = 1; i <= n; i++)
	{
		int x;
		cin >> x;
		t ^= x;//判断是否有必胜策略
		if (s.find(x) != s.end()) s.erase(x);
		else s.insert(x);
	}
	
	if (t) cout << "-1" << endl;
	else 
	{
	    if(s.empty())
		{
			cout << "0" << endl;
			exit(0);
		} 	
		cout << *--s.end() - 1 << endl; 
	}
    
    return 0;
} 

[ARC168C] Swap Characters

传送门link

根本没想到换个角度解决问题。以为肯定可以 dp 或者能推出一个比较快的公式，打死也想不到正解。

正面解决根本不会，那么正难则反，已知一个目标字符串 \(T\)，求从原来的字符串 \(s\) 变换至 \(T\) 的最小操作数是多少

考虑枚举 \(a\rightarrow b,b\rightarrow a,a\rightarrow c,c\rightarrow a,b\rightarrow c,c\rightarrow b\) 的位置数，判断最小交换次数是否小于等于 \(k\)。但是这种复杂度是非常高的，显然过不去。

考虑另一种枚举方法，我们先枚举 \(a,b\) 之间，\(b,c\) 之间以及 \(a,c\) 之间的交换次数，每次交换对最小步数的贡献为 \(1\)，设它们为 \(A,B,C\)。则 \(a\rightarrow b,b\rightarrow a\) 的次数均为 \(A\)，\(a\rightarrow c,c\rightarrow a\) 的次数均为 \(C\)，\(b\rightarrow c,c\rightarrow b\) 的次数均为 \(B\)，再枚举全排列交换次数（显然每次交换对最小步数的贡献为 \(2\)），设为 \(D\)

那么 \(D\) 只可能被加到 \(a\rightarrow b,b\rightarrow c,c\rightarrow a\) 或者 \(a\rightarrow c,c \rightarrow b,b\rightarrow a\) 的次数里。剩下的情况都是这两种情况的其中一种的全排列。

所以直接枚举 \(A,B,C,D\)，再枚举 \(D\) 被加到前者的情况里还是后者的情况里，每次加进答案的贡献数就是组合数。复杂度 \(O(k^4)\)

const int N = 2.5e5 + 5;
const int mod = 998244353;

int n, k, cnt[3], ans;
int fac[N], inv[N], ifac[N];
int ab, ac, bc, ba, ca, cb;

int read() 
{
    int x = 0;
    char c = getchar(), f = 0;

    while (c < '0' || c > '9')
        f |= (c == '-'), c = getchar();

    while (c >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + (c & 15), c = getchar();

    return f ? -x : x;
}

int qpow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1) res = res * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return res;
}

void init()
{
    fac[0] = ifac[0] = 1;
    for (rint i = 1; i < N; i ++)
    {
        fac[i] = fac[i - 1] * i % mod;
        ifac[i] = ifac[i - 1] * qpow(i, mod - 2) % mod; 
    }	
}

int C(int a, int b)
{
	if (b < 0 || a < b) return 0;
	return fac[a] * ifac[a - b] % mod * ifac[b] % mod;
}

void update()
{
    ans = (ans + C(cnt[0], ab) * C(cnt[0] - ab, ac) % mod * C(cnt[1], ba) % mod * C(cnt[1] - ba, bc) % mod * C(cnt[2], ca) % mod * C(cnt[2] - ca, cb) % mod) % mod;
}

signed main() 
{
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	n = read();
	k = read();
    init();

    while (n--) cnt[getchar() - 'A']++;

    for (rint d = 0; d <= (k >> 1); d++)
      for (rint a = 0; a <= k - (d << 1); a++)
        for (rint b = 0; b <= k - (d << 1) - a; b++)
          for (rint c = 0; c <= k - (d << 1) - a - b; c++) 
			{
                ab = a;
				ac = b + d; 
				bc = c;
				ba = a + d;
				ca = b;
				cb = c + d;
				update();

                if (d)
                {
                    ab = a + d;
					ac = b; 
					bc = c + d;
					ba = a;
					ca = b + d; 
					cb = c; 
					update();						
				}
            }

    cout << ans << endl;
    
    return 0;
}

[ARC168D] Maximize Update

传送门link

要么是计数 dp，要么是区间 dp。第一眼想到的是 区间 dp

设 \(f_{i,j}\) 为把 \([i,j]\) 全部涂黑，其他为白的最多操作次数

\(f_{i,j}=\max\limits_{k=i}^{r-1}f_{i,k}+f_{k+1,r}\)

\(f_{i,j}=\max\limits_{k=i}^rf_{i,k-1}+f_{k+1,r}+ cost(l,r)\)

\(cost\) 表示区间内是否有覆盖该格子

然后前缀和处理一下就可以，剩下的板子。

复杂度 \(O(n^3)\)

bool cost(int l, int r, int k)
{
	return bool(s[k][r] - s[k][k - 1] - s[l - 1][r] + s[l - 1][k - 1]);
}

signed main()
{
	cin >> n >> m;
	
	for (rint i = 1; i <= m; i++)
	{
		int a, b;
		cin >> a >> b;
		s[a][b]++; 
	} 
	
	for (rint i = 1; i <= n; i++)
		for (rint j = 1; j <= n; j++)
			s[i][j] += s[i - 1][j];
			
	for (rint i = 1; i <= n; i++)
		for (rint j = 1; j <= n; j++)
			s[i][j] += s[i][j - 1];
	
	for (rint len = 1; len <= n; len++)
	{
		for (rint l = 1; l <= n; l++)
		{
			int r = l + len - 1;
			for (rint k = l; k < r; k++)
			{
				f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r]);
			}
			for (rint k = l; k <= r; k++)
			{
				f[l][r] = max(f[l][r], f[l][k - 1] + f[k + 1][r] + cost(l, r, k));
			}
		}		
	}

	cout << f[1][n] << endl;
	
	return 0;
}

[ARC168E] Subsegments

传送门link

先二分答案转为判定性问题。这时候问题就被转化为，在令答案为 \(x\) 的前提下，是否能够划分出 \(k\) 个连续段。

设 \(f_i\) 表示选出 \(i\) 段的最小代价，每一段的代价使用 \(r-l\) 来刻画

\(f_i\) 是求出恰好答案为 \(i\) 的方案数，这个函数是凸的。到了这一步就简单了。对 \(f\) 进行 wqs 二分。转移不选当前点，或选以当前点为右端点的代价最小的一个区间，从对应位置转移。

复杂度 \(O(n\log^2 n)\)

int n, k, S;
pair<int, int> f[N];
int p[N];
int a[N], s[N];

void F(int x) 
{
    for (rint i = 1; i <= n; i++) 
	{
        f[i] = f[i - 1];
        if (p[i])
        {
            f[i] = min(f[i], {f[p[i] - 1].x + (i - p[i]) - x, f[p[i] - 1].y + 1});			
		}
    }
}

bool check(int x) 
{
    int l = 1, r = n;
	int ans = 0;

    while (l <= r) 
	{
        int mid = (l + r) >> 1;
        F(mid);
        if (f[n].y <= x) l = mid + 1, ans = mid;
        else r = mid - 1;
    }
    F(ans);
    return f[n].x + ans * x <= n - k;
}

signed main() 
{
    cin >> n >> k >> S;

    for (rint i = 1; i <= n; i++)
    {
        cin >> a[i];
		s[i] = s[i - 1] + a[i];		
	}

    for (rint i = 1, j = 0; i <= n; i++) 
	{
        while (s[i] - s[j] >= S) j++;
        p[i] = j;
    }

    int l = 1, r = k;
    int ans = 0;

    while (l <= r) 
	{
        int mid = (l + r) >> 1;
        if (check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }

    cout << ans << endl;
    
	return 0;
}

[ARC168F] Up-Down Queries

传送门 link

不可做，根本不可做。看了题解代码也打不出来，写了一个小时直接弃了。

这道题的前置知识是省选联考2023人员调动。这种题留着，下辈子有机会一定补上。