1 条题解

  • 0
    @ 2025-4-14 18:41:38

    C++ :

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <set>
    #include <map>
    #include <cmath>
    #include <sstream>
    #include <iomanip>
    #include <queue>
    #include <ctime>
    using namespace std;
    template <class T> void checkmin(T &t,T x){if (x < t) t = x;}
    template <class T> void checkmax(T &t,T x){if (x > t) t = x;}
    template <class T> void _checkmin(T &t, T x){if (t == -1) t = x; if (x < t) t = x;}
    template <class T> void _checkmax(T &t, T x){if (t == -1) t = x; if (x > t) t = x;}
    typedef pair <int,int> PII;
    typedef pair <double,double> PDD;
    typedef long long lld;
    #define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
    #define DEBUG(a) cout << #a" = " << (a) << endl;
    #define DEBUGARR(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
    
    const long long INF = 9e17;
    int cnt;
    
    int n,m;
    int a[5];
    long long Pow[63][55][55];
    long long now[55];
    long long init[55];
    long long tmp[55];
    int pos[5][10];
    
    void mul(lld ret[55][55], lld a[55][55], lld b[55][55]) {
    	for (int i = 0; i < cnt; i++) {
    		for (int j = 0; j < cnt; j++) {
    			ret[i][j] = 0;
    			for (int k = 0; k < cnt; k++) {
    					if (b[k][j] && a[i][k] > INF / b[k][j]) {
    						ret[i][j] = INF;
    						break;
    					} else if (ret[i][j] + a[i][k] * b[k][j] > INF){
    						ret[i][j] = INF;
    						break;
    					} else {
    						ret[i][j] += a[i][k] * b[k][j];
    					}
    			}
    		}
    	}
    }
    
    void _mul(lld ret[55], lld a[55], lld b[55][55]) {
    	for (int j = 0; j < cnt; j++) {
    		ret[j] = 0;
    		for (int k = 0; k < cnt; k++) {
    				if (b[k][j] && a[k] > INF / b[k][j]) {
    					ret[j] = INF;
    					break;
    				} else if (ret[j] + a[k] * b[k][j] > INF){
    					ret[j] = INF;
    					break;
    				} else {
    					ret[j] += a[k] * b[k][j];
    				}
    		}
    	}
    }
    
    bool tooBig(long long ans) {
    	for (int j = 0; j < m; j++) {
    		long long sum = 0;
    		for (int i = 0; i < n; i++) {
    			sum += tmp[pos[i][j]];
    			if (sum >= ans) return 1;
    		}
    	}
    	return 0;
    }
    int clzll(lld x){
    	for(int i=62;i>=0;--i)
    		if(x & 1ll<<i)return i;
    }
    long long gao(long long ans) {
    	if(ans == 1)return a[0]-1;
    	memcpy(now, init, sizeof(now));
    	long long ret = 0;
    	for (int i = clzll(ans*100ll); i >=0; i--) {
    		_mul(tmp, now, Pow[i]);
    		if (!tooBig(ans)) {
    			ret |= 1LL << i;
    			for (int i = 0; i < cnt; i++) now[i] = tmp[i];
    		}
    	}
    	return ret;
    }
    
    int main(){
    	int tcc = 0;
    	while (scanf("%d", &n) && n) {
    		printf("Set %d\n", ++tcc);
    		int g=0;
    		for(int i=0;i<n;++i){
    			scanf("%d",a+i);
    			g = __gcd(g,a[i]);
    		}
    		m=0;
    		for(int i=0;i<n;++i)m = max(m,a[i]/=g);
    		sort(a,a+n);
    		cnt = 0;
    		for (int i = 0; i < n; i++) {
    			for (int j = 0; j < m; j++) {
    				pos[i][j] = cnt++;
    			}
    		}
    		memset(Pow[0], 0, sizeof(Pow[0]));
    		memset(now,0,sizeof(now));
    		now[pos[0][m-1]] = 1;
    		memcpy(init, now, sizeof(init));
    		for (int i = 0; i < n; i++) {
    			for (int j = 0; j +1 < m; j++) {
    				Pow[0][pos[i][j + 1]][pos[i][j]] = 1;
    			}
    		}
    		for (int i = 0; i < n; i++) {
    			for (int j = 0; j <= i; j++) {
    				Pow[0][pos[j][m - a[i] ]][pos[i][m-1]] = 1;
    			}
    		}
    		for (int i = 1; i < 63; i++) {
    			mul(Pow[i], Pow[i - 1], Pow[i - 1]);
    		}
    		int q;
    		scanf("%d", &q);
    		for (int i = 0; i < q; i++) {
    			long long x;
    			cin >> x;
    			long long ret = gao(x);
    			if (ret > 100 * x) {
    				puts("no candy for you");
    			} else {
    				cout << (ret + 1)*g << "\n";
    			}
    		}
    	}
    }
    
    • 1

    信息

    ID
    3147
    时间
    1000ms
    内存
    64MiB
    难度
    (无)
    标签
    (无)
    递交数
    0
    已通过
    0
    上传者