2020牛客寒假算法基础集训营2

G.判正误：

牛可乐有七个整数 $a,b,c,d,e,f,g$a,b,c,d,e,f,g ，并且他猜想 $a^d+b^e+c^f=g$ad+be+cf=g。但 牛可乐无法进行如此庞大的计算。
请验证：牛可乐的猜想是否成立。
输入：
第一行一个正整数 $T$T，表示有 $T$T 组数据。
每组数据输入一行七个整数 $a,b,c,d,e,f,g$a,b,c,d,e,f,g。
保证 $1\leq$1≤ $T$T $\leq1000$≤1000 $,$, $-10^9$−109 $\leq$≤ $a,b,c,g$a,b,c,g $\leq$≤ $10^9$109 $,0$,0 $\leq$≤ $d,e,f$d,e,f $\leq$≤ $10^9$109，保证不会出现指数和底数同为 0 的情况。
输出：
每组数据输出一行，若猜想成立，输出 $Yes$Yes ，否则输出 $No$No。
题解：
  显然不能直接算，当时就卡了。看了题解才知道可以在模意义下计算，如果 $a^d+b^e+c^f=g(mod \;M)$ad+be+cf=g(modM)，那么原式有可能成立，可以通过都取几个模数来提高概率。但是如果只取 $M=1e9+7$M=1e9+7 也可以过，不知道什么原因。这种方法在补2019ec final的题时第一次见，随机数法。没想到这里也行。
只模 $1e9+7$1e9+7 的代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll a,b,c,d,e,f,g;
ll power(ll x,ll y)
{
    ll res=1;
    while(y)
    {
        if(y&1)
            res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res%mod;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld%lld%lld%lld%lld%lld",&a,&b,&c,&d,&e,&f,&g);
        ll am=power(a,d);
        ll bm=power(b,e);
        ll cm=power(c,f);
        if((am+bm+cm)==g)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

D.数三角：

暴力：（注意特判三点共线）
$O(n^3)$O(n3)

#include <bits/stdc++.h>
using namespace std;
const int N=550;
typedef long long ll;
ll x[N],y[N];
bool check(int a,int b,int c)
{
    if((y[a]-y[b])*(x[c]-x[b])==(y[c]-y[b])*(x[a]-x[b]))
        return false;
    return true;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&x[i],&y[i]);
    if(n<3)
    {
        printf("0\n");
        return 0;
    }
    ll d[5]={0};
    int cnt=0;
    for(int i=1;i<=n-2;i++)
    {
        for(int j=i+1;j<=n-1;j++)
        {
            for(int k=j+1;k<=n;k++)
            {
                d[1]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
                d[2]=(x[i]-x[k])*(x[i]-x[k])+(y[i]-y[k])*(y[i]-y[k]);
                d[3]=(x[j]-x[k])*(x[j]-x[k])+(y[j]-y[k])*(y[j]-y[k]);
                sort(d+1,d+1+3);//cout<<d[1]<<" "<<d[2]<<" "<<d[3]<<endl;
                if(d[1]+d[2]<d[3]&&check(i,j,k))
                    cnt++;
            }
        }
    }
    printf("%d\n",cnt);
    return 0;
}

E.做计数:

  看到题目，对题目中的等号还是有疑问，如果是浮点数取整为整数，行不行？看了题解才知道不行。即开根号后是多少就是多少。
  原式可以转换为：$i+j+2 \sqrt{ij}=k$i+j+2ij​=k，其中因为 $i,j,k$i,j,k 均为整数，所以 $i*j$i∗j 必为完全平方数。所以可以 $O(\sqrt n)$O(n​)，枚举n以内的完全平方数，然后 $O(\sqrt n)$O(n​) 枚举该数的因子，计数即可，注意去重。
复杂度：$O(n)$O(n)

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,cnt=0;
    scanf("%d",&n);
    for(int i=1;i*i<=n;i++)//枚举完全平方数
    {
        for(int j=1;j<=i;j++)
            if(i*i%j==0)//如果是因子
                cnt+=2;
        cnt--;//i=j重复
    }
    printf("%d\n",cnt);
    return 0;
}

