C. Primitive Root
题意:问你满足:并且的有多少个?
思路:我们知道异或的性质:
由于,即
那么
根据上述性质:,则有:
即:
又因为,那么我们知道:
- 对于任意即都是满足条件的。(最大的都比m小了,那肯定是满足的了),这里有个
- 对于任意即都是不合法的。(最小的都比m大了)
- 对于是不确定是,需要手动判断。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1e9 + 7; const int N = 2e5 + 10;
int main() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); int t; cin>>t; while(t--) { ll p,m; cin>>p>>m; ll l = m/p-1+1,r = (m-2)/p+((m-2)%p!=0)+1; ll cnt = m/p; for(ll k = l;k <= r; k++) if(((k*p+1)^(p-1))<=m)cnt++; cout<<cnt<<"\n"; } return 0; }
|
G. Knapsack
题意:给你个物品,每个物品有相对应的价格和价值。你有元和次免费机会,并且每种物品只能买一次,问你最大价值。
思路:一开始想法的先做背包,然后贪心。不好写,而且复杂度很大。那么怎么去考虑呢?
我们注意到两个事情:
- 如果有两个物品,其中选择免费,而选择花钱。那么一定有
- 如果有两个物品,其中选择免费,而不选择。那么一定有
那么我们发现一个事情:一定存在一个分界点,使得的的前大选择去免费。
我们按照排序。先预处理出前的物品的前大。然后正常去背包(倒着做,因为是后缀),注意记录二维,因为后面要用。最后算答案就行了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
|
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1e9 + 7; const int N = 5e3 + 10;
struct node { ll w,v; }a[N];
bool cmp(node a,node b) { return a.w > b.w; } ll sum[N],f[5010][10010],pre[N]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); int n,W,k; cin>>n>>W>>k; for(int i = 1;i <= n; i++) { ll w,v; cin>>w>>v; a[i].w = w,a[i].v = v; }
sort(a+1,a+1+n,cmp); multiset<int>s; for(int i = 1;i <= n; i++) { int val = a[i].v; if(s.size()<k) { s.insert(val); pre[i] = pre[i-1] + val; } else if(s.size()==k && k != 0){ int t = *s.begin(); if(t < val) { s.erase(s.begin()); s.insert(val); pre[i] = pre[i-1] - t + val; } else pre[i] = pre[i-1]; } } ll ans = 0; for(int i = n;i >= 1; i--) { for(int j = 0;j <= W; j++) { f[n-i+1][j] = f[n-i][j]; if(j>=a[i].w) f[n-i+1][j] = max(f[n-i+1][j],f[n-i][j-a[i].w]+a[i].v); } } for(int j = k;j <= n; j++) { ans = max(ans,f[n-j][W]+pre[j]); }
cout<<ans<<"\n"; return 0; }
|