头像

tianen




离线:21小时前


最近来访(33)
用户头像
小会儿来敲代码了
用户头像
X-7D1C11010
用户头像
Sufferingcreatinglife
用户头像
2022415
用户头像
呆@_9
用户头像
等等__
用户头像
AcWing2AK

活动打卡代码 AcWing 3531. 哈夫曼树

tianen
1天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
//哈夫曼的带权路径长度为 节点两两结合的和 的 和

const int N = 1009;

vector<int> p;
int sum, Sum;
int a, n;

int cmp(int a, int b)
{
    return a > b;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )  cin >> a, p.push_back(a);
    sort(p.begin(), p.end(), cmp);

    while(p.size() > 1)//最后一个为根节点,长度为0
    {
        sum = p[p.size() - 1] + p[p.size() - 2];
        Sum += sum;

        p.pop_back(), p.pop_back();

        p.push_back(sum);
        sort(p.begin(), p.end(), cmp);
    }


    cout << Sum;
    return 0;
}



活动打卡代码 AcWing 3477. 简单排序

tianen
2天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 1007;

vector<int> p;
bool t[N];
int n;

int main()
{
    cin >> n;

    int a;
    // for (int i = 0; i < n; i ++ )
    //     cin >> a, p.push_back(a);

    // sort(p.begin(), p.end());

    // p.erase(unique(p.begin(), p.end()), p.end());

    // for(auto x : p)
    //     cout << x << ' ';

    //桶排序
    for (int i = 1; i <= n; i++)
        cin >> a, t[a] = true;
    for (int i = 1; i <= N; i++)
        if (t[i]) cout << i << ' ';


    return 0;
}



tianen
2天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
//(a(l + 1) + ... + ar) > 100 * (r + 1 - (l + 1)) 
//->> ((a(l + 1) - 100) + ... + (ar - 100)) + 100 *(r + 1 - (l + 1)) > 100 * (r + 1 - (l + 1))
//->>((a(l + 1) - 100) + ... + (ar - 100)) > 0 
//->> sum[r] > sum[l],则判断条件为sum[r] > sum[l]
//将前缀和简化为一个单调递减序列,则在右端点固定时,找序列中 左到右 第一个小于右端点的节点即可
//①节点前缀和比序列最小值小,需要入列,因为没有比他更小的节点,
//②若比序列最小值大,则一定存在一个下标比其小,节点值也比其小的节点,这个节点与右端点的长度一定大于它,无意义

typedef long long LL;

const int N = 1000010;

int n;
LL s[N];//前缀和
int stk[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        scanf("%d", &x);
        s[i] = s[i - 1] + x - 100;//优化前缀和
    }

    int top = 0, res = 0;
    stk[ ++ top] = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if (s[stk[top]] > s[i]) stk[ ++ top] = i;//情况①
        else if (s[stk[top]] < s[i])//情况②
        {
            int l = 1, r = top;
            while (l < r)
            {
                int mid = l + r >> 1;
                if (s[stk[mid]] < s[i]) r = mid;
                else l = mid + 1;
            }
            res = max(res, i - stk[r]);
            //str[r]保存的是左节点的左一个节点de下标
            //stk[r] == (l + 1) - 1 -> i - stk[r] == i - (l + 1) + 1
        }
    }

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




活动打卡代码 AcWing 4486. 数字操作

tianen
2天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;




int main()
{
    int n; cin >> n;
    int res = 1, cnt = 0;//min, cnt
    vector<int> p;

    /*分解质因数*/
    for(int i = 2; i * i <= n; i++)
    {
        if(n % i == 0)
        {
            int c = 0;
            while(n % i == 0) n /= i, c++;//榨干
            p.push_back(c);//次数
            res *= i;//更新最小值
            while((1 << cnt) < c) cnt++;//开根号最小次数
        }
    }
    if(n > 1)//判断最后的n是否为质因数
    {
        res *= n;
        p.push_back(1);
        while((1 << cnt) < 1) cnt++;
    }

    for(auto x : p)
    {
        if(x < (1 << cnt))
        {
            cnt++;
            break;
        }
    }

    cout << res << " " << cnt;
    return 0;
}


