A - City Day

题意：给n,x,y和数组a[n]，求最小的下标d，使得有a[d-x,d-x+1,……d-1,d+1,d-1,d+1,……d+y-1,d+y]都比a[d]小，若d-x<=0则从1开始，若d+y>n，则从n为结尾。

分析：对于a[i]，要在左端找到比a[i]大的且最近的数，在右端找到比a[i]大且最近的数，用单调栈。然后从1开始看到n，看到哪个符合条件就作为答案输出。

1 #include
2
3 #define maxn 100005
4 #define mod 1000000007
5 #define inf 0x3f3f3f3f
6 #define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
7 #define ll long long
8 #define LL long long
9 using namespace std;
10 int a[maxn];
11 int l[maxn];
12 int r[maxn];
13
14 int main() {
15 start;
16 int n, x, y;
17 cin >> n >> x >> y;
18 int t = 0;
19 for (int i = 1; i <= n; ++i) 20 cin >> a[i];
21 stack s;
22 s.push(0);
23 for (int i = 1; i <= n; ++i) { 24 while (a[s.top()] > a[i])
25 s.pop();
26 l[i] = s.top();
27 s.push(i);
28 }
29 stack tmp;
30 tmp.push(n + 1);
31 for (int i = n; i > 0; --i) {
32 while (a[tmp.top()] > a[i])
33 tmp.pop();
34 r[i] = tmp.top();
35 tmp.push(i);
36 }
37 for (int i = 1; i <= n; ++i) { 38 if ((i - l[i] - 1 >= x || l[i] == 0) && (r[i] - i - 1 >= y || r[i] == n + 1)) {
39 cout << i << endl;
40 return 0;
41 }
42 }
43 return 0;
44 }

B - Water Lily

题意：离水面高H的花，走了L触及水面，问水深。

分析：勾股定理。设答案为X，X*X+L*L=(X+H)*(X+H)。（cin和printf同用的不良风格）

1 #include
2
3 #define maxn 100005
4 #define mod 1000000007
5 #define inf 0x3f3f3f3f
6 #define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
7 #define ll long long
8 #define LL long long
9 using namespace std;
10
11 int main() {
12 start;
13 ll h, l;
14 cin >> h >> l;
15 printf("%.13lf",(l * l - h * h) * 1.0 / (2 * h));
16 return 0;
17 }

C - MP3

题意：给定n个数，假设有K个不同的数，就要使用k=ceil(log2(K)) bits去存储每个数，总共需要n*k bits，一个大小为i bytes（1 byte=8 bits）的磁盘。对于一个区间[l,r]我们可以将小于l的数变成l，将大于r的数变成r，问最少变多少数使得磁盘能存下这些数。

分析：能存i bytes，即能存8*i bits，则k=8*i/n，则K=2^(8*i/n)，此即能存下的不同种类的数字（认为是l到r区间长度共有K，wa了一个小时，看到别人代码才发现），可表示为(1<<k)。

(1)排序，可先找K个不同的数，然后滑动区间，左端点将所有等于左端点的数去掉，右端点加上右方下一组相等的数。同时要找最少的变化数，即找区间内最多的数。

1 #include
2
3 #define maxn 400005
4 #define mod 1000000007
5 #define inf 0x3f3f3f3f
6 #define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
7 #define ll long long
8 #define LL long long
9 using namespace std;
10 ll a[maxn];
11
12 int main() {
13 start;
14 int n, I;
15 cin >> n >> I;
16 for (int i = 1; i <= n; ++i) 17 cin >> a[i];
18 sort(a + 1, a + n + 1);
19 int sum = 0;
20 int maxt = 0;
21 ll k = 8 * I / n;
22 if (k >= 30) {//(1<<30)>1e9
23 cout << 0 << endl; 24 return 0; 25 } 26 int K = (1 << k); 27 int l = 1, r = 1; 28 a[n + 1] = (1ll << 31); 29 a[0] = -1;//两个哨兵 30 int count = 1; 31 for (; r <= n; ++r) { 32 if (a[r] != a[r + 1]) { 33 if (count == K) 34 break; 35 ++count; 36 } 37 } 38 if (r >= n) {//如果一整段区间都符合条件，且还可以存数，r会到n+1处
39 cout << 0 << endl;
40 return 0;
41 }
42 maxt = sum = r - l + 1;
43 for (; l + maxt - 1 <= n;) {
44 int t = l;
45 for (; t <= n; ++t)
46 if (a[t] != a[l])
47 break;
48 if (t == n + 1)
49 break;
50 sum -= (t - l);
51 l = t;
52 ++r;
53 ++sum;
54 for (; r <= n; ++r) {
55 if (a[r + 1] != a[r])
56 break;
57 ++sum;
58 }
59 maxt = max(maxt, sum);
60 if (r == n)
61 break;
62 }
63 cout << n - maxt << endl;
64 return 0;
65 }

