五一 考试二
【代码】：
#include<bits/stdc++.h> using namespace std; class People { public: int id, force; People() {} People(int i, int f): id(i), force(f) {} //构造函数，把id赋值为 i，把force赋值为f }; bool operator <(People x, People y) { return x.force < y.force; } int n; set <People> s; int main() { freopen("super.in", "r", stdin); freopen("super.out", "w", stdout); scanf("%d", &n); s.insert(People(1, 1000000000)); //超人，注意他的力量值赋值为一个很大的数 for (int i = 1, x, y; i <= n; ++i) { scanf("%d%d", &x, &y); auto it1 = s.upper_bound(People(x, y)); //找到第一个大于当前能力的人，返回他的指针 if (it1 == s.begin()) printf("%d %d ", x, it1->id); //如果这个人是超人，那就和他比较 else { auto it3 = it1; auto it2 = --it3; //我在怀疑这样操作的话，it2不就是他自己的指针了吗？？？ int a1 = abs(it1->force - y);//与第一个大于ta的数的能力值比较 int a2 = abs(it2->force - y); if (a2 <= a1) it1 = it2; //找一个能力最接近的 printf("%d %d ", x, it1->id); } s.insert(People(x, y)); //加入set } return 0; } //指针大概就相当于结构体吧 it1->id 相当于it1.id
(反正我是暴力出奇迹了。。。。。
除了黄色的部分，其余都是自带输入模板。。。）
#include<bits/stdc++.h> #include <cstdio> #include <ctime> #include <cstdlib> #include <algorithm> using namespace std; const int N = 1e7 + 5; int n, m, a[N], ans[N]; int gen, cute1, cute2; int number() { gen = (1LL * gen * cute1) ^ cute2; return (gen & (n - 1)) + 1; } int qumax(int ll,int rr) { int jie=a[ll]; for(int i=ll+1;i<=rr;i++) { if(a[i]>jie) jie=a[i]; } return jie; } int main() { // freopen("bat.in", "r", stdin); // freopen("bat.out", "w", stdout); scanf("%d%d", &n, &m); scanf("%d%d%d", &gen, &cute1, &cute2); for (int i = 1; i <= n; ++i) a[i] = number(); for (int i = 1; i <= m; ++i) { int l = number(), r = number(); if (l > r) swap(l, r); ans[i]=qumax(l,r); } int sum = 0; for (int i = 1; i <= m; ++i) sum = (1LL * sum * cute1 + ans[i]) % cute2; printf("%d ", sum); // fclose(stdin); // fclose(stdout); return 0; }
（神仙的代码看不懂啊 。。。QAQ）
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int N = 1e7 + 5;
int n, m;
int gen, cute1, cute2;
int number() {
gen = (1LL * gen * cute1) ^ cute2;
return (gen & (n - 1)) + 1;
}
int hd[N], nxt[N], id[N], to[N], cnt;
int ans[N], a[N], p[N], q[N];
int add(int x, int y, int i) {
++cnt;
nxt[cnt] = hd[x];
to[cnt] = y;
id[cnt] = i;
hd[x] = cnt;
}
int getfa(int x, int y) {
int fa = x;
for (int i = x; i; i = p[i])
if (p[i] < y || p[i] == i) {
fa = i;
break;
}
for (int j, i = x; i != fa; i = j) {
j = p[i], p[i] = fa;
}
return fa;
}
int main() {
freopen("bat.in", "r", stdin);
freopen("bat.out", "w", stdout);
scanf("%d%d", &n, &m);
scanf("%d%d%d", &gen, &cute1, &cute2);
for (int i = 1; i <= n; ++i)
a[i] = number();
// for (int i = 1; i <= n; ++i)
// printf("%d ", a[i]);
// printf("
");
for (int i = 1; i <= m; ++i) {
int l = number(), r = number();
if (l > r) swap(l, r);
// printf("%d %d
", l, r);
// printf("%d %d %d
", gen, cute1, cute2);
add(l, r, i);
}
double t1;
fprintf(stderr, "%lf
", t1 = (double)clock()/CLOCKS_PER_SEC);
int ind = 0;
for (int i = 1; i <= n; ++i) {
while (ind && a[q[ind]] <= a[i]) --ind;
if (ind) p[i] = q[ind];
else p[i] = i;
q[++ind] = i;
}
for (int i = n; i; --i) {
for (int j = hd[i]; j; j = nxt[j])
ans[id[j]] = a[getfa(to[j], i)];
}
fprintf(stderr, "%lf
", (double)clock()/CLOCKS_PER_SEC - t1);
int sum = 0;
for (int i = 1; i <= m; ++i)
sum = (1LL * sum * cute1 + ans[i]) % cute2;
printf("%d
", sum);
}
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <climits>
#include <cassert>
#include <ctime>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <functional>
#include <string>
#define x first
#define y second
#define MP std::make_pair
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#pragma GCC optimize("O3")
typedef long long LL;
typedef std::pair<int, int> Pii;
const int oo = 0x3f3f3f3f;
template<typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, true : false; }
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, true : false; }
std::string procStatus()
{
std::ifstream t("/proc/self/status");
return std::string(std::istreambuf_iterator<char>(t), std::istreambuf_iterator<char>());
}
template<typename T> T read(T &x)
{
int f = 1;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-')
f = -1;
for (x = 0; isdigit(ch); ch = getchar())
x = 10 * x + ch - '0';
return x *= f;
}
template<typename T> void write(T x)
{
if (x == 0) {
putchar('0');
return;
}
if (x < 0) {
putchar('-');
x = -x;
}
static char s[20];
int top = 0;
for (; x; x /= 10)
s[++top] = x % 10 + '0';
while (top)
putchar(s[top--]);
}
// EOT
const int MAXN = 1e5 + 5;
int N;
LL K;
int A[MAXN];
LL mergeSort(long double a[], register int n)
{
if (n <= 1)
return 0;
register int mid = n >> 1;
register LL ret = mergeSort(a, mid) + mergeSort(a + mid, n - mid);
static long double t[MAXN];
register int p = 0, q = mid, tot = 0;
while (p < mid || q < n) {
if (p < mid && (q == n || a[p] <= a[q])) {
t[tot++] = a[p++];
ret += q - mid;
} else
t[tot++] = a[q++];
}
memcpy(a, t, sizeof(*a) * n);
return ret;
}
bool check(register long double mid)
{
static long double sum[MAXN];
sum[0] = 0;
for (int i = 1; i <= N; ++i) {
sum[i] = sum[i - 1] + A[i] - mid;
}
return mergeSort(sum, N + 1) >= K;
}
void input()
{
read(N); read(K);
for (int i = 1; i <= N; ++i) {
read(A[i]);
}
}
void solve()
{
long double l = *std::min_element(A + 1, A + N + 1), r = *std::max_element(A + 1, A + N + 1);
while (clock() < 0.9 * CLOCKS_PER_SEC) {
long double mid = (l + r) / 2;
(check(mid) ? r : l) = mid;
}
printf("%.4f
", (double)r);
}
int main()
{
freopen("wonder.in", "r", stdin);
freopen("wonder.out", "w", stdout);
input();
solve();
return 0;
}
暴力出奇迹！！！rank 4！！！