看完题目大意,先思考,再看解析;觉得题目大意不清晰,点击题目链接看原文。
题目链接 题目大意:n个点,坐标x[i]从小到大,每个点可以选择Left或者Right的方向前进,速度v=1,求相遇的时间。 代码实现:
int right = -1;
for (int i = 0; i < n; ++i) {
if (str[i] == 'R') {
right = i;
}
else {
if (right != -1 && a[i] != a[right]) {
if (ret == -1) {
ret = (a[i] - a[right]) / 2;
}
else {
ret = min(ret, (a[i] - a[right]) / 2);
}
}
}
}
题目解析: 对于点i,有两种碰撞情况: 1、方向是L,遇到左边的点方向是R; 2、方向是R,遇到右边的店方向是L; 假设点i和点j是碰撞的点,那么点i的情况1就是点j的情况2; 那么对于点i只考虑左边的点即可; 题目变成:对于每个点,求左边最近的方向为R 的点。
题目链接 题目大意:n*m的棋盘上有若干点,找一个点横竖能覆盖所有点。
代码实现:
// 假设符合的点
for (int i = 0; i < n && OK; ++i) {
for (int j = 0; j < m && OK; ++j) {
Node tmp;
tmp.x = i;
tmp.y = j;
nodes.insert(tmp);
}
}
// 检查假设的点
for (int i = 0; i < n && OK; ++i) {
for (int j = 0; j < m && OK; ++j) {
if (str[i][j] == '*') {
set<Node>::iterator it = nodes.begin();
while (it != nodes.end()) {
if (it->x == i || it->y == j) {
++it;
}
else {
nodes.erase(it++);
}
}
if (nodes.size() == 0) {
OK = 0;
}
}
}
}
题目解析: 假设所有点符合,用set来存放所有的点,每遇到一个点,把不符合的去掉; 时间复杂度为O(NM*LogN),复杂度的关键在于set的构建。
代码实现:
for(i=0;i<n;i++){
for(j=0;j<m;j++){
cin>>c[i][j];
if(c[i][j]=='*'){
k++;
a[i]++;
b[j]++;
}
}
}
for(i=0;i<n;i++){
for(j=0;j<m;j++) {
s=a[i]+b[j];
if(c[i][j]=='*'){
s--;
}
if(s==k) {
cout<<"YES"<<endl<<i+1<<" "<<j+1;
return 0;
}
}
}
题目解析: 假设某一点符合,求这一个点覆盖的点数是否包括其他所有需要覆盖的点; 事先统计每行每列对应的点数,求点覆盖点数时通过每行每列的值可以较快计算出来。 时间复杂度为O(NM)。
题目链接 题目大意:有n天,每天有四种可能,如下。问最少能休息几天。 1、on this day the gym is closed and the contest is not carried out; 2、on this day the gym is closed and the contest is carried out; 3、on this day the gym is open and the contest is not carried out; 4、on this day the gym is open and the contest is carried out. 不能连续两天比赛,也不能连续两天锻炼。
代码实现:
for (int i = 1; i <= n; ++i) {
int k;
cin >> k;
d[i][0] = min(min(d[i - 1][0] + 1, d[i - 1][1] + 1), d[i - 1][2] + 1);
if (k == 0) {
d[i][1] = d[i][2] = N;
}
if (k == 1) { // can to contest
d[i][1] = min(d[i - 1][2], d[i - 1][0]);
d[i][2] = N;
}
if (k == 2) { // can to gym
d[i][1] = N;
d[i][2] = min(d[i - 1][1], d[i - 1][0]);
}
if (k == 3) {
d[i][1] = min(d[i - 1][2], d[i - 1][0]);
d[i][2] = min(d[i - 1][1], d[i - 1][0]);
}
}
cout << min(min(d[n][0], d[n][1]), d[n][2]) << endl;
题目解析: 典型的动态规划。 d[i][j]表示第i天,状态为j时的最小休息天数。 j = 0表示都不去; j = 1表示去contest; j = 2表示去gym;
这样j = 0可以由前面三种状态转换过来; j = 1只能由0和2转换; j = 2只能由1和2转换;
然后动态规划一遍得最优解。
题目链接 题目大意:n个点,每个点对应的a[i]表示第i个点的parent节点,问使其变成一棵树,最少需要修改多少条边,并且把所有值输出。 代码实现:
lld find(lld x) {
lld ret = f[x];
if (ret != x) {
ret = find(ret);
}
return f[x] = ret;
}
int main() {
for (int i = 1; i <= n; ++i) {
if (i != root) {
lld x = find(i);
lld y = find(a[i]);
if (x == y) {
++ans;
if (!root) {
root = x;
}
a[i] = root;
}
else {
f[x] = f[y];
}
}
}
}
题目解析: n个点,n条边。如果是树必然是一条边指向自己,其余n-1条边没有环。(有且仅有一个环) 那么假设有一个根节点root,当出现环的时候,直接将环某个点指向root即可; 需要修改的数量=环的数量 - 1。
两个关键词:动态规划(C题)、并查集(D题)。