【CodeForces-400D】Dima and Bacteria【Disjoint Set + Floyd Warshall Algorithm】

【CodeForces-400D】Dima and Bacteria【Disjoint Set + Floyd Warshall Algorithm】

代码:

#include <iostream>
#include <vector>

using namespace std;
typedef long long LL;
struct Edge {
    int to, w;
};
const int NLIM = 1e5 + 10;
const int SLIM = 500 + 10;
const int INF = 0xfffffff;
vector<Edge> adjOfNode[NLIM];
int parent[NLIM];
int ns[NLIM];       /* Node Set */
int c[SLIM];
int adjOfSet[SLIM][SLIM];

inline int mini(int a, int b) {return a < b ? a : b;}

int Find(int x) {
    if (parent[x] != x) parent[x] = Find(parent[x]);
    return parent[x];
}

void Union(int x, int y) {
    int nx = Find(x);
    int ny = Find(y);
    if (nx != ny) parent[nx] = parent[ny];
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < k; i++) {
        cin >> c[i];
        if (i) c[i] += c[i - 1];
    }
    for (int i = 0; i < k; i++) {
        int crt = i ? c[i - 1] + 1 : 1;
        while (crt <= c[i]) {
            // save each node belong to which set
            ns[crt] = i;
            // init parent array
            parent[crt] = crt;
            crt++;
        }
    }
    // init adjOfSet
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            adjOfSet[i][j] = INF;
        }
    }
    // load the adjacent list and matrix
    int u, v;
    Edge tmp;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> tmp.w;
        tmp.to = v;
        adjOfNode[u].push_back(tmp);
        tmp.to = u;
        adjOfNode[v].push_back(tmp);
        // cout << u << " " << v << " " << ns[u] << " " << ns[v] << " " << tmp.w << endl;
        adjOfSet[ns[u]][ns[v]] = mini(adjOfSet[ns[u]][ns[v]], tmp.w);
        adjOfSet[ns[v]][ns[u]] = mini(adjOfSet[ns[v]][ns[u]], tmp.w);
    }
    // use union-find set to check validity
    bool flag = true;
    for (int i = 0; i < k; i++) {
        int crt = i ? c[i - 1] + 1 : 1;
        if (c[i] == crt) {
            adjOfSet[ns[crt]][ns[crt]] = 0;
        }
        while (crt <= c[i]) {
            for (int j = 0; j < adjOfNode[crt].size(); j++) {
                if (adjOfNode[crt][j].w == 0)
                    Union(crt, adjOfNode[crt][j].to);
            }
            crt++;
        }
        crt = i ? c[i - 1] + 1 : 1;
        int pre = Find(crt++);
        for (; crt <= c[i]; crt++) {
            if (Find(crt) != pre) break;
        }
        if (crt <= c[i]) {
            flag = false;
            break;
        }
    }
    if (flag) {
        // for (int i = 0; i < k; i++) {
        //     for (int j = 0; j < k; j++) {
        //         if (j) cout << ' ';
        //         cout << adjOfSet[i][j];
        //     }
        //     cout << endl;
        // }
        cout << "Yes\n";
        // run the FloydDP
        for (int r = 0; r < k; r++) {
            for (int i = 0; i < k; i++) {
                for (int j = 0; j < k; j++) {
                    adjOfSet[i][j] = mini(adjOfSet[i][j], adjOfSet[i][r] + adjOfSet[r][j]);
                }
            }
        }
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++) {
                if (j) cout << " ";
                cout << (adjOfSet[i][j] == INF ? -1 : adjOfSet[i][j]);
            }
            cout << "\n";
        }
    } else {
        cout << "No\n";
    }
    return 0;
}

 

【CodeForces-816A】Karen and Morning【进制+暴力+栈】

【CodeForces-816A】Karen and Morning【进制+暴力+栈】

问题链接:https://vjudge.net/problem/CodeForces-816A

题目描述:

Karen is getting ready for a new school day!

It is currently hh:mm, given in a 24-hour format. As you know, Karen loves palindromes, and she believes that it is good luck to wake up when the time is a palindrome.

What is the minimum number of minutes she should sleep, such that, when she wakes up, the time is a palindrome?

Remember that a palindrome is a string that reads the same forwards and backwards. For instance, 05:39 is not a palindrome, because 05:39 backwards is 93:50. On the other hand, 05:50 is a palindrome, because 05:50 backwards is 05:50.

Input:

The first and only line of input contains a single string in the format hh:mm (00 ≤ hh  ≤ 2300 ≤  mm  ≤ 59).

Output:

Output a single integer on a line by itself, the minimum number of minutes she should sleep, such that, when she wakes up, the time is a palindrome.

 

Solution:

