CF 673 div2 BCD
程序员文章站
2022-06-26 15:19:05
B. Two Arrays题意:给n个数,把他分成0,1两组,f(x) = 每组内任意两个数字和=T的对数使f(0) + f(1) 最小#include using namespace std;const int maxn = 1e5 + 10;int t,n,T;int x,ans[maxn];map mp;int main(){ios::sync_with_stdio(0);cin >> t;...
B. Two Arrays
题意:给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;
}
C. k-Amazing Numbers
题意:给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;
}
D. Make Them Equal
分析:先把每个数字都加到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;
}
本文地址:https://blog.csdn.net/xcfkaixin/article/details/108863840
推荐阅读
-
CF 673 div2 BCD
-
CF 135 DIV2 B Special Offer! Super Price 999 Bourles!
-
CF #261 Div2 D. Pashmak and Parmida's problem (离散化+逆序对+线段树)_html/css_WEB-ITnose
-
CF #269 DIV2 A,B,C,D_html/css_WEB-ITnose
-
CF #261 div2 D. Pashmak and Parmida's problem (树状数组
-
CF #261 Div2 D. Pashmak and Parmida's problem (离散化+逆序对+线段树)_html/css_WEB-ITnose
-
CF #261 div2 D. Pashmak and Parmida's problem (树状数组
-
CF 673 div2 BCD