[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jTJrl643-1639543185683)(C:UsersADguyAppDataRoamingTyporatypora-user-images1639412660425.png)]
题意:
给出一串长度为 n n n 的序列,可以进行总次数不超过 3n 的 *** 作使得序列中的所有数都相等。
每次 *** 作选择三个数 i , j , x i,j,x i,j,x
使得 a i − = x × i , a j + = x × i a_i-=x times i,a_j+=x times i ai−=x×i,aj+=x×i
如果不行输出 − 1 -1 −1 ,否则输出 *** 作的数量和具体的方案(不要求最小化 *** 作数量)
心路历程:
阿巴阿巴,首先 *** 作看错了,以为是
a
j
+
=
x
×
j
a_j+=x times j
aj+=x×j ,我是fw()
然后发现每次 *** 作过后,序列的总和不变。也就是说,如果序列的总和一开始就不能整除 n n n 说明一定是非法情况。
然后就是漫长的挂机时间
后来看了题解明白了,因为 i = 1 i=1 i=1 的特殊性,可以很方便的分配数字,所以整个过程分两趟进行
- 把所有数字都移到 下标为 1 1 1 里面去
- 均匀分配这些数字,进行 n − 1 n-1 n−1 次 *** 作
假设要把 a i a_i ai 里面的数加到 a 1 a_1 a1 里面去。如果 i ∣ a i i mid a_i i∣ai ,那么就只需要一次 *** 作。否则的话,先利用 a 1 a_1 a1 分配给 a i a_i ai 一些数,使得 i ∣ a i i mid a_i i∣ai ,然后再进行一次 *** 作。
有思考过这样 a 1 a_1 a1 会不会产生不够用的情况,实际上是不会的。以 i = 2 i=2 i=2 为例,如果能整除直接加,因为题目规定 a 1 ≥ 1 a_1geq1 a1≥1,此时 a i ≥ 2 a_igeq2 ai≥2 ,对于 i = 3 i=3 i=3 的情况也能够应付 ;如果不能整除,那么 a 2 a_2 a2 需要加 1 1 1 ,也是够用的,然后就又是上面的情况。这样一直归纳下去可以发现 a 1 a_1 a1 的值是必然够用的。
这样最多 2 2 2 次 *** 作就能完成数字向 a 1 a_1 a1 的转移,再经过 1 1 1 次 *** 作就能把数字均匀的分配到当前位置上,满足了题意orz。
#includeusing namespace std; #define ll long long #define MAXN 10005 #define MAXM 200005 typedef pair pii; #define INF 0x3f3f3f3f int n; int a[MAXN]; int sum=0; struct node { int x,y,val; }; vector ans; void work(int x,int y,int val) { a[x]-=x*val; a[y]+=x*val; ans.push_back({x,y,val}); } void solve() { ans.clear(); sum=0; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; sum+=a[i]; } if(sum%n!=0) { cout<<-1< T; while(T--) { solve(); } return 0; }
貌似贪心是歪解
e a s y easy easy 版本是从一个长度为 n n n 的序列 a 1 , a 2 , a 3 , a 4 , . . . , a n a_1,a_2,a_3,a_4,...,a_n a1,a2,a3,a4,...,an 中任选 k k k 个数使得 a b 1 − a b 2 + a b 3 − . . . + ( − 1 ) k − 1 × a b k a_{b_1}-a_{b_2}+a_{b_3}-...+(-1)^{k-1}times a_{b_k} ab1−ab2+ab3−...+(−1)k−1×abk 最大。
呃呃呃,这是 e a s y easy easy 版本,可以用贪心, h a r d hard hard 版本貌似要用 d p dp dp 了。
首先可以想象取的点必然是波峰或者波谷,且波峰是用来加的,波谷是用来减得。因为如果加的数不是波峰,如果后面把这段的波峰加上说明多扣了一段。比如一段上升序列 1 2 3 4 5。如果加了 1 而且也要加 5,说明中间多扣了 2 3 4,而2 3 4 的绝对值是比1大的,说明这样不可取。
波谷也是同理。
然后把这些波峰波谷都push到vector里面。push的时候如果波峰未出现过则波谷也不能push,push完过后若发现最后的元素为波谷则直接忽略它或者 pop_back。
然后就是记录答案了阿巴阿巴,加波峰减波谷加波峰减波谷。
因为在判断波峰波谷的时候a[n+1]忘记清零了,导致莫名其妙多调了半小时,我真是个菜狗
#includeusing namespace std; #define ll long long #define MAXN 300005 #define MAXM 200005 typedef pair pii; #define INF 0x3f3f3f3f #define rep(i, x, y) for (int i = x; i <= y; i++) #define per(i, x, y) for (int i = x; i >= y; i--) ll read() { ll x = 0, f = 1; char ch; do { ch = getchar(); if (ch == '-') f = -1; } while (ch < '0' || ch > '9'); do { x = x * 10 + ch - 48; ch = getchar(); } while (ch >= '0' && ch <= '9'); return x * f; } ll n, q; ll a[MAXN]; void solve() { n = read(), q = read(); rep(i, 1, n) a[i] = read(); vector ans; a[n+1]=0;//万恶之源呜呜呜 rep(i, 1, n) { if (a[i] > a[i - 1] && a[i] > a[i + 1]) ans.emplace_back(a[i]); else if (a[i] < a[i - 1] && a[i] < a[i + 1] && ans.size() > 0) ans.emplace_back(a[i]); } ll res = 0; if (ans.size() % 2 == 1) { for (int i = 0; i < ans.size(); i++) { if (i & 1) res -= ans[i]; else res += ans[i]; } } else if (ans.size() % 2 == 0&&ans.size()>0) { for (int i = 0; i < ans.size() - 1; i++) { if (i & 1) res = ans[i]; else res += ans[i]; } } cout << res << endl; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T; T = read(); while (T--) { solve(); } return 0; }
阿巴阿巴,我觉得这样挺好的,每天互相发些题目,一是可以交流思路,二是可以相互监督。
os::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
T = read();
while (T–)
{
solve();
}
return 0;
}
阿巴阿巴,我觉得这样挺好的,每天互相发些题目,一是可以交流思路,二是可以相互监督。 睡觉去了,QAQ。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)