• AC修炼计划（AtCoder Regular Contest 180） A~C

    A - ABA and BAB

    A - ABA and BAB (atcoder.jp)

    这道题我一开始想复杂了，一直在想怎么dp，没注意到其实是个很简单的规律题。

    我们可以发现我们住需要统计一下类似ABABA这样不同字母相互交替的所有子段的长度，而每个字段的的情况有（长度+1）/2种，最后所有字段情况的乘积就是最终答案。

    1. #pragma GCC optimize(3)  //O2优化开启
    2. #include
    3. using namespace std;
    4. #define int long long
    5. typedef long long ll;
    6. typedef unsigned long long ull;
    7. typedef pair<int,int> PII;
    8. // const int mod=1e9+7;
    9. const int MX=0x3f3f3f3f3f3f3f3f; 
    10. //inline int read()                     //快读
    11. //{
    12. //    int xr=0,F=1; char cr;
    13. //    while(cr=getchar(),cr<'0'||cr>'9') if(cr=='-') F=-1;
    14. //    while(cr>='0'&&cr<='9')
    15. //        xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();
    16. //    return xr*F;
    17. //}
    18. //void write(int x)                     //快写
    19. //{
    20. //    if(x<0) putchar('-'),x=-x;
    21. //    if(x>9) write(x/10); putchar(x%10+'0');
    22. //}
    23. // 比 unordered_map 更快的哈希表
    24. // #include 
    25. // using namespace __gnu_pbds;
    26. // const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
    27. // struct chash {
    28. //     int operator()(int x) const { return x ^ RANDOM; }
    29. // };
    30. // typedef gp_hash_table hash_t;
    31. constexpr ll mod = 1e9 + 7;                                //此处为自动取模的数
    32. class modint{
    33.     ll num;
    34. public:
    35.     modint(ll num = 0) :num(num % mod){}
    36.  
    37.     ll val() const {
    38.         return num;
    39.     }
    40.  
    41.     modint pow(ll other) {
    42.         modint res(1), temp = *this;
    43.         while(other) {
    44.             if(other & 1) res = res * temp;
    45.             temp = temp * temp;
    46.             other >>= 1;
    47.         }
    48.         return res;
    49.     }
    50.  
    51.     constexpr ll norm(ll num) const {
    52.         if (num < 0) num += mod;
    53.         if (num >= mod) num -= mod;
    54.         return num;
    55.     }
    56.  
    57.     modint inv(){ return pow(mod - 2); }
    58.     modint operator+(modint other){ return modint(num + other.num); }
    59.     modint operator-(){ return { -num }; }
    60.     modint operator-(modint other){ return modint(-other + *this); }
    61.     modint operator*(modint other){ return modint(num * other.num); }
    62.     modint operator/(modint other){ return *this * other.inv(); }
    63.     modint &operator*=(modint other) { num = num * other.num % mod; return *this; }
    64.     modint &operator+=(modint other) { num = norm(num + other.num); return *this; }
    65.     modint &operator-=(modint other) { num = norm(num - other.num); return *this; }
    66.     modint &operator/=(modint other) { return *this *= other.inv(); }
    67.     friend istream& operator>>(istream& is, modint& other){ is >> other.num; other.num %= mod; return is; }
    68.     friend ostream& operator<<(ostream& os, modint other){ other.num = (other.num + mod) % mod; return os << other.num; }
    69. };
    70.  
    71. int n;
    72. string s;
    73. void icealsoheat(){
    74.     
    75.     cin>>n;
    76.     cin>>s;
    77.     s=" "+s;
    78.     int res=1;
    79.     modint ans=1;
    80.     for(int i=2;i<=n;i++){
    81.         if(s[i]!=s[i-1]){
    82.             res++;
    83.         }
    84.         else{
    85.             if(res>=3){
    86.                 ans*=(res+1)/2;
    87.             }
    88.             res=1;
    89.         }
    90.  
    91.     }
    92.     if(res>=3){
    93.         ans*=(res+1)/2;
    94.     }
    95.  
    96.     cout<
    97. }
    98. signed main(){
    99.     ios::sync_with_stdio(false);          //int128不能用快读！！！！！！
    100.     cin.tie();
    101.     cout.tie();
    102.     int _yq;
    103.     _yq=1;
    104.     // cin>>_yq;
    105.     while(_yq--){
    106.         icealsoheat();
    107.     }
    108. }
    109. //
    110. //⠀⠀⠀             ⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
    111. //⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀ ⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
    112. //⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆
    113. //⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀ ⠛⠿⠿⣿⠃
    114. //⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
    115. //⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀ ⠀⠙⢿⡇
    116. //⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
    117. //⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
    118. //⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
    119. //⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
    120. //⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
    121. //⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀
    122. //

    B - Improve Inversions

    B - Improve Inversions (atcoder.jp)

    这题确实不好想，但是get到点儿了就会觉得其实也不难。

    我们需要尽可能的把逆序对最大化，从样例三我们可以发现，我们不妨确立左边一个要交换的下标i，然后找下标大于等于i+k，数值从大到小的找小于ai的数字，并依次与i的数字进行交换。为了尽可能减少替换的影响，我们按数值从小到大的次序去找这个下标i，从而参与上述的交换。因为我们是按从小到大的顺序的，所以小的数字参与交换并不会影响后面大的数字该交换的逆序对。

    1. #pragma GCC optimize(3)  //O2优化开启
    2. #include
    3. using namespace std;
    4. #define int long long
    5. typedef long long ll;
    6. typedef unsigned long long ull;
    7. typedef pair<int,int> PII;
    8. // const int mod=1e9+7;
    9. const int MX=0x3f3f3f3f3f3f3f3f; 
    10. //inline int read()                     //快读
    11. //{
    12. //    int xr=0,F=1; char cr;
    13. //    while(cr=getchar(),cr<'0'||cr>'9') if(cr=='-') F=-1;
    14. //    while(cr>='0'&&cr<='9')
    15. //        xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();
    16. //    return xr*F;
    17. //}
    18. //void write(int x)                     //快写
    19. //{
    20. //    if(x<0) putchar('-'),x=-x;
    21. //    if(x>9) write(x/10); putchar(x%10+'0');
    22. //}
    23. // 比 unordered_map 更快的哈希表
    24. // #include 
    25. // using namespace __gnu_pbds;
    26. // const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
    27. // struct chash {
    28. //     int operator()(int x) const { return x ^ RANDOM; }
    29. // };
    30. // typedef gp_hash_table hash_t;
    31. // constexpr ll mod = 1e9 + 7;                                //此处为自动取模的数
    32. // class modint{
    33. //     ll num;
    34. // public:
    35. //     modint(ll num = 0) :num(num % mod){}
    36.  
    37. //     ll val() const {
    38. //         return num;
    39. //     }
    40.  
    41. //     modint pow(ll other) {
    42. //         modint res(1), temp = *this;
    43. //         while(other) {
    44. //             if(other & 1) res = res * temp;
    45. //             temp = temp * temp;
    46. //             other >>= 1;
    47. //         }
    48. //         return res;
    49. //     }
    50.  
    51. //     constexpr ll norm(ll num) const {
    52. //         if (num < 0) num += mod;
    53. //         if (num >= mod) num -= mod;
    54. //         return num;
    55. //     }
    56.  
    57. //     modint inv(){ return pow(mod - 2); }
    58. //     modint operator+(modint other){ return modint(num + other.num); }
    59. //     modint operator-(){ return { -num }; }
    60. //     modint operator-(modint other){ return modint(-other + *this); }
    61. //     modint operator*(modint other){ return modint(num * other.num); }
    62. //     modint operator/(modint other){ return *this * other.inv(); }
    63. //     modint &operator*=(modint other) { num = num * other.num % mod; return *this; }
    64. //     modint &operator+=(modint other) { num = norm(num + other.num); return *this; }
    65. //     modint &operator-=(modint other) { num = norm(num - other.num); return *this; }
    66. //     modint &operator/=(modint other) { return *this *= other.inv(); }
    67. //     friend istream& operator>>(istream& is, modint& other){ is >> other.num; other.num %= mod; return is; }
    68. //     friend ostream& operator<<(ostream& os, modint other){ other.num = (other.num + mod) % mod; return os << other.num; }
    69. // };
    70.  
    71. int n,k;
    72. int a[200005];
    73. int p[200005];
    74. vectorans;
    75. void icealsoheat(){
    76.     
    77.     cin>>n>>k;
    78.     int bns=0;
    79.     for(int i=1;i<=n;i++)cin>>a[i],p[a[i]]=i;
    80.  
    81.     for(int i=1;i<=n;i++){
    82.  
    83.         int id=p[i];
    84.         int x=i;
    85.         for(int j=i-1;j>=1;j--){
    86.  
    87.             if(p[j]>=id+k){
    88.                 // cout<
    89.                 ans.push_back({p[x],p[j]});
    90.                 a[id]=j;
    91.                 a[p[j]]=x;
    92.                 swap(p[x],p[j]);
    93.                 x=j;
    94.  
    95.             }
    96.  
    97.         }
    98.  
    99.     }
    100.  
    101.     cout<size()<<"\n";
    102.     for(auto [i,j]:ans){
    103.         cout<" "<"\n";
    104.     }
    105.  
    106.     // for(int i=1;i<=n;i++){
    107.     //     cout<
    108.     // }
    109.  
    110. }
    111. signed main(){
    112.     ios::sync_with_stdio(false);          //int128不能用快读！！！！！！
    113.     cin.tie();
    114.     cout.tie();
    115.     int _yq;
    116.     _yq=1;
    117.     // cin>>_yq;
    118.     while(_yq--){
    119.         icealsoheat();
    120.     }
    121. }
    122. //
    123. //⠀⠀⠀             ⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
    124. //⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀ ⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
    125. //⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆
    126. //⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀ ⠛⠿⠿⣿⠃
    127. //⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
    128. //⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀ ⠀⠙⢿⡇
    129. //⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
    130. //⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
    131. //⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
    132. //⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
    133. //⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
    134. //⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀
    135. //

    C - Subsequence and Prefix Sum

    C - Subsequence and Prefix Sum (atcoder.jp)

    一道非常巧妙的dp题，他的状态转移非常的奇妙。

    我们考虑前i位的数字对后面数字的贡献值。可以分成两种情况。

    1.第i位数字没有被选中

    2.第i位数字被选中

    当第i位数字被选中时，每一个位数i它所能合成的状态数字都对后面i+1到n的数字有相应的贡献。而这里面0的情况比较特殊，如果第i位的合成数字是0，其实不会改变下一个选中的数字。

    这里面有一种情况比较特殊

    例如1 -1 5 5 .........

    这里我们会发现，我们选择1和-1后，选择第3个5和第4个5的情况是重复的，所以我们要想办法将它去重。

    1. #pragma GCC optimize(3)  //O2优化开启
    2. #include
    3. using namespace std;
    4. #define int long long
    5. typedef long long ll;
    6. typedef unsigned long long ull;
    7. typedef pair<int,int> PII;
    8. // const int mod=1e9+7;
    9. const int MX=0x3f3f3f3f3f3f3f3f; 
    10. //inline int read()                     //快读
    11. //{
    12. //    int xr=0,F=1; char cr;
    13. //    while(cr=getchar(),cr<'0'||cr>'9') if(cr=='-') F=-1;
    14. //    while(cr>='0'&&cr<='9')
    15. //        xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();
    16. //    return xr*F;
    17. //}
    18. //void write(int x)                     //快写
    19. //{
    20. //    if(x<0) putchar('-'),x=-x;
    21. //    if(x>9) write(x/10); putchar(x%10+'0');
    22. //}
    23. // 比 unordered_map 更快的哈希表
    24. // #include 
    25. // using namespace __gnu_pbds;
    26. // const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
    27. // struct chash {
    28. //     int operator()(int x) const { return x ^ RANDOM; }
    29. // };
    30. // typedef gp_hash_table hash_t;
    31. constexpr ll mod = 1e9 + 7;                                //此处为自动取模的数
    32. class modint{
    33.     ll num;
    34. public:
    35.     modint(ll num = 0) :num(num % mod){}
    36.  
    37.     ll val() const {
    38.         return num;
    39.     }
    40.  
    41.     modint pow(ll other) {
    42.         modint res(1), temp = *this;
    43.         while(other) {
    44.             if(other & 1) res = res * temp;
    45.             temp = temp * temp;
    46.             other >>= 1;
    47.         }
    48.         return res;
    49.     }
    50.  
    51.     constexpr ll norm(ll num) const {
    52.         if (num < 0) num += mod;
    53.         if (num >= mod) num -= mod;
    54.         return num;
    55.     }
    56.  
    57.     modint inv(){ return pow(mod - 2); }
    58.     modint operator+(modint other){ return modint(num + other.num); }
    59.     modint operator-(){ return { -num }; }
    60.     modint operator-(modint other){ return modint(-other + *this); }
    61.     modint operator*(modint other){ return modint(num * other.num); }
    62.     modint operator/(modint other){ return *this * other.inv(); }
    63.     modint &operator*=(modint other) { num = num * other.num % mod; return *this; }
    64.     modint &operator+=(modint other) { num = norm(num + other.num); return *this; }
    65.     modint &operator-=(modint other) { num = norm(num - other.num); return *this; }
    66.     modint &operator/=(modint other) { return *this *= other.inv(); }
    67.     friend istream& operator>>(istream& is, modint& other){ is >> other.num; other.num %= mod; return is; }
    68.     friend ostream& operator<<(ostream& os, modint other){ other.num = (other.num + mod) % mod; return os << other.num; }
    69. };
    70.  
    71. int n,k;
    72. int a[500005];
    73. modint dp[105][5005];
    74. modint sum[5005];
    75. void icealsoheat(){
    76.     
    77.     cin>>n;
    78.     for(int i=0;i<=20;i++)if(i!=10)sum[i]=1;
    79.     for(int i=1;i<=n;i++)cin>>a[i];
    80.  
    81.     modint ans=1;
    82.     for(int i=0;i
    83.  
    84.         dp[i][a[i]+1000]=dp[i][a[i]+1000]+sum[a[i]+10];
    85.         sum[a[i]+10]=0;
    86.  
    87.         for(int j=0;j<=2000;j++){
    88.             if(j==1000)continue;
    89.  
    90.             for(int o=i+1;o<=n;o++){
    91.                 // if(j+a[o]<0)cout<<"+++\n";
    92.                 if(j+a[o]<0)continue;
    93.                 
    94.                 dp[o][j+a[o]]+=dp[i][j];
    95.  
    96.                 ans+=dp[i][j];
    97.  
    98.             }
    99.  
    100.         }
    101.  
    102.         for(int j=0;j<=20;j++){
    103.             if(j!=10)sum[j]+=dp[i][1000];
    104.         }
    105.  
    106.     }
    107.     cout<2][1]<<"+++\n";
    108.  
    109.     cout<
    110.  
    111. }
    112. signed main(){
    113.     ios::sync_with_stdio(false);          //int128不能用快读！！！！！！
    114.     cin.tie();
    115.     cout.tie();
    116.     int _yq;
    117.     _yq=1;
    118.     // cin>>_yq;
    119.     while(_yq--){
    120.         icealsoheat();
    121.     }
    122. }
    123. //
    124. //⠀⠀⠀             ⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
    125. //⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀ ⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
    126. //⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆
    127. //⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀ ⠛⠿⠿⣿⠃
    128. //⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
    129. //⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀ ⠀⠙⢿⡇
    130. //⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
    131. //⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
    132. //⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
    133. //⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
    134. //⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
    135. //⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀
    136. //

  • 相关阅读:
    中间件（nginx，网关）对性能的影响的测试
    设计模式之状态模式
    Java学习——基本语法笔记
    el-form自定义规则后表单验证validate不生效的问题
    脊髓型颈椎病是什么？
    第8期ThreadX视频教程：应用实战，将裸机工程移植到RTOS的任务划分，驱动和应用层交互，中断DMA，C库和中间件处理等注意事项
    在农业数据集上运行VINS-fusion
    【知识点】分布式系统相关名词/概念/知识点
    Microsoft.IO.RecyclableMemoryStream源码解读
    Redis 分布式锁
  • 原文地址：https://blog.csdn.net/kyrietheshy/article/details/140312700