NC218553 机器人（高精度+排序）

贪心点思路很简单，就是根据邻项微扰原则，进行比较两邻项，移项后就能看出公式

但是在这题显然爆ll，因此要用高精度

抄了一下int128的板子，以前虽然碰到过但是都没有记录下来

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int N=2e5+10;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
inline __int128 read() {
    __int128 x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline void print(__int128 x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}
struct node{
    int a,b;
}s[N];
bool cmp(node s1,node s2) {
    if(1.0*(s1.a-1)/s1.b<1.0*(s2.a-1)/s2.b){
        return true;
    }
    return false;
}
int main() {
    int n;
    cin >> n;
    __int128_t x;
    x=read();
    for (int i=1;i<=n;i++)
        cin >>s[i].a>>s[i].b;

    sort(s+1,s+n+1,cmp);
    for (int i=1;i<=n; i++) {
        x=s[i].a*x+s[i].b;
    }
    print(x);
}

 下面是用字符串模拟的板子

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int N=2e5+10;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
struct node{
    int a,b;
}s[N];
bool cmp(node a,node b){
    return 1.0*(a.a-1)/a.b<1.0*(b.a-1)/b.b;
}
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}
vector<int> mul(vector<int> &A, int b){
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}
int main(){
    ios::sync_with_stdio(false);
    int i;
    int n;
    string a;
    cin>>n>>a;
    for(i=1;i<=n;i++){
        cin>>s[i].a>>s[i].b;
    }
    sort(s+1,s+1+n,cmp);
    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    for(i=1;i<=n;i++){
        A=mul(A,s[i].a);
        vector<int> B;
        while(s[i].b){
            B.push_back(s[i].b%10);
            s[i].b/=10;
        }
        A=add(A,B);
    }
    for (int i = A.size() - 1; i >= 0; i -- ) printf("%d", A[i]);
    return 0;
}