【LYOI】LYOI2020 Summer Competition1题解&命题总结

AK这场比赛？真的有手就行！

---

烦人的二元组

题目链接：Link

分析

题目大意即给你一个只由 pair 与 int 组成的字符串，问是否可以组成类似于 pair<__ , __> 的形式。其中 __ 可以是 int 或合法的 pair<__ , __>。

因为需要在原字符串的基础上进行拼接，使用 string 存储答案串。

将原串分为一个个由空格隔开的字符串，依次读入。

如果读入的是pair，则在答案串基础上拼接pair<，并再次递归读入后面的两个元素。

若为int，则直接拼接int。

最后多进行一次读入，确保最后没有多余字符即可。

注意：单独一个 int 也是可以通过编译的

剩下的就是代码实现的问题了。

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define ll long long
#define pb push_back
#define MP make_pair
#define ull unsigned long long
#define PII pair<int , int>
#define PIL pair<int , long long>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 998244353;
const int INF = 2147483647;
const long long INFL = 9223372036854775807;

#define LOCAL

bool flag = 1;
string s , ans;

void input(){
	if (cin >> s){
		if (s == "pair"){
			ans += "pair<";
			input();
			ans += ",";
			input();
			ans += ">";
		}
		else if (s == "int") ans += "int";
        else flag = 0;
	}
}

int main(){
    #ifdef LOCAL
        freopen("pair.in" , "r" , stdin);
        freopen("pair.out" , "w" , stdout);
    #endif
	input();
	if (!flag) ans = "Compile Error"; 
	getline(cin, s);
	if (s.size()) ans = "Compile Error";
	cout << ans << endl;
    
    return 0;
}

---

不确定的括号序列

题目链接：Link

分析

题目大意即给你由 ( , ) , ? 组成的字符串，每一个 ? 被换成左右括号分别要花费不同价值，问最少花费多少使得所有 ? 均被换掉且该括号序列匹配。

70pts

考虑$\text{dp}$。

设 $f[i][j]$ 表示考虑字符串的前 $i$ 位，前面有 $j$ 个左括号未经匹配的最小花费。显然，答案就是 $f[len][0]$。

之后考虑转移，转移时可以枚举每个 ? 是被替换成左括号还是右括号，即

$$f[i][j] = \min\{f[i - 1][j - 1] + a_i , f[i - 1][j + 1] + b_i\}$$

时间复杂度为 $O(n^2)$，可以得到 $70$ 分的好成绩。

---

100pts

满分做法是个不太好想的贪心。

考虑判断一个括号序列是否合法的方法：对于一个只含有 ( , ) 的括号序列，判断其是否合法的方式是将(全部换成$1$，)全部换成$−1$，对其做一遍前缀和。

若前缀和数组的每一个元素均大于等于$0$且最后一个元素为$0$，则该序列合法。

可以看出，如果不考虑最后一个元素为 $0$ 的条件，则这个括号序列可以全为(。

换句话说，中间的)是不合法的关键。

因此我们先将所有的?均换为)。之后对其进行修正。

