牛客算法周周练2(ABCD)

A题：
签到题，直接逆序一下然后相加即可。
代码：

#include<bits/stdc++.h>
using namespace std;

void solved(){
    int n;cin>>n;
    int t = n;
    int res = 0;
    while(t){
        res = res * 10 + (t % 10);
        t/=10;
    }
    cout<<res + n<<endl;
}
int main(){
    solved();
    return 0;
}

C题：

思路：
直接把表打出来，然后二分查一下位置相减即可，注意一下r==table[end]相等的情况。还有l可能等于0需要加进来考虑一下(因为这个白白送了几发wa)。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 10;
typedef long long int ll;
ll table[maxn];
void solved(){
    for(ll i = 0; i <= 100000; i++){
        table[i + 1] = i * i;
    }
    int t;scanf("%d",&t);
    while(t--){
        ll l,r;scanf("%lld%lld",&l,&r);
        ll start = lower_bound(table + 1,table + 1 + 100001,l) - table;
        ll end = lower_bound(table + 1,table + 1 + 100001,r) - table;
        if(table[end] == r)
        cout<<end - start + 1<<endl;
        else cout<<end - start<<endl;
    }
}
int main(){
    solved();
    return 0;
} 

在场上就写了两题，后面划水去了。
D题：

思路：暴力是肯定不行的，这个看题解写出来的,主要由于是一棵树可以将问题简化，因为在做这个题的时候我脑子里有奇奇怪怪的图，比如 假如我们现在要操作的是黑球，如果说要更新他父亲节点的父亲节点，和他儿子节点的儿子节点，能是比较困难的，但是由于他是一棵树，我们可以稍微转化一下， 就变成这样了，我们考虑有一个数组来计数cnt[i][3],cnt[i][0]:表示节点i本身被计数一次，cnt[i][1]:表示节点i的儿子节点被计数一次，cnt[i][2]:表示节点i的儿子的儿子被计数一次。
当我们操作一个节点的时候，考虑它可能会影响到那些节点，给这些节点计数，操作一个节点，它的儿子，儿子的儿子，父亲，父亲的父亲，都需要计数，假如就像上面那个图，父亲节点有多个，父亲的父亲节点也有多个，我们转化下面这个图，因为它是一棵树，那么它只有唯一一个父亲节点和父亲的父亲节点(祖先节点)，其他节点我们都可以认为是它的兄弟节点。
这样就是cnt[i][1]++,cnt[i][2]++,cnt[f[i]][0]++,cnt[f[f[i]]][0]++,cnt[f[i]][1]++,这样就可以计算会它会影响多少节点，那么怎么计算当前节点i呢，换个角度，对于当前节点i它有且仅有可能被它父亲，祖先节点影响，再加上自己本身被影响过的次数即可(因为它有可能是别人的父亲或者祖先，别人在计算的时候就对它进行了计算)。所以答案就是cnt[i][0] + cnt[f[i]][1] + cnt[f[f[i]]][2].
代码

#include<bits/stdc++.h>
using namespace std;
 //dfs先求每个节点的父亲节点然后计数
const int maxn = 750000 + 10;
struct edge{
    int v,next;
    edge(){}
    edge(int a,int b):v(a),next(b){}
}e[maxn << 1];
int head[maxn],tot;
int cnt[maxn][3];
int fa[maxn];
void add(int from,int to){
    e[++tot].v = to;
    e[tot].next = head[from];
    head[from] = tot;
}
void dfs(int v,int f){
    fa[v] = f;
    for(int i = head[v]; i ; i = e[i].next){
        if(e[i].v != f){
            dfs(e[i].v,v);
        }
    }
}
void solved(){
    int n,q;cin>>n>>q;
    for(int i = 1; i < n; i++){
        int u,v;cin>>u>>v;
        add(u,v);add(v,u);
    }
    dfs(1,0);
    while(q--){
        int v;cin>>v;
        cnt[v][1]++;
        cnt[v][2]++;
        cnt[fa[v]][0]++;
        cnt[fa[fa[v]]][0]++;
        cnt[fa[v]][1]++;
        cout<<cnt[v][0] + cnt[fa[v]][1] + cnt[fa[fa[v]]][2]<<endl;
    }
}
int main(){
    solved();
    return 0;
}

B：


这个题其实没那没复杂。。。
题目要求我们只要找到一些数使得他们的和是3600倍数即可，我们可以先对所有数字取模，然后用一个辅助数组求出在取模意义下，所有数字相加的模3600的结果，如果存在某个数模3600等于0即可。
代码

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int dp[maxn],temp[maxn];
//dp[i]:
//dp[i] = 0,表示给的数据之和组不成i 
//dp[i] = 1,表示可以用给的数据之和组成i
//判断dp[i] == 1即可 
void solved(){
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        memset(temp,0,sizeof(temp)); 
        memset(dp,0,sizeof(dp));
        for(int i = 1; i <= n; i++){
            int a;cin>>a;a %= 3600;
            if(!dp[0]){
                for(int k = 0; k < 3600; k++){
                    if(dp[k] > 0 || k == 0)temp[(a + k) % 3600] = 1;
                }
                for(int k = 0; k < 3600; k++){
                    dp[k] += temp[k];
                    if(temp[k] == 1)temp[k] = 0;
                }
            } 
        }
        if(dp[0])cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}
int main(){
    solved();
    return 0;
}