Codeforces Round #361 div2

时间：2022-06-01 06:39:36

ProblemA(Codeforces Round 689A):

题意：

　　给一个手势， 问这个手势是否是唯一。

思路：

　　暴力， 模拟将这个手势上下左右移动一次看是否还在键盘上即可。

代码：

　　

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <ctime>

 #include <set>

 #include <map>

 #include <list>

 #include <stack>

 #include <queue>

 #include <string>

 #include <vector>

 #include <fstream>

 #include <iterator>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define LL long long

 #define INF 0x3f3f3f3f

 #define MOD 1000000007

 #define eps 1e-6

 #define MAXN 10

 #define MAXM 100

 #define dd {cout<<"debug"<<endl;}

 #define pa {system("pause");}

 #define p(x) {printf("%d\n", x);}

 #define pd(x) {printf("%.7lf\n", x);}

 #define k(x) {printf("Case %d: ", ++x);}

 #define s(x) {scanf("%d", &x);}

 #define sd(x) {scanf("%lf", &x);}

 #define mes(x, d) {memset(x, d, sizeof(x));}

 #define do(i, x) for(i = 0; i < x; i ++)

 #define dod(i, x, l) for(i = x; i >= l; i --)

 #define doe(i, x) for(i = 1; i <= x; i ++)

 int n;

 int row[MAXN] = {, , , , , , , , , };

 int col[MAXN] = {, , , , , , , , , };

 int dir[][] = {{-, }, {, }, {, -}, {, }};

 char str[MAXN];

 bool move_one_step(int d)

 {

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

     {

         int x = str[i] - '';

         if((d ==  || d == ) && x == ) return false;

         if(row[x] + dir[d][] <  || col[x] + dir[d][] <  || col[x] + dir[d][] > )

             return false;

         if(x !=  && (row[x] + dir[d][] > ))

             return false;

     }

     return true;

 }

 void get_ans()

 {

     bool flag = false;

     for(int d = ; d < ; d ++)

     {

         if(move_one_step(d)) flag = true;

     }

     printf(flag ? "NO\n" : "YES\n");

 }

 int main()

 {

     scanf("%d", &n);

     scanf("%s", str);

     get_ans();

     return ;

 }

Problem_B(Codeforces Round 689B):

题意：

　　有n个城市， 第i个城市到第j个城市需要消耗abs(i - j)的能量， 然后每个城市可以转移到另一个城市， 只需要一个能量， 转移是单向的。

　　问从第一个城市到各个城市所需要的最少能量。

思路：

　　每次只有三个选择， 即（1、向左走一步， 2、向右走一步， 3、移动到另一个城市）。

　　以第一个城市为起点， bfs一遍， 即可得到从第一个城市到所有城市所需要的最少能量。

