AC修炼计划（AtCoder Regular Contest 179）A~C
A - PartitionA题传送门
这道题不难发现，如果数字最终的和大于等于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;
void icealsoheat(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a;
// sort(a+1,a+1+n);
if(k<=0){
int sum=0;
for(int i=1;i<=n;i++){
sum+=a;
}
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<<" ";
}
}
else{
cout<<"No\n";
}
}
else{
cout<<"Yes\n";
sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
cout<<a<<" ";
}
}
}
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 2^{10} 210的复杂度，还可以再添一个m，以是最终的复杂度最多为O(nmlog 2 10 2^{10} 210)。
我们可通过状压来枚举各个数是否符合条件可以放入的情况。比如第i位，假如我向这个数位放入的数字是j，首先，放入j的条件条件是在当前位数和上一个放入j的位数之间我们放入了至少一个a，此时j可以放入，同时，放入了j后，j会使得后面全部a=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;
modint dp;
int id;
void icealsoheat(){
int m,n;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a;
for(int i=1;i<=n;i++){
id]|=(1<<(i-1));
}
// for(int i=0;i<n;i++)dp=1;
dp[(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;
dp+=dp;
}
}
}
}
modint ans=0;
for(int i=0;i<(1<<n);i++)ans+=dp;
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;
int re=ve.back();
// int x=le+re;
cout<<"+ "<<le<<" "<<re<<endl;
int x;
cin>>x;
ve.erase(ve.begin());
ve.pop_back();
// cout<<"+"<<i
if(ve.size()==0){
break;
}
int l=0,r=ve.size()-1;
int mid;
while(l<r){
mid=(l+r)>>1;
if(cmp(x,ve))r=mid;
else l=mid+1;
}
if(!cmp(x,ve))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();
}
}
//
//⠀⠀⠀ ⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀ ⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
//⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆
//⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀ ⠛⠿⠿⣿⠃
//⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀ ⠀⠙⢿⡇
//⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
//⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
//⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
//⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀
//
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]