1.轉移dp問題

昨天的練習賽上有一個很好玩的起終點問題，第一時間給出bfs的寫法。

但是寫到后面發現不行，還得是的dp轉移的寫法才能完美的解決這道題目。

每個格子可以經過可以不經過，因此它的狀態空間是2^（n*m），但是n,m的數據范圍是500，顯然是不可取的。bfs適用于計數或者最短距離，而不是最大和或最優路徑問題。

故：對于最大和的問題dp是最合適的選擇。

題目意思：

給定起點終點，每個點只能經過一次，找到最大的路徑和，并且只能向下向右走動。

思路：

既然是dp那么一點有初始化，很容易想到第一列一定是固定的，因為該列只能像下走動（從起始點開始）。

那么之后我們就對每一列賦值（從第一列開始，每一列的狀態都是從前面一列轉移過來的）。

對于某一列的賦值，我們可以從頭開始往下走，也可以是從尾開始走到第一行在進行繼續走，那么這里就分成了兩種情況。

我們先任意求出一種情況，然后在慢慢的用前綴和進行維護（因為是一條線下的，前綴和維護方便）。（畢）

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int nima=8e18;
int a[504][504];
void solve(){int n,m;cin>>n>>m;int s,t;cin>>s>>t;s--,t--;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];}}vector<vector<int>> dp(n,vector<int>(m,-nima));//這里的dp[i][j]的意思是從[s][0]開始到[i][j]的最大貢獻// 初始化第一列的值int sum=a[s][0];for(int i=s;;){//一共要遍歷s次dp[i][0]=sum;  // 初始化環形路徑的第一個點i=(i+1)%n;     // 環形移動sum+=a[i][0];   // 累加路徑上的值if(i==s) break; // 回到起點時結束}// 動態規劃處理每一列for(int i=1;i<m;i++){int cnt=-nima;int sum=0;vector<int> pre(n);  // 前綴和數組// 正向遍歷，計算從上方轉移的最大值for(int j=0;j<n;j++){cnt=max(cnt,dp[j][i-1]-sum);  // 維護最大值，從左邊過來的sum+=a[j][i];                   // 累加當前列的值dp[j][i]=cnt+sum;              pre[j]=sum;                     // 記錄前綴和，這個sum是列環形狀態下的前綴和}cnt=-nima;// 反向遍歷，處理環形路徑的情況for(int j=n-1;j>=0;j--){if(j!=n-1) dp[j][i]=max(dp[j][i],cnt+pre[j]);// 計算從下方轉移的最大值（考慮環形路徑）if(j!=0) cnt=max(cnt,dp[j][i-1]+pre[n-1]-pre[j-1]);}}cout<<dp[t][m-1]<<endl;
}signed main(){int ac=1;while(ac--)  solve();return 0;
}

2.簡單數學

這次的團隊賽有個簡單數學問題，挺有意思的。

題目意思：

給出一個數組，找出最大貢獻（每個貢獻是相鄰兩個數字之差的絕對值）。

思路：

我們可以根據題目給的樣例找到....

1 2 3 4 5 6 的最大貢獻是9，即（3,4）(2,5) （1,6）狀態下貢獻是最大的。

我們進行改變之后發現....

3 2 1 4 5 6的最大貢獻也是9，即（1,4）（2,5）（3,6）狀態下貢獻是最大的。

之后在進行任意舉列子之后我們發現....

一組數據進行排序后每次最大貢獻取法是首位找（畢）

小tips：數學問題，大膽猜，先排序，然后...（看看能不能瞎貓碰到死耗子）

#include<bits/stdc++.h>
using namespace std;
#define int long longinline void solve(){int n; cin >> n;vector<int> a(2 * n);for(int i = 0; i < 2 * n; i++) cin >> a[i];sort(a.begin(), a.end());//排序int answer = 0;for(int i = 0; i < n; i++) {answer+= abs(a[i] - a[2 * n - 1 - i]);//首位之差，參考1 2 3 4 5 6這個樣例}cout << answer << endl;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t; cin >> t;while(t--) solve();return 0;
}

3.數論

這次的數論有點點繞...

?題目意思：

給定一個數是好數m，只有m形如k！或者為偶數的條件下才成立。

給定一個數a，找到最少的分類情況k，使得k個好數之后是a。

思路：

觀察題目的數據范圍我們看到，n<=10^12，而且有t組數據，最好做一個狀態壓縮。

我們先對階乘進行賦初值，15!>10^12。

每次減去1到15的階乘，最后加上二進制中1的個數就是答案，每次枚舉維護一個最小值即可。（畢）

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pii pair<int, int> 
vector<int> v;inline void solve() {int sum = 1,i=1;  // 初始化階乘結果為 1while(sum<=1e12){sum*=i++;v.push_back(sum);}//sort(v.begin(), v.end());  // 對向量 v 進行排序// 去除重復的階乘結果//v.erase(unique(v.begin(), v.end()), v.end());int m = v.size();  int n;cin >> n; int ans = 1e9 + 7;// 遍歷所有可能的子集（通過位掩碼的方式）for (int i = 0; i <= (1 << m) - 1; i++) {int res = n;  // 初始化 res 為 n// 遍歷每一位，檢查是否在子集中for (int j = 0; j < m; j++) {if ((1 << j) & i)  // 如果第 j 位在子集 i 中res -= v[j];  // 從 res 中減去對應的階乘值}if (res < 0) continue;  // 如果 res 為負數，跳過當前子集// 計算當前子集的位數和剩余數的位數之和，并更新最小值ans = min(ans, (int)__builtin_popcountll(res) + __builtin_popcountll(i));}cout << ans << endl;
}
signed main() {int nc;cin >> nc;while (nc--) solve();  
}