对于一个没有匹配的)，考虑将其本身或其之前没有被换掉的位置换为(。对此，我们贪心的选择花费最小的一个换掉，使用优先队列维护即可。

若无法找到能够替换的位置或最后左右括号数目不等则无解，输出-1即可。

时间复杂度为 $O(n \log n)$，足以通过本题

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
 
#define I inline
#define ll long long
#define pb push_back
#define MP make_pair
#define ull unsigned long long
#define PII pair<int , int>
#define PIL pair<int , long long>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clear(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
 
using namespace std;
 
const int N = 10001;
const int M = 100001;
const int HA = 998244353;
const int INF = 2147483647;
const long long INFL = 9223372036854775807;
 
#define LOCAL

struct Node{
    int val , pla;
    bool operator < (const Node &b) const {
        return val < b.val;
    }
}node[M];
 
ll cnt , ans;
char s[M << 2];
 
priority_queue<Node> Q;
 
int main() {
    #ifdef LOCAL
        freopen("bracket.in" , "r" , stdin);
        freopen("bracket.out" , "w" , stdout);
    #endif
    scanf("%s" , s);
    int l = 0 , r = 0;
    rep(i , 0 , strlen(s) - 1){
        if(s[i] == '(') l ++;
        else{
            r ++;
            if(s[i] == '?'){
                int a , b;
                scanf("%d%d" , &a , &b);
                ans += b;
                node[++ cnt].val = b - a;
                node[cnt].pla = i;
                Q.push(node[cnt]);
            }
        }
        if(r > l){
            if(Q.empty()) break;
            Node fro = Q.top(); Q.pop();
            ans -= fro.val;
            l ++; r --;
        }
    }
    if(l == r) printf("%lld\n" , ans);
    else puts("-1");
 
    return 0;
}

---

动人的小情歌

题目链接：Link

分析

题目大意即定义一个字符串是好的，当且仅当该字符串仅由 A,B,C 三种字符构成，且没有连续的 $3$ 个 A 或 $2$ 个 B。

多次询问长度为 $n$ 的好的字符串个数。

70pts

考虑一个个的把字母加到字符串的最后的过程。

设 $f[i][0/1/2][0/1]$ 表示字符串前 $i$ 位，末尾有连续 $0/1/2$ 个 A，有 $0/1$ 个 B 的方案数。

显然，答案为：

$$f[n][0][0] + f[i][1][0] + f[i][2][0] + f[i][0][1]$$

之后考虑转移，可以推出以下式子：

$$f[i][0][0]= f[i−1][0][0]+ f[i−1][1][0]+ f[i−1][2][0]+f[i−1][0][1]$$ $$f[i][0][1] = f[i−1][0][0] + f[i−1][1][0] + f[i−1][2][0]$$ $$f[i][1][0] = f[i−1][0][0] + f[i−1][0][1]$$ $$f[i][2][0] = f[i−1][1][0]$$

大力转移即可。

时间复杂度$O(n)$，面对$10^{18}$的数据显得无能为力，但还是能拿到 $n \leq 10^5$ 的 $70$ 分

---

100pts

考虑如何优化上面的$\text{dp}$。

矩阵乘法！

将定义的状态化为矩阵，即

$$\begin{matrix} f_{i , 0 , 0} & f_{i , 1 , 0} & f_{i , 2 , 0} & f_{i , 0 , 1} \end{matrix}$$

该矩阵由以下矩阵转移而来

$$\begin{matrix} f_{i-1 , 0 , 0} & f_{i-1 , 1 , 0} & f_{i-1 , 2 , 0} & f_{i-1 , 0 , 1} \end{matrix}$$

即

$$\begin{matrix} f_{i , 0 , 0} & f_{i , 1 , 0} & f_{i , 2 , 0} & f_{i , 0 , 1} \\ \end{matrix} = \begin{matrix} f_{i-1 , 0 , 0} & f_{i-1 , 1 , 0} & f_{i-1 , 2 , 0} & f_{i-1 , 0 , 1} \\ \end{matrix} \times Base$$

其中 $Base$ 为转移矩阵。

根据上面推出的式子，可得出

$$Base = \begin{matrix} 1 & 1 & 0 & 1\\ 1 & 0 & 1 & 1\\ 1 & 0 & 0 & 1\\ 1 & 1 & 0 & 0\\ \end{matrix}$$

写一个矩阵快速幂即可

单次询问时间复杂度为$𝑂(𝑙^3 \log ⁡𝑛)$，其中 $𝑙$ 为转移矩阵的边长，本题中$𝑙 = 4$，足以通过 $10^{18}$ 的大数据。

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define db double
#define ll long long
#define pb push_back
#define MP make_pair
#define ldb long double
#define ull unsigned long long
#define PII pair<int , int>
#define PIL pair<int , long long>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 998244353;
const int INF = 2047483647;
const long long INFL = 9023372036854775807;

struct Matrix {
	ll data[10][10];
};

Matrix operator * (const Matrix &A , const Matrix &B){
    Matrix C; clean(C.data , 0);
    rep(i , 1 , 4){
        rep(j , 1 , 4){
            rep(k , 1 , 4){
                C.data[i][j] += A.data[i][k] * B.data[k][j] % HA;
                C.data[i][j] %= HA;
            }
        }
    }
    return C;
}

Matrix Pow(Matrix A , Matrix B , ll k){
    while(k){
        if(k & 1){
            A = A * B;
        }
        B = B * B;
        k >>= 1;
    }
    return A;
}

#define LOCAL 

int main() {
    #ifdef LOCAL
        freopen("music.in" , "r" , stdin);
        freopen("music.out" , "w" , stdout);
    #endif
	ll t , n; scanf("%lld" , &t);
    while(t --){
		scanf("%lld" , &n);
		Matrix A , B; clean(A.data , 0); clean(B.data , 0);
		B.data[1][1] = B.data[1][2] = B.data[1][4] = B.data[2][1] = B.data[2][3] = B.data[2][4] = B.data[3][1] = B.data[3][4] = B.data[4][1] = B.data[4][2] = 1;
		A.data[1][1] = A.data[1][2] = A.data[1][4] = 1;
		A = Pow(A , B , n - 1);
		printf("%lld\n" , (A.data[1][1] + A.data[1][2] + A.data[1][3] + A.data[1][4]) % HA);
	}

    return 0;
}

---

命题总结

这次的题目的满分做法分别是模拟，贪心，数学。且后两题对同学们的思维要求较大。

但与之相对的是非完美的 $\text{dp}$ 也能拿到不错的分数，且第三题的正解是在 $\text{dp}$ 的基础上进行优化，对正解有极强的启发作用。

因此，这次的题目在提高组的要求难度之内。

想要备战明年省选的同学们需要拿到 $240$ 分以上，以省一为目标的同学也需要拿到至少 $180$ 分。

同时，有同学因为理解错题意而导致错误。在这里作者要强调：理解与简化题意也是很重要的一项技能，需要多加练习。

请各位同学认真订正并仔细反思。

---

Easter Egg

1. 题目中的名字是真实存在的
2. 第三题稍微玩了一下白学梗，但没那么明显(打过WA2的同学应该能看出来)

---

THE END