蒟蒻只会J组的题了
T1 candy
取模运算实际上把自然数分成了很多类
本题实际上是求x属于[l, r]使得x % n最大
容易知道最理想的情况下x % n最大值为n - 1
所以我们只要判断能否取到n-1即可
- 如果答案能取到n - 1,即存在x属于[l, r]使得x mod n = n - 1
不妨设x = n · y - 1, y属于N*
那么就有l <= n · y - 1 <= r
解得(l + 1) / n <= y <= (l + 1) / n
也就是说只要说明y存在那么x就一定存在
即[(l + 1) / n, (r + 1) / n]中存在整数即可 - 如果不能那么显然r点一定是最优解
AC代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <bits/stdc++.h> using namespace std; int n, l, r; int main() { cin >> n >> l >> r; double a = (l + 1) * 1.0 / n; double b = (r + 1) * 1.0 / n; if (a <= int(b) && int(b) <= b) { cout << n - 1 << endl; } else { cout << r % n << endl; } } |
T2 sort
该题其实就是动态修改a数组,询问a[x]是数组中第?大的数(此处的大小要考虑数的下标),或者说是查询有多少数小于a[x]
所以正解就是树状数组加离散化
不过要注意几个细节
- 因为修改的值也要离散化,所以要把所有数读入后再离线操作
- 因为该题中所有数都不相等,所以离散化时所有数都都要不一样
AC代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
#include <bits/stdc++.h> #define v first #define id second using namespace std; typedef pair<int, int> PII; const int N = 3e5 + 10, M = 2e5 + 10; int n, Q; PII a[N], ask[M]; int op[M]; vector<PII> T; inline char GET_CHAR() { static char buf[N], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, N, stdin), p1 == p2) ? EOF: *p1 ++; } template<class T> inline void read(T &x) { x = 0; int f = 0; char ch = GET_CHAR(); while (ch < '0' || ch > '9') { f |= (ch == '-'); ch = GET_CHAR(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = GET_CHAR(); } x = f ? -x: x; } int lowbit(int x) { return x & -x; } struct tree { int t[N]; void add(int x, int d) { for (; x < N; x += lowbit(x)) t[x] += d; } int query(int x) { int res = 0; for (; x; x -= lowbit(x)) res += t[x]; return res; } } tr; void lisanhua() { sort(T.begin(), T.end()); map<PII, int> m; for (int i = 0; i < T.size(); ++ i) m[T[i]] = i + 1; for (int i = 1; i <= n; ++ i) { a[i].v = m[a[i]]; tr.add(a[i].v, 1); } for (int i = 1; i <= Q; ++ i) if (op[i] == 1) ask[i].v = m[ask[i]]; } void DEbug() { cout << "DEbug<<<<<<<<<<<<<<<<<<<\n"; for (int i = 1; i <= n; ++ i) printf("%d%c", a[i].v, " \n"[i == n]); for (int i = 1; i <= Q; ++ i) { printf("%d %d", op[i], ask[i].id); if (op[i] == 1) printf(" %d", ask[i].v); puts(""); } cout << ">>>>>>>>>>>>>>>>>>>>>>>>\n"; } int main() { read(n), read(Q); int i = 1; for (; i <= n; ++ i) { int t; read(t); a[i] = {t, i}; T.push_back(a[i]); } i = 1; for (; i <= Q; ++ i) { int x, v = 0; read(op[i]), read(x); if (op[i] == 1) { read(v); T.push_back({v, x}); } ask[i] = {v, x}; } lisanhua(); i = 1; for (; i <= Q; ++ i) { int v = ask[i].v, x = ask[i].id; if (op[i] == 1) { tr.add(a[x].v, -1); a[x].v = v; tr.add(v, 1); } else { printf("%d\n", tr.query(a[x].v - 1) + 1); } } } |
T3 network
不用解释，暴暴暴暴暴暴暴暴暴暴暴暴暴就行了
不过有几个好用的stl可以介绍一下
atoi(): char数组转int
to_string() : int转string
AC代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
#include <bits/stdc++.h> using namespace std; const int N = 1e3 + 10; const string str = " ...:"; map<string, int> mp; inline bool is_d(char x) { return x >= '0' && x <= '9'; } struct computer { // #define DEBUG vector<int> number; string op; int name; bool flag = true; computer(string Name, string a) { if (Name == "Server") name = 1; else name = 2; #ifdef DEBUG cout << "debug>>>>>>>>>>>>>>>>>>>>>>>>>>>\n"; #endif for (int i = 0, j = 0; i < a.size() && flag; ++ i) { if (is_d(a[i])) { j = i; string t; while (j < a.size() && is_d(a[j])) t += a[j ++]; int sum = atoi(t.c_str()); #ifdef DEBUG cout << "t:" << t << endl; cout << "sum:" << sum << endl; #endif if (number.size() <= 3 && sum > 255) flag = false; else if (number.size() == 4 && sum > 65535) flag = false; else if (number.size() > 4) flag = false; if (to_string(sum) != t) flag = false; if (flag) number.push_back(sum); i = j - 1; } else { op += a[i]; if (!number.size()) flag = false; else { if (str[number.size()] != a[i]) flag = false; } } } if (number.size() != 5) flag = false; if (op != "...:") flag = false; #ifdef DEBUG cout << "<<<<<<<<<<<<<<<<<<<<<<<<<<<debug\n"; #endif } bool is_err() { return !flag; } }; int main() { cin.tie(0)->sync_with_stdio(0), cout.tie(0); int n; cin >> n; for (int i = 1; i <= n; ++ i) { string name, ip; cin >> name >> ip; computer c = computer(name, ip); if (c.is_err()) cout << "ERR\n"; else { if (c.name == 1) { if (!mp[ip]) { cout << "OK\n"; mp[ip] = i; } else cout << "FAIL\n"; } else { if (mp[ip]) cout << mp[ip] << '\n'; else cout << "FAIL\n"; } } } } |
T4 fruit
这题我调了4个小时
- 可以用连通块维护本题中的块
如果i-1,i在一个块中,那么把i-1,i连一条边
考虑到一个数后面会接一个数,所以不用写邻接表或是链式前向星,只要开一个ne数组就可以了 - 然后将每个连通块的第一个元素放入一个vector中
这就是第一个篮子里的答案
然后把vector中每个数变成对应联通块中的下一个元素,去掉不合法的(即没有出边的)点 - 然后就是最头疼的地方了,如何合并两个块
我的思路是使用并查集,其中的find(x)查找的是连通块的最后一个元素
因为并查集可以非常容易的合并,并且拥有非常出色的时间复杂度,所以想到可以用并查集
到这里,合并应该就容易想到了
即: 将两个块在并查集中合并,并在前一个块的末尾元素加一条边到后一个块还没被使用的第一个元素 - 最后用一个滚动数组实现一下转移就好了
AC代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 |
#include <bits/stdc++.h> #define v first #define id second // #define DEBUG using namespace std; typedef pair<int, int> PII; const int N = 2e5 + 10; int n; int f[N]; int h[N]; inline char GET_CHAR() { static char buf[N], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, N, stdin), p1 == p2) ? EOF: *p1 ++; } template<class T> inline void read(T &x) { x = 0; int f = 0; char ch = GET_CHAR(); while (ch < '0' || ch > '9') { f |= (ch == '-'); ch = GET_CHAR(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = GET_CHAR(); } x = f ? -x: x; } struct mergerfindset { int f[N]; inline void init() { for (int i = 1; i <= n; ++ i) f[i] = i; } inline int find(const int &x) { return f[x] == x ? x: f[x] = find(f[x]); } inline void merge(const int &x, const int &y) { f[find(x)] = find(y); } } ed; inline void add(const int &a, const int &b) { h[a] = b; } inline int my_next(const int &p) { return h[p]; } inline void mergelist(const int &x, const int &y) { add(ed.find(x), y); ed.merge(x, y); } int main() { f[0] = -1; read(n); for (int i = 1; i <= n; ++ i) { read(f[i]); if (f[i - 1] == f[i]) add(i - 1, i); } ed.init(); vector<int> st[2]; for (int i = n, j = n; i; -- i) { while (j && f[i] == f[j]) ed.merge(j --, i); st[0].push_back(j + 1); i = j + 1; } reverse(st[0].begin(), st[0].end()); #ifdef DEBUG for (int i = 1; i <= n; ++ i) { printf("point i:%d next:%d end:%d\n", i, my_next(i), ed.find(i)); } #endif for (int i = 0; st[i].size(); i ^= 1) { vector<int> &a = st[i], &b = st[i ^ 1]; for (int j = 0; j < a.size(); ++ j) { printf("%d%c", a[j], " \n"[j == a.size() - 1]); a[j] = my_next(a[j]); } PII last = {-1, 0}; // v-first表示水果种类 // id-second表示上一个块 for (int j = 0; j < a.size(); ++ j) { if (!a[j]) continue; if (!last.id || last.v != f[a[j]]) { b.push_back(a[j]); last = {f[a[j]], a[j]}; } else { mergelist(last.id, a[j]); } } #ifdef DEBUG cout << "DEbug>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n"; cout << "a: " << endl; for (auto j: a) cout << j << ' '; cout << endl; cout << "b: " << endl; for (auto j: b) cout << j << ' '; cout << endl; cout << "<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n"; #endif a.clear(); a.shrink_to_fit(); } } |
发表回复