头像

_清醒


访客:802

离线:8天前


活动打卡代码 AcWing 1246. 等差数列

_清醒
5个月前
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int q[N];
int gcd(int a, int b) {
    return b? gcd(b, a%b) : a;
}
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> q[i];
    sort(q, q+n);
    int d = 0;
    for (int i = 1; i < n; i ++ ) d = gcd(d, q[i] - q[0]);

    if (!d) printf("%d\n", n);
    else printf("%d\n", (q[n - 1] - q[0]) / d + 1);

    return 0;
}


活动打卡代码 AcWing 1247. 后缀表达式

_清醒
5个月前
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN=1e5+10;
int n,m,k;
LL a[2*MAXN];

int main(){
    scanf("%d%d",&n,&m);
    k=n+m+1;
    for(int i=1;i<=k;i++) scanf("%lld",&a[i]);
    LL sum=0;
    if(!m){
        for(int i=1;i<=k;i++) sum+=a[i];
        printf("%lld\n",sum);
        return 0;
    }
    sort(a+1,a+k+1);
    sum+=a[k];sum-=a[1];m--; 
    for(int i=2;i<k;i++) sum+=abs(a[i]);
    printf("%lld\n",sum);
    return 0;
}


活动打卡代码 AcWing 1239. 乘积最大

_清醒
5个月前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010, mod = 1000000009;

int n, k;
int a[N];

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    sort(a, a + n);

    int res = 1;
    int l = 0, r = n - 1;
    int sign = 1;
    if (k % 2)
    {
        res = a[r -- ];
        k -- ;
        if (res < 0) sign = -1;
    }
    while (k)
    {
        LL x = (LL)a[l] * a[l + 1], y = (LL)a[r - 1] * a[r];
        if (x * sign > y * sign)
        {
            res = x % mod * res % mod;
            l += 2;
        }
        else
        {
            res = y % mod * res % mod;
            r -= 2;
        }
        k -= 2;
    }

    printf("%d\n", res);

    return 0;
}


活动打卡代码 AcWing 1235. 付账问题

_清醒
5个月前
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

int n, s, cnt;
int a[500010];

int main()
{
    scanf("%d%d", &n, &s);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    sort(a, a + n);

    double ave = s * 1.0 / n, cur_ave = ave, sum = 0;
    for (int i = 0; i < n; i++)
    {
        if (a[i] <= cur_ave) 
        {
            s -= a[i];
            sum += (ave - a[i]) * (ave - a[i]);
            cur_ave = s * 1.0 / (n - i - 1);//  当前平均值 
        }
        else sum += (cur_ave - ave) * (cur_ave - ave); 
    }

    printf("%.4lf", sqrt(sum / n));
    return 0;
} 



活动打卡代码 AcWing 104. 货仓选址

_清醒
5个月前
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 +10 ;
int q[N];
int main() {
    int n;
    cin >> n;
    for(int  i = 0; i < n; i ++) cin >> q[i];
    sort(q, q+n);
    int mid = q[n/2];
    int res = 0;
    for(int i = 0;i < n;i ++) {
        res += abs(q[i] - mid);
    }
    cout << res << endl;
}


活动打卡代码 AcWing 1055. 股票买卖 II

_清醒
5个月前
#include <iostream>
using namespace std;
const int N = 100000;
int q[N];

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++ )
        cin >> q[i];

    int res = 0;
    for(int i = 0,j = 0; i < n; i ++) {
        if(q[j] <= q[i]) {
            res += q[i] - q[j];
            j = i;
        }
        else if(q[j] > q[i]) {
            j = i;
        }
    }
    cout << res << endl;
}


活动打卡代码 AcWing 826. 单链表

