1 条题解

  • 0
    @ 2026-11-15 21:49:34

    题目分析

    魔法数列的奇妙探索 - 题解

    50 分

    直接计算 AiA_i,总时间复杂度为 O(NK)O(NK)

    100 分

    在计算 AnA_n 时,我们可以同时维护 S:=An−K+…+An−1S := A_{n-K} + \ldots + A_{n-1} 并相应地更新。

    1. 初始化:令 S=KS = K(因为前 KK 项都是 1)

    2. 递推计算:对于每个 n=K,K+1,…,Nn = K, K+1, \ldots, N,执行以下操作:

      • 令 An=SA_n = S
      • 从 SS 中减去 An−KA_{n-K}
      • 将 AnA_n 加到 SS 中

    时间复杂度为 O(N)O(N)

    #include <iostream>
    #include <vector>
    #include <queue>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    
    using namespace std;
    
    #define int long long
    #define ll long long
    typedef vector<int> vi;
    typedef vector<string> vs;
    typedef pair<int, int> pi;
    #define F first
    #define S second
    #define pb push_back
    #define sz(a) a.size()
    #define Print(a) for(auto x : a) {cout << x << " ";} cout << endl;
    #define all(x) (x).begin(), (x).end()
    #define rall(x) (x).rbegin(), (x).rend()
    #define allr(x) (x).rbegin(), (x).rend()
    #define endl "\n"
    #define YES cout << "YES\n";
    #define NO cout << "NO\n";
    
    const int MOD = 1e9;
    
    void solve() {
        int n, k; cin >> n >> k;
        if (n<k) {
            cout << 1 << endl;
            return;
        }
    
        vi a(n+1, 0);
        for(int i = 0; i < k; i++) {
            a[i] = 1;
        }
    
        queue<int> q;
        int sum = k;
        for(int i = k; i <= n; i++) {
            a[i] = sum;
            sum = (sum+a[i]-a[i-k]+MOD)%MOD;
        }
    
        cout << a[n] << endl;
    }
    
    int32_t main() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        int t = 1;
        //cin >> t;
        while(t--) {
            solve();
        }
    }
    cpp
    #include <bits/stdc++.h>
    using namespace std;
    
    #define int long long
    
    int n, m, k, pre[505][505];
    
    void solve() {
    	cin >> n >> m >> k;
    	string s[505];
    	for (int i = 1; i <= n; i++) cin >> s[i], s[i] = " " + s[i];
    	for (int i = 0; i <= n; i++)
    		for (int j = 0; j <= m; j++) pre[i][j] = 0;
    	for (int i = 1; i <= n; i++)
    		for (int j = 1; j <= m; j++)
    			pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + (s[i][j] == 'g');
    	int res = INT_MAX;
    	for (int i = 1; i <= n; i++)
    		for (int j = 1; j <= m; j++)
    			if (s[i][j] == '.') {
    				int maxx = min(n, i + k - 1), maxy = min(m, j + k - 1);
    				int minx = max(1LL, i - k + 1), miny = max(1LL, j - k + 1);
    				int tmp = pre[maxx][maxy] - pre[minx - 1][maxy] - pre[maxx][miny - 1] + pre[minx - 1][miny - 1];
    				res = min(res, tmp);
    			}
    	cout << pre[n][m] - res << "\n";
    }
    
    signed main() {
        ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
        int T;
        cin >> T;
        while (T--) solve();
        return 0;
    }
    cpp
    #include <bits/stdc++.h>
    using namespace std;
    
    const int mod = 9901;
    int n, k, dp[205][105];
    
    int main() {
    	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    	cin >> n >> k;
    	for (int j = 1; j <= k; j++) dp[1][j] = 1;
    	for (int j = 1; j <= k; j++)
    		for (int i = 3; i <= n; i += 2)
    			for (int t = 1; t <= i - 1; t += 2)
    				dp[i][j] = (dp[i][j] + dp[t][j - 1] * dp[i - t - 1][j - 1] % mod) % mod;
    	cout << (dp[n][k] - dp[n][k - 1] + mod) % mod << endl;
    	return 0;
    }
    
    f(l,r) = max{f(k+1,r) - K, 0}
    
    f(l,r) = f(l+1,r) + 1
    cpp
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    
    using namespace std;
    
    const int SIZE = 3e2 + 5;
    
    char str[SIZE];
    int s;
    int dp[SIZE][SIZE];
    
    int main() {
        
        scanf("%s", str + 1);
        scanf("%d", &s);
    
        int n = (int) strlen(str + 1);
    
        for (int r = 1; r <= n; ++ r) {
            for (int l = r; l >= 0; -- l) {
                // printf("Processing substring: %s\n", string(str + l, str + r + 1).c_str()); // Debugging line to check the current substring
                dp[l][r] = r - l + 1;
    
                for (int k = l; k < r; ++ k) 
                    dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
    
                if (str[l] == 'm') {
                    for (int k = l + 1; k <= r; ++ k) {
                        if (str[k] == 'x' && dp[l + 1][k - 1] == 0) {
                            dp[l][r] = min(dp[l][r], max(0, dp[k + 1][r] - s));
                        }
                    }
                }
            }
        }
    
        printf("%d\n", dp[1][n]);
        return 0;
    }
    cpp
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    constexpr int Max=(1<<20)+10;
    ll s[Max],f[Max];
    int m,n,lg[Max];
    signed main()
    {
    //	freopen("xor.in","r",stdin),freopen("xor.out","w",stdout);
    	ios::sync_with_stdio(false);
    	cin.tie(nullptr),cout.tie(nullptr);
    	cin>>m,n=1<<m;
    	for(int i=2;i<n;++i)
    		lg[i]=lg[i>>1]+1;
    	for(int i=0;i<n;++i)
    		cin>>s[i],f[i]=s[i];
    	for(int i=n-1;i;--i)
    	{
    		int d=m-lg[i],w=1<<(d-1),l=(i<<d)-n;
    		ll x=s[l],y=s[l+w],u,v;
    		for(int j=l;j<l+w;++j)
    		{
    			u=f[j],v=f[j+w];
    			f[j+w]=max(u,v);
    			f[j]=max(u+y,v+x);
    		}
    		s[l]+=s[l+w];
    	}
    	for(int i=0;i<n;++i)
    		cout<<f[i]<<" \n"[i+1==n];
    	return 0;
    }
    
    • 1

    信息

    ID
    212
    时间
    1000ms
    内存
    512MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者