2023 ICPC 南京 CG

Nannan Lv5

The 2023 ICPC Asia Nanjing Regional Contest CG

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
// AC one more times
// nndbk
#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
// AC one more times
// nndbk
#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;
}

  • Title: 2023 ICPC 南京 CG
  • Author: Nannan
  • Created at : 2023-11-27 22:37:00
  • Updated at : 2024-09-30 17:13:40
  • Link: https://redefine.ohevan.com/2023/11/27/2023 ICPC 南京/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments