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

一给  金牌会员 | 2024-7-14 12:18:51 | 显示全部楼层 | 阅读模式
打印 上一主题 下一主题
楼主

主题 786|帖子 786|积分 2358

A - Partition

A题传送门
这道题不难发现，如果数字最终的和大于等于K，我们可以把这个原数列从大到小排序，得到最终答案。
如果和小于K，则从小到大排序，同时验证是否符合要求。
  1. #pragma GCC optimize(3)  //O2优化开启
  2. #include<bits/stdc++.h>
  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 <ext/pb_ds/assoc_container.hpp>
  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<int, int, chash> hash_t;
  31. constexpr ll mod = 1e9 + 7;                                //此处为自动取模的数
  32. class modint{
  33.     ll num;
  34. public:
  35.     modint(ll num = 0) :num(num % mod){}
  37.     ll val() const {
  38.         return num;
  39.     }
  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.     }
  51.     constexpr ll norm(ll num) const {
  52.         if (num < 0) num += mod;
  53.         if (num >= mod) num -= mod;
  54.         return num;
  55.     }
  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. };
  71. int n,k;
  72. int a[500005];
  73. void icealsoheat(){
  74.    
  75.     cin>>n>>k;
  77.     for(int i=1;i<=n;i++)cin>>a[i];
  79.     // sort(a+1,a+1+n);
  80.    
  82.     if(k<=0){
  83.         int sum=0;
  84.         for(int i=1;i<=n;i++){
  85.             sum+=a[i];
  86.         }
  87.         if(sum>=k){
  88.             cout<<"Yes\n";
  89.             sort(a+1,a+1+n,[&](int x,int y){return x>y;});
  90.             for(int i=1;i<=n;i++){
  91.                 cout<<a[i]<<" ";
  92.             }
  93.         }
  94.         else{
  95.             cout<<"No\n";
  96.         }
  98.     }
  99.     else{
  100.         cout<<"Yes\n";
  101.         sort(a+1,a+1+n);
  102.         for(int i=1;i<=n;i++){
  103.             cout<<a[i]<<" ";
  104.         }
  106.     }
  107.    
  109. }
  110. signed main(){
  111.     ios::sync_with_stdio(false);          //int128不能用快读！！！！！！
  112.     cin.tie();
  113.     cout.tie();
  114.     int _yq;
  115.     _yq=1;
  116.     // cin>>_yq;
  117.     while(_yq--){
  118.         icealsoheat();
  119.     }
  120. }
  121. //
  122. //⠀⠀⠀             ⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
  123. //⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀ ⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
  124. //⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆
  125. //⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀ ⠛⠿⠿⣿⠃
  126. //⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
  127. //⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀ ⠀⠙⢿⡇
  128. //⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
  129. //⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
  130. //⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
  131. //⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
  132. //⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
  133. //⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀
  134. //
复制代码
B - Between B and B

B题传送门
想了半天没搞出来，厥后看了大佬的题解提示才名顿开。
这题可以用dp的头脑去求，通过题目标数据，我们可以大胆去猜，首先复杂度肯定要带个n，其次m仅仅等于10也让我们可以发散性的去想到状压的                                             2                            10                                       2^{10}                  210的复杂度，还可以再添一个m，以是最终的复杂度最多为O(nmlog                                             2                            10                                       2^{10}                  210)。
我们可通过状压来枚举各个数是否符合条件可以放入的情况。比如第i位，假如我向这个数位放入的数字是j，首先，放入j的条件条件是在当前位数和上一个放入j的位数之间我们放入了至少一个a[j]，此时j可以放入，同时，放入了j后，j会使得后面全部a[x]=j的数字都可以放入，我们可以通过状态去枚举各个数字是否可以放入，能放入的话对应的二进制位数就是1，不能放入就是0。
  1. #pragma GCC optimize(3)  //O2优化开启
  2. #include<bits/stdc++.h>
  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 <ext/pb_ds/assoc_container.hpp>
  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<int, int, chash> hash_t;
  31. constexpr ll mod = 998244353;                                //此处为自动取模的数
  32. class modint{
  33.     ll num;
  34. public:
  35.     modint(ll num = 0) :num(num % mod){}
  37.     ll val() const {
  38.         return num;
  39.     }
  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.     }
  51.     constexpr ll norm(ll num) const {
  52.         if (num < 0) num += mod;
  53.         if (num >= mod) num -= mod;
  54.         return num;
  55.     }
  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. };
  71. int n,m;
  72. int a[50005];
  73. modint dp[20005][2000];
  74. int id[50005];
  75. void icealsoheat(){
  76.     int m,n;
  78.     cin>>n>>m;
  80.     for(int i=1;i<=n;i++)cin>>a[i];
  82.     for(int i=1;i<=n;i++){
  83.         id[a[i]]|=(1<<(i-1));
  84.     }
  86.     // for(int i=0;i<n;i++)dp[0][1<<i]=1;
  87.     dp[0][(1<<n)-1]=1;
  88.    
  89.     for(int i=1;i<=m;i++){
  91.         for(int j=1;j<=n;j++){
  93.             for(int o=0;o<(1<<n);o++){
  95.                 if(o>>(j-1)&1){
  96.                     
  97.                     int x=o;
  99.                     x-=(1<<(j-1));
  100.                     x|=id[j];
  101.                     dp[i][x]+=dp[i-1][o];
  103.                 }
  105.             }
  107.         }
  109.     }
  111.     modint ans=0;
  113.     for(int i=0;i<(1<<n);i++)ans+=dp[m][i];
  115.     cout<<ans;
  117. }
  118. signed main(){
  119.     ios::sync_with_stdio(false);          //int128不能用快读！！！！！！
  120.     cin.tie();
  121.     cout.tie();
  122.     int _yq;
  123.     _yq=1;
  124.     // cin>>_yq;
  125.     while(_yq--){
  126.         icealsoheat();
  127.     }
  128. }
  129. //
  130. //⠀⠀⠀             ⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
  131. //⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀ ⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
  132. //⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆
  133. //⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀ ⠛⠿⠿⣿⠃
  134. //⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
  135. //⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀ ⠀⠙⢿⡇
  136. //⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
  137. //⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
  138. //⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
  139. //⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
  140. //⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
  141. //⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀
  142. //
