1. 全栈程序员必看首页

noip2015_noip2021复赛

全栈程序员-用户IM • • 未分类

noip2015_noip2021复赛二项式定理推出系数等于a^n*b^m*C(n,k)快速幂+组合数（逆元做除法）结束。具体看代码：#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>#include<vector>#inc…

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

noip2015_noip2021复赛

二项式定理推出系数等于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;
}

noip2015_noip2021复赛noip2015_noip2021复赛

二分。

以最小的石块重量-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;
}

noip2015_noip2021复赛
noip2015_noip2021复赛

一道语文题，模拟，说不上什么算法。

题意大概是有一个会氮气加速的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账号...

赞 (0)
全栈程序员-用户IM全栈程序员-用户IM
0 0
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号