A-符合条件的整数

题意：
给定两个整数N,M,表示区间 [ $图片说明$ ， $图片说明$ ) ,请求出在这个区间里有多少个整数i满足i % 7=1

题解：两种方法一种推公式，另一种暴力枚举
推公式：
我们细心列出一部分就会发现

0  1  2  3  4  5  6   
1  1  1  2  3  5  10

后一个是前一个的2倍-1 如果这个指数能整除3那么那是前一个的二倍，就不用减一，其实就是因为他本身是%7=1，所以把他本身加上。知道这个都简单多了
暴力枚举：
找到左端点第一个%7=1，然后+7循环就好。

公式代码：

#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;

inline int read() {
    int x=0;
    bool t=false;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}

/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上  小根堆         小到大 
priority_queue<ll , vector<ll> , less<ll> > mx;//下       大根堆      大到小
map<ll,ll>mp;*/

ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[1010][1010];
string str,s;

#define read read()

int main(){
     cin>>n>>m;
    a[0]=1;
    a[1]=1;
    a[2]=1;
    for(int i=3;i<=m;i++)
    {
        a[i]=a[i-1]*2-1;
        if(i%3==0) a[i]++;
    }
    sum=a[m]-a[n];


    if(n%3==0) sum++;
    if(m%3==0) sum--;
    cout<<sum<<endl;
    return 0;
}

暴力枚举代码：

#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;

inline int read() {
    int x=0;
    bool t=false;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}

/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上  小根堆         小到大 
priority_queue<ll , vector<ll> , less<ll> > mx;//下       大根堆      大到小
map<ll,ll>mp;*/

ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[1010][1010];
string str,s;

#define read read()

int main(){
     cin>>n>>m;
    a[0]=1;
    for(int i=1;i<=66;i++) a[i]=a[i-1]*2;
    l=a[n];
    while(l%7!=1) l++;
    for(ll i=l;i<a[m];i+=7) sum++;
    cout<<sum<<endl;
    return 0;
}

B-Relic DISCOVERY

题意：就相当如：给你几个商品，给出你单价和数量，让你求出总钱数
题解：听完题意就能直接出来了，就是单价x数量和。
代码：

#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;

inline int read() {
    int x=0;
    bool t=false;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}

/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上  小根堆      小到大
priority_queue<ll , vector<ll> , less<ll> > mx;//下    大根堆     大到小
map<ll,ll>mp;*/

ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[1010][1010];
string str,s;

#define read read()
int main(){
    t=read;
    while(t--){
        n=read;
        sum=0;
        for(int i=1;i<=n;i++)
        {
            a[i]=read,b[i]=read;
            sum+=a[i]*b[i];
        }
        cout<<sum<<endl;

    }
    return 0;
}

D-石子游戏

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

把石子数为奇数的一堆石子分为两堆正整数个石子
把两堆石子数为偶数的石子合并为一堆
两人都足够聪明，会按照最优策略操作。现在Alice想知道自己先手，谁能最后赢得比赛。
题解：
分析一下：两种操作：
1，奇数分解：一个大于1的奇数(x)可以分解成1个奇数1个偶数，那么我们往极端上想，如果分成1和(x-1)(偶数) (x-1)偶数可以跟另一偶数(数列中的一个或者其他奇数生成的)合成偶数最后经过两步就是把原奇数转出来个1并把剩下的加到另一偶数上所以奇数不用管。一定是经过偶数次，对结果相当于没代价。
2，偶数合成：两个偶数合成一个奇数，合成这个偶数，所以最后结果就是交少了一个偶数
最后会化成一个偶数和若干个1。
代码：

#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;

inline int read() {
    int x=0;
    bool t=false;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}

/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上  小根堆         小到大 
priority_queue<ll , vector<ll> , less<ll> > mx;//下       大根堆      大到小
map<ll,ll>mp;*/

ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[1010][1010];
string str,s;

#define read read()
int main(){
     n=read;
     for(int i=1;i<=n;i++){
         a[i]=read;
         if(a[i]%2==0) sum++;//偶数
        //奇数分解成1和另一偶数 偶数可以跟另一偶数合成偶数 最后经过两步就是把 原奇数 转出来个1并把剩下的加到另一偶数上 所以奇数不用管         
     }
    flag=1; 
    while(sum>1){
        sum--;//每次两个偶数相加生成一个偶数 最后结果就是减少一个偶数 
        flag=-flag;
    } 
     if(flag==-1) cout<<"Alice"<<endl;
     else cout<<"Bob"<<endl; 
    return 0;
}

E-凸多边形的划分

题意：
给定一个具有N个顶点的凸多边形，将顶点从1至N标号，每个顶点的权值都是一个正整数。将这个凸多边形划分成N-2个互不相交的三角形，试求这些三角形顶点的权值乘积和至少为多少。
题解：知识点高精度+区间DP
这个题用到区间DP这个应该很好想到
找[i,j]最优值就是找一点k使得[左一半+右一半+a[i]a[j]a[k]]最小这样[i,j]就是最优解
所以我们的状态转移方程是：

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

六边形为例
但鉴于这个题的数据量我们不得不用上高精度

代码：

#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
#define pll __int128
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;

inline int read() {
    int x=0;
    bool t=false;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}

/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上  小根堆         小到大 
priority_queue<ll , vector<ll> , less<ll> > mx;//下       大根堆      大到小
map<ll,ll>mp;*/
ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
string str,s;
pll dp[55][55];
pll a[55];

void print(pll x) {
    if (!x) return ;
    if (x < 0) putchar('-'), x = -x;
    print(x / 10);
    putchar(x % 10 + '0');
}

#define read read()
int main(){

    sf("%lld",&n);
    for(int i=1;i<=n;i++){
        int x;
        x=read;
        a[i]=x;
    }
    memset(dp, 0, sizeof(dp));
    for(int len=2;len<=n;len++){//长度
        for(int i=1;i+len<=n;i++)//起点
        {
        int j=i+len;//终点
        dp[i][j]=1e30+10;
        for(int k=i+1;k<j;k++)//找到内部最优解
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[j]*a[k]);
        }
    }
    if(dp[1][n]==0) cout<<"0"<<endl;
    else print(dp[1][n]);
    return 0;
}

牛客算法周周练9

A-符合条件的整数

B-Relic DISCOVERY

D-石子游戏

E-凸多边形的划分