## 【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;
int parent[NLIM];
int ns[NLIM];       /* Node Set */
int c[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++;
}
}
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
}
}
int u, v;
Edge tmp;
for (int i = 0; i < m; i++) {
cin >> u >> v >> tmp.w;
tmp.to = v;
tmp.to = u;
// cout << u << " " << v << " " << ns[u] << " " << ns[v] << " " << tmp.w << endl;
}
// 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) {
}
while (crt <= c[i]) {
for (int j = 0; j < adjOfNode[crt].size(); j++) {
}
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 << 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++) {
}
}
}
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
if (j) cout << " ";
}
cout << "\n";
}
} else {
cout << "No\n";
}
return 0;
}


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

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

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:

#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:

#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【贪心】

#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

Solution:

#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:

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