头像

AcWing2AK

$$\href{https://www.acwing.com/blog/content/17259/}{\Huge\color{gold}{个人主页}}$$ 六年级蒟蒻无条件互粉+小号回关(特殊除外)




离线:11分钟前


最近来访(4603)
用户头像
非黑即白
用户头像
WаWing
用户头像
Edward2019
用户头像
lsz_
用户头像
孤寄者
用户头像
2010
用户头像
封禁用户
用户头像
忘打周赛
用户头像
limie
用户头像
该用户被封禁AcWing
用户头像
一万小时定律
用户头像
冰中月
用户头像
dugong
用户头像
wangyc
用户头像
我是好人
用户头像
bhdtr
用户头像
john02017
用户头像
化身孤岛的鲸ღ
用户头像
max2021
用户头像
Charlie0998


#include<bits/stdc++.h>
using namespace std;
int a[100010],n,ans=0,i;
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)cin>>a[i];
    for(int i=n;i>=1;i--){
        if((a[i]+ans&1)==0)ans=(a[i]+ans)>>1;
        else ans=(a[i]+ans>>1)+1;
    }
    cout<<ans;
}


活动打卡代码 AcWing 3485. 最大异或和

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010 * 31, M = 100010;

int n, m;
int s[M];
int son[N][2], cnt[N], idx;

void insert(int x, int v)
{
    int p = 0;
    for (int i = 30; i >= 0; i -- )
    {
        int u = x >> i & 1;
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
        cnt[p] += v;
    }
}

int query(int x)
{
    int res = 0, p = 0;
    for (int i = 30; i >= 0; i -- )
    {
        int u = x >> i & 1;
        if (cnt[son[p][!u]]) p = son[p][!u], res = res * 2 + 1;
        else p = son[p][u], res = res * 2;
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        scanf("%d", &x);
        s[i] = s[i - 1] ^ x;
    }

    int res = 0;
    insert(s[0], 1);

    for (int i = 1; i <= n; i ++ )
    {
        if (i > m) insert(s[i - m - 1], -1);
        res = max(res, query(s[i]));
        insert(s[i], 1);
    }

    printf("%d\n", res);
    return 0;
}


活动打卡代码 AcWing 414. 数字游戏

#include<bits/stdc++.h>
using namespace std;
const int N=110,M=10,INF=0x3f3f3f3f;
int n,m;
int w[N],s[N];
int f[N][N][M],g[N][N][M];
int get_mod(int x)
{
    return (x%10+10)%10;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>w[i];
        w[i+n]=w[i];
    }
    for(int i=1;i<=n*2;i++)s[i]=s[i-1]+w[i];
    memset(f,0x3f,sizeof(f));
    memset(g,-0x3f,sizeof(g));
    for(int len=1;len<=n;len++)
        for (int l=1;l+len-1<=n*2;l++){
            int r=l+len-1;
            f[l][r][1]=g[l][r][1]=get_mod(s[r]-s[l-1]);
            for(int k=2;k<=m;k++)
                for(int j=l+k-2;j<r;j++){
                    f[l][r][k]=min(f[l][r][k],f[l][j][k-1]*get_mod(s[r]-s[j]));
                    g[l][r][k]=max(g[l][r][k],g[l][j][k-1]*get_mod(s[r]-s[j]));
                }
        }
    int maxv=-INF,minv=INF;
    for(int i=1;i<=n;i++){
        maxv=max(maxv,g[i][i+n-1][m]);
        minv=min(minv,f[i][i+n-1][m]);
    }
    cout<<minv<<endl;
    cout<<maxv;
}


活动打卡代码 AcWing 3781. 乘车问题

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

int main() 
{
    int n,m,i,x,t,c=0,ans=0;
    cin>>t;
    while(t--){
        cin>>n>>m;
        c=0,ans=0;
        for(int i=1;i<=n;i++){
            cin>>x;
            if(c+x>m){
                ans++;
                c=0;    
            }
            c+=x;
        }
        if(c!=0)ans++;
        cout<<ans<<endl;
    }
}


活动打卡代码 AcWing 3806. 最小化字符串

#include<bits/stdc++.h>
using namespace std;
int n,x;
string st;
int main() 
{
    cin>>n;
    while(n--){
        cin>>x>>st;
        string str;
        for(int i=0;i<x-1;i++){
            if(st[i]>st[i+1]){
                str+=st.substr(i+1); 
                break;
            }
            str+=st[i];
        }
        cout<<str<<'\n';
    }
}


活动打卡代码 AcWing 3802. 消灭数组

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20;

int n;
int w[N];

int dfs(int l, int r)
{
    bool flag = true;
    for (int i = l; i < r; i ++ )
        if (w[i] > w[i + 1])
            flag = false;
    if (flag) return r - l + 1;
    int mid = l + r >> 1;
    return max(dfs(l, mid), dfs(mid + 1, r));
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        cin >> n;
        for (int i = 0; i < n; i ++ ) cin >> w[i];
        cout << dfs(0, n - 1) << endl;
    }
    return 0;
}



class Solution {
public:
    string greatestLetter(string s) {
        unordered_set<char> S;
        for (auto c: s) S.insert(c);
        for (char i = 'z'; i >= 'a'; i -- ) {
            if (S.count(i) && S.count(i - 32)) {
                return string(1, i - 32);
            }
        }

        return "";
    }
};



class Solution {
public:
    int minimumNumbers(int num, int k) {
        if (!num) return 0;
        for (int x = 1; x <= 10; x ++ )
            if (x * k % 10 == num % 10 && x * k <= num)
                return x;
        return -1;
    }
};


活动打卡代码 AcWing 136. 邻值查找

要一个特判

#include<bits/stdc++.h>
using namespace std;
long long n,a[100001],i;
int main()
{
    set<pair<long long,int>>a;
    a.insert({2000000000,-1});
    a.insert({-2000000000,-1});
    cin>>n;
    if(n==2){
        cout<<"2000000000 1";
        return 0;
    }
    for(i=1;i<=n;i++){
        long long x;
        cin>>x;
        if(i>1){
            auto right=a.lower_bound({x,-1});
            auto left=a.upper_bound({x,-1});
            left--;
            long long r=(long long)right->first-x;
            long long l=(long long)x-left->first;
            if(l<=r)cout<<l<<' '<<left->second<<endl;
            else cout<<r<<' '<<right->second<<endl;
        }
        a.insert({x,i});
    }
}



class Solution {
public:
    vector<int> printMatrix(vector<vector<int>>& matrix) {
        vector<int> res;
        if (matrix.empty()) return res;
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<bool>> st(n, vector<bool>(m, false));
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        int x = 0, y = 0, d = 1;
        for (int k = 0; k < n * m; k ++ )
        {
            res.push_back(matrix[x][y]);
            st[x][y] = true;

            int a = x + dx[d], b = y + dy[d];
            if (a < 0 || a >= n || b < 0 || b >= m || st[a][b])
            {
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }
            x = a, y = b;
        }
        return res;
    }
};