头像

alextang

山东大学(威海)




离线:1个月前


最近来访(5)
用户头像
BlizzardWasteland
用户头像
sduwhacm03
用户头像
德鲁大叔

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

alextang
2个月前
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
#define fi first
#define se second
#define mp make_pair
const int N = 1e5 + 10;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
mt19937 mrand(random_device{}()); 
int rnd(int x) { return mrand() % x;}
LL powmod(LL a,LL b,LL mod) {LL res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
LL gcd(LL a,LL b) { return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b) { return a*b/gcd(a,b);}

int main(){
    int T;cin >> T;
    while (T--){
        int n,m;
        cin >> n >> m;
        int res = 0,cur = 0;
        while (n--){
            int x;cin >> x;
            if (x + cur > m)    res++,cur = 0;
            cur += x;
        }
        if (cur)    res++;
        cout << res << endl;
    }
    return 0;
}



活动打卡代码 AcWing 3775. 数组补全

alextang
2个月前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 2e5 + 50;
int n;
int in[N],out[N];
bool vis[N];

int main(){
    int T;cin >> T;
    while (T--){
        cin >> n;
        memset(vis,0,sizeof vis);
        memset(in,0,sizeof in);
        memset(out,0,sizeof out);
        for (int i = 1;i <= n;++i){
            cin >> out[i];
            in[out[i]] = i;
        }
        bool f = 0;
        for (int i = 1;i <= n;++i){
            if (vis[i] || !out[i])  continue;
            vis[i] = true;
            int head = i,tail = i;
            while (out[head] && !vis[out[head]]){
                head = out[head];
                vis[head] = 1;
            }
            while (in[tail] && !vis[in[tail]]){
                tail = in[tail];
                vis[tail] = 1;
            }
            if (out[head] == tail)  continue;
            if (!f){
                f = 1;
                for (int j = 1;j <= n;++j){
                    if (!in[j] && !out[j]){
                        out[head] = j;
                        head = j;
                        vis[j] = 1;
                    }
                }
            }
            out[head] = tail;
        }
        if (!f){
            int x = 0,y = 0;
            for (int i = 1;i <= n;++i){
                    if (!out[i])
                    {
                    if (!x && !y)   x = y = i;
                    else{
                        out[x] = i;
                        x = i;
                    }
            }
            }
            out[x] = y;
        }
        for (int i = 1;i <= n;++i){
            printf("%d ",out[i]);
        }
        puts("");
    }
    return 0;
}


活动打卡代码 AcWing 3777. 砖块

alextang
2个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 220;
int n;
void update(char &c){
    if (c == 'W') c = 'B';
    else c = 'W';
}

bool check(string s,char c){
    vector<int> step;
    for (int i = 0;i < n - 1;++i){
        if (s[i] != c){
            step.push_back(i+1);
            update(s[i]);
            update(s[i+1]);
        }
    }
    if (s.back() != s[0])   return false;
    cout << step.size() << endl;
    for (auto x: step)  cout << x << ' ';
    if (step.size()) cout << endl;
    return true;    
}

int main(){
    int T;cin >> T;
    while (T--){
        string s;
        cin >> n >> s;
        if (!check(s,'W') && !check(s,'B')) puts("-1");
    }   
    return 0;
}


活动打卡代码 AcWing 3776. 水果拼盘

alextang
2个月前
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int T;cin >> T;
    while (T--){
        int a,b,c,d,e,f;
        cin >> a >> b >> c >> d >> e >> f;
        int res = 0;
        if (e >= f){
            res += min(a,d) * e;
            d -= min(a,d);
            res += f * min(b,min(c,d));
        }else{
            res += min(b,min(c,d)) * f;
            d -= min(b,min(c,d));
            res += e * min(a,d);
        }
        printf("%d\n",res);
    }
    return 0;
}


活动打卡代码 AcWing 3773. 兔子跳

alextang
2个月前
#include <iostream>
#include <algorithm>

using namespace std;


