牛客算法周周练9(题解)

A:符合条件的整数
题意
给定两个整数N,M,表示区间 [2^N,2^M），请求出在这个区间里有多少个整数i满足i % 7=1
题解
也就是求2^N-1~2^M-2有多少数被7整除，答案就是

用一下__int128就好
代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

void solve(){
    int n,m;cin>>n>>m;
    __int128 a=1,b=1;
    for(int i=0;i<n;i++)a*=2;
    for(int i=0;i<m;i++)b*=2;
    a-=2;b-=2;
    __int128 ans=b/7-a/7;
    ll now=ans;
    cout<<now;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<'\n';
    solve();
    return 0;
}

B.Relic Discovery
题意
Recently, paleoanthropologists have found historical remains on an island in the Atlantic Ocean. The most inspiring thing is that they excavated in a magnificent cave and found that it was a huge tomb. Inside the construction, researchers identified a large number of skeletons, and funeral objects including stone axe, livestock bones and murals. Now, all items have been sorted, and they can be divided into N types. After they were checked attentively, you are told that there are Ai items of the i-th type. Further more, each item of the i-th type requires Bi million dollars for transportation, analysis, and preservation averagely. As your job, you need to calculate the total expenditure.
题解
直接计算
代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

void solve(){
    int n;cin>>n;
    ll ans=0;
    for(int i=0;i<n;i++){
        ll x,y;cin>>x>>y;
        ans+=x*y;
    }
    cout<<ans;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)solve(),cout<<'\n';
    //solve();
    return 0;
}

D.石子游戏

Alice和Bob在玩游戏，他们面前有n堆石子，对于这些石子他们可以轮流进行一些操作，不能进行下去的人则输掉这局游戏。
可以进行两种操作:

1. 把石子数为奇数的一堆石子分为两堆正整数个石子
2. 把两堆石子数为偶数的石子合并为一堆
   两人都足够聪明，会按照最优策略操作。现在Alice想知道自己先手，谁能最后赢得比赛。

题解
奇数个数石头对答案其实没有影响，因为你操作后产生偶数个石头和奇数个石头，偶数石头会被对手合并掉，此时又轮到你了，所以答案只取决与偶数个数石头。注意对于0，和1个数石头可以忽略不计
代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}
void solve(){
    int n,k=0,kk=0;cin>>n;
    for(int i=0;i<n;i++){
        int x;cin>>x;
        if(x&1&&x!=1)k++;
        else if(x&&x%2==0)kk++;
    }
    if(kk%2==0&&(kk||k))cout<<"Alice";
    else cout<<"Bob";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<'\n';
    solve();
    return 0;
}

E.凸多边形的划分
给定一个具有N个顶点的凸多边形，将顶点从1至N标号，每个顶点的权值都是一个正整数。将这个凸多边形划分成N-2个互不相交的三角形，试求这些三角形顶点的权值乘积和至少为多少。
题解
凸边形，取两个点，形成的一条边，我们把那条边形成的多边形中按顺序取点，区间DP。状态方程

dp[i][r]=min(dp[i][r],dp[i][j]+dp[j][r]+a[i]*a[j]*a[r]);

用一下__int128
代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

__int128 dp[60][60],a[60];
void solve(){
    int n,x;cin>>n;
    for(int i=1;i<=n;i++)cin>>x,a[i]=x;
    __int128 inf=1e9;
    for(int l=2;l<=n;l++){
        for(int i=1;i+l-1<=n;i++){
            int r=i+l-1;
            dp[i][r]=inf*inf*inf;
            if(l==2)dp[i][r]=0;
            for(int j=i+1;j<r;j++){
                dp[i][r]=min(dp[i][r],dp[i][j]+dp[j][r]+a[i]*a[j]*a[r]);
            }
        }
    }
    __int128 ans=dp[1][n];
    string s;
    while(ans>0){
        s=(char)((ans%10)+'0')+s;
        ans/=10;
    }
    cout<<s;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<'\n';
    solve();
    return 0;
}