2023牛客寒假算法基础集训营4

A题

题意：总共20张牌，求x进制还是y进制表示的数字多。

思路：用20 除以进制数表示每个数字有几张牌，也就是数字最多有几位，每位可以填进制内的数字，所以表示的数字就是进制的几位的乘方，但是要把3进行特判。这个题有个结论，3进制表示的数字最多，2，4进制表示的数字一样，剩下的进制越大表示的数字越少。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll n,m;
    cin>>n>>m;
    ll tn=20/n,tm=20/m;
    if(n==3||m==3)cout<<3<<endl;
    else if(pow(n,tn)<pow(m,tm))cout<<m;
    else if(pow(n,tn)>pow(m,tm))cout<<n;
    else cout<<min(n,m);
    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
typedef long long ll;
typedef double D;
int a[1010][1010],s[1010][1010];
int main() {
    IOS;
    CC;
    int n,m;
    cin>>n>>m;
    if(n==3||m==3)cout<<3<<endl;
    else cout<<min(n,m)<<endl;
    return 0;
}

C题

思路：就是一个01背包的问题，再枚举一边n个蝴蝶结，在判断一下就可以了。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
using namespace std;
typedef double D;
const int N = 110, M = 1e9 + 7;
int v[N],w[N],dp[N];
int main() {
    IOS;
    CC;
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            for (int k = m; k >= w[j]; k--) {
                dp[k] = max(dp[k], dp[k - w[j]] + v[j]);
            }
        }
        ll ans = dp[m] - dp[m - w[i]] - v[i] + 1;
        if (ans < 0) cout << 0 << endl;
        else cout << ans << endl;
    }
    return 0;
}

E题

思路：一个一个打死怪兽是最好的，然后就考虑每个怪兽打多少下即可，有个比较好写的写法就是我们先砍一刀，然后剩下的就是没砍死和恢复的过程，求数量的时候上取整即可。

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

int main() {
    long long int n, t, a, rr, rrr, res = 0, flag = 0, h, v;
    cin >> n >> t >> a;
    for (int i = 0; i < n; i++) {
        cin >> h >> v;
        res += t, h -= a;
        if (h <= 0) {
            continue;
        }
        if (t * v >= a) {
            cout << "-1";
            return 0;
        } else {
            res += (h / (a - t * v)) * t;
            if (h % (a - t * v)) {
                res += t;
            }
        }
    }
    cout << res - t + 1;
}

L题

题意：给三个点的权值Va，Vb，Vc，Va=lb+lc，Vb=la+lc，Vc=lb+la，求出la，lb，lc，判断能否构成三角形，能就输出Yes，并输出三条边，否则输出No。

思路：解三元一次方程求出边长，但求解的公式中有（）/2所以（）里面的数必须为偶数，不然边就不是正整数了，所以再判断三角形之前先判断奇数还是偶数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
ll va, vb, vc;
ll lb, la, lc;
ll a, b, c;
int main() {
    cin >> t;
    while (t--) {
        scanf("%lld%lld%lld", &va, &vb, &vc);
        b = (vc + va - vb);
        a = (vc + vb - va);
        c = (va + vb - vc);
        bool flag = true;
        if (a % 2 != 0 || b % 2 != 0 || c % 2 != 0)flag = false;
        lb = b / 2;
        la = a / 2;
        lc = c / 2;
        if (flag && la + lb > lc && la + lc > lb && lb + lc > la && abs(la - lb) < lc && abs(lb - lc) < la &&
            abs(la - lc) < lb)
            printf("Yes\n%lld %lld %lld\n", la, lb, lc);
        else printf("No\n");
    }
    return 0;
}

M题

题意：求n个数，这n个数中，每三个相邻的数不能构成三角形。最后输出这十个数。

思路：先初始定义三个数不能构成三角形，然后从第四个数开始循环，每次从一开始循环，只要满足条件，就break，将这个数push进数组就可，当满足n个数结束循环。

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N];
int main() {
    int n;
    cin >> n;
    vector<int> ve = {1, 1, 2};
    while(ve.size()<n) {
        int k = ve.size() - 1;
        for(int i=1;;i++)
        if (ve[k] + ve[k - 1] <= i || ve[k] + i <= ve[k - 1] || i + ve[k - 1] <= ve[k]){
            ve.push_back(i);
            break;
        }
    }
    for (auto i: ve)cout << i << ' ';
    return 0;
}

2023牛客寒假算法基础集训营6

A题

