以https://www.luogu.com.cn/problem/P7252 为例
正解
#include <iostream>
#include <cstring>
#include <cstdio>using namespace std;const int N = 5e4 + 10, M = N * 17;int n, m, mn = N - 10;
int a[N], rt[N], idx;struct node {int ls, rs;int val;
} t[M];void update (int p) { t[p].val = t[t[p].ls].val + t[t[p].rs].val; }int clone (int p) {t[ ++ idx] = t[p];return idx;
}int modify (int p, int l, int r, int pos) {p = clone (p);if (l == r) {t[p].val ++;return p;}int mid = (l + r) >> 1;if (pos <= mid) t[p].ls = modify (t[p].ls, l, mid, pos);else t[p].rs = modify (t[p].rs, mid + 1, r, pos);update (p);return p;
}void query (int p, int q, int l, int r, int len) {if (!p && !q) return;if (l == r) {cout << l << endl;return;}int mid = (l + r) >> 1;int lcnt = t[t[q].ls].val - t[t[p].ls].val, rcnt = t[t[q].rs].val - t[t[p].rs].val;if (lcnt > len) query (t[p].ls, t[q].ls, l, mid, len);else if (rcnt > len) query (t[p].rs, t[q].rs, mid + 1, r, len);else {cout << 0 << endl;return;}
}int main () {freopen ("test/test.in", "r", stdin);freopen ("test/test.out", "w", stdout);cin >> n >> m;for (int i = 1; i <= n; i ++) {cin >> a[i];rt[i] = modify (rt[i - 1], 1, mn, a[i]);}for (int i = 1; i <= m; i ++) {int x, y;cin >> x >> y;query (rt[x - 1], rt[y], 1, mn, (y - x + 1) / 2);}return 0;
}
暴力
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>using namespace std;typedef long long ll;const int N = 1e3 + 10, M = N << 1;int n, m;
int a[N], b[N];
int cnt[N];int main () {freopen ("test/test.in", "r", stdin);freopen ("test/ans.out", "w", stdout);cin >> n >> m;for (int i = 1; i <= n; i ++) {cin >> a[i];}for (int i = 1; i <= m; i ++) {int l, r, len;cin >> l >> r;len = (r - l + 1) / 2;for (int j = l; j <= r; j ++) {cnt[a[j]] ++;}bool ok = 0;for (int j = l; j <= r; j ++) {if (cnt[a[j]] > len) {cout << a[j] << endl;ok = 1;break;}}if (!ok) cout << 0 << endl;for (int j = l; j <= r; j ++) {cnt[a[j]] = 0;}}return 0;
}
随机数据
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <random>using namespace std;const int N = 1e5 + 10;int n, m, sd;mt19937 rng;int rnd (int l, int r) {return rng () % (r - l + 1) + l;
}int main () {freopen ("test/seed.txt", "r", stdin);scanf ("%d", &sd);rng.seed (sd);freopen ("test/test.in", "w", stdout);int n = rnd (1, 1e3), m = rnd (1, n);printf ("%d %d\n", n, m);for (int i = 1; i <= n; i ++) {printf ("%d ", rnd (1, n));}printf ("\n");for (int i = 1; i <= m; i ++) {int x = rnd (1, n), y = rnd (1, n);if (x > y) swap (x, y);printf ("%d %d\n", x, y);}fclose (stdout);freopen ("test/seed.txt", "w", stdout);printf ("%d", rnd (0, 2e9));return 0;
}
对拍文件
编译选项的话可以自己调
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>using namespace std;int main () {system ("g++ -g -std=c++14 -o tt tt.cpp");system ("g++ -g -std=c++14 -o random random.cpp");system ("g++ -g -std=c++14 -o force force.cpp");int T;cin >> T;for (int i = 1; i <= T; i ++) {printf ("Case #%d ...", i);system ("./random");double fst = clock ();system ("./force");double fed = clock ();double st = clock ();system ("./tt");double ed = clock ();int sig = system ("diff -BZb test/ans.out test/test.out");if (sig != 0) {printf ("Wrong Answer!!!\n");return 0;}printf ("Accepted time: %.3lf ftime: %.3lf\n", (ed - st) / 1000, (fed - fst) / 1000);}printf ("Congradulation!\n");return 0;
}
自动编译器
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>using namespace std;int main () {string name, compile, run, tmp;compile = "g++ -std=c++14 -Wall -fsanitize=address,undefined,leak -o ";cin >> name;tmp = ' ' + name + ".cpp";compile += name;compile += tmp;int sig = system (compile.c_str());if (sig != 0) {cout << "Compile Error\n";return 0;}run = "./" + name;system (run.c_str());return 0;
}