网站建设毕业设计论文,贸易公司如何做英文网站,查看网站域名,个人怎么做网站优化A - Partition
A题传送门 这道题不难发现#xff0c;如果数字最终的和大于等于K#xff0c;我们可以把这个原数列从大到小排序#xff0c;得到最终答案。 如果和小于K#xff0c;则从小到大排序#xff0c;同时验证是否符合要求。
#pragma GCC optimize(3) //O2优化开启…A - Partition
A题传送门 这道题不难发现如果数字最终的和大于等于K我们可以把这个原数列从大到小排序得到最终答案。 如果和小于K则从小到大排序同时验证是否符合要求。
#pragma GCC optimize(3) //O2优化开启
#includebits/stdc.h
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pairint,int PII;
// const int mod1e97;
const int MX0x3f3f3f3f3f3f3f3f;
//inline int read() //快读
//{
// int xr0,F1; char cr;
// while(crgetchar(),cr0||cr9) if(cr-) F-1;
// while(cr0cr9)
// xr(xr3)(xr1)(cr^48),crgetchar();
// return xr*F;
//}
//void write(int x) //快写
//{
// if(x0) putchar(-),x-x;
// if(x9) write(x/10); putchar(x%100);
//}
// 比 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_tableint, 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(){cinnk;for(int i1;in;i)cina[i];// sort(a1,a1n);if(k0){int sum0;for(int i1;in;i){suma[i];}if(sumk){coutYes\n;sort(a1,a1n,[](int x,int y){return xy;});for(int i1;in;i){couta[i] ;}}else{coutNo\n;}}else{coutYes\n;sort(a1,a1n);for(int i1;in;i){couta[i] ;}}}
signed main(){ios::sync_with_stdio(false); //int128不能用快读cin.tie();cout.tie();int _yq;_yq1;// 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后j会使得后面所有a[x]j的数字都可以放入我们可以通过状态去枚举各个数字是否可以放入能放入的话对应的二进制位数就是1不能放入就是0。
#pragma GCC optimize(3) //O2优化开启
#includebits/stdc.h
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pairint,int PII;
// const int mod1e97;
const int MX0x3f3f3f3f3f3f3f3f;
//inline int read() //快读
//{
// int xr0,F1; char cr;
// while(crgetchar(),cr0||cr9) if(cr-) F-1;
// while(cr0cr9)
// xr(xr3)(xr1)(cr^48),crgetchar();
// return xr*F;
//}
//void write(int x) //快写
//{
// if(x0) putchar(-),x-x;
// if(x9) write(x/10); putchar(x%100);
//}
// 比 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_tableint, 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;cinnm;for(int i1;in;i)cina[i];for(int i1;in;i){id[a[i]]|(1(i-1));}// for(int i0;in;i)dp[0][1i]1;dp[0][(1n)-1]1;for(int i1;im;i){for(int j1;jn;j){for(int o0;o(1n);o){if(o(j-1)1){int xo;x-(1(j-1));x|id[j];dp[i][x]dp[i-1][o];}}}}modint ans0;for(int i0;i(1n);i)ansdp[m][i];coutans;}
signed main(){ios::sync_with_stdio(false); //int128不能用快读cin.tie();cout.tie();int _yq;_yq1;// cin_yq;while(_yq--){icealsoheat();}
}
//
//⠀⠀⠀ ⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀ ⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
//⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆
//⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀ ⠛⠿⠿⣿⠃
//⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀ ⠀⠙⢿⡇
//⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
//⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
//⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
//⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀
//
C - Beware of Overflow
C题传送门 还是我太菜了看题目都费劲最后还是不争气的看了题解竟然题解把查询放入了排序的cmp函数中确实还是我自己的思维太局限了容易想到的是我们把所有的数从小到大排序然后头尾相加再把相加的数通过二分按顺序放入这个数中重复上述操作知道符合最后条件为止O(nlogn)的复杂度所以不会超过25000次询问。
#pragma GCC optimize(3) //O2优化开启
#includebits/stdc.h
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pairint,int PII;
// const int mod1e97;
const int MX0x3f3f3f3f3f3f3f3f;
//inline int read() //快读
//{
// int xr0,F1; char cr;
// while(crgetchar(),cr0||cr9) if(cr-) F-1;
// while(cr0cr9)
// xr(xr3)(xr1)(cr^48),crgetchar();
// return xr*F;
//}
//void write(int x) //快写
//{
// if(x0) putchar(-),x-x;
// if(x9) write(x/10); putchar(x%100);
//}
// 比 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_tableint, 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 bendl;int s;cins;return s;
}
// bool check(int p,int o){
// cout? p oendl;
// int x;
// cinx;
// return x0;
// }
void icealsoheat(){cinn;vectorintve;for(int i1;in;i){ve.push_back(i);}sort(ve.begin(),ve.end(),cmp);while(ve.size()1){int leve[0];int reve.back();// int xlere;cout le reendl;int x;cinx;ve.erase(ve.begin());ve.pop_back();// coutiif(ve.size()0){break;}int l0,rve.size()-1;int mid;while(lr){mid(lr)1;if(cmp(x,ve[mid]))rmid;else lmid1;}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;_yq1;// cin_yq;while(_yq--){icealsoheat();}
}
//
//⠀⠀⠀ ⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀ ⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
//⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆
//⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀ ⠛⠿⠿⣿⠃
//⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀ ⠀⠙⢿⡇
//⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
//⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
//⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
//⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀
//