int main(){
    int T;scanf("%d",&T);
    while (T--){
        int n,x;
        scanf("%d%d",&n,&x);
        bool f = 0;
        int a = 0;
        while (n--){
            int b;scanf("%d",&b);
            if (b == x) f = 1;
            a = max(a,b);
        }
        //cout << "asdasdas:" << a << endl; 
        if (f)  puts("1");
        else if (a > x) puts("2");
        else printf("%d\n",(x+a-1) / a);
    }
    return 0;
}


活动打卡代码 AcWing 113. 特殊排序

alextang
11个月前
// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> res;
        res.push_back(1);
        for (int i = 2; i <= N;++i){
            int l = 0,r = res.size()-1;
            while (l <= r){
                int mid = (l + r) >> 1;
                if (compare(res[mid],i)) l = mid + 1;
                else    r = mid - 1;
            }
            // r l 
            res.push_back(i);
            for (int i = res.size() - 2;i >= l;--i) swap(res[i+1],res[i]);
        }
        return res;
    }
};


活动打卡代码 AcWing 102. 最佳牛围栏

alextang
11个月前
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
double a[N],b[N],s[N];
int n,L;
bool check(){
    double ans = -INF;
    double minn = INF;
    for (int i = L;i <= n;++i){
        minn = min(minn,s[i-L]);
        ans = max(ans,s[i] - minn);
    }
    return ans >= 0;
}
int main(){
    cin >> n >> L;
    for (int i = 1;i <= n;++i){
        scanf("%lf",&a[i]);
    }
    double l = 1e-6,r = 1e6;
    while (r - l > eps){
        double mid = (r + l) / 2;
        for (int i = 1;i <= n;++i){
            b[i] = a[i] - mid;
        }
        for (int i = 1;i <= n;++i){
            s[i] = s[i-1] + b[i];
        }
        if (check())    l = mid;
        else    r = mid;
    }
    cout << int(r * 1000) << endl;
    return 0;
}


活动打卡代码 AcWing 101. 最高的牛

alextang
11个月前
#include <bits/stdc++.h>
using namespace std;
int n,p,h,m;
const int maxn = 1e4 + 5;
map<pair<int,int>,bool> vis;
int d[maxn];
int c[maxn];
int main(){
    cin >> n >> p >> h >> m;
    for (int i = 0;i < m;++i){
        int a,b;cin >> a >> b;
        if (a > b)  swap(a,b);
        if (vis[make_pair(a,b)])    continue;
        d[a+1]--;d[b]++;
        vis[make_pair(a,b)] = 1;
    }
    //c[1] = d[1];
    for (int i = 1;i <= n ;++i){
        c[i] = c[i-1] + d[i];
        cout << c[i] + h << endl;
    }
    return 0;
}


活动打卡代码 AcWing 100. IncDec序列

alextang
11个月前
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5  +5;
int a[maxn];
int n;
int main(){
    scanf("%d",&n);
    for (int i = 1;i <= n;++i){
        scanf("%d",&a[i]);
    }
    for (int i = n;i > 1;--i){
        a[i] -= a[i-1];
    }
    long long pos = 0;
    long long neg = 0;
    for (int i = 2;i <= n;++i){
        if (a[i] > 0)   pos += a[i];
        else if (a[i] < 0)  neg -= a[i];
    }
    cout << min(pos,neg) + abs(pos-neg) << endl;
    cout << abs(pos-neg) + 1 << endl;
    return 0;
}


活动打卡代码 AcWing 99. 激光炸弹

alextang
11个月前
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5010;
int g[maxn][maxn];
int main(){
    int N,r;cin >> N >> r;
    r = min(5001,r);
    int n = 5001,m = 5001;
    for (int i = 0,x,y,w;i < N;++i){
        cin >> x >> y >> w;
        x++;y++;
        g[x][y] += w;
    }
    for (int i = 1;i <= n;++i){
        for (int j = 1;j <= m;++j){
            g[i][j] += g[i-1][j] + g[i][j-1] - g[i-1][j-1];
        }
    }
    int res = 0;
    for (int i = r;i <= n;++i){
        for (int j = r;j <= m;++j){
            res = max(res,g[i][j] - g[i-r][j] - g[i][j-r] + g[i-r][j-r]);
        }
    }
    cout << res << endl;
    return 0;
}