牛客算法周周练10 解题报告(A.签到 B.贪心 D.暴力 E.二分答案 F.树形dp)

A.论如何出一道水题
签到题，注意下特殊情况

n=input()
n=int(n)
if n==1:
    print(2)
else:
    print(2*n-1)

B.暴力出奇迹
感觉好难想。。
这道题的方法是：按位把ai分解，然后，按照二进制位，纵向的看各个ai，若在一段中ai在某一位上都是1，那么，这一点"与运算"出来的结果也会是1，那么，我们就可以尝试下这个值是不是最大值(说简单点，就是一整段&之后去和ans取一个max),最后出来的结果就是最大值。
直接写完会有个疑虑:会不会存在一种情况，中间有个0，但是选出来的AND*SUM更大呢？这个得看其他位上的情况。若其他位上的这个位置都为0，那么很显然这一段是没有尝试的必要的，因为一&一下AND的值就成为0了。否则，这一段总会在纵向看某一位的时候被尝试到的。所以，这是一种贪心算法。

#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset> 
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}

template<typename T> void read(T &x)
{
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod 
    ll ans=1;
    while(n){
        if(n&1) ans=(ans*a)%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans%mod;
}
//==============================================================
const int maxn=1e5+10;
ll n;
ll a[maxn];

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    //===========================================================
    read(n);
    ll ans=0;
    rep(i,1,n) read(a[i]);
    rep(j,0,18){
        ll sum=0,AND=a[1];
        rep(i,1,n){
            if((a[i]>>j)&1) AND&=a[i],sum+=a[i],ans=max(ans,AND*sum);
            else{
                AND=a[i+1];
                sum=0;
            }
        }
    }
    write(ans);
    //===========================================================
    return 0;
}

D.Cliques
这题看到数据范围应该就是要暴力的(但还是不会Orz)。
首先要理解好Cliques(团)这个概念，他指的是一个连通分量中每两个顶点都有一条相连的边(注意，是边，不是路径),因此，我们可以得到以下结论：在一个图中，如果两个点之间存在路径，则，与其中一个点相连的点肯定也需要和另一个点存在路径相连，这是我们走下去的依据。
这道题提供了两种操作：删除已存在边或增加本不存在的边。我们可以枚举任意两个点，若这两个点有直接的边相连，我们再去枚举第三个点，若这第三个点和这两个点都有边相连，则符合题意，无需操作。否则，需要操作。
我们可以考虑三种方法：
1、把第一、第二个点之间的边删掉，让他们不连通，就没有这个烦恼啦
2、把缺失的边给添加上，然后再递归一层dfs验证整个图是否符合题意。
3、把原本链接第三个点的边删掉，也是递归一层验证。
然后全局顶一个res去记录最小操作数就行了。
但是，这道题因为运算量很大，所以，题目给了我们限制：10次以上的算作无法完成，所以，每次递归到10次之后可以直接return，该更改方案不成立。
另外，如果在某一个递归中发现不符合题意，则可以直接break跳出循环，不用继续尝试，因为如果需要更新答案，下一层dfs已经更新好了，不能更新依旧不能更新，这一层没有再继续的必要。

#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset> 
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}

template<typename T> void read(T &x)
{
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod 
    ll ans=1;
    while(n){
        if(n&1) ans=(ans*a)%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans%mod;
}
//==============================================================
int e[105][105];
int n,t;
int res=11;
void dfs(int step){
    if(step>=res) return ;
    int flag=0;
    rep(i,1,n){
        rep(j,i+1,n){
            if(e[i][j]){
                rep(k,1,n){
                    if(i==k||j==k) continue;
                    if(!(e[i][k]^e[j][k])) continue;
                    flag=1;
                    e[i][j]^=1,e[j][i]^=1;
                    dfs(step+1);
                    e[i][j]^=1,e[j][i]^=1;

                    e[i][k]^=1,e[k][i]^=1;
                    dfs(step+1);
                    e[i][k]^=1,e[k][i]^=1;

                    e[j][k]^=1,e[k][j]^=1;
                    dfs(step+1);
                    e[j][k]^=1,e[k][j]^=1;
                    if(flag) break;
                }
            }
            if(flag) break;
        }
        if(flag) break;
    }
    if(!flag){
        res=min(res,step);
    }
    return ;
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    //===========================================================
    read(t);
    int kase=0;
    while(t--){
        res=11;
        read(n);
        rep(i,1,n){
            rep(j,1,n){
                read(e[i][j]);
            }
        }
        dfs(0);
        if(res>=11){
            printf("Case #%d: %d\n",++kase,-1);
        }
        else{
            printf("Case #%d: %d\n",++kase,res);
        }
    }
    //===========================================================
    return 0;
}

E.跳石头
这道题写出来也是一波三折的。。
这道题的做法是二分验证答案。具体还是看代码吧，语言不好描述。。有点贪心的思路。

#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset> 
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
//#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}

template<typename T> void read(T &x)
{
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod 
    ll ans=1;
    while(n){
        if(n&1) ans=(ans*a)%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans%mod;
}
//==============================================================
const int maxn=5e4+10;
ll d[maxn];
ll n,m,l;
bool check(ll x){
    int cnt=0;
    int pre=0;
    rep(i,1,n){
        if(d[i]-d[pre]<x){
            cnt++;
        }
        else{
            pre=i;
        }
    }
    if(cnt<=m) return true;
    return false;
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    //===========================================================
    read(l),read(n),read(m);
    rep(i,1,n) read(d[i]);
    d[n+1]=l;
    n++;
    ll l=0,r=1e9+7;
    while(l<=r){
        ll m=(l+r)>>1;
        if(check(m)){
            l=m+1;
        }
        else{
            r=m-1;
        }
    }
    write(l-1);
    //===========================================================
    return 0;
}

F.树上求和
这道题比较容易想。通过观察，我们会发现，树链和其实就是对每两个节点的组合都走一次。根据贪心思想，我们要是的权值和最小，只需要让经过次数最多的边权值小就行了。级数边被经过的次数，就是把这条边的两边看着两个连通块，这条边经过的次数就是两边的size的乘积。

#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset> 
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}

template<typename T> void read(T &x)
{
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod 
    ll ans=1;
    while(n){
        if(n&1) ans=(ans*a)%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans%mod;
}
//==============================================================
#define int ll
const int maxn=1e5+10;
struct Edge{
    int next,to;
}e[maxn<<1];
int n;
int head[maxn],cnt;
int si[maxn],si2[maxn];
int in[maxn];
void add(int x,int y){
    e[cnt].to=y;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
void dfs(int u,int fa){
    si[u]=1;
    for(int i=head[u];~i;i=e[i].next){
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u);
        si[u]+=si[v];
    }
    si2[u]=n-si[u];
}
vector<ll> num;
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    //===========================================================
    read(n);
    memset(head,-1,sizeof(head));
    rep(i,2,n){
        int a,b;
        read(a),read(b);
        add(a,b),add(b,a);
        in[b]++;
    }
    int s=-1;
    rep(i,1,n){
        if(in[i]==0){
            s=i;
            break;
        }
    }
    dfs(s,-1);
    rep(i,1,n){
        if(si[i]*si2[i]!=0) num.push_back(si[i]*si2[i]);
    }
    sort(num.begin(),num.end(),greater<ll>());
    ll ans=0;
    rep(i,0,num.size()-1){
        ans+=num[i]*(i+1);
    }
    write(ans);
    //===========================================================
    return 0;
}