这道题十分有趣。Karen认为在“回文时间”起床十分幸运,于是,程序要求,对于给出的她要睡觉的时间,找到这个时间距离最近的“回文(Palindrome)时间”间隔多少分钟。【解释:这题所谓“回文时间”,如05:50,它是回文的。而如05:23,它不是回文的,即两边数值是不对称的】

第一点:关于时间(年月日时)的处理十分常见,时间可以看成一种特殊的进制,在这里,我们可以注意到,分钟数是以60为进制的,每60分钟,就可以进位1到小时位上。反过来,1小时就相当于60分钟,那么我们可以把每一时刻都转化到唯一的分钟数上,如05:50就等于5 * 60 + 50 = 350分钟。

第二点:暴力(Brute Force)。暴力枚举在数据范围很小的情况下通常是一种很好的解决方案,这道题注意到时间的取值范围是00:00 ~ 23:59,按照“第一点”所提的方法,这里可以转化为24 * 60 + 0个不同的分钟数,直接尝试每个分钟数所对应的时间是否构成“回文时间”就好。

第三点:用栈判断回文。栈是一种很常用的数据结构,可以想象它是一个衣柜,每次我们只能把新的衣服放到最顶部,而取衣服的时候也只能从最顶部取。考虑时间05:50,我们先处理小时部分,即05,我们把个位的5先放入栈中,再把十位的0压入栈中,如下图。

接着,我们考虑分钟部分的50,我们依然先考虑它的个位(即0),我们将这个与上图栈顶的数比较,发现0 = 0,很好,二者一样;于是我们将这个栈顶的0扔掉,接着我们用十位(即5)比较现在的栈顶(刚刚栈顶的0扔出去了,于是现在的栈顶是5),发现5 = 5,很好,又一样,因此我们的任务完成了,发现这个就是“回文时间”。

我们发现,这里使用栈这种数据结构,为我们提供了逆序,因为我们知道,如果这个串是回文的,它的两边一定是对称的,那么我们如果把一边的顺序颠倒一下,二者就应该完全一样了,如果发现不一样,就说明不是回文。

#include <stdio.h>

int stack[2];
int isPalindrome(int h, int m) {
    int pos = 0;
    int cx = 2;
    while (cx--) {
        stack[pos++] = h % 10;
        h /= 10;
    }
    while(pos--) {
        if (stack[pos] != m % 10) return 0;
        m /= 10;
    }
    return 1;
}

int main(void) {
    int h, m;
    int lim = 24 * 60;
    scanf("%d:%d", &h, &m);
    for (int cnt = h * 60 + m; true; cnt++) {
        if (cnt >= lim) cnt %= lim;
        if (isPalindrome(cnt / 60, cnt % 60)) {
            printf("%d\n", ((cnt - h * 60 - m) % lim + lim) % lim);
            break;
        }
    }
    return 0;
}

 

【CodeForces-812C】Sagheer and Nubian Market【二分】

【CodeForces-812C】Sagheer and Nubian Market【二分】

Solution:

二分数量。按照下面的解决方案需要注意sum可能会爆掉,但是根据合法数据的s,是不会爆掉的,所以只要爆整数范围就认为当前试验的数量太多了,直接进入左区间。

每次需要排序,故复杂度O(nlognlogn).

代码:

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;
int w;
struct Node {
    int val, id;
    bool operator < (const Node & n) const {
        return val + id * w < n.val + n.id * w;
    }
};

const int LIM = 1e5 + 10;
Node dat[LIM];

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    LL s;
    cin >> n >> s;
    for (int i = 0; i < n; i++) {
        cin >> dat[i].val;
        dat[i].id = i + 1;
    }
    int l = 0, r = n;
    int mid;
    LL sum;
    while (l + 1 < r) {
        mid = (l + r) >> 1;
        w = mid;
        sort(dat, dat + n);
        sum = 0;
        for (int i = 0; i < mid && sum >= 0; i++)
            sum += dat[i].val + dat[i].id * mid;
        // cout << mid << ": " << sum << endl;
        if (sum >= s || sum < 0) r = mid;
        else l = mid;
    }
    w = l;
    sort(dat, dat + n);
    LL ansa = 0;
    for (int i = 0; i < l; i++)
        ansa += dat[i].val + dat[i].id * l;
    w = r;
    sort(dat, dat + n);
    LL ansb = 0;
    for (int i = 0; i < r; i++)
        ansb += dat[i].val + dat[i].id * r;
    if (ansb > s) cout << l << ' ' << ansa;
    else cout << r << ' ' << ansb;
    cout << '\n';
    return 0;
}

 

【CodeForces-258A】Little Elephant and Bits【贪心】

【CodeForces-258A】Little Elephant and Bits【贪心】