活动打卡代码 AcWing 4485. 比大小

tianen
2天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int a, b, suma, sumb, n;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        cin >> a, suma += a;
    for (int i = 0; i < n; i ++ )
        cin >> b, sumb += b;

    if(suma >= sumb) cout <<"Yes";
    else cout << "No";

    return 0;
}


活动打卡代码 AcWing 1854. 晋升计数

tianen
2天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int p[4][2];

int a, b, c;

int main()
{
    for(int i = 0; i < 4; i++)
        cin >> p[i][0] >> p[i][1];

    c = p[3][1] - p[3][0];//白金 后 - 前
    b = p[2][1] - (p[2][0] - c);//金后 - (金前 - 晋级) 
    a = p[1][1] - (p[1][0] - b);//银后 - (银前 - 晋级)

    cout << a << endl << b << endl << c;

    return 0;
}


活动打卡代码 AcWing 1866. 围栏刷漆

tianen
3天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int a, b, c, d;

int main()
{
    cin >> a >> b >> c >> d;

    int len = 0;

    if(c > b || d < a) len = (b - a) + (d - c);//不重合
    else len = ( max(a, max(b, max(c, d))) - min(a, min(b, min(c, d))) );//重合

    cout << len;

    return 0;
}


活动打卡代码 AcWing 1775. 丢失的牛

tianen
3天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <math.h>
using namespace std;

int x, y;

int main()
{
    cin >> x >> y;
    int len = abs(x - y);

    int i = 0;
    for(i = 0; ; i++)
        {
            /*人牛相对位置不同,i结束值不同*/
            if((y >= x) && (int)pow(2, i) >= len) break; 
            i++;
            if((x > y) && (int)pow(2, i) >= len) break;
        }

    int dis = 2 * (pow(2, i) - 1) + len;
    cout << dis;

    return 0;
}



tianen
3天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

bool one[11];//记录第一次位置
bool side[11];//记录第n次观察前的位置
int ans;

int n;

int main()
{
    cin >> n;
    int num; bool s;
    while (n -- )
    {
        cin >> num >> s;
        if(!one[num]) one[num] = true, side[num] = s;
        else if(side[num] != s) ans++, side[num] = s;
    }

    cout << ans;
    return 0;
}


活动打卡代码 AcWing 3428. 放苹果

tianen
3天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;


// int sum, ans;
// int n, m;

// //若有空盘子,前面的盘子会空,后面的不会
// void dfs(int step, int num)
// {
//     if(step == n)//
//     {
//         if(m - sum >= num) ans++;
//         return;
//     }
//     for(int j = num; j <= m - sum; j++)
//     {
//         sum += j;
//         dfs(step + 1, j);
//         sum -= j;
//     }
// }

// int main()
// {
//     while(~scanf("%d%d", &m, &n))
//     {
//         sum = ans = 0;
//         dfs(1, 0);
//         cout << ans << endl;
//     }


//     return 0;
// }


const int N = 12;

int m, n;
int f[N][N]; // f[m][n] 表示把 m 个同样的苹果放在 n 个同样的盘子里的分法数

int main()
{
    for (int i = 0; i < N; i++) f[i][1] = 1; // 把 i 个苹果放在 1 个盘子里,只有 1 种方案
    for (int i = 0; i < N; i++) f[0][i] = 1; // 把 0 个苹果放在 i 个盘子里,也只有 1 种方案

    for (int i = 1; i < N; i++) // 枚举苹果数
        for (int j = 2; j < N; j++) // 枚举盘子数
            if (i < j) f[i][j] = f[i][i]; // 如果苹果数 < 盘子数,则必定有 (盘子数 - 苹果数) 个空着的盘子,可以将这些空着的盘子去掉
            else f[i][j] = f[i][j - 1] + f[i - j][j]; // 苹果数 ≥ 盘子数,分两种情况讨论,可以有一个盘子空着,也可以每个盘子至少放 1 个

    while (cin >> m >> n) cout << f[m][n] << '\n';

    return 0;
}