The Preliminary Contest for ICPC Asia Shanghai 2019 （B L ）

约定不等于承诺〃 2023-06-01 11:15 13阅读 0赞

B. Light bulbs

思路：差分 + 离散化， 好不容易懂了差分却没想到离散化，还是要罗老板出马....。

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     for(int i = 1;i <= t;i++)
     9     {
    10         int n, m;
    11         cin >> n >> m;
    12         map<int , int > mp;
    13         while(m--){
    14             int l, r;
    15             cin >> l >> r;
    16             mp[l] += 1;
    17             mp[r + 1] -= 1;
    18         }
    19         int last = 0, ans = 0, cnt = 0;
    20         for(auto it : mp)
    21         {
    22             ans += (it.first - last) * (cnt & 1);
    23             cnt += it.second;
    24             last = it.first;
    25         }
    26         cout << "Case #" << i << ": " << ans << endl;
    27     }
    28     return 0;
    29 }

L. Digit sum

思路：打个表，O（1）查询。

AC代码：

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

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 const int maxn = 1e6 +5 ;
     5 ll dp[maxn][10];
     6 int main()
     7 {
     8     std::ios::sync_with_stdio(false);
     9     int t;
    10     cin >>t;
    11     for(int i = 1;i <= 1e6;i++)
    12     {
    13         for(int j = 2;j <= 10;j++){
    14             dp[i][j] = 0;
    15             int tmp = i;
    16             while(tmp){
    17                 dp[i][j] += tmp % j;
    18                 tmp /= j;
    19             }
    20             dp[i][j] += dp[i-1][j];
    21         }
    22     }
    23     for(int i = 1;i <= t;i++)
    24     {
    25         int n, d;
    26         cin >> n >> d;
    27         cout << "Case #" << i << ": ";
    28         cout << dp[n][d] << endl;
    29     }
    30     return 0;
    31 }

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

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/a7f43caead3a41ab8dbdece1a63f62d8.png