问题十分简单,给出一个二进制表示的数,要求去除任意一位后,能够取得的最大值,我们使用字符串来操作,因为相同长度下,较大的数值其字典序一定较大【如果长度不一样则不一定满足,需要注意】,在一般情况下,我们只能够删去一个0或者一个1,如果删去0,则删去从左边开始的第一个0会得到所有删去0的结果的最大值,因为它让其右边的所有位数尽可能的向高位靠拢;类似的,如果删去1,则从最右边开始的第一个1删去,可得到所有删去1的结果中最大的值,之后比较这两个值就可以知道是删除0还是删除1的方案得到的数更大。对于特殊情况【全是0或全是1】,需要加一些特殊处理,让最后生成的字符串长度为n【即出现没有删减的情况】,我们检测到删0或删1方案得到的数没有删减时,就可以确认另一种删的方案一定成功删除了,故直接输出另一种方案即可。

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string str;
    cin >> str;
    int n = str.size();
    string tmp = "", a, b;
    bool flag = true;
    int pos = 0;
    for (int i = 0; i < n; i++) {
        if (flag && str[i] == '0') {
            flag = false;
            continue;
        }
        if (str[i] == '1') pos = i;
        tmp += str[i];
    }
    a = tmp;
    tmp = "";
    for (int i = 0; i < n; i++) {
        if (i == pos && str[i] == '1') continue;
        tmp += str[i];
    }
    b = tmp;
    if (b.size() == n || a.size() != n && a > b)
        cout << a << "\n";
    else
        cout << b << "\n";
    return 0;
}

 

【CodeForces-1029D】Concatenated Multiples

【CodeForces-1029D】Concatenated Multiples

问题链接:http://codeforces.com/problemset/problem/1029/D

Solution:

原来自己没有解决,参照了别人写的题解:http://codeforces.com/blog/entry/61439

首先分析组合后的数:\(a_i * 10^{len_j} + a_j\),这个数如果要被k整除,则必要加号两侧各自被k除后的余数都是0或者相加为k,接下来就是关键的处理步骤了。

如果我们暴力每个i、j,复杂度将是\(O(n^2)\)的,根据这道题的数据范围,规模会达到4e10,所以我们不能采用暴力来解决。参照上边链接内的题解,给出了一种方案,因为我们需要的只是在确定长度时等于0(当\(a_i * 10^{len_j} % k = 0\)时 )或等于\(k – a_i * 10^{len_j} % k\)(当\(a_i * 10^{len_j} % k \neq 0\)时)的\(a_j % k\)的数量,那么为每一种a[i]长度开一个vector,其中存储一下该长度的a[i]对k取模后的值,接着在这里使用它来作为a[j],排序后,可以使用二分搜索来确定索引上下界,索引上界减去索引下界就是数量,之后再判断一下是否包含的当前枚举的a[i]自身就好【如果包含,要将ans–】

根据这个设计,我写的代码是这样:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;
const int LIM = 2e5 + 10;
const int LENGTH = 11;
LL data[LIM], digits[LIM];
LL table[LENGTH];
vector<LL> remain[LENGTH];

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    LL n, k;
    cin >> n >> k;
    table[0] = 1;
    for (int i = 1; i < LENGTH; i++)
        table[i] = table[i - 1] * 10 % k;
    for (int i = 0; i < n; i++) {
        cin >> data[i];
        LL tmp = data[i];
        digits[i] = 0;
        while (tmp) {
            tmp /= 10, digits[i]++;
        }
        remain[digits[i]].push_back(data[i] % k);
    }
    for (int i = 0; i < LENGTH; i++)
        sort(remain[i].begin(), remain[i].end());
    LL ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < LENGTH; j++) {
            LL rem = data[i] * table[j] % k;
            vector<LL>::iterator l = lower_bound(remain[j].begin(), remain[j].end(), rem ? k - rem : 0);
            vector<LL>::iterator r = upper_bound(remain[j].begin(), remain[j].end(), rem ? k - rem : 0);
            ans += r - l;
            if (j == digits[i] && (rem ? k - rem : 0) == data[i] % k) ans--;
        }
    }
    cout << ans << "\n";
    return 0;
}

rem ? k – rem : 0这个写起来太麻烦了,按照题解的做法,可以改成:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;
const int LIM = 2e5 + 10;
const int LENGTH = 11;
LL data[LIM], digits[LIM];
LL table[LENGTH];
vector<LL> remain[LENGTH];

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    LL n, k;
    cin >> n >> k;
    table[0] = 1;
    for (int i = 1; i < LENGTH; i++)
        table[i] = table[i - 1] * 10 % k;
    for (int i = 0; i < n; i++) {
        cin >> data[i];
        LL tmp = data[i];
        digits[i] = 0;
        while (tmp) {
            tmp /= 10, digits[i]++;
        }
        remain[digits[i]].push_back(data[i] % k);
    }
    for (int i = 0; i < LENGTH; i++)
        sort(remain[i].begin(), remain[i].end());
    LL ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < LENGTH; j++) {
            LL rem = data[i] * table[j] % k;
            vector<LL>::iterator l = lower_bound(remain[j].begin(), remain[j].end(), (k - rem) % k);
            vector<LL>::iterator r = upper_bound(remain[j].begin(), remain[j].end(), (k - rem) % k);
            ans += r - l;
            if (j == digits[i] && (rem + data[i] % k) % k == 0) ans--;
        }
    }
    cout << ans << "\n";
    return 0;
}

 