_清醒
5个月前
#include<iostream>
using namespace std;
const int N=100010;
int idx,head,n[N],ne[N];
int a;
void add_head(int x){
    n[idx]=x;
    ne[idx]=head;
    head=idx++;
}
void add(int k,int x){
    n[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx++;
}
void remove(int k){
    ne[k]=ne[ne[k]];
}

int main(){

    head=-1;idx=0;
    cin>>a;
    while(a--){
        string op;
        int k,x;
        cin>>op;
        if(op=="D")
        {

            cin>>k;
            if(!k)head=ne[head];
            remove(k-1);
        }
        else if(op=="H")
        {
            cin>>x;
            add_head(x);
        }
        else if(op=="I"){
            int k,x;
            cin>>k>>x;
            add(k-1,x);
        }
    }
    for(int i=head;i!=-1;i=ne[i])
      cout<<n[i]<<" ";
    return 0;

}



活动打卡代码 AcWing 1207. 大臣的旅费

_清醒
5个月前
#include <bits/stdc++.h>
using namespace std;

const int  N = 100010;

struct Edge{
    int id, w;
};

vector<Edge> h[N];
int dis[N];

void dfs(int u, int father, int distance) {
    dis[u] = distance;
    //cout << u << " "<< distance << endl;
    for(int i = 0;i < h[u].size();i++){
        if(h[u][i].id != father) 
            dfs(h[u][i].id, u, distance + h[u][i].w);
    }
}

int main() {
    int n;
    cin >> n;
    int a, b, c;
    for(int i = 0; i < n - 1; i ++) {
        scanf("%d%d%d",&a,&b,&c);
        h[a].push_back({b,c});
        h[b].push_back({a,c});
    }
    dfs(1, -1, 0);
    int res = 0;
    for(int i = 1; i <= n; i++) {
        if(dis[i] > dis[res]) res = i;
    }
    dfs(res, -1, 0);
    res = 0;
    for(int i = 1; i <= n; i++) {
        if(dis[i] > dis[res]) res = i;
    }
    //cout << "res = "<< res<<endl;
    int ans = dis[res];
    printf("%lld\n",(long long)(21+ans)*ans/2) ;

    return 0 ;
}


活动打卡代码 AcWing 1233. 全球变暖

_清醒
5个月前
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second

typedef pair<int,int> PII;

const int N = 1010;
char g[N][N];
int vis[N][N];

int dx[5] = {0, 0, 1, -1, 0};
int dy[5] = {1, -1, 0, 0, 0};
bool isFlood(int x_, int y_) {
    for(int i = 0; i < 5; i ++) {
       int  x = x_ + dx[i];
        int y = y_ + dy[i];
        if(g[x][y] == '.') return true;
    }
    return false;
}


bool dfs(int x_, int y_) {
    vis[x_][y_] = 1;
    int flag = 0;
    PII p;
    p.x = x_, p.y = y_;
    queue<PII> q;
    q.push(p);
    while(!q.empty()) {
        PII t = q.front();
        q.pop();
        for(int i = 0; i < 4; i ++) {
            int x = t.x, y = t.y;
            x += dx[i], y += dy[i];
            if(!vis[x][y] && g[x][y] == '#'){
                vis[x][y] = 1;
                q.push({x, y});
                if(!isFlood(x, y)) flag = 1;
            }
        }
    }
    return flag;
}

int main() {
    int n;
    int res = 0;
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> g[i];

    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++) {
            if(g[i][j] =='#' && vis[i][j] == 0) 
                if(dfs(i,j) == 0) res ++;
        }
    cout << res << endl;
}


活动打卡代码 AcWing 1113. 红与黑

_清醒
5个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 25;
int H, W;
char g[N][N];
int vis[N][N];

struct Point {
    int x, y;
}st;

int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};

bool check(int x, int y) {
    if(g[x][y] == '#') return false;
    else if(x < 0|| y < 0 || x >= H || y >= W) return false;
    else if(vis[x][y]) return false;
    return true;
}

int bfs() {
    memset(vis, 0, sizeof vis);
    vis[st.x][st.y] = 1;
    int res = 1;
    queue<Point> q;
    q.push(st);
    while(!q.empty()) {
        //cout << 111111111;
        Point t = q.front();
        q.pop();
        for(int i = 0; i < 4; i++) {
            int x = t.x +dx[i];
            int y = t.y +dy[i];
            if(check(x, y)) {
                res++;
                q.push({x,y});
                vis[x][y] = 1;
            }
        }
    }
    return res;
}


int main() {
    while(cin >> W >> H && W || H) {
        for(int i = 0; i < H; i ++) {
            scanf("%s",g[i]);
            for(int j = 0; j < W; j ++) {
                if(g[i][j] == '@') st = {i,j};
            }
        }
        int res = bfs();
        cout << res << endl;
    }
}