• atcoder abc357

    A Sanitize Hands 

    问题：

    思路：前缀和，暴力，你想咋做就咋做

    代码：

    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. const int N = 2e5 + 10;
    6.  
    7. int n, m;
    8. int a[N];
    9.  
    10. int main() {
    11.     cin >> n >> m;
    12.     for(int i = 1; i <= n; i ++ ) {
    13.         cin >> a[i];
    14.     }
    15.     
    16.     int ans = 0;
    17.     for(int i = 1; i <= n; i ++ ) {
    18.         m -= a[i];
    19.         ans = i;
    20.         if(m <= 0) break;
    21.     }
    22.     
    23.     if(m < 0) cout << ans - 1;
    24.     else cout << ans;
    25.     return 0;    
    26. }

    B Uppercase and Lowercase

    问题：

    思路：大小写转换，这里有个问题，为什么我的转换最后都变成数字了，先留个疑问

    代码：

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. using namespace std;
    6.  
    7. const int N = 2e5 + 10;
    8.  
    9. string str;
    10.  
    11. int main() {
    12.     cin >> str;
    13.     int cnt1 = 0, cnt2 = 0;
    14.     for(auto t: str) {
    15.         if(t >= 'a' && t <= 'z') cnt1 ++;
    16.         else cnt2 ++;
    17.     }
    18.     
    19.     if(cnt1 >= cnt2)
    20.     transform(str.begin(),str.end(),str.begin(),::tolower);
    21.     else 
    22.     transform(str.begin(),str.end(),str.begin(),::toupper);
    23.     cout<
    24.     return 0;
    25. }

    C Sierpinski carpet

    问题：

    思路：阴间题，第一眼递归，但是不想求太多坐标，于是想到把图全变成‘#’最后填充'.'

    代码：

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. using namespace std;
    6.  
    7. const int N = pow(3, 6) + 10;
    8.  
    9. char g[N][N];
    10. int n;
    11.  
    12. int main() {
    13.     cin >> n;
    14.     int len = pow(3, n);
    15.     for(int i = 1; i <= len; i ++ ) {
    16.         for(int j = 1; j <= len; j ++ ) {
    17.             g[i][j] = '#';
    18.         }
    19.     }
    20.     
    21.     for(int level = 1; level <= n; level ++ ) {
    22.         for(int i = 1 + pow(3, level - 1); i <= len; i += pow(3, level)) {
    23.             for(int j = 1 + pow(3, level - 1); j <= len; j += pow(3, level)) {
    24.                 for(int k = i; k <= i + pow(3, level - 1) - 1; k ++ ) {
    25.                     for(int u = j; u <= j + pow(3, level - 1) - 1; u ++ ) {
    26.                         g[k][u] = '.';
    27.                     }
    28.                 }
    29.             }
    30.         }
    31.     }
    32.     
    33.     for(int i = 1; i <= len; i ++ ) {
    34.         for(int j = 1; j <= len; j ++ ) {
    35.             cout << g[i][j];
    36.         }
    37.         cout << endl;
    38.     }
    39.     return 0;
    40. }

    D 88888888

    问题：

    思路：逆元，快速幂，对原式子变形后发现最后的结果实际上就是x 乘上一个等比数列，这是碰见的第一道逆元的题目，也明确了我对逆元的认识，由于 a / b % mod != (a % mod/ b % mod) % mod，而直接除的话会造成精度丢失，因此我们可以把除法变成乘法，根据费马小定理如果b和p互质，那么b的逆元就等于b ^ p - 2 因此可以快速幂求逆元

    代码：
     

    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. const int mod = 998244353;
    6.  
    7. long long x;
    8.  
    9. int get(long long a) {
    10.     int cnt = 0;
    11.     while(a) {
    12.         a /= 10;
    13.         cnt ++;
    14.     }
    15.     return cnt;
    16. }
    17.  
    18. long long qmi(long long a, long long b) {
    19.     long long res = 1;
    20.     while(b) {
    21.         if(b & 1) res = ((res % mod) * (a % mod)) % mod;
    22.         b >>= 1;
    23.         a = (a % mod * a % mod) % mod;
    24.     }
    25.     return res;
    26. }
    27.  
    28. int main() {
    29.     cin >> x;
    30.     int len = get(x);
    31.     long long part1 = x % mod;
    32.     long long a = qmi(10, (long long)len);
    33.     long long b = qmi(a, x);
    34.     b --;
    35.     long long c = qmi(a - 1, 998244353 - 2);
    36.     long long part2 = (b % mod * c % mod) % mod;
    37.     cout << (part1 * part2) % mod;
    38.     return 0;
    39. }

    E Reachability in Functional Graph

    问题：

    思路：考虑如果题目是一颗树的话那么直接一个记忆化即可，但是该题会出现环，因此考虑缩点，记得开long long

    据说这是基环树板子，回头学一下基环树

    代码：

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. using namespace std;
    7.  
    8. const int N = (2e5 + 10) * 2;
    9.  
    10. stack<int> stk;
    11. int n;
    12. int val[N], ne[N], h[N], idx;
    13. int dfn[N], low[N], id[N], _size[N], scc_cnt, ts;
    14. int cnt[N];
    15. bool ins[N], st[N];
    16. long long ans = 0;
    17.  
    18. void add(int a, int b) {
    19.     val[idx] = b;
    20.     ne[idx] = h[a];
    21.     h[a] = idx ++;
    22. }
    23.  
    24. void tarjan(int u) {
    25.     dfn[u] = low[u] = ++ ts;
    26.     stk.push(u);
    27.     ins[u] = true;
    28.     for(int i = h[u]; i != -1; i = ne[i]) {
    29.         int j = val[i];
    30.         if(!dfn[j]) {
    31.             tarjan(j);
    32.             low[u] = min(low[u], low[j]);
    33.         } else if(ins[j]) low[u] = min(low[u], dfn[j]);
    34.     }
    35.     
    36.     if(dfn[u] == low[u]) {
    37.         ++ scc_cnt;
    38.         int y;
    39.         do {
    40.             y = stk.top();
    41.             stk.pop();
    42.             ins[y] = false;
    43.             id[y] = scc_cnt;
    44.             _size[scc_cnt] ++;
    45.         } while (y != u);
    46.     }
    47. }
    48.  
    49. void dfs(int u) {
    50.     for(int i = h[u]; i != -1; i = ne[i]) {
    51.         int j = val[i];
    52.         if(!st[j]) {
    53.             dfs(j);
    54.             st[j] = true;
    55.         }
    56.         cnt[u] += cnt[j];
    57.         ans += _size[u] * cnt[j];
    58.     }
    59. }
    60.  
    61. int main() {
    62.     memset(h, -1, sizeof h);
    63.     cin >> n;
    64.     scc_cnt = n;
    65.     for(int i = 1; i <= n; i ++ ) {
    66.         int x;
    67.         cin >> x;
    68.         add(i, x);
    69.     }
    70.     
    71.     for(int i = 1; i <= n; i ++ ) if(!dfn[i]) tarjan(i);
    72.     for(int i = 1; i <= n; i ++ ) cnt[id[i]] = _size[id[i]];
    73.     mapint, int>, int> ma;
    74.     for(int i = 1; i <= n; i ++ ) {
    75.         for(int j = h[i]; j != -1; j = ne[j]) {
    76.             int k = val[j];
    77.             if(id[i] != id[k] && !ma[{i, k}]) {
    78.                 add(id[i], id[k]);
    79.                 ma[{i, k}] ++;
    80.             }
    81.         }
    82.     }
    83.     
    84.     memset(st, 0, sizeof st);
    85.     for(int i = scc_cnt; i > n; i -- ) {
    86.         if(!st[i]) {
    87.             st[i] = true;
    88.             dfs(i);
    89.         }
    90.     }
    91.     for(int i = scc_cnt; i > n; i -- ) ans += (long long)_size[i] * (_size[i] - 1);
    92.     cout << ans + n;
    93.     return 0;
    94. }

    F two sequence queries

    题目：

    思路：对sigema a*b做一点变形 设a加上了x，b加上了y 

    原式 = sigema (a + x) (b + y) = sigema a * b + y * a + x * b + x * y

    于是题目变成了区间修改区间查询，显然线段树lazytag板子

    代码：这里代码只a了21个数据，应该是哪里没有mod到位或者什么细节没有注意到，短时间内不改了，到期末了

    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. const int N = 2e5 + 10;
    6. const int mod = 998244353;
    7.  
    8. int n, m;
    9. struct node{
    10.     unsigned long long l, r;
    11.     unsigned long long suma, sumb, sumab;
    12.     unsigned long long taga, tagb;
    13. }tr[4 * N];
    14.  
    15. void pushup(int u) {
    16.     tr[u].suma = (tr[u << 1].suma + tr[u << 1 | 1].suma) % mod;
    17.     tr[u].sumb = (tr[u << 1].sumb + tr[u << 1 | 1].sumb) % mod;
    18.     tr[u].sumab = (tr[u << 1].sumab + tr[u << 1 | 1].sumab) % mod;
    19. }
    20.  
    21. void pushdown(int u) {
    22.     tr[u << 1].sumab = (tr[u << 1].sumab + tr[u].taga * tr[u << 1].sumb + tr[u].tagb * tr[u << 1].suma + tr[u].taga * tr[u].tagb * (tr[u << 1].r - tr[u << 1].l + 1)) % mod;
    23.     tr[u << 1 | 1].sumab = (tr[u << 1 | 1].sumab + tr[u].taga * tr[u << 1 | 1].sumb + tr[u].tagb * tr[u << 1 | 1].suma + tr[u].taga * tr[u].tagb * (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1)) % mod;
    24.  
    25.     tr[u << 1].suma = (tr[u << 1].suma + (tr[u << 1].r - tr[u << 1].l + 1) * tr[u].taga) % mod;
    26.     tr[u << 1 | 1].suma = (tr[u << 1 | 1].suma + (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tr[u].taga) % mod;
    27.     tr[u << 1].taga = (tr[u << 1].taga + tr[u].taga) % mod;
    28.     tr[u << 1 | 1].taga = (tr[u << 1 | 1].taga + tr[u].taga) % mod;
    29.     tr[u].taga = 0;
    30.     tr[u << 1].sumb = (tr[u << 1].sumb + (tr[u << 1].r - tr[u << 1].l + 1) * tr[u].tagb) % mod;
    31.     tr[u << 1 | 1].sumb = (tr[u << 1 | 1].sumb + (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tr[u].tagb) % mod;
    32.     tr[u << 1].tagb = (tr[u << 1].tagb + tr[u].tagb) % mod;
    33.     tr[u << 1 | 1].tagb = (tr[u << 1 | 1].tagb + tr[u].tagb) % mod;
    34.     tr[u].tagb = 0;
    35. }
    36.  
    37. void build(int u, int l, int r) {
    38.     tr[u].l = l, tr[u].r = r;
    39.     if(l == r) return;
    40.     int mid = l + r >> 1;
    41.     build(u << 1, l, mid);
    42.     build(u << 1 | 1, mid + 1, r);
    43. }
    44.  
    45. void add(int u, int p, int x, int type) {
    46.     if(tr[u].l == tr[u].r) {
    47.         if(type == 1) tr[u].suma = x;
    48.         else if(type == 2) tr[u].sumb = x;
    49.         tr[u].sumab = (tr[u].suma * tr[u].sumb) % mod;
    50.     } else {
    51.         int mid = tr[u].l + tr[u].r >> 1;
    52.         if(p <= mid) add(u << 1, p, x, type);
    53.         else add(u << 1 | 1, p, x, type);
    54.         pushup(u);
    55.     }
    56. }
    57.  
    58. void modify(int u, int l, int r, unsigned long long d, int type) {
    59.     if(tr[u].l >= l && tr[u].r <= r) {
    60.         if(type == 1) {
    61.             tr[u].suma = (tr[u].suma + d * (tr[u].r - tr[u].l + 1)) % mod;
    62.             tr[u].taga = (tr[u].taga + d) % mod;
    63.             tr[u].sumab = (tr[u].sumab + d * tr[u].sumb) % mod;
    64.         } else if(type == 2) {
    65.             tr[u].sumb = (tr[u].sumb + d * (tr[u].r - tr[u].l + 1)) % mod;
    66.             tr[u].tagb = (tr[u].tagb + d) % mod;
    67.             tr[u].sumab = (tr[u].sumab + d * tr[u].suma) % mod;
    68.         }
    69.     } else {
    70.         pushdown(u);
    71.         int mid = tr[u].l + tr[u].r >> 1;
    72.         if(mid >= l) modify(u << 1, l, r, d, type);
    73.         if(mid < r) modify(u << 1 | 1, l, r, d, type);
    74.         pushup(u);
    75.     }
    76. }
    77.  
    78. long long query(int u, int l, int r) {
    79.     if(tr[u].l >= l && tr[u].r <= r) {
    80.         return tr[u].sumab;
    81.     } else {
    82.         pushdown(u);
    83.         int mid = tr[u].l + tr[u].r >> 1;
    84.         long long res = 0;
    85.         if(mid >= l) res = query(u << 1, l, r);
    86.         if(mid < r) res = (res + query(u << 1 | 1, l, r)) % mod;
    87.         return res;
    88.     }
    89. }
    90.  
    91. int main() {
    92.     cin >> n >> m;
    93.     build(1, 1, n);
    94.     for(int i = 1; i <= n; i ++ ) {
    95.         int x;
    96.         cin >> x;
    97.         add(1, i, x % mod, 1);
    98.     }    
    99.     for(int i = 1; i <= n; i ++ ) {
    100.         int x;
    101.         cin >> x;
    102.         add(1, i, x % mod, 2);
    103.     }
    104.  
    105.     while(m -- ) {
    106.         int op;
    107.         cin >> op;
    108.         if(op == 1) {
    109.             int l, r;
    110.             unsigned long long d;
    111.             cin >> l >> r >> d;
    112.             modify(1, l, r, d % mod, 1);
    113.         } else if(op == 2) {
    114.             int l, r, d;
    115.             cin >> l >> r >> d;
    116.             modify(1, l, r, d % mod, 2);
    117.         } else {
    118.             int l, r;
    119.             cin >> l >> r;
    120.             cout << query(1, l, r) << endl;
    121.         }
    122.     }
    123.     return 0;
    124. }

  • 相关阅读:
    opensips开启python支持
    03 vi编辑器
    剑指offer面试题36 数组中的逆序对
    Vue基础面试题（二）
    switch里面，一开头就放default是什么意思
    多目标优化问题的研究概述（Matlab代码实现）
    c++（15）静态成员变量、静态成员函数、static占用大小
    Container容器
    Python configparser模块
    Python3-excel文档操作（六）：利用openpyxl库处理excel表格：Excel可视化，折线图
  • 原文地址：https://blog.csdn.net/2201_75845839/article/details/139566862