The 2023 ICPC Asia Nanjing Regional Contest CG

C. Primitive Root

题意：问你满足：\(g\le m\)并且\(g⊕(p-1)≡1(\bmod p)\)的\(g\)有多少个？

思路：我们知道异或的性质：\(a-b\le a⊕b \le a+b\)

由于\(g⊕(p-1)≡1(\bmod p)\)，即\(g⊕(p-1) = kp+1\)

那么\(g = (kp+1)⊕(p-1)\)

根据上述性质：\(a-b\le a⊕b \le a+b\),则有：\((kp+1)-(p-1)\le g \le (kp+1)+(p-1)\)

即：\(p(k-1)+2\le g \le p(k+1)\)

又因为\(g\le m\)，那么我们知道：

• 对于任意\(p(k+1)\le m\)即\(k\le \lfloor m/p\rfloor-1\)都是满足条件的。(最大的都比m小了，那肯定是满足的了),这里有\(m/p\)个 \((0～(m/p-1))\)
• 对于任意\(p(k-1)+2>m\)即\(k>\lceil(m-2)/p\rceil+1\)都是不合法的。(最小的都比m大了)
• 对于\(k\in[\lfloor m/p\rfloor-1+1,\lceil(m-2)/p\rceil+1]\)是不确定是，需要手动判断。

// 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

题意：给你\(n\)个物品，每个物品有相对应的价格\(w\)和价值\(v\)。你有\(W\)元和\(k\)次免费机会，并且每种物品只能买一次，问你最大价值。

思路：一开始想法的先做\(01\)背包，然后贪心。不好写，而且复杂度很大。那么怎么去考虑呢？

我们注意到两个事情：

• 如果有两个物品\(a,b\)，其中\(a\)选择免费，而\(b\)选择花钱。那么一定有\(w[a]\ge w[b]\)
• 如果有两个物品\(a,b\)，其中\(a\)选择免费，而\(b\)不选择。那么一定有\(v[a]\ge v[b]\)

那么我们发现一个事情：一定存在一个分界点\(M\),使得\(i\le M\)的\(val\)的前\(k\)大选择去免费。

我们按照\(w\)排序。先预处理出前\(i\)的物品的\(val\)前\(k\)大。然后正常去\(01\)背包(倒着做，因为是后缀)，注意记录二维，因为后面要用。最后算答案就行了。

// 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;
}