noip2015_noip2021复赛

noip2015_noip2021复赛扩展欧几里得模板题。注意取模。#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#definein(x)scanf("%d",&x)#definelin(x)scanf("%lld",&x)#defineout(x)printf("%d",x)#defin…

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

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

noip2015_noip2021复赛

扩展欧几里得模板题。

注意取模。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define in(x) scanf("%d",&x) 
#define lin(x) scanf("%lld",&x)
#define out(x) printf("%d",x)
#define lout(x) printf("%lld",x)
#define ex putchar('\n')
#define ko putchar(' ')
ll a,b,x,y;

void Exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b == 0)
	{
		x = 1;
		y = 0;
		return;
	}
	Exgcd(b,a%b,x,y);
	int t = x;
	x = y;
	y = t - y*(a/b);
	return;
}

int main()
{
//	freopen("mod.in","r",stdin);
//	freopen("mod.out","w",stdout);
	lin(a);lin(b);
	Exgcd(a,b,x,y);
	cout << (x % b + b) % b;
	return 0;
}

noip2015_noip2021复赛

noip2015_noip2021复赛

差分+二分。

差分相当于区间加减,用于找是否可以满足条件。

二分用于找第一个不满足的订单。

具体直接看代码吧,很简单明显。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define in(x) x = read()
#define lin(x) scanf("%lld",&x)
#define out(x) write(x)
#define lout(x) printf("%lld",x)
#define ex putchar('\n')
#define ko putchar(' ')
const int MAXN = 1e6 + 5;
int n,m;
int cf[MAXN],now[MAXN],res[MAXN];
int l[MAXN],r[MAXN],d[MAXN];

inline int read()
{
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}

inline void write(int x)
{
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}


bool check(int k)
{
	memset(cf,0,sizeof cf);
	for(int i = 1;i <= k;i++)
	{
		cf[l[i]] += d[i];
		cf[r[i]+1] -= d[i];
	}
	
	for(int i = 1;i <= n;i++)
	{
		now[i] = now[i-1] + cf[i];
		if(now[i] > res[i]) return 0;
	}
	return 1;
}

int main()
{
//	freopen("classroom.in","r",stdin);
//	freopen("classroom.out","w",stdout);
	in(n);in(m);
	for(int i = 1;i <= n;i++)
		in(res[i]);
	for(int i = 1;i <= m;i++)
		in(d[i]),in(l[i]),in(r[i]);
	if(check(m)) 
	{
		cout << 0;
		return 0;
	}
	int left = 1,right = m;
	while(left < right)
	{
		int mid = left + (right - left)/2;
		if(check(mid)) left = mid + 1;
		else right = mid;
	}
//	cout << -1 << endl << left;
	printf("-1\n%d",left);
	return 0;
}

三题坑。。。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/172051.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • matlab读取txt文件指定行_matlab中if判断中返回

    matlab读取txt文件指定行_matlab中if判断中返回MATLAB提供了一系列低层输入输出函数,专门用于文件操作。本文提供了几种Matlab读写文件的方法和预写的脚本。

  • 黑盒测试、白盒测试到底差别是什么?

    黑盒测试、白盒测试到底差别是什么?邓小平曾言:不管白猫、黑猫,能抓到老鼠就是好猫。如果用在软件测试领域,这句话也一点都没错。不管黑盒、白盒,能找出Bug、发现缺陷,保证软件质量才是王道。对于刚踏足软件测试的新手小白来说,黑盒测试、

  • 注意了:这4种情况下,员工主动辞职,单位也须支付经济补偿

    注意了:这4种情况下,员工主动辞职,单位也须支付经济补偿

  • 51单片机实现流水灯

    51单片机实现流水灯文章目录51单片机实现流水灯一、点亮第一个LED灯二、流水灯1.总线型控制2.延时函数3._crol_函数使用4.实现流水灯51单片机实现流水灯以下是本篇文章正文内容,下面案例可供参考一、点亮第一个LED灯#include<reg52.h>#defineuintunsignedint//简化定义#defineucharunsignedchar//同上sbitD1=P2^1;voidmain(){ D1=0;}代码中D1代表着位定义,相.

  • C++ 编程之QueryInterface函数(一)

    C++ 编程之QueryInterface函数(一)前言组件对外公布的是接口;一个组件可以实现多个接口,也就是说可以对外公布多个接口,之前也总结过了,你很少会100%的去完全了解一个组件的所有接口,就像你去学习编程一样,你几乎不可能去成为编程中的全才。那么,既然我们不能去完全的了解一个组件提供的所有接口,那么我们在实际开发中,如何去判断一个组件是否提供对应的接口呢?看文档?是的,是个好主意,在文档的海洋,找到一个知识点,真的很难,浪费时间和

  • linux内核编程接口小结(一)

    linux内核编程接口小结(一)1、下面两幅图描述了linux内核编程接口函数

发表回复

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

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