Educational Codeforces Round 71 (Rated for Div. 2)

一时失言乱红尘 2023-06-01 11:14 22阅读 0赞

[A. There Are Two Types Of Burgers][]

思路：签到题，价格高的先做就行。

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 int main()
     4 {
     5     std::ios::sync_with_stdio(false);
     6     int t;
     7     cin >> t;
     8     int b,p,f;
     9     int h, c;
    10     while(t--)
    11     {
    12         cin >> b >> p >> f;
    13         cin >> h >> c;
    14         b /= 2;
    15         int ans = 0;
    16         if(h > c)
    17         {
    18             while(p && b)
    19             {
    20                 ans += h;
    21                 p--;
    22                 b--;
    23             }
    24             while(f && b)
    25             {
    26                 ans += c;
    27                 f--;
    28                 b--;
    29             }
    30         }
    31         else{
    32             while(f && b)
    33             {
    34                 ans += c;
    35                 f--;
    36                 b--;
    37             }
    38              while(p && b)
    39             {
    40                 ans += h;
    41                 p--;
    42                 b--;
    43             }
    44         }
    45         cout << ans << endl;
    46     }
    47     return 0;
    48 }

--------------------

[B. Square Filling][]

思路：翻车题，答案数组开的不够大一直没发现，把A为0的在B中标记成1，暴力搜索一遍将可以标记成1的标记，最后检索有没有0即可。

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 int mp[500][500];
     4 int ansx[3000], ansy[3000];
     5 int vis[500][500];
     6 int n, m;
     7 int cnt;
     8 bool check(int x, int y)
     9 {
    10     if(mp[x][y] == 1)
    11         return true;
    12     else return false;
    13 }
    14 void dfs(int x, int y)
    15 {
    16     if(check(x,y) && check(x + 1,y) &&  check(x,y + 1) &&  check(x + 1,y + 1) )
    17     {
    18         ansx[cnt] = x + 1,ansy[cnt++] = y + 1;
    19         vis[x][y] = 1;
    20         vis[x +1][y] = 1;
    21         vis[x][y + 1] = 1;
    22         vis[x + 1][y + 1] = 1;
    23     }
    24 }
    25 int main()
    26 {
    27     std::ios::sync_with_stdio(false);
    28     cin >> n >> m;
    29     memset(mp, 0, sizeof(mp));
    30     for(int i = 0;i < n;i++)
    31         for(int j = 0;j < m;j++)
    32         {
    33             cin >> mp[i][j];
    34             if(mp[i][j] == 0) vis[i][j] = 1;
    35         }
    36  
    37     for(int i = 0;i < n - 1;i++)
    38         for(int j = 0;j < m - 1;j++)
    39             dfs(i,j);
    40     for(int i = 0;i < n;i++)
    41         for(int j = 0;j < m;j++)
    42             if(!vis[i][j])
    43             {
    44                 cout << -1 << endl;
    45                 return 0;
    46             }
    47     cout << cnt << endl;
    48     for(int i = 0;i < cnt;i++)
    49     {
    50         cout << ansx[i] << " " << ansy[i]<< endl;
    51     }
    52     return 0;
    53 }

--------------------

[C. Gas Pipeline][]

思路：设管道花费为a,柱子为b，首先图中横的管道加柱子最少有的花费是 a\*n + b\* ( n + 1), 每次走上面要花费 1 个 a ,上去之后每次都有1个b的花费，那么遇到1上去，遇到0就考虑下来再上去的花费值不值，是继续上面直接走，还是下来再上去，检索这一段 0 的长度， 当 pos(i - j - 1 \*b >= 2\*a)时 选择下来，你观察图会发现，下来的时候也有b的花费（我在上去的时候加），= 是因为最后要走下来，所以花费一样的情况下走下面优并且遇到的0直接到n也要下来。

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 int main()
     5 {
     6     std::ios::sync_with_stdio(false);
     7     int t;
     8     cin >> t;
     9     ll a,b, n;
    10     string s;
    11     while(t--)
    12     {
    13         cin >> n >> a >> b;
    14         cin >> s;
    15         ll pos;
    16         bool up = false;
    17         ll ans = a * n + b * (n + 1);
    18         for(int i = 0;i < n;i++)
    19         {
    20             if(up) ans += b;
    21             if(s[i] == '1' && !up)
    22             {
    23                 up = true;
    24                 ans += a;
    25                 ans += b;
    26             }
    27             else if(up)
    28             {
    29                 pos = i;
    30                 while(s[pos] == '0' && pos < n ) pos++;
    31                 if( (pos - i - 1) * b >= 2*a || pos == n)
    32                 {
    33                     ans += a;
    34                     up = false;
    35                 }
    36             }
    37  
    38  
    39         }
    40         if(up) ans += a;
    41         cout << ans << endl;
    42     }
    43     return 0;
    44 }

D. Number Of Permutations（待补）

思路

转载于:https://www.cnblogs.com/Carered/p/11406733.html

[A. There Are Two Types Of Burgers]: http://codeforces.com/contest/1207/problem/A
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/b33413d0cb2448048282fa2c8b27dcfd.png
[B. Square Filling]: http://codeforces.com/contest/1207/problem/B
[C. Gas Pipeline]: http://codeforces.com/contest/1207/problem/C