首页 > 其他分享 >AT_abc347_c 题解

AT_abc347_c 题解

时间:2024-03-30 23:13:35浏览次数:18  
标签:10 ch 一周 题解 rep abc347 LL define

最开始的思路爆炸了我就不写了。

d[i]%=(a+b)

然后,排序,破环为链,相当于存储了下一周。

再然后,从 \(1\) 到 \(n\) 进行一个循环,若 d[i+n-1]-d[i]+1<=a 就输出 Yes

它的原理是什么?

翻译一下上面那个语句,就是“我前一个任务的日期的下一周距离我这个任务的日期小于等于节假日天数”。

那你直接把这个任务放在一周的第一天,其他不就好了!

有人会觉得后面的万一飞到工作日去了的话,会错,但是别忘了我们一周整整 a+b 天,破环为链的时候会加一周的天数,而且我们最初 d[i]%=(a+b) 了,一定是不可能飞到工作日去的。

#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
	i128 f=1;
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=f;
}
void writing(i128 x)
{
	if(x>=10)writing(x/10);
	putchar(x%10+'0');
}
void write(i128 x)
{
	if(x<0)
	{
		cout<<'-';
		x=-x;
	}
	writing(x);
}
LL n,a,b,d[200010];
bool f;
int main()
{
	cin>>n>>a>>b;
	rep(i,1,n,1)
	{
		cin>>d[i];
		d[i]%=(a+b);
	}
	sort(d+1,d+n+1);
	rep(i,1,n,1)
	{
		d[i+n]=d[i]+a+b;
	}
	rep(i,1,n,1)
	{
		if(d[i+n-1]-d[i]+1<=a)
		{
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
	return 0;
}

标签:10,ch,一周,题解,rep,abc347,LL,define
From: https://www.cnblogs.com/cppom/p/-/ABC347C-tijie

相关文章

  • ABC347题解
    省流:输+赢D按位分析。既然两个数异或后的结果是\(C\),那就考虑\(C\)中为\(1\)的数中有几个是在\(X\)当中的。假如\(\text{a-popcnt(X)==b-popcnt(Y)}\),那么在\(C\)中为\(0\)的数中随便选\(\text{a-popcnt(x)}\)个即可。注意longlong。codeE假如......
  • CF712E Memory and Casinos 题解
    假设只保留数组上\([l,r]\)的这段数,记\(f_i\)表示从点\(i\)出发到达\(n+1\)的概率,则有\(f_0=0,f_{n+1}=1,f_i=(1-p_i)f_{i-1}+p_if_{i+1}\),题目要求的是\(f_1\)。考虑对最后一个等式进行一些变换,把\(f_i\)的系数拆开得:\[p_if_i+(1-p_i)f_i=(1-p_i)f_{i-1}+p_if_{i+1......
  • ABC347G题解
    我不会,但是我会退火!第一眼,\(n\le20\)。退火,启动!大致思路就是随机选一个初始为0的数置为\(1\sim5\)中的某个数,显然图中没有0一定不比有0劣(把所有0改成同一个数一定不劣)。然后把单次计算的复杂度从\(O(n^2)\)变成\(O(1)\):更新有变化位置的值就行了。瞎调调参数......
  • P5624 [Celeste-A] Black Moonrise 题解
    考虑莫队。记数\(i\)的个数为\(c_i\),套路地用莫比乌斯函数容斥,发现答案为\(\sum_{i=1}^{10^5}\frac{c_i(c_i+1)}2\sum_{d|i}\mu(\fracid)d\)。先预处理出前面的常数和每个数的因子,每次移动端点枚举因子更新答案即可。因为数是随机的,所以时间复杂度\(\mathcalO(n\sqrtn......
  • 信息工程大学第五届超越杯程序设计竞赛(同步赛)题解
    比赛传送门c++模板框架#pragmaGCCoptimize(3,"Ofast","inline")#include<bits/stdc++.h>#definerep(i,a,b)for(inti=a;i<b;++i)#defineper(i,a,b)for(inti=a;i>b;--i)#definesesecond#definefifirst#defineendl'\n�......
  • luogu P1543 [POI2004] SZP 题解
    题目传送门前置知识树形DP解法将\(a_{i}\)向\(i\)连一条有向边,这样就形成了基环外向树森林。基环外向树森林内每棵基环外向树是相互独立的,需要单独处理。对于每棵基环外向树,任取环上一点\(x\),断开\(x\)到\(fa_{x}\)的有向边,外向树就变成了一棵以\(x\)为根的树。......
  • Enumerating Rational Numbers 题解
    EnumeratingRationalNumbers题解先下结论,这道题是一道欧拉函数板子题观察题面可以发现,生成的分数有如下特性:分数都是最简分数分母与分子互质,且分子$\le$分母当然第一个除外,那个特判即可,不用纳入考虑范围我们知道,对于任意正整数n,欧拉函数,即\(\varphi(n)\)是小......
  • 题解 CF698C【LRU】
    题解CF698C【LRU】题目描述有\(n\)种物品和大小为\(k\)的队列。每次操作,以\(p_i\)的概率选择第\(i\)种物品放入队尾,如果已经有物品\(i\)了就将物品\(i\)拿出来扔到队尾。若队列大小\(\gtk\),弹出队首。求\(10^{100}\)次操作后每种物品在队列里的概率。\(1\leq......
  • upload-labs简单题解
    upload-labs详解1-19关通关全解(最全最详细一看就会)-CSDN博客Upload-labs1-21关靶场通关笔记(含代码审计)_upload-labs21关-CSDN博客搭建upload-labs环境参考文章渗透测试——upload-labs环境部署_upload-loadsphpstudy-CSDN博客文件上传浅谈-CSDN博客 Pass-01考点:J......
  • 题解 ARC175C【Jumping Through Intervals】
    先不考虑构造字典序最小的方案,只考虑求出最小的\(\sum\limits_{i=1}^{N-1}|A_{i+1}-A_i|\)。设定义域为\([L_i,R_i]\)的函数\(F_i(x)\)表示考虑后缀\([i,N]\),令\(A_i=x\)时上式最小的值。初值为\(F_N(x)=0,(x\in[L_N,R_N])\)。显然有转移方程:\[F_i(x)=\min\limits_{y......