头像

仰望星空z




离线:2小时前


最近来访(39)
用户头像
qyc
用户头像
cyb-包子
用户头像
yxc
用户头像
紫罗兰永恒花园
用户头像
dyl_
用户头像
moreexcellent
用户头像
daydayyang
用户头像
leimingze
用户头像
zkjjy
用户头像
用户头像
skydegree
用户头像
Supimo

活动打卡代码 AcWing 1073. 树的中心

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

using namespace std;

const int N = 10010, M = 2 * 10010;

int n, e[M], ne[M], h[N], idx, w[M];
int d1[N], d2[N], p[N], up[N];

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}

int dfs_d(int u, int father)
{
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == father)
        continue;
        int d = dfs_d(j, u) + w[i];

        if(d >= d1[u])
        d2[u] = d1[u], d1[u] = d, p[u] = j;
        else if(d > d2[u])
        d2[u] = d;
    }
    return d1[u];
}

void dfs_u(int u, int father)
{
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == father)
        continue;

        if(j == p[u])
        up[j] = max(up[u], d2[u]) + w[i];
        else
        up[j] = max(up[u], d1[u]) + w[i];

        dfs_u(j, u);
    }
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n;

    for(int i = 1; i < n; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    dfs_d(1, -1);
    dfs_u(1, -1);

    int ans = 0x3f3f3f3f;

    for(int i = 1; i <= n; i ++ )
    ans = min(ans,max(d1[i], up[i]));

    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 1072. 树的最长路径

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

using namespace std;

const int N = 10010, M = 2 * N;

int n, d1[N], d2[N], w[M], res = 0;
int ne[M], e[M], h[N], idx;

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}

int dfs(int u, int father)
{
    int dis = 0, d1 = 0, d2 = 0;

    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == father)
        continue;

        int d = dfs(j, u) + w[i];

        if(d >= d1)
        d2 = d1, d1 = d;
        else if(d > d2)
        d2 = d;
    }
    res = max(res, d1 + d2);
    return d1;
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    for(int i = 1; i < n; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    dfs(1, -1);

    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 3418. 杨辉三角形

/*
关于为什么要逆序枚举
            1  ---> C(0, 0)
          1 
        1   2  ---> C(2, 1)
      1   3                             ---> C(2n, n)
    1   4   6  ---> C(4, 2)
  1   5   10
1   6   15  20 ---> C(6, 3)
如果我顺序枚举,比如第斜二行枚举得到6,那么我能否认为这个6就是答案?不能
因为6右边是递增,而6的右边的斜上方是递减,所以如果我顺序枚举斜线,那么我可能可以从左边的斜上方
左左边的斜斜上方找到一个值,也就是通过增减,增增减的方法来找到6的。这样找到的6下标一定会更小

所以我要从最后一行枚举,枚举到了答案的话,那么如果还想找到答案出现的位置,那么只能从左下方找。而左下方的下标一定更大
所以找到的一定是答案,如果没找到,说明答案不在这一行,就找倒数第二行,已经确定了倒数第一行没找到答案,
所以我无法通过左然后斜上,也就是跳到最后一行找答案(就是因为最后一行没答案我才走到倒数第二行的)
*/
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

LL n;

LL C(int a, int b)
{
    LL res = 1;
    for(int i = 1, j = a; i <= b; i ++ , j -- )
    {
        res = res * j / i;
        if(res > n)
        return res;
    }
    return res;
}

bool cheak(int k)                   //当输入1,则l = 32, r = 1, 跳过while,然后答案出错,所以r取值要改变
{
//    cout << " yes" << endl;
    LL l = 2 * k, r = max(n, l);
    while(l < r)
    {
        LL mid = l + r >> 1;
        if(C(mid, k) >= n)
        r = mid;
        else
        l = mid + 1;
    }

    if(C(r, k) > n)
    return false;


    LL p = (r + 1) * r / 2 + k + 1;
    cout << p << endl;

    return true;
}

int main()
{
    cin >> n;

    for(int k = 16; ; k -- )
    if(cheak(k))
    break;

    return 0;
}


活动打卡代码 AcWing 3417. 砝码称重

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 1e5 + 10;

int n, w[110],s, m;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++ )
    {
        cin >> w[i];
        s = max(s, w[i]);
        m += w[i];
    }

    bool f[110][N + s];

    f[0][0] = true;

    for(int i = 1; i <= n; i ++ )
    for(int j = 0; j <= m; j ++ )
    {
        f[i][j] = f[i - 1][j] || f[i - 1][abs(j - w[i])] || f[i - 1][j + w[i]];
    }

    int ans = 0;
    for(int j = 1; j <= m; j ++ )
    if(f[n][j])
    ans ++ ;

    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 3416. 时间显示