签到题，按同意模拟即可。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
using namespace std;
typedef double D;
const int N=100010;
int a[N],b[N],c[N];
int as[N],cs[N];
int cnt[N],s[N];
int main() {
    IOS;
    CC;
    ll n;
    cin>>n;
    if(n>=1&&n<=7)cout<<"very easy";
    if(n>7&&n<=233)cout<<"easy";
    if(n>233&&n<=10032)cout<<"medium";
    if(n>10032&&n<=114514)cout<<"hard";
    if(n>114514&&n<=1919810)cout<<"very hard";
    if(n>1919810)cout<<"can not imagine";
    return 0;
}

C题

题意：给n个数，不断融合这n个数，就是每一轮相邻的两个数相加形成一个新的数，直至加到只剩一个数，就是最后的值，要是这个值尽可能大，输出这n个数的排列方法。

思路；要使值尽可能大，那么就要将较大的数放再中间，多加几次，所以先从中间开始，从大到小依次排列，最后再用两个for循环求出最后的值就是最大的。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
using namespace std;
typedef double D;
const int N = 1010, M = 1e9 + 7;
int a[N], b[N], c[N];
int as[N], cs[N];
int cnt[N], s[N];
int main() {
    IOS;
    CC;
    int n;
    cin >> n;
    int t = n, k = 0;
    if (n & 1) {
        a[n / 2 + 1] = t--;
        for (int i = n / 2, j = n / 2 + 2; i > 0; i--, j++) {
            if (k % 2 == 0)a[i] = t--, a[j] = t--, k++;
            else a[j] = t--, a[i] = t--, k++;
        }
    } else {
        for (int i = n / 2, j = n / 2 + 1; i > 0; i--, j++) {
            if (k % 2 == 0)a[i] = t--, a[j] = t--, k++;
            else a[j] = t--, a[i] = t--, k++;
        }
    }
    for (int i = 1; i <= n; i++)b[i] = a[i];
    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= i - 1; j++) {
            b[j] = b[j] % M + b[j + 1] % M;
        }
    }
    cout << b[1] % M << endl;
    for (int i = 1; i <= n; i++)cout << a[i] << ' ';
    return 0;
}

F题

题意：阿宁有一个长度为 � n的数组 � a，下标从 1 1开始。

定义 � ( � ) f(x)是x在二进制表示下1的个数。例如5的二进制是101因此f(5)=2阿宁有q次询问，每次询问后数组恢复原样。 在一次询问中，给出k。在一次操作中，可以选择一个数(1≤i≤n)，将a[i]修改为f(a[i])请你恰好进行k次操作，要求整个数组的最大值最小，这个最大值是多少?

思路：这个题可以使用堆来做，优先队列，用大根堆，维护最大的值到堆顶，再结合位运算求二进制里1的个数，最后输出即可。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
using namespace std;
typedef double D;
const int N = 110, M = 1e9 + 7;
int v[N],w[N],dp[N];
priority_queue<int> Q;
vector<int> ans;
int f(int num){
    int res=0;
    while(num){
        if(num&1) res++;
        num>>=1;
    }
    return res;
}
int main() {
    IOS, CC;
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        int temp;
        cin >> temp;
        Q.push(temp);
    }
    while (Q.top() != 1) {
        int temp = Q.top();
        Q.pop();
        temp = f(temp);
        Q.push(temp);
        ans.push_back(Q.top());
    }
    for (int i = 1; i <= q; i++) {
        int k;
        cin >> k;
        if (k > ans.size()) cout << "1" << endl;
        else cout << ans[k - 1] << endl;
    }
    return 0;
}

H题

题意：先杀死y个脆皮，当杀了这y个脆皮以后还剩脆皮就可以攻击到，不剩下就不能攻击到，求能被攻击到的概率，要进却到1e-6以上才可以。

思路：此题分三种情况，一定不能被攻击到，一定能被攻击到，可能被攻击到，分别讨论即可。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
using namespace std;
typedef double D;
const int N=100010;
int a[N],b[N],c[N];
int as[N],cs[N];
int cnt[N],s[N];
int main() {
    IOS;
    CC;
    double x,l,r;
    cin>>x>>l>>r;
    if(x<l)cout<<0;
    else if(x>r)cout<<1;
    else printf("%.16f",(x-l)/(r-l+1));
    return 0;
}

G题

题意:阿宁有一个长度为n的整数数组a，阿宁想要在其中选出恰好k对整数，使得每对整数相乘并求和尽可能大。阿宁想知道最终得到的值是多少？