(2)排序，记录每一个相同的数有多少种，记为一组，然后找K组，然后滑动区间每次保证K组，找到区间内最多的数。

1 #include
2
3 #define maxn 400005
4 #define mod 1000000007
5 #define inf 0x3f3f3f3f
6 #define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
7 #define ll long long
8 #define LL long long
9 using namespace std;
10 ll a[maxn];
11
12 int main() {
13 start;
14 int n, I;
15 cin >> n >> I;
16 for (int i = 1; i <= n; ++i) 17 cin >> a[i];
18 sort(a + 1, a + n + 1);
19 ll k = 8 * I / n;
20 if (k >= 30) {//(1<<30)>1e9
21 cout << 0 << endl; 22 return 0; 23 } 24 a[n + 1] = -1;//哨兵 25 int K = (1 << k); 26 vector num;
27 int cnt = 1;
28 for (int i = 1; i <= n; ++i) {
29 if (a[i] == a[i + 1])
30 ++cnt;
31 else {
32 num.push_back(cnt);
33 cnt = 1;
34 }
35 }
36 if (num.size() < K) {
37 cout << 0 << endl;
38 return 0;
39 }
40 int sum = 0;
41 int l = 0, r = K - 1;
42 for (int i = 0; i <= r; ++i)
43 sum += num[i];
44 int maxt = sum;
45 for (; r + 1 < num.size();) {
46 sum -= num[l];
47 ++l;
48 ++r;
49 sum += num[r];
50 maxt = max(maxt, sum);
51 }
52 cout << n - maxt << endl;
53 return 0;
54 }

D - Welfare State

题意：给n个数，有两种操作，第一种操作输入p和x，将第p个数变为x；第二种操作输入x，将所有小于x的数变成x。

分析：对于a[i]，最后的第一种操作一定是有效的，假设变为x，如果在该操作后出现了大于第二种操作输入的y，且y>x，则该数变成y。我们将q种操作编号为1~q。记录一个p[n]数组，一个t[n]数组，对于第i个数，p[i]表示最后的第一种操作，t[i]表示这个操作的编号。再记录一个maxi[n]数组，maxi[i]表示在第i个操作（包括第i个操作）之后的第二个操作变成的最大的数。

1 #include
2
3 #define maxn 400005
4 #define mod 1000000007
5 #define inf 0x3f3f3f3f
6 #define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
7 #define ll long long
8 #define LL long long
9 using namespace std;
10 ll a[maxn];
11 ll p[maxn];
12 ll t[maxn];
13 ll maxi[maxn];
14
15 int main() {
16 start;
17 memset(p, -1, sizeof(p));
18 int n;
19 cin >> n;
20 for (int i = 1; i <= n; ++i) 21 cin >> a[i];
22 int q;
23 cin >> q;
24 for (int i = 0; i < q; ++i) { 25 int x; 26 cin >> x;
27 if (x == 1) {
28 int y, z;
29 cin >> y >> z;
30 p[y] = z;
31 t[y] = i;
32 } else {
33 cin >> maxi[i];
34 }
35 }
36 /*后缀操作，对于第i次操作，假设是第二种操作，如果后续有比该操作更大的值，则该操作可被后续操作覆盖*/
37 /* 假设是第一种操作，假设后续有比该操作更大的第二次操作的值，同样可被覆盖*/
38 for (int i = q - 2; i >= 0; --i)
39 maxi[i] = max(maxi[i], maxi[i + 1]);
40 for (int i = 1; i <= n; ++i) { 41 int maxt = t[i];//a[i]最后进行第一次操作的编号 42 if (p[i] == -1)//如果a[i]没有进行第一次操作，t[i]为0 43 cout << max(a[i], maxi[maxt]) << ' ';//如果第0次操作后进行的第二种操作的x比a[i]大则输出x，反之亦反。 44 else if (maxi[maxt] > p[i])//a[i]在最后一次（maxt次）第一种操作变成了x，在第maxt次后有一个第二种操作，该操作的值大于x，则输出该值
45 cout << maxi[maxt] << ' ';
46 else//第maxt操作将a[i]变成了p[i]且后续无有效操作
47 cout << p[i] << ' ';
48 }
49 return 0;
50 }

E和F我这种菜鸡估计是A不出来的。

（如有问题，请在评论区和我说）