#include <iostream>

using namespace std;

long long n;

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

    n /= 1000;
    n %= 86400;

    int h = n / 3600;
    n %= 3600;
    int m = n / 60;
    int s = n % 60;

    printf("%02d:%02d:%02d", h, m, s);
    return 0;
}


活动打卡代码 AcWing 2068. 整数拼接

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

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

LL a[N], n, k, s[11][N], f[11][N];

int main()
{
    cin >> n >> k;

    for(int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        LL t = a[i] % k;
        for(int j = 0; j < 11; j ++ )
        {
            s[j][t] ++ ;
            t = t * 10 % k;         //为什么可以这样迭代呢?因为下一行只是比上一行多乘了一个10,所以上一行mod之后乘以10然后mod的结果和乘100mod的结果一样
        }                           //反而如果你乘100,那么到后面10000000的时候可能会直接爆int,而这样迭代结果一样,计算过程还不会爆
    }

    LL res = 0;

    for(int i = 1; i <= n; i ++ )
    {
        int t = a[i] % k;
        int l = to_string(a[i]).size();
        res += s[l][(k - t) % k];

        int r = t;
        while(l -- )
        r = r * 10 % k;
        if(r == (k - t) % k)
        res -- ;
    }

    cout << res << endl;

    return 0;
}
/*
1 由题意知道,我们用序列中的a[i]、a[j]来拼接出一个数,且i和j不相同,a[i]在前在后是不同的选法。
2 例如a[j]在前,a[i]在后,即a[j]*(10^leni) + a[i],leni表示a[i]的位数。
3 当这个数对m取模为零,即(a[j]*(10^leni)+a[i])%m==0
那么我们就可以得到 a[j] * (10^leni)%m = (-a[i])%m注意:这里的-a[i]为负数
我们知道对负数取模,在c++会得到负数。例如(-5)%3=-2,因此我们写成(3+(-5)%3)%3=1,就可以得到正数。
最重要的来了, 5%3=2 所以,3-5%3 = (3+(-5)%3)%3=1
因此代码中(m-a[i]%m)%m其实就是利用(正的)a[i]求得(-a[i])%m。
4 代码中预处理求的是a[j] * (10^leni)%m的余数出现的次数。然后我们枚举每一个a[i],利用(m-t)%m求出(-a[i])%m,根据(-a[i])%m查找预处理出来的表。

简而言之就是可以通过公式转化a[j] * (10^leni)%m = (-a[i])%m,但是这是数学里的公式,也就是(-a[i]) % m >=0的
而c++里是小于0的,所以要通过int t = a[i] % k,   (k - t) % k 来转化,也就是((-a[i] % k) + k) % k,这是47用来查表的
查表查的是啥呢,就是a[j] * (10^leni)%m,这里要通过迭代来得到,刚开始的预处理出来了

最后要检查以下a[i]是否重复,38——40,将a[i]转化成a[j] * (10^leni)%m(j用i来代替罢了),然后与(k - t) % k 来比较,如果相等则说明a[i]自己和自己凑成的数是能整除k

明明res应该+2啊,这里是怎么处理出来的。简单,如果枚举ij和ji都能整除k,那么枚举i的时候加一次,枚举j的时候也会加一次的
*/