思路：要使负负相乘，整整相乘，所以先排个序，使用双指针，一个从头开始，一个从尾部，每次前两个数和后两个数比较相乘的大小，大的加到总和里并且移动这两个数对应的指针，循环结束即可。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
using namespace std;
typedef double D;
const int N=200010;
int a[N],b[N],c[N];
int as[N],cs[N];
int cnt[N],s[N];
int main() {
    IOS;
    CC;
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)cin >> a[i];
    sort(a, a + n);
    int res = 0, ans = 0;
    int i = 0, j = n - 1;
    while (1) {
            if (a[i] * a[i + 1] <= a[j] * a[j - 1])
                res += a[j] * a[j - 1], j -= 2, ans++;
            else res += a[i] * a[i + 1], i += 2, ans++;
        if (ans == k)break;
    }
    cout << res << endl;
    return 0;
}

SMU 2023 年冬季赛 #9 （Div.2）

A题

签到题

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
using namespace std;
typedef double D;
const int N=1e5+10;
int a[N],b[N],c[N];
int n,m;
int main() {
    IOS;
    CC;
    cout<<"Ranni the Witch";
    return 0;
}

B题

题意：有n个怪，前k秒每秒可以群伤x，之后群伤y，求干掉所有怪需要的最少时间

思路：先找出血最厚的怪，然后分类讨论，<kx直接做除法，不够的话-kx再除y，注意取整即可。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
using namespace std;
typedef double D;
const int N = 110, M = 1e9 + 7;
int v[N],w[N],dp[N];
int main() {
    IOS, CC;
    int T;
    cin >> T;
    while (T--) {
        int n, k, x, y;
        cin >> n >> k >> x >> y;
        int mx;
        cin >> mx;
        for (int i = 2; i <= n; i++) {
            int t;
            cin >> t;
            mx = max(mx, t);
        }
        if (k * x >= mx) {
            int t = mx / x;
            if (mx % x != 0)t++;
            cout << t << "\n";
        } else {
            mx -= k * x;
            int t = k + mx / y;
            if (mx % y != 0)t++;
            cout << t << "\n";
        }
    }
    return 0;
}

C题

题意：给出两段冒泡排序的伪代码，求构造一个长为n的排列（不重），满足使用两段代码排序的交换次数相同。

思路：对于冒泡排序，其交换次数= 逆序对数量，可以发现若构造的排列a1 = n，两个算法的交换次数都是其逆序对数量。所以随便输出一个首位为n 的排列即可。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
using namespace std;
typedef double D;
const int N = 110, M = 1e9 + 7;
int v[N],w[N],dp[N];
int main() {
    IOS, CC;
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = n; i >= 1; i--) {
            cout << i << " ";
        }
        cout << "\n";
    }
    return 0;
}

F题

题意：T组（1e5）数据，每次给出n, k（1e9），求1~n所有数除以pow(2,k)后分母部分相加的结果。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
using namespace std;
typedef double D;
const int N = 110, M = 1e9 + 7;
int v[N],w[N],dp[N];
int main() {
    IOS, CC;
    int T;
    cin >> T;
    while (T--) {
        ll n, k;
        cin >> n >> k;
        ll sum = n * (n + 1) / 2;
        while (n > 0 && k > 0) {
            n >>= 1;
            sum -= n * (n + 1) / 2;
            k--;
        }
        cout << sum << "\n";
    }
    return 0;
}

L题

题意：打怪，给出怪物塔的总层数 n 和能达到的层数 k\n当打死一层的怪会获得怪的能力值，本层消失，本层上边的层数减一，求通关的最小能力值

思路：打怪的顺序是唯一的，所以维护一个有 k 个元素的小根堆，每次处理最小的元素，如果现有能力值大于怪的能力值，加上怪的能力值，否则更新初始值；\n\n每遇到一个打不过的怪，最小可能初始值 = 怪的能力值-前面获得的能力值总和，用这个值去更新之前的 初始值，取其中大的。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
using namespace std;
const int N = 1e6+100;
ll t,n,k;
ll a[N];
priority_queue<ll,vector<int>,greater<int> >pmin;
ll sta,now;
int main() {
    //IOS,CC;
    cin >> t;
    while (t--) {
        cin >> n >> k;
        sta = 0;
        now = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
        }
        for (int i = 1; i <= n; i++) {
            if (pmin.empty() || pmin.size() < k) pmin.push(a[i]);//注意判空
            else {
                ll s = pmin.top();
                pmin.pop();
                if (now >= s) {
                    now += s;
                }
                else {
                    sta = max(sta, s - now);
                    now += s;
                }
                pmin.push(a[i]);
            }
        }
        while (!pmin.empty()) {
            ll s = pmin.top();
            pmin.pop();
            if (now >= s) {
                now += s;
            } else {
                sta = max(sta, s - now);
                now += s;
            }
        }
        cout << sta << endl;
    }
    return 0;
}