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

A - Partition

A题传送门
这道题不难发现，如果数字最终的和大于等于K，我们可以把这个原数列从大到小排序，得到最终答案。
如果和小于K，则从小到大排序，同时验证是否符合要求。

#pragma GCC optimize(3)  //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
// const int mod=1e9+7;
const int MX=0x3f3f3f3f3f3f3f3f; 
//inline int read()                     //快读
//{
//    int xr=0,F=1; char cr;
//    while(cr=getchar(),cr<'0'||cr>'9') if(cr=='-') F=-1;
//    while(cr>='0'&&cr<='9')
//        xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();
//    return xr*F;
//}
//void write(int x)                     //快写
//{
//    if(x<0) putchar('-'),x=-x;
//    if(x>9) write(x/10); putchar(x%10+'0');
//}
// 比 unordered_map 更快的哈希表
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
// struct chash {
//     int operator()(int x) const { return x ^ RANDOM; }
// };
// typedef gp_hash_table<int, int, chash> hash_t;
constexpr ll mod = 1e9 + 7;                                //此处为自动取模的数
class modint{ll num;
public:modint(ll num = 0) :num(num % mod){}ll val() const {return num;}modint pow(ll other) {modint res(1), temp = *this;while(other) {if(other & 1) res = res * temp;temp = temp * temp;other >>= 1;}return res;}constexpr ll norm(ll num) const {if (num < 0) num += mod;if (num >= mod) num -= mod;return num;}modint inv(){ return pow(mod - 2); }modint operator+(modint other){ return modint(num + other.num); }modint operator-(){ return { -num }; }modint operator-(modint other){ return modint(-other + *this); }modint operator*(modint other){ return modint(num * other.num); }modint operator/(modint other){ return *this * other.inv(); }modint &operator*=(modint other) { num = num * other.num % mod; return *this; }modint &operator+=(modint other) { num = norm(num + other.num); return *this; }modint &operator-=(modint other) { num = norm(num - other.num); return *this; }modint &operator/=(modint other) { return *this *= other.inv(); }friend istream& operator>>(istream& is, modint& other){ is >> other.num; other.num %= mod; return is; }friend ostream& operator<<(ostream& os, modint other){ other.num = (other.num + mod) % mod; return os << other.num; }
};int n,k;
int a[500005];
void icealsoheat(){cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];// sort(a+1,a+1+n);if(k<=0){int sum=0;for(int i=1;i<=n;i++){sum+=a[i];}if(sum>=k){cout<<"Yes\n";sort(a+1,a+1+n,[&](int x,int y){return x>y;});for(int i=1;i<=n;i++){cout<<a[i]<<" ";}}else{cout<<"No\n";}}else{cout<<"Yes\n";sort(a+1,a+1+n);for(int i=1;i<=n;i++){cout<<a[i]<<" ";}}}
signed main(){ios::sync_with_stdio(false);          //int128不能用快读！！！！！！cin.tie();cout.tie();int _yq;_yq=1;// cin>>_yq;while(_yq--){icealsoheat();}
}
//
//⠀⠀⠀             ⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀ ⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
//⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆
//⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀ ⠛⠿⠿⣿⠃
//⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀ ⠀⠙⢿⡇
//⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
//⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
//⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
//⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀
//

B - Between B and B

B题传送门

想了半天没搞出来，后来看了大佬的题解提示才恍然大悟。

这题可以用dp的思想去求，通过题目的数据，我们可以大胆去猜，首先复杂度一定要带个n，其次m仅仅等于10也让我们可以发散性的去想到状压的$2^{10}$的复杂度，还可以再添一个m，所以最终的复杂度最多为O(nmlog$2^{10}$)。
我们可通过状压来枚举各个数是否符合条件可以放入的情况。比如第i位，假如我向这个数位放入的数字是j，首先，放入j的前提条件是在当前位数和上一个放入j的位数之间我们放入了至少一个a[j]，此时j可以放入，同时，放入了j后，j会使得后面所有a[x]=j的数字都可以放入，我们可以通过状态去枚举各个数字是否可以放入，能放入的话对应的二进制位数就是1，不能放入就是0。

