AtCoder ABC 183

本文主要是介绍AtCoder ABC 183，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本期考察STL的性质较多，如果熟悉的话基本可以秒掉

C - Travel

简单的搜索问题，练手

#define _CRT_SECURE_NO_WARNINGS#include <iostream>
#include <string>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#define LT(x) (x * 2)
#define RT(x) (x * 2 + 1)using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef vector<int> vi;int n, K;
int w[10][10];
bool vis[10];
int ans = 0;void dfs(int step, int u, int val) {if (step == n - 1) {if (val + w[u][0] == K)ans += 1;return;}for (int v = 0; v < n; ++v) {if (vis[v] == 0) {vis[v] = 1;dfs(step + 1, v, val + w[u][v]);vis[v] = 0;}}
}int main() { //freopen("in.txt", "r", stdin);scanf("%d%d", &n, &K);for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {scanf("%d", &w[i][j]);}}vis[0] = 1;dfs(0, 0, 0);printf("%d\n", ans);return 0;
}

D - Water Heater

模拟，会排序就能做
用map来记录当前时间点的操作，每个时间点的操作完毕检查

#define _CRT_SECURE_NO_WARNINGS#include <iostream>
#include <string>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#define LT(x) (x * 2)
#define RT(x) (x * 2 + 1)using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef vector<int> vi;LL n, W;
map<LL, vector<pair<LL, LL>>> orders;int main() { //freopen("in.txt", "r", stdin);scanf("%lld%lld", &n, &W);set<LL> ts;for (int i = 0; i < n; ++i) {LL s, t, w;scanf("%lld%lld%lld", &s, &t, &w);orders[s].push_back({ 1, w });orders[t].push_back({ 2, w });ts.insert(s);ts.insert(t);}vi ti(ts.begin(), ts.end());sort(ti.begin(), ti.end());bool ac = 1;LL cur = 0;for (auto x : ti) {for (auto &item : orders[x]) {if (item.first == 1) {cur += item.second;}else {cur -= item.second;}}if (cur > W) {ac = 0;break;}}if (ac) {printf("Yes\n");}else {printf("No\n");}return 0;
}

E - Queen on Grid

由于可以走任意步，实际上就是在三个方向上求前缀和

#define _CRT_SECURE_NO_WARNINGS#include <iostream>
#include <string>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#define LT(x) (x * 2)
#define RT(x) (x * 2 + 1)using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef vector<int> vi;int H, W;
char s[2005][2005];
LL dp[2002][2002];
LL row_dp[2002][2002];      // sum
LL col_dp[2002][2002];
LL dia_dp[2002][2002];
LL mod = LL(1e9) + 7;int main() { //freopen("in.txt", "r", stdin);scanf("%d%d", &H, &W);for (int i = 0; i < H; ++i) {scanf("%s", s[i]);}dp[0][0] = 1;row_dp[0][0] = col_dp[0][0] = dia_dp[0][0] = 1;for (int i = 0; i < H; ++i) {for (int j = 0; j < W; ++j) {if (i + j == 0) continue;if (s[i][j] == '#') continue;if (i - 1 >= 0) dp[i][j] += col_dp[i - 1][j];if (j - 1 >= 0) dp[i][j] += row_dp[i][j - 1];if (i - 1 >= 0 && j - 1 >= 0) dp[i][j] += dia_dp[i - 1][j - 1];dp[i][j] %= mod;col_dp[i][j] = row_dp[i][j] = dia_dp[i][j] = dp[i][j];if (i - 1 >= 0)col_dp[i][j] = (col_dp[i - 1][j] + col_dp[i][j]) % mod;if (j - 1 >= 0)row_dp[i][j] = (row_dp[i][j - 1] + row_dp[i][j]) % mod;if (i - 1 >= 0 && j - 1 >= 0)dia_dp[i][j] = (dia_dp[i - 1][j - 1] + dia_dp[i][j]) % mod;}}LL ans = dp[H - 1][W - 1];printf("%lld\n", ans);return 0;
}

F - Confluence

并查集是并查集，但是在并查集里进行分类操作。乍一看是 $O(N^2)$ 操作。实际上如果并到最后，并没有那么多的并操作。具体的时间复杂度待研究。。。。
用一个map[i][j]来记录第i个组去上j课的人数。并查集操作的时候小集加入大集。

#define _CRT_SECURE_NO_WARNINGS#include <iostream>
#include <string>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#define LT(x) (x * 2)
#define RT(x) (x * 2 + 1)using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef vector<int> vi;map<int, int> cnt[200020];
int n, q;
int c[200020];
int lev[200020];
int fa[200020];int getf(int x) {if (x == fa[x]) return x;return fa[x] = getf(fa[x]);
}int main() { //freopen("in.txt", "r", stdin);scanf("%d%d", &n, &q);for (int i = 1; i <= n; ++i) {scanf("%d", c + i);cnt[i][c[i]] = 1;}for (int i = 1; i <= n; ++i)fa[i] = i, lev[i] = 1;for (int i = 0; i < q; ++i) {int op, u, v;scanf("%d%d%d", &op, &u, &v);if (op == 1) {int fu = getf(u), fv = getf(v);if (fu == fv) continue;if (lev[fu] <= lev[fv]) {swap(fu, fv);}fa[fv] = fu;if (lev[fu] == lev[fv])lev[fu] += 1;for (auto it : cnt[fv]) {int ci = it.first;cnt[fu][ci] += it.second;}}else {int fu = getf(u);printf("%d\n", cnt[fu][v]);}}return 0;
}