原【模拟】NewBuildingforSIS

原【模拟】NewBuildingforSIS


题意:给你n个相邻的建筑(从左到右编号1到n),每个建筑有h层,每个建筑的a层到b层中任意一层c层可以花一秒通过连廊直接到隔壁建筑的c层。上下楼1层需要1秒。求q次查询(建筑a,层a)到(建筑b,层b)的最短时间。


#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int main()
{
	int n,h,a,b,k;
    scanf("%d%d%d%d%d",&n,&h,&a,&b,&k);
    while(k--)
    {
        int ta,fa,tb,fb;long long ans=0;
        scanf("%d%d%d%d",&ta,&fa,&tb,&fb);
        if(ta==tb)
            ans+=abs(fb-fa);//同楼层
        if(ta!=tb)
        {
            ans+=abs(tb-ta);//计算横向移动时间
            if(fa>=a&&fa<=b)
            {
                ans+=abs(fb-fa);//如果都处于连廊直接通过的楼层,附加纵向距离
            }
            else
            {
				int temp1=0,temp2=0;
                temp1+=abs(fa-a);//temp1代表如果从最下层连廊走
                temp1+=abs(fb-a);
                temp2+=abs(fa-b);//temp1代表如果从最上层连廊走
                temp2+=abs(fb-b);
				ans+=min(temp1,temp2);//取最短距离
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

 

原SDAU暑假训练第13天做题(2018811)

原SDAU暑假训练第13天做题(2018811)

上午做了大概三个题,挑软柿子捏的,难的不会还是不会,题解的证明也是似懂非懂。下午HDU莫名其妙的关了,没法做题,就看了看算法进阶那本书的数学部分(之前学数学的时候还没买这本书)

然后,感觉613太冷了,晚上就出去溜达去了,路上跟我爸进行了一些心理学方面算是学术性的瞎扯淡,我俩还真是一扯问题就来劲了,幸福。

回宿舍之后和段大佬谈人生,收获相当大,感谢大佬的指点。

看电影去了,看完再睡

原【欧拉函数模板题】【前缀和】FareySequence

原【欧拉函数模板题】【前缀和】FareySequence

Problem Description

The Farey Sequence Fn for any integer n with n >= 2 is the set of irreducible rational numbers a/b with 0 < a < b <= n and gcd(a,b) = 1 arranged in increasing order. The first few are 
F2 = {1/2} 
F3 = {1/3, 1/2, 2/3} 
F4 = {1/4, 1/3, 1/2, 2/3, 3/4} 
F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5} 
You task is to calculate the number of terms in the Farey sequence Fn.

Input

There are several test cases. Each test case has only one line, which contains a positive integer n (2 <= n <= 10<sup>6</sup>). There are no blank lines between cases. A line with a single 0 terminates the input.

Output

For each test case, you should output one line, which contains N(n) —- the number of terms in the Farey sequence Fn. <b

Sample Input

2

3

4

5

0

 

Sample Output

1

3

5

9

思路:由a / b,gcd(a,b)=1知,当前f(n)是在f(n – 1)的基础上加上以n为分母,与n互质的数为分子的分数,所以f(n)比f(n – 1)增加了1~n内与n互质的数的个数,现在题意就很明显了,就是要求1-N的欧拉函数之和。

 

#include <iostream>
using namespace std;
typedef long long ll;
const int MAX=1000005;
int oula[MAX];
void init()
{
	oula[1]=1;
	for(int i=2;i<MAX;i++)
		oula[i]=i;
	for(int i=2;i<MAX;i++)
		if(oula[i]==i)
			for(int j=i;j<MAX;j+=i)
				oula[j]=oula[j]/i*(i-1);
}
int main()
{
	ll n,ans=0;
	init();
	while(cin>>n&&n)
	{
		ans=0;
		for(int i=2;i<=n;i++)
			ans+=oula[i];
		cout<<ans<<endl;
	}
	return 0;
}

原SDAU暑假训练第12天做题(2018810)

原SDAU暑假训练第12天做题(2018810)

题目的分析过程是什么鬼啦!!!!

拿到手的题如果是新的完全不知道他想要干嘛。。

一旦知道它具体考啥了之后,写代码又无比的简单。

这种对题目数学的敏感性还是尽力慢慢培养吧,没事多跟大饼学着点。

明天还有一天,继续加油。

PS:做题速度大佬们一个比一个快,,菜鸡感到压力很大

原SDAU暑假训练第11天看博客做题(201889)

原SDAU暑假训练第11天看博客做题(201889)

上午看博客,做了hdu上面的几个题。

背上板子就能过的题也敲了一遍,加深印象。

从题目中勉强能找出来它想考啥,但是有的题知识点看答案能明白但是做的时候推不出来公式,这大概就是数学题最大的难点吧。

下午比赛的题挺有意思的,就是被这个大水题把我坑了,和第一组样例对不上,找错误和更正都没问题,后来发现我的输出结果虽然跟样例1不一样,一度怀疑样例有错,后来看下面的解释我的答案也对,于是我又改回去交上过了。。。。没看完题就着急做这毛病真的得改。。

【leetcode458】【规律题】【突破性思维】可怜的小猪

【leetcode458】【规律题】【突破性思维】可怜的小猪

先看一个题

题目

有1000只水桶,其中有且只有一桶装的含有毒药,其余装的都是水。它们从外观看起来都一样。如果小猪喝了毒药,它会在15分钟内死去。

问题来了,如果需要你在一小时内,弄清楚哪只水桶含有毒药,你最少需要多少只猪?

回答这个问题,并为下列的进阶问题编写一个通用算法。

进阶:

假设有 n 只水桶,猪饮水中毒后会在 m 分钟内死亡,你需要多少猪(x)就能在 p 分钟内找出“有毒”水桶?n只水桶里有且仅有一只有毒的桶。

分析

可怜的小猪,被拿去做实验了。

先看1只小猪,60分钟的话,它最多可以判断出 60/15+1 = 5只水桶中的毒药桶。每隔十五分钟喝一次水,喝四次,如果幸运的话活了下来,就是最后一桶。

再接着看2只小猪,60分钟,它最后可以判断出25只水桶,可以这样:

00     01     02     03      04

10     11     12     13      14

20     21     22     23      24

30     31     32     33      34

40     41     42     43      44

将桶像上面摆放,第一只猪猪喝掉第一二三四五混合后的水,每隔15分钟喝一次,这样如果不幸运,在x行被毒死了,则证明毒药在第x行,幸运活下来的话,则毒药在第五行;在第一只猪猪和的同时让第二只猪猪喝第一二三四列混合后的水,如果在y列被毒死,则毒药在第y列,如果活下来,则毒药在第五列。这样第一只猪猪判断出了横坐标x,第二只猪猪判断出来纵坐标y,则可以知道哪桶水有毒。

以此类推,1只小猪5^1,  2只小猪5^2,  3只小猪5^3,  4只小猪5^4  ,5只小猪5^5……

java代码:

class Solution {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        
        if(buckets == 1) return 0;
        
        int w = minutesToTest / minutesToDie + 1;
        int re = 1;
        while(Math.pow(w,re) < buckets)
            re ++;
        
        return re;
    }
}


引用 leetcode 458. 可怜的小猪 及 题目的不严谨

以下是原文

这道题很有意思,感觉是之前老鼠喝毒药的进阶版,增加了个时间属性,不错解法差不多,主要是看看在测试时间内,有多少批猪死亡,例如:60分钟内,死亡时间为15,则增加了4个状态,则变成了5个状态,所以就要对log(1000) / log(5)上取整,有这么多头猪就可以了。

class Solution {
public:
    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        if(minutesToTest < minutesToDie)
            return 0;
        return ceil(log(buckets) / log(floor(minutesToTest/minutesToDie) + 1));
    }

};

 

题目不严谨,有可能只需一只猪就可以判断1000个桶

为什么要规定每15分钟猪才能喝一次水?作为一只小猪猪难道不可以每一分钟喝水?

那么由5个状态就变成46个状态,我真是一个天才,哈哈

 

就如上图所示,其他人陷入思维误区,以为把60分钟分为4个15分钟,上图红色所示,我们16分钟那批猪如果检查出毒药了,那肯定是1分钟那批桶有问题,自查看1分钟那批桶的编号即可,依次类推,就可以增加了无数个时间状态,其实可以分成无数个15分钟,涉及到精度的问题,暂且规定1分钟为一批猪,则可以分成60-15个状态,即45个状态,和之前的那个二进制状态,一共46个状态。那么就是log(1000) / log(46) ,上取整,为2只猪。

如果你手速很快,猪可以一秒喝一口水的话,那就有45*60+1个状态,则需要1只猪就可以了。