思维题练习部分

附注： 今天被降维打击了hh,被虐的滋味真不爽，orz

1.指针

初始时，量角器上的指针指向刻度 0。

现在，请你对指针进行 n 次拨动操作，每次操作给定一个拨动角度 ai，由你将指针拨动 ai 度，每次的拨动方向（顺时针或逆时针）由你自由决定。

请你判断，能否通过合理选择每次拨动的方向，使得指针最终仍然指向刻度 0。
输入格式
第一行包含整数 n。

接下来 n 行，每行包含一个整数 ai，表示一次操作的拨动角度。

输出格式
如果可以做到指针最终仍然指向刻度 0，则输出 YES，否则输出 NO。

数据范围
前 4 个测试点满足 1≤n≤3。
所有测试点满足 1≤n≤15，1≤ai≤180。

输入样例1：
3
10
20
30
输出样例1：
YES
输入样例2：
3
10
10
10
输出样例2：
NO
输入样例3：
3
120
120
120
输出样例3：
YES

没什么好说的，直接暴力

思路一：dfs

#include 
#define int long long 
using namespace std;
const int N = 510;
int n;
int a[N];
int f[N][N];
bool dfs(int u,int sum)
{
    if(u>n)return sum%360==0;
    if(dfs(u+1,sum+a[u])|dfs(u+1,sum-a[u]))return true;
}
signed main()
{
    cin>>n;
    for (int i = 1; i <= n; i ++ )cin>>a[i];
    if(dfs(1,0))puts("YES");
    else puts("NO");
    return 0;
}

思路二： dp

定义f[i][j]为从前i个物品里，角度为j的方案数

方程：

f[i][j]=f[i-1][(j+a[i])%360]

f[i][j]+=f[i][(j-a[i]+360)m%360];

这里只需要判断是不是即可，可以用位运算符代替

#include
using namespace std;
#define int long long 
const int N = 500,mod = 360;
int n;
int a[N];
int f[N][N];
signed main()
{
    cin>>n;
    for (int i = 1; i <= n; i ++ )cin>>a[i];
    f[0][0]=1;
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= 360; j ++ )
        {
            f[i][j]=f[i-1][(j+a[i])%mod];
            f[i][j]+=f[i-1][(j-a[i]+mod)%mod];
        }
    if(f[n][0])puts("YES");
    else puts("NO");
    return 0;
}

2.相遇问题

一个无限长的楼梯上站着两个人，其中一个人在第 aa 级台阶上，另一个人在第 bb 级台阶上。

两个人都可以自由的上下移动，每人每次可以向上或向下移动一级台阶。

每个人的每次移动都要消耗体力，具体为：

对于同一个人来说，其第 1次移动消耗的体力为 1，第 2 次移动消耗的体力为 2，第 3 次移动消耗的体力为 3，以此类推。

例如，如果一个人先向上移动一级台阶，再向下移动一级台阶，最后再次向上移动一级台阶，那么他消耗的总体力值为 1+2+3=6。

两个人想要通过合理移动，使得他们能够在同一级台阶上相遇，并且相遇时，两人消耗的总体力值之和尽可能小。

请你计算，两人消耗的总体力值之和的最小可能值。

输入格式

第一行包含一个整数 a。

第二行包含一个整数 b。

输出格式

一个整数，表示两人消耗的总体力值之和的最小可能值。

数据范围

所有测试点满足，1≤a,b≤1000，a≠b。

输入样例1：
3
4
输出样例1：
1
样例1解释
在本样例中，让第一个人上一级台阶或第二个人下一级台阶均可，消耗总体力为 1。

思路：我们可以发现，每一次移动消耗的体力都比上一次要多，所以我们可以考虑贪心来得到最优解。经过分析，我们发现，这样的策略可以得到最优解：A移动一步，B移动一步，A移动一步，B移动一步.....以此类推。消耗的体力为：1，1，2，2，3，3，4，4.....这样可以保证体力消耗得更少。

我们可以先算出两人的距离（也就是abs(a-b)），然后除以2让A走一半B走另一半。接着，我们用等差求和公式(首项+末项)*项数/2求出路程，再乘2就是他们俩的路程和。需要注意的是，当两人的距离为奇数的时候，需要其中一个人再移动一步，所以当距离为奇数的时候我们应该再加上abs(a-b)/2+1。

当然，我用的是前缀和处理

时间复杂度 O(1)

#include 
#include 
#include 
using namespace std;
const int N = 1e5;
int a,b;
int s[N];
int main()
{
    cin>>a>>b;
    int res = 0;
    for (int i = 1; i <= 1000; i ++ )
        s[i]=s[i-1]+i;
    int r1 = abs(b - a)/2,r2 = abs(b-a)-abs(b - a)/2;
    res=s[r1]+s[r2];
    cout << res <<'\n';
    return 0;
}
 
 
//也可以这样写
#include 
#include 
#include 
 
using namespace std;
 
int main()
{
    int a, b;
    cin >> a >> b;
    int n = abs(a - b);
    int x = n / 2, y = n - x;
    cout << x * (x + 1) / 2 + y * (y + 1) / 2 << endl;
 
    return 0;
}

3.砝码称重

砝码是一种作为质量标准的物体，通常为金属块或金属片，可以用作称量较精准的质量。

给定一个整数 nn，我们需要选取一些砝码用于称量，砝码只能放在一边，要求：

所有选取砝码的总重量恰好为 n。
每个选取砝码的重量 x 都是满足 1≤x≤n的正整数。
可以选取多个重量相同的砝码，例如选取两个重量为 1 的砝码。
利用选取的砝码（部分或全部），可以组成 1∼n之间的任意整数重量。
选取砝码的数量应尽可能少。
请你计算并输出选取砝码的最少可能数量。
输入格式

共一行，一个整数 n。

输出格式

一个整数，表示选取砝码的最少可能数量。

数据范围

前三个测试点满足 1≤n≤10。

所有测试点满足 1≤n≤109。

输入样例1：
 
6
输出样例1：
 
3
样例1解释
 
在此样例中，我们只需要选取重量为 1,2,3 的砝码各一个，即可组成 1∼6 之间的任意整数重量：
 
1=1
2=2
3=3
4=1+3
5=2+3
6=1+2+3
所以最少需要 3 个砝码。

有点像蓝桥里的一道题，思想类似

小学奥数里有一道题类似与本题，结论是取1，2，4，8，......的时候能组成的数字最多

思路： 数字选择 1，2 ，4.....2^(k)       2^(k+1)

如果下一个数字小于2^(k+1)那么能表示的数字比2^(k+1)小，不妨用2^(k+1)代替

能表示的数的范围是1~2(k)-1

#include 
#define int long long
using namespace std;
int n;
signed main()
{
    cin>>n;
    int res = 0;
    while((1 << res ) - 1 < n)res++;
    cout << res <<'\n';
    return 0;
}
 
//这样写也行
#include 
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    int res = 0;
    while(n)
    {
        n /= 2;
        res ++;
    }
    cout << res << "\n";
    return 0;
}
 
//当然大家会发现，log以2为底的数也可以做
#include 
using namespace std ;
int main () {
    int n ;
    cin >> n ;
    cout << (int)(log2 (n)) + 1 ;
}

其他的改天再补吧，晚安，玛卡巴卡

嗷嗷嗷~