代码：

　　

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <ctime>

 #include <set>

 #include <map>

 #include <list>

 #include <stack>

 #include <queue>

 #include <string>

 #include <vector>

 #include <fstream>

 #include <iterator>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define LL long long

 #define INF 0x3f3f3f3f

 #define MOD 1000000007

 #define eps 1e-6

 #define MAXN 200010

 #define MAXM 100

 #define dd {cout<<"debug"<<endl;}

 #define pa {system("pause");}

 #define p(x) {printf("%d\n", x);}

 #define pd(x) {printf("%.7lf\n", x);}

 #define k(x) {printf("Case %d: ", ++x);}

 #define s(x) {scanf("%d", &x);}

 #define sd(x) {scanf("%lf", &x);}

 #define mes(x, d) {memset(x, d, sizeof(x));}

 #define do(i, x) for(i = 0; i < x; i ++)

 #define dod(i, x, l) for(i = x; i >= l; i --)

 #define doe(i, x) for(i = 1; i <= x; i ++)

 int n;

 int a[MAXN];

 int step[MAXN];

 bool vis[MAXN];

 void update(int pos)

 {

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

         step[i] = min(step[i], step[pos] + (i - pos));

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

         step[i] = min(step[i], step[pos] + pos - i);

 }

 void show()

 {

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

         printf("%d ", step[i]);

     printf("\n");

 }

 void bfs()

 {

     queue <int> Q;

     Q.push();

     step[] = ;

     while (!Q.empty())

     {

         int cnt = Q.front();

         Q.pop();

         if(vis[cnt]) continue;

         vis[cnt] = true;

         //left

         if(step[cnt - ] > step[cnt] +  && cnt -  > )

         {

             step[cnt - ] = step[cnt] + ;

             if(!vis[cnt - ])

                 Q.push(cnt - );

         }

         //right

         if(step[cnt + ] > step[cnt] +  && cnt +  <= n)

         {

             step[cnt + ]  = step[cnt] + ;

             if(!vis[cnt + ])

                 Q.push(cnt + );

         }

         //move

         if(a[cnt] != cnt)

         {

             if(step[a[cnt]] > step[cnt] + )

             {

                 step[a[cnt]] = step[cnt] + ;

                 if(!vis[a[cnt]])

                     Q.push(a[cnt]);

             }

         }

     }

 }

 int main()

 {

     scanf("%d", &n);

     mes(vis, false);

     mes(step, 0x3f);

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

     {

         scanf("%d", &a[i]);

         // step[i] = i - 1;

     }

     bfs();

     show();

     return ;

 }

Problen_C(Codeforces Round 689C):

题意：

　　有四个小偷， 假设第一个小偷偷了a块巧克力， 那么第二个小偷则偷了a*k块， 第三个a*k*k块，第四个a*k*k*k个。

　　然而所有小偷的背包都有一个容量n， 现在给你一个m， 表示小偷们恰好有m种可能偷法。

　　求满足上述条件的n， n为恰好满足上述条件的最大的背包容量n， 要使得n尽可能的小。

思路：

　　最值最大/小化， 典型的二分。

　　由于a, k, n 都是未知的， 先来看一下它们的关系：

　　　　第四个小偷偷到a*k^3块巧克力， 是四个小偷里偷到的最多的。

　　　　假设现在已知n， 那么如果n/(x^3) > 0, 说明这个x是一个满足条件的k。

　　　　然后再看a, a = n / (x^3), 那么从1 ~ a  条件n/(x^3)都是成立的。

　　　　所以， 当k = x时， 有n/(x^3)种方案。

　　那么， 可以知道， 如果n已知， 则可以求出其方案数。

　　这里就可以二分n， 找到一个满足的n， 然后在这个范围内去找到最小的n.

代码：

　　

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <ctime>

 #include <set>

 #include <map>

 #include <list>

 #include <stack>

 #include <queue>

 #include <string>

 #include <vector>

 #include <fstream>

 #include <iterator>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define LL long long

 #define INF 0x7ffffffffffffff

 #define MOD 1000000007

 #define eps 1e-6

 #define MAXN 1000010

 #define MAXM 100

 #define dd {cout<<"debug"<<endl;}

 #define pa {system("pause");}

 #define p(x) {printf("%d\n", x);}

 #define pd(x) {printf("%.7lf\n", x);}

 #define k(x) {printf("Case %d: ", ++x);}

 #define s(x) {scanf("%d", &x);}

 #define sd(x) {scanf("%lf", &x);}

 #define mes(x, d) {memset(x, d, sizeof(x));}

 #define do(i, x) for(i = 0; i < x; i ++)

 #define dod(i, x, l) for(i = x; i >= l; i --)

 #define doe(i, x) for(i = 1; i <= x; i ++)

 LL m;

 LL check(LL n)

 {

     LL sum = ;

     for (LL i = ; ; i ++)

     {

         if (n < i * i * i) return sum;

         sum = sum + n / (i * i * i);

     }

     return sum;

 }

 LL get_ans(LL &mid)

 {

     LL l = , r = INF;

     LL num = ;

     while (l < r)

     {

         mid = (l + r + ) / ;

         num = check(mid);

         if (num == m) return num;

         if (num > m) r = mid - ;

         else l = mid + ;

     }

     return num == m ? num : -;

 }

 int main()

 {

     scanf("%lld", &m);

     LL n = , mid;

     LL m1 = get_ans(mid);

     if(m1 != m) printf("-1\n");

     else

     {

         for(LL i = ; ; i ++)

         {

             if(i * i * i > mid) break;

             n = max(n, mid / (i * i * i) * (i * i * i));

         }

         printf("%lld\n", n);

     }

     return ;

 }

