五一   考试二  

 

 

 

【代码】：

#include
     
      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 
      
        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\n", 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\n", x, it1->id);        }        s.insert(People(x, y));  //加入set     }    return 0;}//指针大概就相当于结构体吧   it1->id  相当于it1.id
      
     

 

 

 

 

 

 

 

 

 

 

 (反正我是暴力出奇迹了。。。。。

   除了黄色的部分，其余都是自带输入模板。。。）

#include
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          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\n", sum);    //    fclose(stdin);//    fclose(stdout);    return 0;    }
         
        
       
      
     

（神仙的代码看不懂啊 。。。QAQ）

#include 
     
      #include 
      
       #include 
       
        #include 
        
         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("\n");    for (int i = 1; i <= m; ++i) {        int l = number(), r = number();        if (l > r) swap(l, r);        // printf("%d %d\n", l, r);        // printf("%d %d %d\n", gen, cute1, cute2);        add(l, r, i);    }    double t1;    fprintf(stderr, "%lf\n", 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\n", (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\n", sum);}
        
       
      
     

 

 

 

 

 

 

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #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
                  
                    Pii;const int oo = 0x3f3f3f3f;template
                   
                     inline bool chkmax(T &a, T b) { return a < b ? a = b, true : false; }template
                    
                      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
                     
                      (t), std::istreambuf_iterator
                      
                       ());}template
                       
                         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
                        
                          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--]);}// EOTconst 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\n", (double)r);}int main(){ freopen("wonder.in", "r", stdin); freopen("wonder.out", "w", stdout); input(); solve(); return 0;}
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

 

 

 暴力出奇迹！！！rank 4！！！