noip2015_noip2021复赛

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

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

扩展欧几里得模板题。

注意取模。

#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;
}

差分+二分。

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

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

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

#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;
}

三题坑。。。