计蒜客 2020 蓝桥杯省赛 B 组模拟赛（五）E区间dp H 裴蜀 J dp A-J 权值线段树
题目链接
因为要去笔试。所以只打了两个小时，有点求快，很多细节没写好就匆匆交，而且没有检查，打的有点菜
C-煎牛排
做法: 所有的面的个数sum=2*n 然后sum/(2*k)即可。
ans=max(10,n/k) 如果只有一个饼，也是要煎10分钟的，所以最低十分钟
E-卡片游戏
区间dp+记忆化搜索
设dp[l][r] 为区间内l到r时蒜头君减去花耶妹的答案
#include
using namespace std;
typedef long long ll;
const int N=1e2+10;
ll dp[N][N],a[N];int vis[N][N],n;
ll dfs(int l,int r,int ty)
{if(l>r) return 0;if(vis[l][r]) return dp[l][r];vis[l][r]=1;ll &ans=dp[l][r];if(ty==0){ans=max(dfs(l+1,r,1)+a[l],dfs(l,r-1,1)+a[r]);}else{if(a[l]>=a[r]) ans=dfs(l+1,r,0)-a[l];else ans=dfs(l,r-1,0)-a[r];}return dp[l][r];}
int main()
{cin>>n;for(int i=1;i<=n;++i) cin>>a[i];ll ans=dfs(1,n,0);cout< H-两个数组
做法：裴蜀定理+推导
通过裴蜀定理知道 a数组中相邻的差值 需要b数组进行 方程转换 求出来：
x1*b[1]+x2*b[2]......xn*b[n]==a[i+1]-a[i]
又：x1*b[1]+x2*b[2]......xn*b[n]=k*gcd(x1,x2,x3...xn) 有解
假设使a数组最后相同的数是x
设d有：d=x-a[i]
即：x1*b[1]+x2*b[2]......xn*b[n]=d 余 0 或者 是 x1*b[1]+x2*b[2]......xn*b[n]=d1 余 mod ==>d1+mod=d
所以现在要填补所有的差值 所有的差值与gcd(x1,x2,x3...xn)的模 有相同的余数即可。
#include
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair
#define mk make_pair
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int N=1e5+10;
int n,m;
ll a[N],b[N];
int main()
{int _;cin>>_;while(_--){scanf("%d%d",&n,&m);rep(i,1,n) scanf("%lld",&a[i]);rep(i,1,m) scanf("%lld",&b[i]);if(n==1){puts("Yes");continue;}ll d=b[1];rep(i,2,m) d=gcd(d,b[i]);sort(a+1,a+1+n);int flag=1;ll res=(a[2]-a[1])%d;for(int i=1;i I-函数求和
题意：
做法：
代码：
#include
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair
#define mk make_pair
using namespace std;
typedef unsigned long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int N=1e5+10;
const ll mod=998244353;
ll a[N],b[N],c[N];
int n;bool cmp(ll x,ll y)
{return x>y;
}
void add(ll &x,ll y)
{x=(x+y)%mod;
}
int main()
{scanf("%d",&n);rep(i,1,n) {cin>>a[i];a[i]=1ll*i*(n-i+1)*a[i];}rep(i,1,n)cin>>b[i];sort(a+1,a+1+n);sort(b+1,b+1+n,cmp);ll ans=0;rep(i,1,n) {ll x=a[i]%mod*b[i]%mod;add(ans,x);}cout< J-序列划分
题意：
官方题解：
注意，这里的子序列要求下标是连续的分在一起，我以为下标是不连续的，贪心写wa了
下标连续的话就是比较经典的dp了，前缀和，区间最小值维护一下就可以了。
设dp[i]为前i个元素 分配的最小权值和。
#include
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair
#define mk make_pair
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int N=1e5+10;
ll a[N],dp[N],mi[4*N],sum[N];
int n,c;
void build(int id,int l,int r)
{if(l==r) {mi[id]=a[l];return ;}int mid=l+r>>1;build(id<<1,l,mid);build(id<<1|1,mid+1,r);mi[id]=min(mi[id<<1],mi[id<<1|1]);
}
ll qu(int id,int l,int r,int ql,int qr)
{if(ql<=l&&r<=qr) return mi[id];ll res=1e18;int mid=l+r>>1;if(ql<=mid) res=qu(id<<1,l,mid,ql,qr);if(qr>mid) res=min(res,qu(id<<1|1,mid+1,r,ql,qr));return res;
}
int main()
{cin>>n>>c;rep(i,1,n){scanf("%lld",&a[i]);sum[i]=sum[i-1]+a[i];}for(int i=1;i 顺便写写A组的题。
A组
E-GCD
题意：
做法：经典欧拉函数了
A组 J 全排列
题意：
cf原题。。
博客链接
原题链接E题
官方题解：
#include
using namespace std;
typedef long long ll;const int N=2e5+10;
int p[N],n;
ll a[N],sum[4*N],lazy[4*N],mi[4*N];
void pushdown(int id)
{if(lazy[id]){lazy[id<<1]+=lazy[id];lazy[id<<1|1]+=lazy[id];mi[id<<1]+=lazy[id];mi[id<<1|1]+=lazy[id];lazy[id]=0;}
}
void up(int id,int l,int r,int ql,int qr,ll val)
{if(ql<=l&&r<=qr){lazy[id]+=val;mi[id]+=val;return ;}pushdown(id);int mid=l+r>>1;if(ql<=mid) up(id<<1,l,mid,ql,qr,val);if(qr>mid) up(id<<1|1,mid+1,r,ql,qr,val);mi[id]=min(mi[id<<1],mi[id<<1|1]);
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d",&p[i]);}for(int i=1;i<=n;++i){scanf("%d",&a[i]);}for(int i=1;i1;--i){if(p[i]+1<=n) up(1,1,n,p[i]+1,n,a[i]);up(1,1,n,1,p[i],-a[i]);ans=min(ans,mi[1]);}printf("%lld\n",ans);
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！