【扬中集训DAY2T2】机智的AmyZhi

【题目链接】

【算法】

据说标算是暴力？从N-200开始搜

不过我用了搜索+一些奇怪的剪枝，也A了....

【代码】

标程

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,cases;
bool check(ll x){
    ll tmp=x;
    for(int i=1;i<=20;i++){
        tmp+=x%10;
        x/=10;
    }
    if(tmp==n)return 1;
    return 0;
}
int main(){
        scanf("%I64d",&cases);
        int flag;
        while(cases--)
        {
            flag=0;
            scanf("%I64d",&n);
            for(ll i=max(1LL,n-200);i<=n;i++)
                if(check(i)){
                    printf("%I64d
",i);
                    flag=1;
                    break;
                }
            if (flag==0) puts("Stupid SiriusRen");
        }
    return 0;
}

我的程序

#include<bits/stdc++.h>
using namespace std;
#define MAXL 17
typedef long long LL;

LL i,j,l,T,N,len,lth,sum;
LL a[MAXL+10][MAXL+10],s[MAXL+10][MAXL+10],f[MAXL+10],ans[MAXL+10];
vector<LL> vec,res;
bool solved;

template <typename T> inline void read(T &x) {
    int f = 1; x = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
}

template <typename T> inline void write(T x) {
    if (x < 0) { putchar('-'); x = -x; }
    if (x > 9) write(x/10);
    putchar(x%10+'0');
}

template <typename T> inline void writeln(T x) {
    write(x);
    puts("");
}

inline void save_answer() {
    int i;
    for (i = 1; i <= len; i++) res.push_back(ans[i]);    
} 

inline void dfs(int dep) {
    int i,l,r;
    if (solved) return;
    if (sum > N) return;
    if (sum + 9 * (s[len][len] - s[len][dep-1]) < N) return;
    if (dep > len) {
        if (sum == N) {
            solved = true;
            save_answer();
        }
    } else {
        l = 0; r = 9;
        if (dep == 1) l = 1;
        for (i = l; i <= r; i++) {
            if (solved) break;
            if (sum + a[len][dep] * i <= N) {
                sum += a[len][dep] * i;
                ans[++lth] = i;
                dfs(dep+1);
                sum -= a[len][dep] * i;
                --lth;
            }
        }
    }    
}

void print() {
    int i;
    for (i = 0; i < res.size(); i++) write(res[i]);
    cout<<endl;
}

int main() {
    
    freopen("amy.in","r",stdin);
    freopen("amy.out","w",stdout);
    
    f[0] = 1;
    for (i = 1; i <= MAXL; i++) f[i] = (f[i-1] << 3) + (f[i-1] << 1); 
    for (i = 1; i <= MAXL; i++) {
        a[i][i] = 2;
        for (j = i - 1; j >= 1; j--) {
            a[i][j] = f[i-j] + 1; 
        }    
    } 
    for (i = 1; i <= MAXL; i++) {
        for (j = 1; j <= MAXL; j++) {
            s[i][j] = s[i][j-1] + a[i][j];
        }
    }
    read(T);
    while (T--) {
        vec.clear(); res.clear();
        solved = false;
        read(N);
        for (l = 1; l <= MAXL; l++)    {
            if (s[l][l] * 9 < N) continue;
            if (a[l][1] > N) break;
            vec.push_back(l);
        }
        for (i = 0; i < vec.size(); i++) {
            lth = sum = 0; len = vec[i];
            dfs(1);
            if (solved) break;
        }
        if (solved) print();
        else puts("Stupid SiriusRen");
    }
    
    return 0;

}

【扬中集训DAY2T2】 机智的AmyZhi

【扬中集训DAY2T2】机智的AmyZhi