首页 > 其他分享 >2024.3.31

2024.3.31

时间:2024-03-31 22:55:04浏览次数:31  
标签:itn 2024.3 frac int 31 madis dis

2024.3.31 【人间骄阳刚好,风吹过树梢,彼时他们正当年少——某某】

Sunday 二月二十二


<BGM = 那年·年少 - 宋宇宁>
<theme = oi-"search">
来看道典题

P1763 埃及分数

附本体链接

//2024.3.31
//by white_ice
#include<bits/stdc++.h>
using namespace std;
#define itn long long
#define int long long
const int oo = 10000007;

int jgby(int a,int b){while(b^=a^=b^=a%=b);return a;}
int ngm (itn a,itn b){return a<b?a:b;}
itn jntm(itn a,itn b){return a>b?a:b;}

int a,b,madis;
int out[oo],st[oo];
int s;

bool dfs(itn a,itn b,int dis){
	if (dis == madis){
		if (a==1&&b>st[dis-1]&&(b<out[dis]||!out[dis])){
			st[dis] = b;
			memcpy(out,st,sizeof(st));
			return true;
		}
		return false;
	}
	if (dis == madis - 1){
		for (itn z=(b<<2)/a/a+1;z<ngm((s<<1)/a,s*s/a);z++){
			itn d = a*a*z*z-(b<<2)*z;
            itn s = sqrt(d);
			if (s*s!=d||a*z+s&1)
				continue;
			st[dis] = a*z-s>>1;
            st[dis+1]=a*z+s>>1;
			if (st[dis+1]<out[dis+1]||!out[dis+1]){
				memcpy(out,st,sizeof(st));
				return true;
			}
		}
		return false;
	}

	itn l = jntm(st[dis-1],(b-1)/a)+1LL;
    int r = (madis-dis+1)*b/a;

	bool flag = 0;
	for (int i=l;i<r;i++){
		itn tx = a*i-b,ty = b*i;
        itn g = jgby(tx, ty);
		st[dis] = i;

		if (dfs(tx/g,ty/g,dis+1))
			flag = 1;
	}
	return flag;
}

signed main (){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >> a >> b;

    bool tag = 0;
    while (!tag){
        s = 100;
        madis++;
        while (s<1e7&&!tag)
            s = (s<<3)+(s<<1),tag = dfs(a,b,1);
    }

    for (itn i=1;i<=madis;i++)
        cout << out[i] << ' ';

    return 0;
}

本题使用了iddfs,也就是迭代加深搜索。

通过每次设定一个预期的dis,也就是预定深度,再依据此深度为限制进行搜索。
本代码中设为madis。

当搜索致dis = madis - 1时,若剩余分数仍久分子不为一,则剪枝优化掉。

下面推一下柿子:
\frac{a}{b} = \frac{1}{x}\ + \ \frac{1}{y}\

\left{
\begin{aligned}
az = x+y\
bz = xy
\end{aligned}
\right.
\rArr
x^2\ - \ azx\ - \ bz \ =\ 0
也就是:

\[x\ = \ \frac{az\ - \ \sqrt{\Delta}}{2}\\ y\ = \ \frac{az\ + \ \sqrt{\Delta}}{2} \]

柿子非常好看啊。

只要证明一下$ \Delta $能够被整开就行。

然后就代码就行。

标签:itn,2024.3,frac,int,31,madis,dis
From: https://www.cnblogs.com/white-ice/p/18107443

相关文章

  • CTFshow pwn31
    PWN31使用checksec查看保护发现除了canary剩下保护全开,那么就没有前面几个题目那么简单了,ida打开看见他给了我们main函数地址虽然开了pie但是在他们之间的偏移是一定的,那么我们就可以通过他给的main函数的真实地址减去偏移得到文件(elf)的基地址,然后puts_pltputs_got表地址就......
  • 腾讯2024实习生在线笔试-0331
    Q1小红的图上染色小红拿到了一个无向图,其中一些边被染成了红色。小红定义一个点是“好点”,当且仅当这个点的所有邻边都是红边。现在请你求出这个无向图“好点”的数量。注:如果一个节点没有任何邻边,那么它也是好点。输入描述第一行输入两个正整数n,m,代表节点的数量和边......
  • 2024-03-31
    2024-03-31讲课提到的很有道理啊,确实很常见在窗口的星星里面就用到了还有一个小技巧求区间0的个数不好做有的时候满足所有数非负转化成求区间最小值是不是0和区间最小值的个数就行了这两天讲课的时候还经常提到·修改和查询的复杂度不平衡的时候,把他平衡会更优秀......
  • 0324-0331题解反思
    最近我突然发现,写题解是常常会遗忘的,然而题目中的一些技巧才是永恒的,那么接下来的题解,我应该对以前的题目含有的这些技巧进行一些深刻的复盘。知识点模块1.当我们要实现一个图形的字符串的倒置,比如把福倒过来,我们可以进行以下的操作:先进行行的交换,在进行列的倒置,我们需要用到s......
  • q1-投资理财-2024.3.31
    q1-投资理财-2024.3.31​ 接上回,持有的徐工机械,一边下跌一边加仓,截止到5.86清仓想全仓做t,等第二天下跌下来再买入,没想到直接高开6个点,望尘莫及,亏死。​ 盈利的基本不去动了,亏损的等以后看看能不能想办法搞回来,传智资金到12-13左右就资金一直在流出,这玩应,我发现资金流入的很有......
  • 2024.3.31补题
    SMU2024spring天梯赛2(补题)https://pintia.cn/problem-sets/1772539187410104320/exam/overview7-10红色警报错误:①没写②用的unordered_map<>判断的联通条件。只要有城市和它相连就判它在城市群里,只对了样例。。。③不会深搜。。。#include<bits/stdc++.h>using......
  • 3.31
    所花时间:5小时代码量:154博客篇:1地铁起点到终点的最短路径查询:使用广度优先遍历,当要访问该站点时先储存在队列,最后出队形式访问每次访问传入数据:name:站点名;now:之前访问的站点字符串总和;nowline:当前站点的线路;ed:要到达的站点名称;i:当前经过站数以及字符串的数组下标;s:当前......
  • 3.31 联考
    3.31补题A\(5pts\)\(n=2\)时,\(\fracn2=1\),即为nim游戏。\(30pts\)对于\((a_1,a_2,a_3,a_4,a_5,a_6)\)这样的六元组,至多有\(10^6\)个。记忆化搜索他们的SG值即可。可能需要若干剪枝,因为复杂度其实是\(10^6\times6^3\)的。\(100pts\)首先观察样例2,合理猜测......
  • SUM-ACM,3月24-3-31周报
    两场天梯赛和一场atcoder。主要错误知识点在于字符串的处理和并查集的掌握不够,不懂灵活运用。第一场pta天梯赛7-56翻了一道字符串的题,我只拿了14分。我不熟悉一个点,f(i,0,s.length())是有问题的,在replace后,s.length()会改变,这个时候replace不是一个好的选择。我们只需要输......
  • 3.25-3.31
    天梯赛2:7-12这是二叉搜索树吗?在满足题意的前提下从前后分别往中间走模拟二叉树的建立即可。///l、//(゚、。7//l、~ヽ//じしf_,)ノ//不要放弃!猫猫会为你加油!#include<bits/stdc++.h>#defineendl'\n'#defineintlonglongusingnamespacestd;constint......