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

  • 开发
  • 20

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 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优化开启
#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<<"+"<<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[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();
    }
}
//
//⠀⠀⠀             ⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀ ⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
//⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆
//⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀ ⠛⠿⠿⣿⠃
//⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀ ⠀⠙⢿⡇
//⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
//⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
//⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
//⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀
//
阅读全部

相关推荐

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

    2024-07-13 00:34:03       21 阅读

  2. AC修炼计划（ AtCoder Regular Contest 178）A~C

    2024-07-13 00:34:03       23 阅读

  5. Atcoder ABC179

    2024-07-13 00:34:03       50 阅读

  6. AtCoder ABC172

    2024-07-13 00:34:03       53 阅读

  7. AtCoder ABC175

    2024-07-13 00:34:03       50 阅读

  8. AtCoder ABC176

    2024-07-13 00:34:03       47 阅读

  9. AcWing 173.矩阵距离

    2024-07-13 00:34:03       38 阅读

  10. Error: incorrect data check at Zlib.zlibOnError [as onerror] (node:zlib:189:17)

    2024-07-13 00:34:03       49 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-13 00:34:03       67 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-13 00:34:03       72 阅读

  9. 在Django里面运行非项目文件

    2024-07-13 00:34:03       58 阅读

  19. Python语言-面向对象

    2024-07-13 00:34:03       69 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-07-13 00:34:03       64 阅读

热门阅读

  3. 迎接AI新时代：GPT-5的技术飞跃与未来展望

    2024-07-13 00:34:03       23 阅读

  10. JVM的基础，class文件的理解（2）

    2024-07-13 00:34:03       22 阅读

  12. 云端典藏：iCloud中个人收藏品目录的智能存储方案

    2024-07-13 00:34:03       27 阅读

  13. Onnx 1-深度学习-概述1

    2024-07-13 00:34:03       27 阅读

  17. WPF透明置顶窗口wine适配穿透问题解决

    2024-07-13 00:34:03       23 阅读

  20. qt explicit 啥意思

    2024-07-13 00:34:03       26 阅读

  21. 【spring boot项目】mybatis-plus配置类

    2024-07-13 00:34:03       20 阅读

  25. 【c++刷题笔记-动态规划】day36：1049. 最后一块石头的重量 II 、 494. 目标和 、 474.一和零

    2024-07-13 00:34:03       18 阅读

  29. Unity3D中UI层级改变详解

    2024-07-13 00:34:03       24 阅读