Petrozavodsk Winter Training Camp 2016: Moscow SU Trinity Contest _生活百科

题目列表

A.ABBA
E.Elvis Presley
G. Biological Software Utilities
J. Burnished Security Updates

A.ABBA题意：就是问你一个矩阵能由几个行向量表示出来

Solution其实就是求矩阵的秩，但是会被卡精度（被卡了好几发），直接抄个矩阵求秩的板子就AC了

Code

#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;}

E.Elvis Presley题意：在形如二叉树的DAG上选出一个包含a，b的极大点集，使这些点互不可达，且选的个数最少

Solution阅读理解题

Code

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 << " ";}

G.Green Day题意：略

Solution题解：仿样例，凑出来的，神奇的AC姿势

Code【Petrozavodsk Winter Training Camp 2016: Moscow SU Trinity Contest】

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;}}}

J. Burnished Security Updates题意：给定一棵边权为小写字母的树和一个目标串$S$ , 问是否存在一条简单路径，使S成为该路径构成的字符串的子序列。若存在，输出任何一条合法路径的两个端点$($先起点，后终点$)$，否则输出-1 -1 。