【牛客算法周周练2】

A.思路：a不大 直接模拟即可 如果数据范围大点套个大数板子就好

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int x;

    cin >> x;

    int y = 0;
    int k = 1;

    int a = x;
    int b = x;

    while(a)
    {
        a /= 10;
        k *= 10;
    }

    k /= 10;

    while(x)
    {
        y += (x%10)*k;
        x /= 10;

        k /= 10;
    }

    cout << b + y << '\n';

    return 0;
}

B.思路：这题有点离谱 涨个姿势 bitset优化 根据抽屉原理知道 如果你n >= 3600 是一定存在的
然后根据bitset 将多余的3600 和 剩下的加上 |运算就是加上的含义

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

#define LL long long

int dp[N][3605],a[N];

int main()
{
    ios::sync_with_stdio(false);

    int t;

    cin >> t;

    while(t --)
    {
        int n;

        cin >> n;

        for(int i = 1;i <= n;i ++)
            cin >> a[i];

        bitset<3600>bit;

        for(int i = 1;i <= n;i ++)
        {
            int x = a[i]%3600;

            bit |= (bit << x) | (bit >> (3600 - x));

            bit[x] = 1;
        }

        if(bit[0] == 1)
            cout << "YES" ;
        else
            cout << "NO" ;

        cout << '\n';
    }

    return 0;
}

C.思路：两种方法 根据数学公式的话有个 O(1)就可以得到答案 也可以打表 然后二分答案 总共就三万多个
1.二分

#include <bits/stdc++.h>

using namespace std;

#define LL long long

vector <LL> vec;


int main()
{
    ios::sync_with_stdio(false);

    for(LL i = 0;i * i<= 1000000000 ;i ++)
        vec.push_back(i * i);

    int n ;

    cin >> n ;

    while(n --)
    {
        LL l,r;

        cin >> l >> r;

        cout << upper_bound(vec.begin(),vec.end(),r)  - lower_bound(vec.begin(),vec.end(),l) << '\n';
    }

    return 0;
}

2.数学公式

#include <bits/stdc++.h>

using namespace std;

#define LL long long

vector <LL> vec;


int main()
{
    ios::sync_with_stdio(false);

    int n ;

    cin >> n ;

    while(n --)
    {
        LL l , r;

        cin >> l >> r;

        int x = (int)sqrt(r);
        int y = (int)sqrt(l);

        int res = x - y ;

        if(y * y == l)
            res ++ ;

        cout << res << '\n';
    }
    return 0;
}

D.看到跟树有关的 多半是有dfs没跑了 关键点在于对于树上的更新 我们先跑dfs标记出每个点的父亲 然后用sum[i][3] 0 1 2 分别代表对本身 儿子 孙子 的影响 同样波及的有它父亲 和 爷爷 对于他的兄弟结点 就把影响算在 他们父亲结点对儿子结点的影响上即可

答案的话就是 本身的影响 + 父亲爷爷 对它的影响

#include <bits/stdc++.h>

using namespace std;

const int N = 750005,INF = 0x3f3f3f3f;

vector <int> e[N];
int fa[N],sum[N][3];///本身 儿子 孙子

void dfs(int u,int v)///预处理每个点父亲结点的关系
{
    fa[u] = v;

    for(int i = 0;i < e[u].size();i ++)
    {
        if(e[u][i] == v)
            continue;

        dfs(e[u][i],u);
    }
}

int main()
{
    int n , q;

    ios::sync_with_stdio(false);

    cin >> n >> q;

    for(int i = 1;i < n;i ++)
    {
        int u,v;

        cin >> u >> v;

        e[u].push_back(v);
        e[v].push_back(u);
    }

    dfs(1,0);

    while(q --)
    {
        int x;

        cin >> x;

        sum[x][1] ++ ,sum[x][2] ++ ;///对儿子孙子
        sum[fa[x]][0] ++ ,sum[fa[fa[x]]][0] ++ ;///父亲 爷爷
        sum[fa[x]][1] ++;///i 本身 和 i 的兄弟结点共同波及

        cout << sum[x][0] + sum[fa[x]][1] + sum[fa[fa[x]]][2] << '\n';
    }

    return 0;
}