#pragma GCC optimize(3)  //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
// const int mod=1e9+7;
const int MX=0x3f3f3f3f3f3f3f3f; 
//inline int read()                     //快读
//{
//    int xr=0,F=1; char cr;
//    while(cr=getchar(),cr<'0'||cr>'9') if(cr=='-') F=-1;
//    while(cr>='0'&&cr<='9')
//        xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();
//    return xr*F;
//}
//void write(int x)                     //快写
//{
//    if(x<0) putchar('-'),x=-x;
//    if(x>9) write(x/10); putchar(x%10+'0');
//}
// 比 unordered_map 更快的哈希表
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
// struct chash {
//     int operator()(int x) const { return x ^ RANDOM; }
// };
// typedef gp_hash_table<int, int, chash> hash_t;
constexpr ll mod = 998244353;                                //此处为自动取模的数
class modint{ll num;
public:modint(ll num = 0) :num(num % mod){}ll val() const {return num;}modint pow(ll other) {modint res(1), temp = *this;while(other) {if(other & 1) res = res * temp;temp = temp * temp;other >>= 1;}return res;}constexpr ll norm(ll num) const {if (num < 0) num += mod;if (num >= mod) num -= mod;return num;}modint inv(){ return pow(mod - 2); }modint operator+(modint other){ return modint(num + other.num); }modint operator-(){ return { -num }; }modint operator-(modint other){ return modint(-other + *this); }modint operator*(modint other){ return modint(num * other.num); }modint operator/(modint other){ return *this * other.inv(); }modint &operator*=(modint other) { num = num * other.num % mod; return *this; }modint &operator+=(modint other) { num = norm(num + other.num); return *this; }modint &operator-=(modint other) { num = norm(num - other.num); return *this; }modint &operator/=(modint other) { return *this *= other.inv(); }friend istream& operator>>(istream& is, modint& other){ is >> other.num; other.num %= mod; return is; }friend ostream& operator<<(ostream& os, modint other){ other.num = (other.num + mod) % mod; return os << other.num; }
};int n,m;
int a[50005];
modint dp[20005][2000];
int id[50005];
void icealsoheat(){int m,n;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){id[a[i]]|=(1<<(i-1));}// for(int i=0;i<n;i++)dp[0][1<<i]=1;dp[0][(1<<n)-1]=1;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){for(int o=0;o<(1<<n);o++){if(o>>(j-1)&1){int x=o;x-=(1<<(j-1));x|=id[j];dp[i][x]+=dp[i-1][o];}}}}modint ans=0;for(int i=0;i<(1<<n);i++)ans+=dp[m][i];cout<<ans;}
signed main(){ios::sync_with_stdio(false);          //int128不能用快读！！！！！！cin.tie();cout.tie();int _yq;_yq=1;// cin>>_yq;while(_yq--){icealsoheat();}
}
//
//⠀⠀⠀             ⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀ ⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
//⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆
//⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀ ⠛⠿⠿⣿⠃
//⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀ ⠀⠙⢿⡇
//⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
//⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
//⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
//⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀
//

C - Beware of Overflow

C题传送门
还是我太菜了，看题目都费劲，最后还是不争气的看了题解，竟然题解把查询放入了排序的cmp函数中，确实还是我自己的思维太局限了，容易想到的是，我们把所有的数从小到大排序，然后头尾相加，再把相加的数通过二分按顺序放入这个数中，重复上述操作，知道符合最后条件为止，O(nlogn)的复杂度，所以不会超过25000次询问。

#pragma GCC optimize(3)  //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
// const int mod=1e9+7;
const int MX=0x3f3f3f3f3f3f3f3f; 
//inline int read()                     //快读
//{
//    int xr=0,F=1; char cr;
//    while(cr=getchar(),cr<'0'||cr>'9') if(cr=='-') F=-1;
//    while(cr>='0'&&cr<='9')
//        xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();
//    return xr*F;
//}
//void write(int x)                     //快写
//{
//    if(x<0) putchar('-'),x=-x;
//    if(x>9) write(x/10); putchar(x%10+'0');
//}
// 比 unordered_map 更快的哈希表
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
// struct chash {
//     int operator()(int x) const { return x ^ RANDOM; }
// };
// typedef gp_hash_table<int, int, chash> hash_t;
constexpr ll mod = 998244353;                                //此处为自动取模的数
class modint{ll num;
public:modint(ll num = 0) :num(num % mod){}ll val() const {return num;}modint pow(ll other) {modint res(1), temp = *this;while(other) {if(other & 1) res = res * temp;temp = temp * temp;other >>= 1;}return res;}constexpr ll norm(ll num) const {if (num < 0) num += mod;if (num >= mod) num -= mod;return num;}modint inv(){ return pow(mod - 2); }modint operator+(modint other){ return modint(num + other.num); }modint operator-(){ return { -num }; }modint operator-(modint other){ return modint(-other + *this); }modint operator*(modint other){ return modint(num * other.num); }modint operator/(modint other){ return *this * other.inv(); }modint &operator*=(modint other) { num = num * other.num % mod; return *this; }modint &operator+=(modint other) { num = norm(num + other.num); return *this; }modint &operator-=(modint other) { num = norm(num - other.num); return *this; }modint &operator/=(modint other) { return *this *= other.inv(); }friend istream& operator>>(istream& is, modint& other){ is >> other.num; other.num %= mod; return is; }friend ostream& operator<<(ostream& os, modint other){ other.num = (other.num + mod) % mod; return os << other.num; }
};
int n;
bool cmp(int a,int b){cout<<"? "<<a<<" "<<b<<endl;int s;cin>>s;return s;
}
// bool check(int p,int o){
//     cout<<"? "<<p<<" "<<o<<endl;
//     int x;
//     cin>>x;
//     return x==0;
// }
void icealsoheat(){cin>>n;vector<int>ve;for(int i=1;i<=n;i++){ve.push_back(i);}sort(ve.begin(),ve.end(),cmp);while(ve.size()>1){int le=ve[0];int re=ve.back();// int x=le+re;cout<<"+ "<<le<<" "<<re<<endl;int x;cin>>x;ve.erase(ve.begin());ve.pop_back();// cout<<"+"<<iif(ve.size()==0){break;}int l=0,r=ve.size()-1;int mid;while(l<r){mid=(l+r)>>1;if(cmp(x,ve[mid]))r=mid;else l=mid+1;}if(!cmp(x,ve[l]))l++;ve.insert(ve.begin()+l,x);}cout<<"!"<<endl;
}
signed main(){ios::sync_with_stdio(false);          //int128不能用快读！！！！！！cin.tie();cout.tie();int _yq;_yq=1;// cin>>_yq;while(_yq--){icealsoheat();}
}
//
//⠀⠀⠀             ⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀ ⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
//⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆
//⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀ ⠛⠿⠿⣿⠃
//⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀ ⠀⠙⢿⡇
//⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
//⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
//⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
//⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀
//