2020-牛客多校-10
C 思维 & 树
C* Namomo 2C
区间减1，代价为长度的平方，问将区间操作为全0的最小代价和最大代价。
1#include <iostream>
2
3#include <algorithm>
4#include <string>
5#include <vector>
6#include <stack>
7#include <queue>
8#include <set>
9#include <map>
10#include <unordered_map>
11#include <unordered_set>
12#include <random>
13#include <chrono>
14
15#include <cstdio>
16#include <cstring>
17#include <cmath>
18#include <ctime>
19#include <cstdlib>
20#include <cassert>
21
22#define itn int
23#define fro for
24#define scnaf scanf
25#define sacnf scanf
26#define Fastin freopen("in.txt", "r", stdin)
27#define Fastout freopen("out.txt", "w", stdout)
28#define manx maxn
29#define lowbit(x) ((x) & (-x))
30#define ceil(n, p) (((n) +(p) - 1) / (p))
31#define DBG(x) (void)(cout << "L" << __LINE__ << ": " << #x << " = " <<( x) << '\n')
32#define clr(a, x) memset((a), x, sizeof (a))
33#define min(a, b) ((a) < (b)? (a): (b))
34#define max(a, b) ((a) > (b)? (a): (b))
35
36using namespace std;
37typedef long long ll;
38
39int read(){
40 int ng=0,x=0;
41 char ch=getchar();
42 for(;ch<'0' || ch>'9';ch=getchar()) ng|=ch=='-';
43 for(;ch>='0' && ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
44 return ng?-x:x;
45}
46/*------------------------------------------------------------------------------------*/
47ll gcd(ll x, ll y){return !x? y: gcd(y % x, x);}
48void exgcd(ll a, ll b, ll &x, ll &y){
49 if(!b){x = 1; y = 0;return;}
50 exgcd(b, a % b, y, x); y -= a / b * x;
51}
52ll qp(ll a, ll p){
53 if(p < 0) return 0;
54 ll ans = 1; while(p){if(p & 1) ans = ans * a ; a = a * a; p >>= 1;}
55 return ans;
56}
57ll qp(ll a, ll p, ll M){
58 ll ans = 1; while(p){ if(p & 1) ans = ans * a % M; a = a * a % M; p >>= 1;}
59 return ans;
60}
61/*------------------------------------------------------------------------------------*/
62
63const int maxn = 5e5 + 10;
64const int M = 1e9 + 7;
65int a[maxn], b[maxn];
66
67ll cal(int l, int r){return (r - l) * 1ll * (r - l) % M;}
68
69stack<pair<int, int>> sta;
70
71int main(){
72// Fastin;
73 int n; scnaf("%d", &n);
74 for(int i = 1; i <= n; i++) scanf("%d", a + i); a[n + 1] = 0;
75
76 for(int i = 1; i <= n + 1; i++) b[i] = a[i] - a[i - 1];
77 while(b[n + 1] == 0) n--;
78 ll ans = 0;
79 int p = 1, q = 1; while(b[q] >= 0) q++;
80 while(p <= n + 1){
81 if(b[p] + b[q] > 0){
82 ans += -b[q] * cal(p, q); ans %= M;
83 b[p] += b[q];
84 q++; while(q <= n + 1 && b[q] >= 0) q++;
85 }
86 else if(b[p] + b[q] == 0){
87 ans += b[p] * cal(p, q); ans %= M;
88 p++; q++; while(p <= n + 1 && b[p] < 0) p++; while(q <= n + 1 && b[q] >= 0) q++;
89 }
90 else{
91 ans += b[p] * cal(p, q); ans %= M;
92 b[q] += b[p];
93 p++; while(p <= n + 1 && b[p] < 0) p++;
94
95 }
96 }
97 printf("%lld ", ans % M);
98
99 for(int i = 1; i <= n + 1; i++) b[i] = a[i] - a[i - 1];
100 ans = 0;
101 for(int i = 1; i <= n + 1; i++){
102 if(b[i] > 0) sta.push({i, b[i]});
103 else if(b[i] < 0){
104 while(1){
105 pair<int, int> now = sta.top(); sta.pop();
106 if(now.second + b[i] < 0){
107 ans += now.second * cal(now.first, i); ans %= M;
108 b[i] += now.second;
109 }
110 else{
111 ans += -b[i] * cal(now.first, i); ans %= M;
112 now.second += b[i];
113 sta.push(now);
114 break;
115 }
116
117 }
118 }
119 }
120
121 printf("%lld\n", ans);
122
123 return 0;
124}I 构造
虽然感觉还是说不太清楚qaq
假设当前将要引入第i个人进入比赛，考虑在最优的构造下，之前在场的$i - 1$个人中最多有多少个人可以与第i人比赛。如果已有$j-1$个人跟i人比过赛，第j人将要跟i人比赛，则这次对决对于那些已经比过赛的$j-1$人没有任何意义，这些人最终都会因此多等待一天；而如果j人不与i人比赛，那么下一轮操作(最多意味着不会再考虑$j + 1$人的情况)就是引入第$i+1$人，这也就说明如果这次不比赛，之后尚未引入的$n-i$个人的进场时间都会提前一天。那么我们比较两个时间，如果$j - 1< n - i$，就选择比赛，不然则不比赛。可以直接顺序将j从1到i -1进行枚举考虑，原因非常神秘，我感觉我可能不太理解。当上述过程重复操作完成后，将那些没有比过的赛再全部安排上即可。
1const int maxn = 3e2 + 10;
2bool vis[maxn][maxn];
3
4int main(){
5 Fastin;
6 TTT{
7 clr(vis, 0);
8 int n; scanf("%d", &n);
9 for(int i = 1; i <= n; i++) for(int j = 1; j < i; j++) if(j - 1 < n - i){
10 printf("%d %d\n", j, i);
11 vis[j][i] = 1;
12 }
13 for(int i = 1; i <= n; i++) for(int j = i + 1; j <= n; j++) if(!vis[i][j])
14 printf("%d %d\n", i, j);
15 }
16 return 0;
17}