題意：給n個數，把他分成0，1兩組，
f(x) = 每組內任意兩個數位和=T的對數
使f(0) + f(1) 最小
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int t,n,T;
int x,ans[maxn];
map<int,int> mp;
int main(){
ios::sync_with_stdio(0);
cin >> t;
while(t--){
mp.clear();
cin >> n >> T;
for(int i = 0; i < n; i++) {
cin >> x;
if(mp.count(T-x) == 1)
ans[i] = mp[T - x] ^ 1;
else ans[i] = 0;
mp[x] = ans[i];
}
for(int i = 0; i < n; i++){
if(i) cout << " " << ans[i];
else cout << ans[i];
}
cout << endl;
}
return 0;
}
題意：給n個數位,當長度分別為1,2…n的時候，公共的最小數位是幾，沒有-1
分析：
當長度越長的時候，這個數位越小
給的n個數位的範圍是1-n
假設長度為i的時候，最小的公共數位為x,然後擴充套件，看看其他的是否也是x
具體看程式碼吧
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
int t,n,arr[maxn],last[maxn],ans[maxn];
void Init(){
for(int i = 1; i <= n; i++){
arr[i] = last[i] = 0;
ans[i] = -1;
}
}
int main(){
ios::sync_with_stdio(0);
cin >> t;
while(t--){
cin >> n;
Init();
for(int i = 1; i <= n; i++){
int x;
cin >> x;
/*arr表示和上一個數位之間差著幾個數,
如果是1，說明相鄰 ,即長度為1的時候，是最小值 ，例如aa
是2的話，說明隔著1個數位，長度為2的時候符合,例如aba
以此類推...
*/
arr[x] = max(arr[x],i - last[x]);
last[x] = i;//記錄x的位置
}
for(int i = 1; i <= n; i++){
/*arr[i]已經是前半部分的分段的最小值了,
要滿足整個陣列,
所以考慮後半部分，後半部分也就是n - last[i] + 1*/
arr[i] = max(arr[i], n - last[i] + 1);
for(int j = arr[i];j <= n && ans[j] == -1;j++)
ans[j] = i;
}
for(int i = 1; i <= n; i++){
if(i != 1) cout << " ";
cout << ans[i];
}
cout << endl;
}
return 0;
}
分析：先把每個數位都加到1上，其他數位變為0；
然後再把1上的數位分到其他數位上
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 10;
int t,n;
long long a[maxn],sum;
int main(){
ios::sync_with_stdio(0);
cin >> t;
while(t--){
cin >> n;
sum = 0;
for(int i = 1; i <= n; i++){
cin >> a[i];
sum += a[i];
}
if(sum % n){
cout << "-1" << endl;
continue;
}
cout << 3 * n << endl;
for(int i = 1; i <= n; i++){
int x1 = (a[i] % i) ? (i - a[i] % i) : 0;
/*為什麼變化時,a[1]會是正的？
因為a[i] % i的資料範圍[1,i -1],，在上一步1相當於j的時候,a[j] = a[j] + i * x,
所以走這一步的時候，不會變成負的*/
cout << 1 << " " << i << " " << x1 << endl;//相當於把第二個數位變成i的倍數
cout << i << " " << 1 << " " << (a[i] + x1)/i << endl;//a[i] = a[i] - i * x; 此時a[i] = 0;
}
sum /= n;
for(int i = 1; i <= n; i++)
cout << 1 << " " << i << " " << sum << endl;
}
return 0;
}