Problem_D(CodeForces 689D):

题意：

　　有两个长度为n的数列a, b。

　　找出下列子序列的个数：

　　　　在[l, r]这个区间内， a数列的最大值 == b数列的最小值。

思路：

　　求最大最小值， 可以用RMQ, 线段树。

　　又不涉及修改， 可以使用RMQ, 查询为O(1)， 预处理复杂度为O(nlogn)

　　先将a, b 数列进行处理。

　　然后， 枚举左端点， 然后再找到满足条件的 右端点的范围， 计算求和即可。

代码：

　　

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <ctime>

 #include <set>

 #include <map>

 #include <list>

 #include <stack>

 #include <queue>

 #include <string>

 #include <vector>

 #include <fstream>

 #include <iterator>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define LL long long

 #define INF 0x3f3f3f3f

 #define MOD 1000000007

 #define eps 1e-6

 #define MAXN 200010

 #define MAXM 21

 #define dd {cout<<"debug"<<endl;}

 #define pa {system("pause");}

 #define p(x) {printf("%d\n", x);}

 #define pd(x) {printf("%.7lf\n", x);}

 #define k(x) {printf("Case %d: ", ++x);}

 #define s(x) {scanf("%d", &x);}

 #define sd(x) {scanf("%lf", &x);}

 #define mes(x, d) {memset(x, d, sizeof(x));}

 #define do(i, x) for(i = 0; i < x; i ++)

 #define dod(i, x, l) for(i = x; i >= l; i --)

 #define doe(i, x) for(i = 1; i <= x; i ++)

 int n;

 int a[MAXN], b[MAXN];

 int mx_a[MAXN][MAXM], mi_b[MAXN][MAXM];

 int p[MAXM], flog[MAXN];

 void init()

 {

     p[] = , flog[] = -;

     for(int i = ; i < MAXM; i ++) p[i] =  * p[i - ];

     for(int i = ; i <= n; i ++) flog[i] = (i & (i - )) ? flog[i - ] : (flog[i - ] + );

     for(int i = ; i <= n; i ++) mx_a[i][] = a[i];

     for(int j = ; j < MAXM; j ++)

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

             if(i + p[j] -  <= n)

                 mx_a[i][j] = max(mx_a[i][j - ], mx_a[i + p[j - ]][j - ]);

     for(int i = ; i <= n; i ++) mi_b[i][] = b[i];

     for(int j = ; j < MAXM; j ++)

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

             if(i + p[j] - <= n)

                 mi_b[i][j] = min(mi_b[i][j - ], mi_b[i + p[j - ]][j - ]);

 }

 int get_mx_a(int l, int r)

 {

     int k = flog[r - l + ];

     return max(mx_a[l][k], mx_a[r - p[k] + ][k]);

 }

 int get_mi_b(int l, int r)

 {

     int k = flog[r - l + ];

     return min(mi_b[l][k], mi_b[r - p[k] + ][k]);

 }

 int min_l(int pos)

 {

     int l, r, mid;

     l = pos - , r = n + ;

     while(r - l > )

     {

         mid = (l + r) >> ;

         if(get_mx_a(pos, mid) >= get_mi_b(pos, mid)) r = mid;

         else l = mid;

     }

     return r;

 }

 int max_r(int pos)

 {

     int l, r, mid;

     l = pos - , r = n + ;

     while(r - l > )

     {

         mid = (l + r) >> ;

         if(get_mx_a(pos, mid) > get_mi_b(pos, mid)) r = mid;

         else l = mid;

     }

     return r;

 }

 int main()

 {

     scanf("%d", &n);

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

         scanf("%d", &a[i]);

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

         scanf("%d", &b[i]);

     init();

     LL ans = ;

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

     {

         int l = min_l(i);

         int r = max_r(i);

         ans = ans + (r - l);

     }

     printf("%I64d\n", ans);

     return ;

 }

