前言
Rank 7，Rating +48。
第二道题 $STL$ 莫名玄学炸 T 掉 40 分。
P1 电阻
题面
题目描述
询问要得出一个电阻值为 $\frac ab$ 的电阻。
元件由 $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$ ，很简单的一个背包问题。
Orz