校内OJ 2019.3.17 NOIP 模拟赛

前言

Rank 7,Rating +48。

第二道题 $STL$ 莫名玄学炸 T 掉 40 分。

P1 电阻

题面

题目描述

询问要得出一个电阻值为 $\frac ab$ 的电阻。

元件由 $3$ 种方式组成:

  1. 一个电阻
  2. 一个元件与一个电阻串联
  3. 一个元件与一个电阻并联

输入格式

一行两个数, $a$ 和 $b$ 表示询问元件的阻值为 $\frac ab$ 。

输出格式

一行一个数 $ans$ ,表示最少需要的电阻数。

样例

输入 #1

233 666

输出 #1

27

思路

两个电阻 $R1,R2$ 串联,总电阻 $R0=R1+R2$。

两个电阻 $R1,R2$ 并联,总电阻 $R_0=\frac{1}{\frac1{R_1}+\frac1{R_2}}$ ,变形一下即为 $\frac1{R_0}=\frac1{R_1}+\frac1{R_2}$ 。

考虑一组较为简单的样例,$R=\frac 75 \Omega$。

因为 $\frac 75 > 1$,所以一定为两个电阻(元件)串联而成。其中一个电阻值为整数,另一个为小数。我们将其拆分为 $\frac 75 = 1 + \frac 25$ 。(整数部分和小数部分)

其中的 $1$ 为整数,不用再分。$\frac 25$ 不是整数,所以要再分。因为 $\frac 25 < 1$ ,所以是由两个元件并联而成的。我们取倒数(根据公式)后将其拆分为 $\frac 52 = 2+\frac 12$ 。

后者 $\frac 12$ 的倒数为整数 $2$ ,无需再分。前者 $2$ 的倒数为 $\frac 12$ ,由于 $\frac 12 < 0$ ,所以它是并联而成的。我们取倒数后拆分为 $\frac 2 = 2$ 。我们发现,它已经为整数,无法拆分了。

上面这组样例为整数的电阻数一共用了 $5$ 个,所以答案为 $5$ ,下面是电路图:

现在我们推广开来,对于任意的 $\frac ab$ ,都可以用这种方法求得需要用到的电阻个数。

我们还发现,不管 $R$ 大于还是小于 $1$ ,其实拆分都是一样的,因为取倒数后的拆分相同。

所以我们在并联情况时可以 $swap$ 一下。

代码

#include<bits/stdc++.h>
using namespace std;
long long sol(long long a,long long b){
	if (a==0){
		return 0;
	}
	if (a%b==0){
		return (long long)a/b;
	}
	if (b==a+1){
		return b;
	}
	if (a==1){
		return b;
	}
	if (a==b){
		return 1;
	}
	if (a<b){
		swap(a,b);
	}
	if (a>b){
		long long y=a%b;
		long long x=(a-y)/b;
		return x+sol(y,b);
	}
	return 0;
}
int main(){
	long long a,b;
	cin>>a>>b;
	cout<<sol(a,b);
}

P2 找零

题面

题目描述

现在小A就要出去购物了

他的手头上有 $n$ 种不同面值的硬币,每种面值的硬币有无数个

为了携带方便,他希望带最少数量的硬币

同时为了防止再收到找零,他希望他可以用这些硬币组合出 $1 \sim x$ 之间的任意值

输入格式

第一行两个数字, $x$ 和 $n$ 。

第二行共 $n$ 个数字,表示 $n$ 种不同硬币的面值

输出格式

一行一个数,表示最少需要的硬币数

如果小A无论怎么取硬币都无法避免被找零的命运,请直接输出 $-1$。

代码

#include<bits/stdc++.h>
using namespace std;
inline long long read(){
    long long ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
long long n,x,s[1000005];
int main(){
	cin>>x>>n;
	for (int i=1;i<=n;i++){
		s[i]=read();
	}
	sort(s+1,s+1+n); 
	if(s[1]!=1){
		cout<<"-1";
		return 0;
	}
	long long now=0,ans=0;
	while(now<x){
		int k=upper_bound(s+1,s+n+1,now+1)-s-1;
		now+=s[k];
		ans++;
	}
	cout<<ans;
}

P3 2048

题面

给定一个长度为 $n$ 的数列,在这个数列中选取一个子序列使得这个子序列中的数能合出 $2048$

对于合并操作,可以选择这个序列中的任意两个数进行合并,当然这两个数必须是相同的(即2个 $x$ 合并后成为一个 $2x$)

对于每个序列,只要进行若干次合并操作后,这个序列中至少有一个$2048$(可以有其他数剩余),就称这个序列是合法的

我们可以认为只要选取的数在原数列中的位置不同,这些序列就是不同的

对于给定的数列,小朋友们需要算出有多少子序列是合法的,并把这个数 对 $998244353$ 取模。

思路

粘一段学长的题解

一个子序列或者说子集合法的条件是:只要二的次幂的和 不小于 $2048$ 即可。

可以想象,二进制加法即 $2048$ 合并的过程。

转化为用 $DP$ 统计有多少子集的和不小于 $2048$ ,很简单的一个背包问题。

评论

  1. yzx1798106406
    Windows Chrome

    Orz

    1年前
    2019-3-31 16:09:39

发送评论 编辑评论


				
上一篇
下一篇