codeforces 576 div2 A-D题解

A题

Description

题目链接: https://codeforces.com/contest/1199/problem/A
题意:
　　给定长度为n(1≤n≤100000)的一个序列a，以及两个整数x,y(0≤x,y≤7)。要求在序列里最靠前的一个索引d满足a[j]>=a[d] (d−x≤j<d,d<j<d+y)。
　　简单说就是找出一天使它的权值小于之前x天和之后y天，超出[1，n]的不考虑

Solution

思路:
　　模拟从前往后遍历一遍，找到满足条件就输出。

 #include <bits/stdc++.h>

 #define lson rt << 1, l, mid

 #define rson rt << 1 | 1, mid + 1, r

 using namespace std;

 using ll = long long;

 using ull = unsigned long long;

 using pa = pair<int, int>;

 using ld = long double;

 int n, m, k;

 const int maxn = 1e6 + ;

 template <class T>

 inline T read(T &ret)

 {

     int f = ;

     ret = ;

     char ch = getchar();

     while (!isdigit(ch))

     {

         if (ch == '-')

             f = -;

         ch = getchar();

     }

     while (isdigit(ch))

     {

         ret = (ret << ) + (ret << ) + ch - '';

         ch = getchar();

     }

     ret *= f;

     return ret;

 }

 template <class T>

 inline void write(T n)

 {

     if (n < )

     {

         putchar('-');

         n = -n;

     }

     if (n >= )

     {

         write(n / );

     }

     putchar(n %  + '');

 }

 int a[maxn];

 int main(int argc, char const *argv[])

 {

     read(n);

     int x, y;

     read(x);

     read(y);

     for (int i = ; i <= n; i++)

         read(a[i]);

     for (int i = ; i <= n; i++)

     {

         int f = ;

         for (int j = i - x; j >  && j < i; j++)

             if (a[j] <= a[i])

             {

                 f = ;

                 break;

             }

         if (f)

         {

             for (int j = i + ; j <= n && j <= i + y; j++)

                 if (a[j] <= a[i])

                 {

                     f = ;

                     break;

                 }

         }

         if (f)

         {

             cout << i << "\n";

             break;

         }

     }

     return ;

 }

B题

Description

题目链接: https://codeforces.com/contest/1199/problem/B
题意:
　　有一朵荷花长在水面上，高出水面的部分为H，往右拉了长度L后刚好露出水面，
　　求水的深度

Solution:

思路:
　　勾股定理推出公式水面高H=(L^₂ - H²) / (2H)

 #include <bits/stdc++.h>

 #define lson rt << 1, l, mid

 #define rson rt << 1 | 1, mid + 1, r

 using namespace std;

 using ll = long long;

 using ull = unsigned long long;

 using pa = pair<int, int>;

 using ld = long double;

 int n, m, k;

 const int maxn = 1e6 + ;

 template <class T>

 inline T read(T &ret)

 {

     int f = ;

     ret = ;

     char ch = getchar();

     while (!isdigit(ch))

     {

         if (ch == '-')

             f = -;

         ch = getchar();

     }

     while (isdigit(ch))

     {

         ret = (ret << ) + (ret << ) + ch - '';

         ch = getchar();

     }

     ret *= f;

     return ret;

 }

 template <class T>

 inline void write(T n)

 {

     if (n < )

     {

         putchar('-');

         n = -n;

     }

     if (n >= )

     {

         write(n / );

     }

     putchar(n %  + '');

 }

 int main(int argc, char const *argv[])

 {

     ios::sync_with_stdio(false);

     cin.tie();

     cout.tie();

     ld h, l;

     cin >> h >> l;

     ld ans = (l * l - h * h) / (h * );

     cout << fixed << setprecision() << ans << '\n';

     return ;

 }

C题

Description

题目链接: https://codeforces.com/contest/1199/problem/C
题意:
　　给一个长度为n的序列代表数字信号长度和一个I表示存储Ibyte,（1byte=8bit）。对于数字信号，每个信号需要花费k bits存储，k由序列内不同元素个数K决定，k=log₂K向上取整，为了满足存储要求，我们可以将存储信号长度划定在一个区间[L,R]内
　　小于L的变为L，大于R的变为R。问如何选取L，R使得改变的数字信号最少。输出最少改变次数。

Solution:

