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^-1
if(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
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。
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;
}
标签：
留言评论