【CodeForces-807C】Success Rate【二分】

【CodeForces-807C】Success Rate【二分】

Solution:

一开始按照x *q 与 y * p比较来做的,小于就x++,y++,大于就只y++,结果TLE。然后就按照最初想的,最后结果一定有x’ = kq,且y’ = kp,需要有x’ >= x,y’ >= y,枚举k试了一下,结果发现有问题,样例的3 10 1 2当k取5的时候上面不等式就已经满足了,但是这个k = 5是有问题的,发现y的增量需要保证大于等于x的增量,接着发现增量一做差就是没有通过的数量的增量,那么索性先求出y – x以及p – q,即没有通过的数量,之后再保证没有通过的和通过的数量的增量都是正的,根据这点来二分就可以了。

#include <iostream>

using namespace std;

typedef long long LL;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    LL x, y, p, q;
    cin >> t;
    while (t--) {
        LL cnt = 0;
        cin >> x >> y >> p >> q;
        if ((p == q && x != y) || (p == 0 && x != 0)) {
            cout << -1 << "\n";
            continue;
        }
        LL diff = y - x;
        LL d2 = q - p;
        LL l = 1, r = 1e9;
        while (l < r) {
            LL mid = (l + r) >> 1;
            if (mid * d2 < diff || mid * p < x) l = mid + 1;
            else r = mid;
        }
        cout << l * (q - p) - y + x + l * p - x << "\n";
    }
    return 0;
}

 

【CodeForces-1029F】Multicolored Markers

【CodeForces-1029F】Multicolored Markers

Solution:

内部各自至少也要有一个是矩形,我们首先将可能的矩形存下来,之后枚举大矩形的时候判断一下它是否可能嵌套小矩形来决定当前方案是否可行就可以。

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

typedef long long LL;

inline LL mini(LL a, LL b) {return a < b ? a : b;}

vector<LL> boxa, boxb;

int main(void) {
    LL a, b;
    scanf("%lld%lld", &a, &b);
    LL area = a + b;
    LL lim = sqrt(a);
    for (int i = 1; i <= lim; i++) {
        if (a % i == 0) boxa.push_back(i);
    }
    lim = sqrt(b);
    for (int i = 1; i <= lim; i++) {
        if (b % i == 0) boxb.push_back(i);
    }
    lim = sqrt(area);
    // cout << lim << endl;
    LL ans = 0x3f3f3f3f3f3f3f3f;
    for (int i = 1; i <= lim; i++) {
        if (area % i) continue;
        LL tmp = area / i;
        for (int j = 0; j < boxa.size(); j++) {
            if (boxa[j] <= i && a / boxa[j] <= tmp) {
                ans = mini((i + tmp) * 2, ans);
                break;
            }
        }
        for (int j = 0; j < boxb.size(); j++) {
            if (boxb[j] <= i && b / boxb[j] <= tmp) {
                ans = mini((i + tmp) * 2, ans);
                break;
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

 

【codeforces-1020A】New Building for SIS

【codeforces-1020A】New Building for SIS

爬楼的策略:

1.一栋楼上,不用考虑楼之间通道位置,直接去对应楼层。

2.楼与楼之间,如果两个位置都不在有通道的楼层,应当都寻找最近的通道楼层,耗时应当是两边各自到这个楼层的时间+穿越几栋楼的时间;如果任意一个位置在有通道的楼层,无论选择如何去目标位置,竖直方向最短距离都是两层的差值。

#include <iostream>
#include <cmath>

using namespace std;

inline bool inRange(int x, int a, int b) {
    return x >= a && x <= b;
}

int main(void) {
    int n, h, a, b, k, f1, t1, f2, t2;
    scanf("%d%d%d%d%d", &n, &h, &a, &b, &k);
    while (k--) {
        scanf("%d%d%d%d", &t1, &f1, &t2, &f2);
        if (t1 == t2) {
            printf("%d\n", abs(f1 - f2));
        } else {
            if (inRange(f1, a, b) || inRange(f2, a, b))
                printf("%d\n", abs(f1 - f2) + abs(t1 - t2));
            else
                printf("%d\n", min(abs(f1 - a) + abs(f2 - a), abs(f1 - b) + abs(f2 - b))
                    + abs(t1 - t2));
        }
    }
    return 0;
}