题目列表
- A.ABBA
- E.Elvis Presley
- G. Biological Software Utilities
- J. Burnished Security Updates
Solution其实就是求矩阵的秩，但是会被卡精度（被卡了好几发），直接抄个矩阵求秩的板子就AC了
Code
E.Elvis Presley题意：在形如二叉树的DAG上选出一个包含a，b的极大点集 ， 使这些点互不可达，且选的个数最少#define CLR(x) memset(x,0,sizeof(x))//定义宏using namespace std;double mat[300][300];//定义矩阵int r,c;int cmp(double x,double y){double v = x - y;if(v > 1e-1) return 1;//1e-1表示10^-1if(v < -1e-1) return -1;return 0;}//乘相应值void subrow(int r1 , int r2,double temp){for(int i = 1 ; i <= c ; i++){mat[r1][i] -= mat[r2][i]*temp;}}//交换数值void swaprow(int r1 , int r2){for(int i = 1 ; i <= c ; i++){swap(mat[r1][i],mat[r2][i]);}}//判断秩（主要判定函数）void solve() {for (int i = 1; i <= r; i++) {for (int cal = i; cal <= c; cal++) { //对这 i 行的每一列来找，要是这列本身和之下的列全是0，则找 i 行下一列 。bool flag = true;if (cmp(mat[i][cal], 0) == 0) {flag = false;//如果第 i 行 cal 列这个位置是 0 ，那找找这列下面的行有没有for (int j = i + 1; j <= r; j++) {//一个不为 0 的数 , 要是有，就将它与 i 行交换 。int tmp = cmp(mat[j][cal], 0);if (tmp == 1 || tmp == -1) {flag = true;swaprow(j, i);break;}}}if (!flag) continue;//如果这列全是 0，到下一列 。int v = i;//如果发现这列有值不为 0 并把它跟 i 行交换后，int maxn = mat[i][cal];//就再找这列有没有比 i 行 这个位置的值更大的值，如果有 ， 将那一行for (int j = i + 1; j <= r; j++) {//跟i行交换 。（听说是为了减小误差）if (cmp(mat[j][cal], mat[i][cal]) == 1) {v = j;maxn = mat[j][cal];}}if (v != i) {swaprow(i, v);}for (int j = 1; j <= r; j++) {if (j == i) continue;if (cmp(mat[i][cal], 0) == 0) continue;double tmp = mat[j][cal] / mat[i][cal];subrow(j, i, tmp);}break;}}}int main() {CLR(mat);scanf("%d %d", &r, &c);for (int i = 1; i <= r; i++) {for (int j = 1; j <= c; j++) {scanf("%lf", &mat[i][j]);}}solve();bool f = false;int ans = 0;for (int i = r; i >= 1; i--) {for (int j = 1; j <= c; j++) {int tmp = cmp(mat[i][j], 0);if (tmp == 1 || tmp == -1) {f = true;break;}}if (f) {ans = i;break;}}printf("%d\n", ans);//输出秩return 0;}Solution阅读理解题
Code
G.Green Day题意：略int main() {int a, b;cin >> a >> b;if (a > b) swap(a, b);if (a == 1) {cout << -1;return 0;}set stt;int now = a;while (now) {stt.insert(now);now /= 2;}now = b;int lca;while (now) {if (stt.find(now) != stt.end()) {if (now == a) {cout << -1;return 0;}lca = now;break;}now /= 2;}now = b;vector ans;while (now / 2 != lca) {if (now % 2) ans.push_back(now / 2 * 2);else ans.push_back(now / 2 * 2 + 1);now /= 2;}now = a;while (now / 2 != lca) {if (now % 2) ans.push_back(now / 2 * 2);else ans.push_back(now / 2 * 2 + 1);now /= 2;}now = lca;while (now != 1) {if (now % 2) ans.push_back(now / 2 * 2);else ans.push_back(now / 2 * 2 + 1);now /= 2;}ans.push_back(a), ans.push_back(b);sort(ans.begin(), ans.end());for (int i: ans)cout << i << " ";}Solution题解：仿样例，凑出来的，神奇的AC姿势
Code
J. Burnished Security Updates题意：给定一棵边权为小写字母的树和一个目标串$S$ , 问是否存在一条简单路径，使S成为该路径构成的字符串的子序列 。若存在，输出任何一条合法路径的两个端点$($先起点，后终点$)$ ， 否则输出-1 -1 。void solve() {int k;cin >> k;cout<< 2*k << endl;for (int i = 1; i <= k; ++i) {for (int j = 1; j <= k; ++j) {cout << i << " " << i + j<< endl;}for (int j = k+1 ; j <= 2 * k-1 ; ++j) {cout << i + k << " " << (i + j-1)%(2*k)+1 << endl;}}}Solution思路:? 树形dp维护以某个节点为根的子树中，以根为路径的一个端点，可以在$S$ 中匹配的最长前缀和后缀 。当某棵子树的前后缀已经覆盖了$S$，并且前后缀的路径不重复，就是合法路径 。保证不重复的方法详见代码 。
Code
int n, m, idx;string s;int head[maxn];pii st[maxn], ed[maxn], ans;struct Edge {int to, nxt; char c;} edge[maxn * 2];void addedge(int u, int v, char c) {edge[idx] = {v, head[u], c};head[u] = idx ++;edge[idx] = {u, head[v], c};head[v] = idx ++;}void dfs(int u, int fa) {st[u] = ed[u] = {0, u};for(int i = head[u]; ~i; i = edge[i].nxt) {int v = edge[i].to; char c = edge[i].c;if(v == fa) continue;dfs(v, u);if(c == s[st[v].x + 1] && st[v].x < m) st[v].x ++;if(c == s[m - ed[v].x] && ed[v].x < m) ed[v].x ++;// 路径不重复if(st[u].x + ed[v].x >= m) ans = {st[u].y, ed[v].y};if(ed[u].x + st[v].x >= m) ans = {st[v].y, ed[u].y};st[u] = max(st[u], st[v]);ed[u] = max(ed[u], ed[v]);}}int main() {ios;cin >> n >> m;for(int i = 1; i <= n; i ++) head[i] = -1;for(int i = 1; i < n; i ++) {int u, v; char c;cin >> u >> v >> c;addedge(u, v, c);}cin >> s;s = "?" + s;ans = {-1, -1};dfs(1, 0);cout << ans.x << " " << ans.y;}
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
