前言，第一次正規的寫題解，不喜勿噴

T1 舞蹈機器?(dance)

題目

題意

在?個擁有?限??的?維平?的原點處，有?個舞蹈機器?，這個機器?將在這個平?上跳舞。
這個機器?每次可以向??的前?移動?個單位的?度，由于它需要在移動的過程中跳舞，因此，舞蹈機器?每移動?次，就必須向左或右?向旋轉 ，即如果此次機器?往或下?向進?了?次移動，那么，下?次就只能往左或右?向進??次移動。最開始時，它可以選擇上下左右四個?向中的任意?個作為初始?向。現在，機器?根據上述規則?共移動了s步，請問，機器?最終可以到達多少個不同的終點？機器?到達終點時的?向可以忽略。

輸入與輸出

輸入

597

輸出

179400

思路

首先想到暴力（也就是DFS），通過暴力，制作一個二維的bool數組，第k步設為1，其余為0。
然后遍歷這個數組，ans記錄可能位置。
但很明顯，這個方法它超時了。我們要采取更優化的方法，這能數學求解。
對于機器?的移動??，因為第?次移動的?向必須是在第?次的基礎上進?旋轉，所以對于整個機器?的移動過程??，每兩次移動就相當于是在正?形的對?線上移動了?次（即斜著?了?步），也就是每兩步一個周期。
因此奇（qi）數步的思路為(1+(n+1)/2)*(n+1)
偶數則為(n/2+1)*(n/2+1)
時間復雜度僅為O(1).

代碼

#include<bits/stdc++.h>
using namespace std;
int main() {
//	freopen("dance.in","r",stdin);考試不加會G掉的 
//	freopen("dance.out","r",stdout);
	long long n;//十年OI一場空，不開_______見祖宗
	cin>>n;
	if(n%2==1) cout<<(1+(n+1)/2)*(n+1)<<'\n';//如思路
	else cout<<(n/2+1)*(n/2+1)<<'\n';
}

T2 劃分(partition)

題目

思路

· 30pts
暴?搜索劃分?案即可
· 60pts 使用一個動態規劃維護
· 80pts 發現手玩一定是n/2
. 100pts思路
注意到?個關鍵性質gcd(a+b,c)>=gcd(a,b,c)。
證明是容易的，設d=gcd(a,b,c) ，那么d|(a+b) ，于是gcd(a+b,c)>=gcd(a,b,c)肯定成?。
這個性質說明最優劃分?定只會劃分為兩段，否則將相鄰的兩段合并起來?定更優。
于是滾?個前綴和，暴?枚舉分割點即可

代碼

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e18;
int t,n;
vector<int> s(n + 1);
int main() {
	cin>>t;
	while (t--) {
		cin>>n;
		for (int i=1;i<=n;i++) {
			cin>>s[i];
			s[i]+=s[i-1];
		}
		int ans=0;
		for(int i=1;i<=n;i++) {
			ans=max(ans,gcd(a[i],a[n]-a[i]));
		}
		cout<<ans<<'\n'
	}
}