ToB企服应用市场:ToB评测及商务社交产业平台

标题: AC修炼计划（AtCoder Regular Contest 179）A~C [打印本页]

---

作者: 一给    时间: 2024-7-14 12:18
标题: AC修炼计划（AtCoder Regular Contest 179）A~C
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企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4