牛客算法周周练2 A,C,D

A题：相反数
模拟就行了，数字不是很大只要用循环让他变反再加上是原数就行了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1555555;
inline int read(){
    int s=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;c=getchar();
    }
    while(c>='0'&&c<='9'){
        s=(s<<1)+(s<<3)+(c^48);c=getchar();
    }
    return f*s;
}
int n,m,a[N];
int main(){
    int n=read();
    int s=n,u=0;
    while(s){
        u=u*10+s%10;
        s/=10;
    }
    cout<<n+u<<endl;
    return 0;
}

C题：完全平方数
n <= 100000
0<= l <= r <= 1000000000
如果我们枚举的话n*根号r，如果都是最大范围的话会超时。
所以我们用差分约束就行了
算出1到l和1到r有多少平方数然后相减就是答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1555555;
inline int read(){
    int s=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;c=getchar();
    }
    while(c>='0'&&c<='9'){
        s=(s<<1)+(s<<3)+(c^48);c=getchar();
    }
    return f*s;
}
int n,m,a[N];
int main(){
    int T=read();
    while(T--){
        int l=read(),r=read();
        int x=sqrt(l),y=sqrt(r);
        if(x*x!=l)x++;
        cout<<y-x+1<<endl;
    }
    return 0;
}

D题：小H和游戏
距离小于2的点有这么些情况：儿子，父亲，儿子的儿子，父亲的儿子（兄弟）
每次修改的时候该节点和其父亲节点+1.
查询我们查询它的儿子和它的父亲有多少个+1，儿子的儿子会让儿子+1，兄弟和自身会让父亲+1，但是还差父亲的父亲，所以我们再单独加上父亲的父亲即可.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1555555;
inline int read(){
    int s=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;c=getchar();
    }
    while(c>='0'&&c<='9'){
        s=(s<<1)+(s<<3)+(c^48);c=getchar();
    }
    return f*s;
}
int n,m,a[N],f[N],num[N];
vector<int>q[N];
void dfs(int u,int fa){
    f[u]=fa;
    for(int i=0;i<q[u].size();i++){
        int t=q[u][i];if(t==fa)continue;
        dfs(t,u);
    }
}
int main(){
    int n=read(),m=read();
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        q[x].push_back(y);
        q[y].push_back(x);
    }
    dfs(1,0);
    f[1]=n+1;
    for(int i=1;i<=5;i++){
        f[n+i]=n+i+1;
    }
    while(m--){
        int x=read();num[x]++;
        a[x]++;
        a[f[x]]++;
        int s=num[f[f[x]]]+a[f[x]];
        for(int i=0;i<q[x].size();i++){
            if(q[x][i]==f[x])continue;
            s+=a[q[x][i]];
        }
        printf("%d\n",s);
    }
    return 0;
}