题意:用\(k\)元钱最多可以购买多少件价格在\([l,r]\)的物品。
贪心,排序后按照在\([l,r]\)范围内价格从小到大的顺序取即可。
/* Author: EndlessK * Time: 2021-11-26 19:15:07 **/ #include<bits/stdc++.h> #define pb push_back #define ll long long #define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; const int maxn = 110; ll a[maxn]; int n; int main() { fast; int T; cin>>T; while(T--) { int l,r,k; cin>>n>>l>>r>>k; for(int i=1;i<=n;i++) { cin>>a[i]; } sort(a+1,a+n+1); ll sum=0; ll ans=0; for(int i=1;i<=n;i++) { if(a[i]>=l && a[i]<=r) { if(sum+a[i]<=k) sum+=a[i],ans++; } } cout<<ans<<'\n'; } return 0; }
题意:给出\(n\)个系数,在数轴上找\(n+1\)个点,使得\(\sum\limits_{i=1}^n2\cdot a_i \cdot |x_0-x_i|\)最小。
贪心,假定\(x_0\)处于\(0\),先将点按照系数从大到小排序,系数大的应当离的更近,顺序按照\(1\rightarrow-1\rightarrow2\rightarrow-2\)的顺序进行分配即可。
/* Author: EndlessK * Time: 2021-11-26 19:15:07 **/ #include<bits/stdc++.h> #define pb push_back #define ll long long #define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; const int maxn = 200010; int n; ll b[maxn]; struct node{ ll x; int idx; } a[maxn]; bool cmp(node a,node b) { return a.x>b.x; } int main() { fast; int T; cin>>T; while(T--) { ll tmp=1; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i].x; a[i].idx=i; } sort(a+1,a+n+1,cmp); b[0]=0; ll ans=0; for(int i=1;i<=n;i++) { b[a[i].idx]=tmp; ans+=abs(tmp)*a[i].x; if(tmp>0) tmp=-tmp; else tmp=-tmp+1; } cout<<2*ans<<'\n'; for(int i=0;i<=n;i++) { cout<<b[i]<<' '; } cout<<'\n'; } return 0; }
题意:\(n\)个数,给定\(m\)个区间的同或和,求出整个序列的\(coziness\)。
赛后看了思路懂了整个推导过程。
首先对于每一个序列而言,如果仅存在\(x\)和\(0\),那么只要\(x\)的个数不为\(0\),其\(coziness\)是不变的。
那么对于每一个二进制数位,其实我只需要知道这一位是否有\(1\)就可以知道答案。
同或和还有一个性质:两个区间的同或和进行或运算可以得到他们并集的同或和。根据这一点,加上题目中提到必然会遍及每一个元素,那么把给出的\(m\)个区间的同或和进行或运算即可得到\([1,n]\)的同或和\(x\)。
这样我们就可以假设\(x\)恰为第一个数(虽然不符合题目但不影响结果),这样结果就为\(x\cdot 2^{n-1}\),最后记得取模。
/* Author: EndlessK * Time: 2021-11-26 19:15:07 **/ #include <bits/stdc++.h> #define pb push_back #define ll long long #define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) using namespace std; const int maxn = 200010; const int mod = 1000000007; ll Pow(ll a, ll b) { if (b == 0) return 1; if (b % 2) return a * Pow(a, b - 1) % mod; ll tmp = Pow(a, b / 2); return tmp * tmp % mod; } int main() { fast; int T; cin >> T; while (T--) { int n, m; cin >> n >> m; ll l, r, x; ll sum = 0; for (int i = 1; i <= m; i++) { cin >> l >> r >> x; sum = (sum | x); } ll ans = 1; ans = Pow(2, n - 1) * sum % mod; cout << ans << '\n'; } return 0; }
D题补了,但是还没手推状态转移方程,之后来补。