F.拿物品：

  这个题目算是给自己以后写贪心题提个醒，不能想当然，一定要认真思考贪心的准则，判断清楚。一开始天真的认为牛牛选a值大的，牛可乐选b值大的。但如果仔细考虑拉大分值差的方法，其实不是这样。
  如果牛牛选第 $i$i 件物品，牛可乐选第 $j$j 件物品，那么对于牛牛而言，与对方的分值差为 $(a_i-b_j)$(ai​−bj​)，如果交换，则交换后的分值差为 $(a_j-b_i)$(aj​−bi​)。二者的差值为：$\Delta=(a_i+b_i-a_j-b_j)$Δ=(ai​+bi​−aj​−bj​)，要使牛牛与对方分值高，那么$\Delta$Δ 应该大于0，所有它应该选择 $(a+b)$(a+b) 值更大的物品。对牛可乐也是如此。
$O(nlogn)$O(nlogn)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int>P;
const int N=2e5+5;
ll a[N],b[N];
P c[N];
vector<int>ans[2];
bool cmp(P x,P y)
{
    return x.first>y.first;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%lld",&b[i]);
    for(int i=1;i<=n;i++)
    {
        c[i].second=i;
        c[i].first=a[i]+b[i];
    }
    sort(c+1,c+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        if(i&1)
            ans[0].push_back(c[i].second);
        else
            ans[1].push_back(c[i].second);
    }
    printf("%d",ans[0][0]);
    for(int i=1;i<ans[0].size();i++)
        printf(" %d",ans[0][i]);
    printf("\n");
    printf("%d",ans[1][0]);
    for(int i=1;i<ans[1].size();i++)
        printf(" %d",ans[1][i]);
    printf("\n");
    return 0;
}

C.算概率：

  一开始以为是算组合数，但是发现根本算不出。看了题解才发现，原来是一道概率dp，dp没有学好的我不是很无奈。虽然状态转移方程挺好理解，但就是想不到。
$dp[i][j]$dp[i][j]:表示前 $i$i 道题对了 $j$j 道。
$dp[i][j]=dp[i-1][j]*(1-p_i)+dp[i-1][j-1]*p_i$dp[i][j]=dp[i−1][j]∗(1−pi​)+dp[i−1][j−1]∗pi​
还有就是逆元的应用。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=2010;
ll p[N],dp[N][N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&p[i]);
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=(dp[i-1][0]*(1-p[i])%mod+mod)%mod;
        for(int j=1;j<=i;j++)
            dp[i][j]=(dp[i-1][j]*(1-p[i])%mod+dp[i-1][j-1]*p[i]%mod+mod)%mod;
    }
    for(int i=0;i<=n;i++)
        printf("%lld%c",dp[n][i],i==n?'\n':' ');
    return 0;
}

？H.施魔法：

又是一道 $dp$dp，自己大概看懂了，就是一个动态维护的过程，但细究的话还是有点疑问，看来 $dp$dp 也要赶快跟上。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;
int a[N];
ll dp[N];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    for(int i=1;i<k;i++)
        dp[i]=2e9;
    ll pre=-a[1];
    for(int i=k;i<=n;i++)
    {
        dp[i]=pre+a[i];
        pre=min(pre,dp[i-k+1]-a[i-k+2]);//前者小表示继续前一段的选择，后者小表示重新开始选择一段
    }
    printf("%lld\n",dp[n]);
    return 0;
}

I.建通道：

思维，二进制，$set$set的应用。
首先去重，如何枚举二进制位，如果某一位的为0和1的数都有，就可以建边，此时花费最小。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
set<int>st;
int main()
{
    int n,v;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&v);
        st.insert(v);
    }
    set<int>::iterator it;
    ll ans=0;
    for(int i=0;i<30;i++)
    {
        int cnt1=0,cnt0=0;
        for(it=st.begin();it!=st.end();it++)
        {
            if(((*it)>>i)&1)
                cnt1++;
            else
                cnt0++;
        }
        if(cnt1>0&&cnt0>0)
        {
            ans=((1LL)<<i)*(cnt1+cnt0-1);
            break;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

*J.求函数:

首先，对第二种操作化简：

$f_r(f_{r-1}(...f_{l+1}(f_l(1))...))=\prod^{r}_{i=l}{k_i}$fr​(fr−1​(...fl+1​(fl​(1))...))=∏i=lr​ki​$+\sum^{r}_{i=l}{b_i*\prod^{r}_{j=i+1}{k_j}}$+∑i=lr​bi​∗∏j=i+1r​kj​

对于$"+"$"+"前面部分，可以用一个线段树来维护。
对于后面的部分，