活动打卡代码 AcWing 2067. 走方格

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

using namespace std;

const int N = 35;

int a[N][N], f[N][N], n, m, book[N][N];

int main()
{
    cin >> n >> m;

    for(int i = 1; i <= n; i ++ )
    for(int j = 1; j <= m; j ++ )
    if(i % 2 == 0 && j % 2 == 0)
    book[i][j] = 1;

    f[1][1] = 1;

    for(int i = 1;i <= n; i ++ )
    for(int j = 1;j <= m; j ++ )
    {
        if(i == 1 && j == 1)
        continue;
        if(book[i][j] == 1)
        continue;

        f[i][j] = f[i - 1][j] + f[i][j - 1];
    }

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

    cout << f[n][m] << endl;

    return 0;

}


活动打卡代码 AcWing 2066. 解码

#include <iostream>
#include <cstring>

using namespace std;

string a;

int main()
{
    cin >> a;

    for(int i = 0; a[i]; i ++ )
    {
        if(a[i] > '9' && a[i + 1 ] <= '9' && a[i + 1] >= '1')
        {
            int k = a[i + 1] - '0';
            while(k -- )
            cout << a[i];

            i ++ ;
        }
        else
        cout << a[i];
    }
    return 0;
}
//注意怎么枚举之间的关系,这里枚举当前字母是否是数字,不是数字并且前面有数字,则可以按前面数字大小输出,然后i++以免将前面的数字输出
//当枚举到数字 字母这种情况也会正确输出数字,也能处理 Q234Z这种情况


活动打卡代码 AcWing 2065. 整除序列

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

using namespace std;

long long n;

int main()
{
    cin >> n;

    while(n)
    {
        cout << n <<' ';
        n /= 2;
    }
    return 0;
}


活动打卡代码 AcWing 3492. 负载均衡

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

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int n, m;
int s[N];
priority_queue<PII, vector<PII>, greater<PII>> q[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &s[i]);
    while (m -- )
    {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        while (q[b].size() && q[b].top().x <= a)    //如果队列b不为空,且队列b的堆顶元素(最早的结束时间) <= a,则说明可以执行完堆顶,然后再执行新的abcd
        {                                           
            s[b] += q[b].top().y;                   //所以让队列b的堆顶出队,要先将时间数组b恢复 + q[b].top().y
            q[b].pop();
        }
        if (s[b] < d) puts("-1");                   //上面是特殊处理,如果堆顶的结束时间比新任务的小,那么就出队,然后s恢复
        else                                        //如果第二个堆顶还是小就继续出队,直到机器算的任务大于1或者全部出队。
        {
            q[b].push({a + c, d});                  //如果当前计算机b的算力足够,那么就将新任务入队
            s[b] -= d;                              //入队后算力减少
            printf("%d\n", s[b]);                   //输出剩余算力
        }
    }
    return 0;
}
/*
priority如果只是一个q,那么就是一个优先队列数字,如果是q[N]那么就是多个优先队列数组
不同的机器属于不同的优先队列数组中
并且优先队列是以x为第一关键字排序(因为是queue),所以每个机器的优先队列是以结束时间为第一关键字来做堆顶且是小根堆

对于while的特殊处理,会不会有这种情况,第二小和堆顶的结束时间相隔很近,然后新加入的这个任务的开始时间
相比之下是第三小,但是任务需要的算力要堆顶和第二小都出队才能执行的情况?

会出现比如数据
2 6
5 5
1 1 5 3
2 2 2 6
3 1 2 3
4 1 2 1
5 1 3 3
6 1 3 5
任务1入对,任务4入队,此时s[1] = 0, 当时间为6时,出队堆顶,但是只出队堆顶明显时不够的,因为任务6需要算力5,
所以上面的才会用while啊,while出队之后发现新的堆顶还是<=a,所以继续出队
*/