[数据结构与算法]牛客挑战赛53 题解（A+B+C）

???????https://ac.nowcoder.com/acm/contest/11193#description???????

智乃哥哥的小迷题A：

最理想的是

1?=1

1+2=3

1+2+3=6

1+2+3+4=10

1+2+3+4+5=15

那么要凑10 直接就是4了

那如果凑11 12呢

我们可以15-1-1-1-1 当然不是最优解

我们只需要-4即可

我们可以

1+2-1+4+5=11 凑-4

那么凑-3呢只需要 1-1+3+4+5=12

但是要凑-1呢

我们只能才最后的位置-1即可

我们要求n*(n+1)/2==x的 n 可以拿二分来找

int main(){
    int t;
    cin>>t;
    while (t--) {
        int x;
        cin >> x;
        ll l = 0;
        ll r = 1e8;
        while(l < r){
            ll mid = l + r >> 1;
            if (mid * (mid + 1) / 2 >= x) r = mid;
            //check()判断mid是否满足性质
            else l = mid + 1;
            }
            ll z = l * (l + 1) / 2 - x;
            if(z == 1)
                l++;
        cout << l << endl;
    }
}

简单的序列：

这道题刚开始拿贪心去找了 根本不知道哥德巴赫猜想

原代码?（错误的）

int main(){
    int t;
    int k=e_cheak(MAX);
    cin>>t;
    while (t--) {
        ll s;
        cin>>s;
        ll ss=s;

        vector<ll>v;
        v.clear();
        if(!vis[s]) cout<<1<<endl,cout<<s<<" = "<<s;
        else if(s==0) cout<<1<<endl,cout<<0<<" = "<<0;
        else {
            while (s!=0) {
                ll x=s;
                while (vis[x]) {
                    x--;
                }
                v.push_back(x);
                s-=x;
            }
            cout<<v.size()<<endl;
            for(int i=v.size()-1;i>=1;i--){
                cout<<v[i]<<" + ";
            }
            cout<<v[0]<<" = "<<ss<<endl;
        }
    }
}

正确（哥德巴赫猜想）

const int N=1e7+10;
const long long mx=1e7;
int T,p[N],cnt,n,ans1[N],ans2[N];
bool vis[N];
inline void check(int x){
    for(int i=1;i<=cnt;i++)
    if(!vis[x-p[i]]){
        printf("%d + %d ",p[i],x-p[i]);
        return;
    }
}
int main(){
    for(ll i=2;i<=mx;i++){
        if(!vis[i]){
            for(ll j=i*i;j<=mx;j+=i)vis[j]=1;
            p[++cnt]=i;
        }
    }
    cin>>T;
    while(T--){
        cin>>n;
        if(n==0||n==1||!vis[n]){
            printf("1\n%d = %d\n",n,n);
            continue;
        }
        if(n%2==0)printf("2\n"),check(n),printf("= %d\n",n);
        else{
            if(!vis[n-2])printf("2\n%d + %d = %d\n",2,n-2,n);
            else printf("3\n"),check(n-1),printf("+ 1 = %d\n",n);
        }
    }
}

奇奇怪怪的魔法阵

直接拿状压dp来枚举情况即可

const int N=26;
int dp[1<<N];
int ys[1<<N];
int t[1<<N];
const int mod=1e9+7;
int res=0;
int main()
{
    int n;
    cin>>n;
    int m;
    cin>>m;
    for(int i=0;i<n;i++) t[i]=(1<<i);
    while(m--){
        int a,b;
        cin>>a>>b;
        t[a]|=(1<<b);
        t[b]|=(1<<a);
    }
    dp[0]=1;
    for(int i=0;i<n;i++)
        ys[1<<i]=i;
    for(int i=1;i<1<<n;i++){
        int id=ys[i&(-i)];
        dp[i]=dp[i^(1<<id)]+dp[i^(i&t[id])];
        if(dp[i]>=mod)
        dp[i]-=mod;
    }
    int res=0;
//  for(int i=0;i<1<<n;i++){
//      cout<<dp[i]<<" ";
//  }
//  cout<<endl;
    for(int i=(1<<n)-1;i>=0;i--){
        res=(res*1ll*233+dp[i])%mod;
    }
    cout<<res;
}

?其他的没做 有时间补题吧！！！

弱鸡！