头像

wuog




离线:6小时前


新鲜事 原文

wuog
3天前
有没有中石油北京的大佬呀!



wuog
12天前

题意

给定 n 个正整数,找出它们中出现次数最多的数。

算法—直接模拟

思路

由于数据不大可以直接用数组操作,找到最大即可!

代码
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;
    int a[10005];
    memset(a,0,sizeof a);
    for(int i=1;i<=n;i++){
        int t;cin>>t;a[t]++;
    }
    int ans=0,res=0;
    for(int i=1;i<=10000;i++){
        if(res<a[i])ans=i,swap(a[i],res);

    }
    cout<<ans<<endl;
}


活动打卡代码 AcWing 479. 加分二叉树

wuog
28天前
#include <cstdio>

const int N=31;

int n,w[N];
int f[N][N],g[N][N];

void write(int l,int r)
{
    if(l>r)return;
    printf("%d ",g[l][r]);
    write(l,g[l][r]-1);
    write(g[l][r]+1,r);
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",w+i),f[i][i]=w[i],g[i][i]=i;
    for(int l=1;l<n;l++)
        for(int i=1;i+l<=n;i++)
        {
            int j=i+l;
            for(int k=i;k<=j;k++)
            {
                int ls=k==i?1:f[i][k-1],rs=k==j?1:f[k+1][j],s=ls*rs+w[k];
                if(s>f[i][j])f[i][j]=s,g[i][j]=k;
            }
        }
    printf("%d\n",f[1][n]);
    write(1,n);
    return 0;
}


活动打卡代码 AcWing 257. 关押罪犯

wuog
29天前
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define endl '\n'
const int maxl = 2e5 + 7;
const int inf = 0x3f3f3f3f;
struct node
{
    int v, w;
};
vector<node> edge[maxl];
int col[maxl];
int n, m, x;
bool dfs(int u,int fa)
{
    col[u] = -col[fa];
    for(auto&tt:edge[u])
    {
        int v = tt.v, w = tt.w;
        if(w<=x)
            continue;
        if(!col[v])
        {
            if(!dfs(v, u))
                return false;
        }
        else
        {
            if(col[v]!=col[fa])
                return false;
        }
    }
    return true;
}
bool check()
{
    memset(col, 0, sizeof col);
    col[0] = 1;
    for (int i = 1; i <= n;i++)
    {
        if(!col[i])
            if(!dfs(i, 0))
                return false;
    }
    return true;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for (int i = 0; i<m;i++)
    {
        int u, v, w;
        cin>>u>>v>>w;
        edge[u].push_back({v, w});
        edge[v].push_back({u, w});
    }
    int l = 0, r = inf;
    while (l<=r)
    {
        int mid = l + r >> 1;
        x = mid;
        if(check())
            r = mid - 1;
        else
            l = mid + 1;
    }
    cout << l;
}



活动打卡代码 AcWing 1432. 棋盘挑战

wuog
29天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15;

int n;
bool col[N], dg[N * 2], udg[N * 2];
int path[N], ans;

void dfs(int x)
{
    if (x > n)
    {
        ans ++ ;
        if (ans <= 3)
        {
            for (int i = 1; i <= n; i ++ )
                cout << path[i] << ' ';
            cout << endl;
        }
        return;
    }

    for (int y = 1; y <= n; y ++ )
        if (!col[y] && !dg[x + y] && !udg[x - y + n])
        {
            path[x] = y;
            col[y] = dg[x + y] = udg[x - y + n] = true;
            dfs(x + 1);
            col[y] = dg[x + y] = udg[x - y + n] = false;
            path[x] = 0;
        }
}

int main()
{
    cin >> n;
    dfs(1);
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 1414. 牛异或

wuog
29天前
#include <iostream>
using namespace std;

const int N = 100010, M = N * 21;
int s[N], son[M][2], id[M], idx;

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

int search(int x) {
    int p = 0;
    for (int i = 20; i >= 0; i--) {
        int u = x >> i & 1;
        if (son[p][!u]) p = son[p][!u];
        else p = son[p][u];
    }
    return id[p];
}

int main() {
    int n;
    scanf("%d", &n);

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

    int res = -1, l, r;
    insert(s[0], 0);
    for (int i = 1; i <= n; i++) {
        int k = search(s[i]);
        int t = s[k] ^ s[i];
        if (res < t) {
            l = k + 1, r = i;
            res = t;
        }
        insert(s[i], i);
    }

    cout << res << ' ' << l << ' ' << r << endl;

    return 0;
}


活动打卡代码 AcWing 499. 聪明的质监员

wuog
29天前
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;

int n, m;
LL S;
int w[N], v[N];
int sum[N], cnt[N];
int L[N], R[N];

LL get_Y(int W) {
    for (int i = 1; i <= n; ++i) {
        if (w[i] >= W) {
            cnt[i] = cnt[i - 1] + 1;
            sum[i] = sum[i - 1] + v[i];
        } else {
            cnt[i] = cnt[i - 1];
            sum[i] = sum[i - 1];
        }
    }
    LL res = 0;
    for (int i = 0; i < m; ++i) {
        res += (sum[R[i]] - sum[L[i] - 1]) * (cnt[R[i]] - cnt[L[i] - 1]);
    }
    return res;
}
int main() {
    scanf("%d%d%lld", &n, &m, &S);
    for (int i = 1; i <= n; ++i) scanf("%d%d", &w[i], &v[i]);
    for (int i = 0; i <  m; ++i) scanf("%d%d", &L[i], &R[i]);

    int l = 0, r = 1e6 + 1;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (get_Y(mid) >= S) l = mid;
        else r = mid - 1;
    }
    printf("%lld\n", min(get_Y(l) - S, S - get_Y(l + 1)));
    return 0;
}



活动打卡代码 AcWing 122. 糖果传递

wuog
29天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 1000010;

int n;
LL s[N], c[N];

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

    LL b = s[n] / n;
    int k = 0;
    for (int i = 1; i < n; i ++ ) c[k ++ ] = i * b - s[i];
    c[k ++ ] = 0;

    nth_element(c, c + k / 2, c + k);
    LL res = 0;
    for (int i = 0; i < k; i ++ )
        res += abs(c[i] - c[k / 2]);

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



活动打卡代码 AcWing 1308. 方程的解

wuog
29天前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 150;

int k, x;
int f[1000][100][N];

int qmi(int a, int b, int p)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

void add(int c[], int a[], int b[])
{
    for (int i = 0, t = 0; i < N; i ++ )
    {
        t += a[i] + b[i];
        c[i] = t % 10;
        t /= 10;
    }
}

int main()
{
    cin >> k >> x;
    int n = qmi(x % 1000, x, 1000);
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j <= i && j < k; j ++ )
            if (!j) f[i][j][0] = 1;
            else add(f[i][j], f[i - 1][j], f[i - 1][j - 1]);  
    int *g = f[n - 1][k - 1];
    int i = N - 1;
    while (!g[i]) i -- ;
    while (i >= 0) cout << g[i -- ];

    return 0;
}



活动打卡代码 AcWing 754. 平方矩阵 II

wuog
29天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int a[N][N];

int main()
{
    while (cin >> n, n)
    {
        for (int i = 1; i <= n; i ++ )
        {
            for (int j = i, k = 1; j <= n; j ++, k ++ )
            {
                a[i][j] = k;
                a[j][i] = k;
            }
        }

        for (int i = 1; i <= n; i ++ )
        {
            for (int j = 1; j <= n; j ++ )
                cout << a[i][j] << ' ';
            cout << endl;
        }
        cout << endl;
    }

    return 0;
}