题意:先给出n个数字,然后可以有m次操作,每次操作以数字对(x,y)表示最多能选x个数字把它变成y,问经历m次操作后n个数字和最大为多少?
解法:一个明显正确的做法是:用y尽量大的操作去改变数组,直到不能改变(产生负收益)为止。
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,m,a[N]; struct dat{ int x,y; bool operator < (const dat &rhs) const { return y>rhs.y; } }b[N]; int main() { cin>>n>>m; for (int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); for (int i=1;i<=m;i++) scanf("%d%d",&b[i].x,&b[i].y); sort(b+1,b+m+1); int nowa=1,nowb=1; while (nowa<=n && nowb<=m) { if (b[nowb].y<=a[nowa]) break; for (int i=1;i<=b[nowb].x;i++) { if (nowa>n) break; if (b[nowb].y<=a[nowa]) break; a[nowa]=b[nowb].y; nowa++; } nowb++; } long long ans=0; for (int i=1;i<=n;i++) ans+=(long long)a[i]; cout<<ans<<endl; return 0; }View Code
题意:给出n*m的表格,每次选k个,然后计算这k个格子任两个欧几里得距离和。算出以上所有不同方案答案距离总和。
解法:这题一看题目明显往算贡献方面想。选k个格子方案数是C(n,m),然后k个格子任两个欧几里得距离有C(k,2)对,那么每一对的距离是多少呢?我们注意到每一对的距离都可能不尽相同,但是题目要求计算的是任两对的距离,那么我们就可以考虑用总数*平均得到总和,这里有一个结论:任两个格子的平均欧几里得距离是(n+m)/3。那么答案就是:C(n*m,k)*C(k,2)*(n+m)/3。
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int P=1e9+7; const int N=2e5+10; int n,m,k; LL fac[N],inv[N]; LL power(LL x,LL p) { LL ret=1; for (;p;p>>=1) { if (p&1) ret=ret*x%P; x=x*x%P; } return ret; } void prework() { fac[0]=1; inv[0]=power(fac[0],P-2); for (int i=1;i<=200000;i++) { fac[i]=fac[i-1]*i%P; inv[i]=power(fac[i],P-2); } } LL C(LL n,LL m) { return fac[n]*inv[m]%P*inv[n-m]%P; } int main() { prework(); cin>>n>>m>>k; LL ans=C(n*m,k)%P*C(k,2)%P*(n+m)%P*power(3,P-2)%P; cout<<ans<<endl; return 0; }View Code
题意:每个给出操作或查询,操作是给出(a,b)然后f(x)=f(x)+|x-a|+b,查询是查询所有f(x)的最小值坐标x以及最小值f(x)。
解法:大但猜想最小值坐标是不是a的中位数,手动尝试几个(a,b)操作后发现确实是这样。那么这题就变成景经典的动态中位数问题了,用大根堆小根堆解法可以解决。
#include<bits/stdc++.h> using namespace std; typedef long long LL; priority_queue<int,vector<int>,greater<int> > q1; priority_queue<int> q2; LL sum,sum1,sum2; int main() { int n,m; cin>>m; while (m--) { int opt; scanf("%d",&opt); if (opt==1) { int x,y; scanf("%d%d",&x,&y); n++; sum+=y; q1.push(x); sum1+=x; while (!q1.empty() && !q2.empty() && q1.top()<q2.top()) { sum1-=q1.top(); sum1+=q2.top(); sum2-=q2.top(); sum2+=q1.top(); int t=q1.top(); q1.pop(); q1.push(q2.top()); q2.pop(); q2.push(t); } if (q1.size()-q2.size()>=2) sum1-=q1.top(),sum2+=q1.top(),q2.push(q1.top()),q1.pop(); } else { int mid; if (n%2) mid=q1.top(); else mid=q2.top(); LL ans=((LL)mid*(n/2)-sum2)+(sum1-(LL)mid*(n-n/2))+sum; printf("%d %lld\n",mid,ans); } } return 0; }View Code