Problem_E(CodeForces 689E):

题意：

　　f([l, r])表示区间[l, r]内元素个数：r - l + 1

　　现在给n个区间， 求这n个区间任选k个， 将其求交集运算后的f值。

　　求出所有情况的f值之和。

思路：　　

　　先考虑每个点， 假设已知这个点被x个区间覆盖，  那么， 这个点被计算的次数就是C(x, k)次。

　　求出所有点的情况即可。 再拓展一下， 如果连续y个点的覆盖数是一样的， 那么就可以得出这y个点被计算的总次数是 y * C(x, k)

　　利用求前缀和的思路来处理这个点， 左右端点+-1.

　　这里左端点-1 其实是将整个区间往前移动了一下， 相当于是从0开始。

代码：

　　

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <ctime>

 #include <set>

 #include <map>

 #include <list>

 #include <stack>

 #include <queue>

 #include <string>

 #include <vector>

 #include <fstream>

 #include <iterator>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define LL long long

 #define INF 0x3f3f3f3f

 #define MOD 1000000007

 #define eps 1e-6

 #define MAXN 200010

 #define MAXM 100

 #define dd {cout<<"debug"<<endl;}

 #define pa {system("pause");}

 #define p(x) {printf("%d\n", x);}

 #define pd(x) {printf("%.7lf\n", x);}

 #define k(x) {printf("Case %d: ", ++x);}

 #define s(x) {scanf("%d", &x);}

 #define sd(x) {scanf("%lf", &x);}

 #define mes(x, d) {memset(x, d, sizeof(x));}

 #define do(i, x) for(i = 0; i < x; i ++)

 #define dod(i, x, l) for(i = x; i >= l; i --)

 #define doe(i, x) for(i = 1; i <= x; i ++)

 LL n, k;

 LL f[MAXN];

 LL fac[MAXN], fack[MAXN];

 map <LL, LL> mp;

 vector <LL> v;

 LL qpow(LL x, LL k)

 {

     LL res = ;

     while(k)

     {

         if(k & ) res = res * x % MOD;

         x = x * x % MOD;

         k >>= ;

     }

     return res;

 }

 LL inv(LL a, LL x)

 {

     return qpow(a, x - );

 }

 LL C(LL n, LL m)

 {

     if(n < m || m < ) return ;

     return ((fac[n] * fack[n - m] % MOD) * fack[m]) % MOD;

 }

 void init()

 {

     fac[] = fack[] = ;

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

     {

         fac[i] = (fac[i - ] * i) % MOD;

         fack[i] = inv(fac[i], MOD);

     }

     mp.clear();

     v.clear();

 }

 int main()

 {

     init();

     LL l, r;

     scanf("%lld %lld", &n, &k);

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

     {

         scanf("%lld %lld", &l, &r);

         mp[l - ] ++;

         v.push_back(l - );

         mp[r] --;

         v.push_back(r);

     }

     sort(v.begin(), v.end());

     LL ans = , num = , pre_pos = - 1e9 - , cnt_pos, len;

     int vlen = v.size();

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

     {

         cnt_pos = v[i];

         len = cnt_pos - pre_pos;

         if(num >= k)

             ans = (ans + len * C(num, k) % MOD) % MOD;

         if(pre_pos != cnt_pos)

         {

             pre_pos = cnt_pos;

             num = num + mp[cnt_pos];

         }

     }

     printf("%lld\n", ans);

     return ;

 }

相关文章