2019年牛客寒假算法基础集训营1

2019年牛客寒假算法基础集训营1

A-模拟

倒序模拟
https://ac.nowcoder.com/acm/contest/317/A

代码：

//#include<bits/stdc++.h>
//using namespace std;
#include<stdio.h>

typedef long long ll;
int n;
ll X;
ll ans = 0;

struct ve{
    int opt;
    ll x;
};

struct ve V[110];

int main(){
    scanf("%d%ld",&n,&X);
    ans = (ll)X;
    for(int i=n;i>=1;i--){
        int opt;
        ll x;
        scanf("%d%ld",&opt,&x);
        V[i].opt = opt;
        V[i].x = x;
    }
    for(int i=1;i<=n;i++){
        if(V[i].opt == 1) ans -= V[i].x;
        if(V[i].opt == 2) ans += V[i].x;
        if(V[i].opt == 3) ans /= V[i].x;
        if(V[i].opt == 4) ans *= V[i].x;
    }
    printf("%lld",ans);
    return 0;
}

B贪心+构造(一大一小）

https://ac.nowcoder.com/acm/contest/317/B

1.输入的序列其实用处不大，因为最终不需要输出方案，我们只需要记录下2/0/4分别出现的次数即可
一个显然的构造策略是首先放置4, 0, 4, 0，直到其中一个用光。
接下来如果4多余，那么可以按4,0,4,0,…,4,2,4,2,…(先4后2)的方法构造
如果0多余，可以按照4,0,4,0 … 4,0,2,0,2 …(先2后0)的方法构造
std中的a数组展示了其中一种最优的构造方案

2.实际上此题还可以推广到更一般的情况，也就是第一个位置放最大的，第二个位置放最小的，第三个位置放
第二大的以此类推，这种思路写起来也会更简单一些

int a[N];
int main(){
    int n;
    LL sum=0;
 
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    
    sort(a,a+n+1);
 
    for(int i=n;i>n/2;i--)
        sum+=pow(a[i]-a[n-i],2)+pow(a[n-i+1]-a[i],2); //一大一小
 
    cout<<sum<<endl;
 
    return 0;
}

C-背包dp、线性基

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e3+5;
int A[maxn];
int B[maxn];
int P[maxn];
int cnt;
void solve() {
    for (int i = 1; i <= cnt; ++i) {
        for (int j = 15; j >= 0; --j) {
            if ((A[i]>>j) & 1) {
                if (P[j] == 0) {
                    P[j] = A[i];
                    break;
                } else {
                    A[i] ^= P[j];
                }
            }
        }
    }
}
int main() {
    std::ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> B[i];
    }
    
    for (int i = 2; i < n; ++i) {
        if (B[i] < B[1] && B[i] > B[n]) {
            A[++cnt] = B[i];
        }
    }
    solve();
    int ans = B[1]^B[n];
    for (int j = 15; j >= 0; --j) {
        ans = max(ans, ans^P[j]);
    }
    if (ans > 0 && B[1] > B[n])
        cout << ans << endl;
    else
        cout << -1 << endl;
    return 0;
}

蓝桥杯刷习惯了就只会暴搜了。。
dfs暴力搜索 过10%数据

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int n;
int a[3010];
int vst[3010];
ll ans = -1;
int flag = 0;

void dfs(int cur,int last,ll t){
    if(cur == n-1){
        if(a[last] > a[cur] || last == n-1){
            ans = max(ans,t^a[last]);
            flag = 1;
        }
        return;
    }
    
    for(int i=0;i<n;i++){
        if(!vst[i]){
            if(a[last] <= a[i]) continue;
            vst[i] = 1;
            ll dd = t;
            t ^= a[i];
            dfs(i,cur,t);
            t = dd;
            vst[i] = 0;
        }
    }
} 


int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    ans = a[0];
    vst[0] = 1;
    dfs(0,0,ans); //0 0边界需要调整 
//  printf("%lld",ans);
    if(flag || ans != a[0] || n==1|| ans ==0) printf("%lld",ans);
    else printf("-1");
    return 0;
}

2019年牛客寒假算法基础集训营1

原文：https://www.cnblogs.com/fisherss/p/10383455.html