复制代码
C - Beware of Overflow

C题传送门
还是我太菜了，看题目都费劲，最后还是不争气的看了题解，竟然题解把查询放入了排序的cmp函数中，确实还是我本身的思维太范围了，容易想到的是，我们把全部的数从小到大排序，然后头尾相加，再把相加的数通过二分按次序放入这个数中，重复上述操作，知道符合最后条件为止，O(nlogn)的复杂度，以是不会超过25000次扣问。
  1. #pragma GCC optimize(3)  //O2优化开启
  2. #include<bits/stdc++.h>
  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 <ext/pb_ds/assoc_container.hpp>
  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<int, int, chash> hash_t;
  31. constexpr ll mod = 998244353;                                //此处为自动取模的数
  32. class modint{
  33.     ll num;
  34. public:
  35.     modint(ll num = 0) :num(num % mod){}
  37.     ll val() const {
  38.         return num;
  39.     }
  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.     }
  51.     constexpr ll norm(ll num) const {
  52.         if (num < 0) num += mod;
  53.         if (num >= mod) num -= mod;
  54.         return num;
  55.     }
  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. int n;
  71. bool cmp(int a,int b){
  72.     cout<<"? "<<a<<" "<<b<<endl;
  73.     int s;
  74.     cin>>s;
  75.     return s;
  76. }
  77. // bool check(int p,int o){
  78. //     cout<<"? "<<p<<" "<<o<<endl;
  79. //     int x;
  80. //     cin>>x;
  81. //     return x==0;
  82. // }
  83. void icealsoheat(){
  84.     cin>>n;
  85.     vector<int>ve;
  86.     for(int i=1;i<=n;i++){
  87.         ve.push_back(i);
  88.     }
  90.     sort(ve.begin(),ve.end(),cmp);
  92.     while(ve.size()>1){
  94.         int le=ve[0];
  96.         int re=ve.back();
  97.         // int x=le+re;
  98.         cout<<"+ "<<le<<" "<<re<<endl;
  99.         int x;
  100.         cin>>x;
  101.         ve.erase(ve.begin());
  102.         ve.pop_back();
  103.         // cout<<"+"<<i
  104.         if(ve.size()==0){
  105.             break;
  106.         }
  107.         int l=0,r=ve.size()-1;
  108.         int mid;
  109.         while(l<r){
  110.             mid=(l+r)>>1;
  111.             if(cmp(x,ve[mid]))r=mid;
  112.             else l=mid+1;
  113.         }
  114.         if(!cmp(x,ve[l]))l++;
  116.         ve.insert(ve.begin()+l,x);
  118.     }
  119.     cout<<"!"<<endl;
  120. }
  121. signed main(){
  122.     ios::sync_with_stdio(false);          //int128不能用快读！！！！！！
  123.     cin.tie();
  124.     cout.tie();
  125.     int _yq;
  126.     _yq=1;
  127.     // cin>>_yq;
  128.     while(_yq--){
  129.         icealsoheat();
  130.     }
  131. }
  132. //
  133. //⠀⠀⠀             ⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
  134. //⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀ ⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
  135. //⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆
  136. //⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀ ⠛⠿⠿⣿⠃
  137. //⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
  138. //⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀ ⠀⠙⢿⡇
  139. //⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
  140. //⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
  141. //⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
  142. //⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
  143. //⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
  144. //⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀
  145. //
复制代码
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
回复

使用道具 举报

0 个回复

倒序浏览
返回列表

快速回复

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

一给

金牌会员
这个人很懒什么都没写!

楼主热帖

标签云

挺好的 服务器
微信订阅号
微信服务号
微信客服
小程序
H5
关于我们 商务合作 网站地图
©Copyright 2022-2024 杭州祥升科技有限公司 版权所有 浙ICP备20004199号
快速回复 返回顶部 返回列表