可分解的正整數

算法：思維

因為可以有負數 所以除了1以外的任何數都可以構造

當這個數為x構造方法為

-(x-1)? -(x-2)? -(x-3) ....-1 0 1...x-3 x-2 x-1 x

除了x，x以前的數都會被負數抵消

#include <bits/stdc++.h>
#define ll long long
ll a[100005];
using namespace std;
int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}ll ans=0;for(int i=1;i<=n;i++){if(a[i]!=1) ans++;}cout<<ans<<"\n";return 0;
}

產值調整

算法：思維 打表

當三個數相同時 不管怎么調整 結果不會發生改變，所以當三個數相同時break即可

根據模擬題目要求打表后發現，調整100次后 所有數都會變成相同的，所以break后不會使代碼超時

#include <bits/stdc++.h>
#define ll long long
ll a[100005];
using namespace std;
int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll t;cin>>t;while(t--){ll a,b,c,k;cin>>a>>b>>c>>k;for(int i=1;i<=k;i++){ll na,nb,nc;na=(b+c)/2;nb=(a+c)/2;nc=(a+b)/2;a=na;b=nb;c=nc;if(a==b and b==c) break;}cout<<a<<" "<<b<<" "<<c<<" "<<"\n";}return 0;
}

畫展布置

算法：前綴和
觀察計算公式 需要用到的數皆為平方 提前處理 將每個數平方后 公式將被簡化為 每兩個數之間的差的和 貪心的思考 使得一組數相鄰兩個數之間差的和最小 數組有序為最優 先排序 排序后枚舉開始的位置?求當前位置到當前位置+m位置的差的和 使用前綴和預處理每個位置的前綴和查詢即可。

#include <bits/stdc++.h>
#define ll long long
ll a[100005],b[100005],c[100005];
using namespace std;
int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+1+n);for(int i=1;i<n;i++){b[i]=a[i+1]*a[i+1]-a[i]*a[i];}for(int i=1;i<n;i++){c[i]=c[i-1]+b[i];}ll ans=1e18;for(int i=1;i<=n-m+1;i++){ans=min(ans,c[i+m-2]-c[i-1]);}cout<<ans<<"\n";return 0;
}

水質檢測

算法：模擬

按題目要求模擬即可，唯一需要貪心的點，即為

#.
.#

的情況 從左往右判斷時 若要使它們聯通 最優的方案為

##
.#

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);string s[2];cin>>s[0]>>s[1];ll n=s[0].size();s[0]=" "+s[0];s[1]=" "+s[1];ll ans=0;ll l=0,r=0;for(int i=1;i<=n;i++){if((s[0][i]=='#' || s[1][i]=='#') && l==0){l=i;}if((s[0][i]=='#' || s[1][i]=='#')){r=i;}}ll cnt=-1;if(s[0][l]=='.' && s[1][l]=='#') cnt=1;if(s[1][l]=='.' && s[0][l]=='#') cnt=0;for(int i=l+1;i<=r;i++){if(s[0][i]=='.' && s[1][i]=='.'){ans++;}else if(s[0][i]=='#' && s[1][i]=='.'){if(cnt==1){cnt=-1;ans++;}else{cnt=0;}}else if(s[0][i]=='.' && s[1][i]=='#'){if(cnt==0){cnt=-1;ans++;}else{cnt=1;}}else{cnt=-1;}}cout<<ans<<"\n";return 0;
}

生產車間

算法：樹形DP/樹上DP

先考慮這道題 但沒考慮出來 開始蹭分

于是輸出根的權值獲得（洛谷50%）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[1005];
int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll n;cin>>n;ll ans=0;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<n;i++) {ll o,p;cin>>o>>p;}cout<<a[1];return 0;
}

裝修報價

方案1：DFS爆搜（30%分）

算法：DFS

為每兩個數字之間遍歷它們是否為異或。如果當前位置為異或，則提前計算，并儲存它們異或后的數字序列。 然后遍歷每個位置是‘+’還是‘-’并計算，加入答案。

#include <bits/stdc++.h>
#define ll long long
ll a[100005];
using namespace std;
const ll MOD = 1e9 + 7;
ll ans=0;ll n;
void dfs2(vector<ll> v){if(v.size()==1){ans+=v[0];ans%=MOD;return;}ll it=v[v.size()-1];v.pop_back();v[0]+=it;dfs2(v);v[0]-=it;v[0]-=it;dfs2(v);
}
void dfs(vector<ll> v,ll x){if(x>n) {dfs2(v);return;}v.push_back(a[x]);dfs(v,x+1);v.pop_back();if(v.size()){ll tp=v[v.size()-1];v[v.size()-1]^=a[x];dfs(v,x+1);v[v.size()-1];}
}
int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;vector<ll> d;ll now=0;for(int i=1;i<=n;i++){cin>>a[i];now^=a[i];}dfs(d,1);cout<<ans<<"\n";return 0;
}

方案2：數學 規律 打表（100%分）

時間復雜度：O(n)

每個數字后都存在‘+’和‘-’，無論之后的數字間填寫什么符號，結果都會被抵消，但從第一個位置異或到第i個位置的答案會保留（1<=i<=n）。

位置1異或到3 （1組）
0⊕2⊕5=7
位置1異或到2 （2組）位置3和它之后的都被抵消
0⊕2  +5=7
0⊕2  ?5=?3
位置1 （6組） 位置2和它之后的都被抵消
0  +2⊕5=7
0  ?2⊕5=?70  +2?5=?3
0  ?2+5=30  +2+5=7
0  ?2?5=?7

所以最后的結果為

第一個數字 1組

第一個數字異或到第二個數字 2組

第二個數字異或到第三個數字 6組

第三個數字異或到第四個數字 18組

從第n-1個數字前 每個位置的組數是后一個的三倍 依次遞增求和即可

#include <bits/stdc++.h>
#define ll long long
ll a[100005];
using namespace std;
const ll MOD = 1e9 + 7;
ll ans=0;ll n;
int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;vector<ll> d;ll now=0;for(int i=1;i<=n;i++){cin>>a[i];now^=a[i];}ll op=2;ans+=now;now^=a[n];ll tp=0;for(int i=n-1;i>=1;i--){ans+=now*op;ans%=MOD;now^=a[i];op*=3;op%=MOD;}ans%=MOD;ans+=MOD;ans%=MOD;cout<<ans<<"\n";return 0;
}