PAT BASIC 1101-1104

1101 b是a的多少倍

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    string s;
    cin >> s;
    int a;
    cin >> a;
    string s1 = s.substr(s.length() - a);
    s1 += s.substr(0, s.length() - a);
    int c, d;
    c = stoi(s);
    d = stoi(s1);
    printf("%.2f\n", 1.0*d/c);
    return 0;
}

1102 教超冠军卷

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    string id;
    int price, cnt;
    string bestid, bestid2;
    int bestCnt = -1;
    int bestTotal = -1;
    for(int i = 0; i < n; i++)
    {
        cin >> id >> price >> cnt;
        if(cnt > bestCnt)
        {
            bestCnt = cnt;
            bestid = id;
        }
        if(price*cnt > bestTotal)
        {
            bestTotal = price*cnt;
            bestid2 = id;
        }
    }
    cout << bestid << ' ' << bestCnt << endl;
    cout << bestid2 << ' ' << bestTotal << endl;
    return 0;
}

缘分数

a³ - (a-1)³ = c², c = b² + (b-1)²
题目限制a的范围(0, 25000)，计算sqrt(25000³ - 24999³) = 43300.4
也就是说b的平方和一定 <= 43300.4;
for( i从1开始遍历 ) 当ii + (i-1)(i-1) > 45000，break;
数组arr记录的就是arr[i]表示i的平方和数

注意，这里存在一个问题，sqrt函数输出值是double类型，要和a数组下标匹配，必须强制转换为int，但这就出现了精度损失问题，导致很多脏数据也被显示，为了解决这个问题，让强制转型后的sqrt和没有转型的sqrt相减，取绝对值，如果该值小于0.001，那么可判断符合要求。sqrt返回值的精度要小于0.001。

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 100010;
int a[N];

int main()
{
    //枚举所有b*b+(b-1)*(b-1)，a[tmp] = b；
    for(int i = 2; ; i++)
        //i从2开始，是因为题目要求a和a-1的立方差是另一个整数c的平方
    {
        int tmp = i*i + (i-1)*(i-1);
        if(tmp > 50000) break;
        a[tmp] = i;
    }
    int n, m;
    cin >> n >> m;
    bool flag = false;
    for(int i = n; i <= m; i++)
    {
        int tmp = (int)sqrt(i*i*i - (i-1)*(i-1)*(i-1));
        if(a[tmp]!=0 && fabs(tmp - sqrt(i*i*i - (i-1)*(i-1)*(i-1))) < 0.001)
        {
            cout << i << ' ' << a[tmp] << endl;
            flag = true;
        }
    }

    if(!flag) cout << "No Solution" << endl;
    return 0;
}

1104 天长地久

a的各位数字之和m，a+1的各位数字之和n
最后一位必须是9，如果不是9，那么n = m+1，gcd(m, m+1) = 1;
假设最后有c位9，那么n = m - c*9+1

1. dfs去枚举每一个位上的数值
2. 剪枝：当前枚举到的数a的各位之和sum - (k - u) < m

#include <iostream>
#include <cmath>
#include <unordered_set>
#include <set>

using namespace std;
int k, m;
//无序set容器存所有满足条件的n
unordered_set<int> st;
//有序set容器，pair的作用是按照第一个升序，再按第二个升序
set<pair<int, int>> res;
//是否有解的标志
bool flag;

int gcd(int a, int b)
{
    return b ? gcd(b, a%b) : a;
}

bool is_prime(int x)
{
    if(x<=1) return false;
    for(int i = 2; i <= x/i; i++)
        if(x%i==0) return false;
    return true;
}

int digit_sum(int n)
{
    int sum = 0;
    while(n)
    {
        sum += n%10;
        n /= 10;
    }
    return sum;
}

//u表示枚举到哪一位，sum表示各位的和，a是当前数，a的各位数字之和为m
void dfs(int u, int sum, int a)
{
    if(u > k || sum > m) return;
    if(sum + (k - u) * 9 < m) return;//后面的数不足以组合
    //枚举够k位了，并且各位之和 = m
    if(u == k && sum == m)
    {
        //求a+1的各位数之和n，看是否存在
        int n = digit_sum(a+1);
        if(st.count(n))
        {
            flag = true;
            res.insert({n, a});
        }
        return;
    }
    //枚举每一位数
    for(int i = 0; i <= 9; i++)
    {
        if(u==0 && i==0) continue;//第1位不能取0
        dfs(u+1, sum+i, a*10+i);
    }
}

int main()
{
    int N;
    cin >> N;
    for(int i = 1; i <= N; i++)//t组数据
    {
        cout << "Case " << i << endl;
        cin >> k >> m;
        //预处理，能与m凑出最大公约数是大于2的素数的满足条件的n
        flag = false;
        res.clear();
        st.clear();
        for(int n = 1; n <= 90; n++)
        {
            auto t = gcd(n, m);
            if(t>2 && is_prime(t))
                st.insert(n);
        }
        //dfs
        dfs(0, 0, 0);
        if(!flag) puts("No Solution");
        else
            for(auto x : res)
                printf("%d %d\n", x.first, x.second);
    }
    return 0;
}