1 条题解
-
0
题目分析
魔法数列的奇妙探索 - 题解
50 分
直接计算 ,总时间复杂度为
100 分
在计算 时,我们可以同时维护 并相应地更新。
-
初始化:令 (因为前 项都是 1)
-
递推计算:对于每个 ,执行以下操作:
- 令
- 从 中减去
- 将 加到 中
时间复杂度为
#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
- 上传者