大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
二项式定理推出系数等于a^n * b^m * C(n,k)
快速幂+组合数（逆元做除法）结束。
具体看代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<climits>
#define MOD 10007
#define MAXA 10005
using namespace std;
typedef long long LL;
LL a,b,k,n,m,JC[MAXA],Factor;
LL Pow(LL a,LL b) {
LL Ans = 1;
while(b) {
if(b & 1)
Ans = Ans * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return Ans % MOD;
}
LL C(LL m,LL n) {
LL Ans = JC[n];
Ans = JC[n] * Pow((JC[m] * JC[n-m] % MOD),MOD - 2) % MOD;
return Ans % MOD;
}
int main() {
// freopen("factor.in","r",stdin);
// freopen("factor.out","w",stdout);
JC[1] = 1;
for(int i=2;i<=1005;i++)
JC[i] = (i * JC[i-1]) % MOD;
cin >> a >> b >> k >> n >> m;
if(m == 0)
Factor = Pow(a,k);
else if(n == 0)
Factor = Pow(b,k);
else Factor = Pow(a,n) * Pow(b,m) * C(n,k) % MOD;
cout << Factor % MOD;
}
二分。
以最小的石块重量-1为下界，最重的石块+2为上界二分一个重量。（把left开成mn-1,right开成mx+2(注意取mx+1时即为W比所有都大，Y是0，这个情况要考虑，所以+2包含mx+1)就可以包含左右端点的check了，会简单点））
每次都以找出来的重量w更新一次前缀和，比w大的就加入前缀和，然后算出绝对值，然后取一个最小就行了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cctype>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define RG register
#define ll long long
#define in(x) x = read()
#define lin(x) scanf("%lld",&x)
#define llin(x) x = lread
#define din(x) scanf("%lf",&x)
#define dout(x) printf("%lf",x)
#define out(x) print(x)
#define lout(x) printf("%lld",x)
#define ex putchar('\n')
#define ko putchar(' ')
const ll p = 1e10 + 7;
const int MAXN = 2e5 + 5;
int w[MAXN],v[MAXN];
int n,m,maxn = -1,minn = 1e9,l[MAXN],r[MAXN];
ll sumn[MAXN],sumv[MAXN];
ll temp,s,sum;
ll ans = 1e11;
inline int read()
{
int X=0,w=1;
char ch=getchar();
while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
return X*w;
}
inline ll lread()
{
ll X=0,w=1;
char ch=getchar();
while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0' && ch<='9') X=((X<<3)+(X<<1)+ch-'0')%p,ch=getchar();
return X*w;
}
void print(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
print(x/10);
}
putchar(x%10+'0');
}
ll check(int W)
{
temp = 0,sum = 0;
memset(sumn,0,sizeof sumn);
memset(sumv,0,sizeof sumv);
for(int i = 1;i <= n;i++)
{
if(w[i] >= W)
{
sumn[i] = sumn[i-1]+1;
sumv[i] = sumv[i-1]+v[i];
}
else sumn[i] = sumn[i-1],sumv[i] = sumv[i-1];
}
for(int i = 1;i <= m;i++)
{
temp += (sumn[r[i]] - sumn[l[i] - 1]) * (sumv[r[i]] - sumv[l[i]-1]);
}
sum = abs(temp-s);
return temp;
}
void init()
{
in(n);in(m);lin(s);
for(int i = 1;i <= n;i++)
{
in(w[i]);in(v[i]);
maxn = max(maxn,w[i]);
minn = min(minn,w[i]);
}
for(int i = 1;i <= m;i++)
{
in(l[i]);in(r[i]);
}
}
void divide()
{
int left = minn - 1,right = maxn + 2,mid;
while(left <= right)
{
mid = left + (right - left)/2;
if(check(mid) > s) left = mid + 1;
else right = mid -1;
if(sum < ans) ans = sum;
}
}
int main()
{
// freopen("qc.in","r",stdin);
// freopen("qc.out","w",stdout);
init();
divide();
lout(ans);
return 0;
}
一道语文题，模拟，说不上什么算法。
题意大概是有一个会氮气加速的bus，它要在n个站接m个客人（一定要接，bus到了人没到要等），然后问我们怎么加速才能使所有客人的旅行时间（从上车到下车）加起来最短。
主要方法是：
先统计每次bus到达时间和人上车时间，取两者大值作为此站发车时间（最后时间：lastone），相当于预处理一下。
然后先算一个不加速的答案出来（因为也可能一个加速都没有），然后我们一次次的用加速，每次选一个最节约时间的地方下。
我们每次加速后都重新统计一遍路况（也就是time、lastone之类的）方便下次统计。
至于统计加速的影响，用了一个influence数组，因为我们可以看出一次加速对后面很多地方都有影响，但是对于1、bus到了人还没到的情况用加速没有意义，2、加速完了的路不能减到0以下，于是这种影响是间断的，所以我们需要判断一下影响区间。
具体使用还是看代码。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cctype>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define RG register
#define ll long long
#define in(x) x = read()
#define lin(x) scanf("%lld",&x)
#define llin(x) x = lread
#define din(x) scanf("%lf",&x)
#define dout(x) printf("%lf",x)
#define out(x) print(x)
#define lout(x) printf("%lld",x)
#define ex putchar('\n')
#define ko putchar(' ')
const int MAXN = 1e3 + 5;
const int lenth = 1e4 + 5;
int n,k,m;
int ans,pos;
int max_cut_Time;
int dis[MAXN],Time[lenth];
int from[lenth],to[lenth];
int lastone[MAXN],leave[MAXN],bus[MAXN];
int influence[MAXN];
inline int read()
{
int X=0,w=1;
char ch=getchar();
while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
return X*w;
}
inline ll lread()
{
ll X=0,w=1;
char ch=getchar();
while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
return X*w;
}
void print(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
print(x/10);
}
putchar(x%10+'0');
}
void init()
{
in(n);in(m);in(k);
for(int i = 1;i < n;i++)
in(dis[i]);
for(int i = 1;i <= m;i++)
{
in(Time[i]); in(from[i]); in(to[i]);
lastone[from[i]] = max(lastone[from[i]],Time[i]);
leave[to[i]]++;
}
for(int i = 2;i <= n;i++)
leave[i] += leave[i-1];
bus[1] = lastone[1];
}
void work()
{
for(int i = 2;i <= n;i++)
{
bus[i] = max(bus[i-1],lastone[i-1]) + dis[i-1];
}
for(int i = 1;i <= m;i++)
{
ans += (bus[to[i]] - Time[i]);
}
while(k--)
{
influence[n] = n;
influence[n-1] = n;
max_cut_Time = 0;
for(int i = n-2;i>=1;i--)
{
if(bus[i+1] <= lastone[i+1])
{
influence[i] = i+1;
}
else influence[i] = influence[i+1];
}
for(int i = 1;i <= n;i++)
{
if(((leave[influence[i]] - leave[i]) > max_cut_Time) && dis[i])
{
max_cut_Time = leave[influence[i]] - leave[i];
pos = i;
}
}
ans -= max_cut_Time;
dis[pos]--;
for(int i = 2;i <= n;i++)
bus[i] = max(bus[i-1],lastone[i-1]) + dis[i-1];
}
out(ans);
}
int main()
{
// freopen("bus.in","r",stdin);
// freopen("bus.out","w",stdout);
init();
work();
return 0;
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/189756.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