思路:
　　阅读理解实锤了，看题看了半天没搞明白。首先我们可以将总共的字节数bits算出来，即8*I，用bits除以序列长度n得到每个数字信号的存储字节数m。这时候我们会发现2^m就是序列里的不同数字信号长度的上限,
　　如果2^m≥序列长度n，那么肯定不用修改长度，此时答案为0。否则的话就需要我们对序列进行遍历判断了，我这里采用的是尺取法（？还是单调队列，我一直分不清，感觉差不多）。
　　嗯还有就是在判断上限时不能采用直接取幂的方式，应该以对数来判断，不然存不下这个数会wa掉
　　还wa了一个log，log是自然对数，log2才是2的对数，qaq

 //注意数据范围

 //log是自然对数 log2才是！！！

 #include <bits/stdc++.h>

 #define lson rt << 1, l, mid

 #define rson rt << 1 | 1, mid + 1, r

 using namespace std;

 using ll = long long;

 using ull = unsigned long long;

 using pa = pair<int, int>;

 using ld = long double;

 ll n, m, k;

 const int maxn = 4e5 + ;

 const int inf = 0x3f3f3f3f;

 template <class T>

 inline T read(T &ret)

 {

     int f = ;

     ret = ;

     char ch = getchar();

     while (!isdigit(ch))

     {

         if (ch == '-')

             f = -;

         ch = getchar();

     }

     while (isdigit(ch))

     {

         ret = (ret << ) + (ret << ) + ch - '';

         ch = getchar();

     }

     ret *= f;

     return ret;

 }

 template <class T>

 inline void write(T n)

 {

     if (n < )

     {

         putchar('-');

         n = -n;

     }

     if (n >= )

     {

         write(n / );

     }

     putchar(n %  + '');

 }

 vector<int> a(maxn);

 map<int, int> mp;

 set<int> s;

 struct node

 {

     int x, tot;

     node() {}

     node(int x, int tot)

     {

         this->x = x;

         this->tot = tot;

     }

 };

 int main(int argc, char const *argv[])

 {

     read(n);

     read(m);

     ll bits = m * ; //总的字节数

     m = bits / n;    //一个元素可以占的字节数

     ld tmp = log2(n);

     for (int i = ; i < n; i++)

     {

         read(a[i]);

         ++mp[a[i]];

         s.insert(a[i]);

     }

     ll ans = ;

     if (m >= tmp)

     {

         write();

         putchar('\n');

         return ;

     }

     ull t =  << m;

     auto now = s.begin();

     ll cnt = ;

     ull tot = ;

     deque<int> dq;

     dq.clear();

     for (auto x : s)

     {

         ++tot;              //不同元素个数

         dq.emplace_back(x); //保存状态

         cnt += mp[x];       //不同元素总的个数

         if (tot > t)

         {

             if (!ans)

                 ans = inf;

             --tot;

             cnt -= mp[dq.front()];

             dq.pop_front();

             ans = min(n - cnt, ans);

         }

     }

     write(ans);

     return ;

 }

D题

Description:

题目链接: https://codeforces.com/contest/1199/problem/D
题意:
　　给一个长为n的序列，q次操作，操作分为两种，一是将区间l,r内所有小于v的数改为v，二是将索引l位置的数改为x。q次操作后输出最后的序列。

Solution:

思路:
　　赛场上t了，赛后重写了遍lazytag才过（哭了)。（感觉和前两天做的2018杭电多校有个题挺像，直接改了改交然后就t）
　　回到主题，首先这个题区间操作，上线段树，区间修改加个懒标记，单点修改直接update，不过这个题在单点修改的时候需要将当前点的lazy标记清空，防止在查询答案时混淆。

 //线段树区间更新

 //对于单点，线段树维护下更新并将lazy赋值为0

 //对于区间，加上lazy标记

 #include <algorithm>

 #include <cstring>

 #include <iostream>

 #define lson rt << 1

 #define rson rt << 1 | 1

 using namespace std;

 using ll = long long;

 const int mod =  << ;

 const int maxn = 2e5 + ;

 int n, m;

 template <class T>

 inline T read(T &ret)

 {

     int f = ;

     ret = ;

     char ch = getchar();

     while (!isdigit(ch))

     {

         if (ch == '-')

             f = -;

         ch = getchar();

     }

     while (isdigit(ch))

     {

         ret = (ret << ) + (ret << ) + ch - '';

         ch = getchar();

     }

     ret *= f;

     return ret;

 }

 template <class T>

 inline void write(T n)

 {

     if (n < )

     {

         putchar('-');

         n = -n;

     }

     if (n >= )

     {

         write(n / );

     }

     putchar(n %  + '');

 }

 struct node

 {

     int lazy, val, l, r;

 } tr[maxn << ];

 int a[maxn];

 void pushdown(int rt)

 {

     if (tr[rt].lazy)

     {

         tr[lson].val = max(tr[lson].val, tr[rt].lazy);

         tr[rson].val = max(tr[rson].val, tr[rt].lazy);

         tr[lson].lazy = max(tr[rt].lazy, tr[lson].lazy);

         tr[rson].lazy = max(tr[rt].lazy, tr[rson].lazy);

         tr[rt].lazy = ;

     }

 }

 void build(int rt, int l, int r)

 {

     tr[rt].l = l;

     tr[rt].r = r;

     tr[rt].lazy = ;

     if (l == r)

     {

         read(tr[rt].val);

         a[l] = tr[rt].val;

         return;

     }

     int mid = l + r >> ;

     build(rt << , l, mid);

     build(rt <<  | , mid + , r);

 }

 void update(int rt, int L, int v)

 {

     int l = tr[rt].l;

     int r = tr[rt].r;

     if (l == r)

     {

         tr[rt].val = v;

         tr[rt].lazy = ; //此题单点更新优先级大于懒标记

         return;

     }

     int mid = l + r >> ;

     pushdown(rt); //没有返回代表不是完全包含于待查询区间，需要先下放懒标记再向左右区间查询

     if (L <= mid)

         update(rt << , L, v);

     else

         update(rt <<  | , L, v);

 }

 void query(int rt, int L, int R)

 {

     int l = tr[rt].l;

     int r = tr[rt].r;

     if (l == r)

     {

         a[l] = max(tr[rt].val, tr[rt].lazy);

         return;

     }

     pushdown(rt); //同update

     int mid = l + r >> ;

     if (L <= mid)

         query(rt << , L, R);

     if (R > mid)

         query(rt <<  | , L, R);

 }

 int main(int argc, char const *argv[])

 {

     read(n);

     build(, , n);

     read(m);

     for (int i = ; i < m; i++)

     {

         int op, x, y;

         read(op);

         if (op == )

         {

             read(x);

             read(y);

             update(, x, y);

         }

         else

         {

             read(x);

             tr[].lazy = max(tr[].lazy, x);

         }

     }

     query(, , n);

     for (int i = ; i <= n; i++)

     {

         write(a[i]);

         putchar(' ');

     }

     return ;

 }

巴特西

codeforces 576 div2 A-D题解

A题

Description

Solution

B题

Description

Solution:

C题

Description

Solution:

D题

Description:

Solution:

最新文章

热门文章