2025年2月26日

VP ，昨晚没打。

Codeforces Round 1006 (Div. 3)¶

比赛链接: https://codeforces.com/contest/2072

唉唉，有点菜了。

上课vp的，F vp结束半小时才ac。每题都写太慢了。。。

A¶

$k$ 是正数或者负数是没有什么不一样的，所以直接让 $k$ 一直为正数就好了。然后其实就是直接输出 $\frac{k}{p}$ 向上取整就好了。

void solve() {
    int n,k,p;
    cin>>n>>k>>p;
    k=abs(k);
    int ans=(k-1)/p+1;
    if(k==0) ans=0;
    cout<<(ans>n?-1:ans)<<'\n'; 
}

我赛时写的有点唐。

void solve() {
    int n,k,p;
    cin>>n>>k>>p;
    if(!k) {
        cout<<"0\n";
        return;
    }
    int sum=0;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=p; j++) {
            if(sum<=k) break;
            sum--;
        }
        for(int j=1; j<=p; j++) {
            if(sum>=k) break;
            sum++;
        }
        if(sum==k){
            cout<<i<<"\n";
            return;
        }
    }
    cout<<"-1\n";
}

B¶

对于每一个 _ ，它的贡献是它前面的 _ 的数量乘它后面的 _ 的数量。我们可以简单的想到，把一个数拆成两个数，使得它们的乘积最大，那么这两个数一定是要尽量相等。

所以我们重新排列的字符串，肯定是 _ 全部放中间，前面后面的 - 各放一半。

void solve()
{
    int n;
    string s;
    cin>>n>>s;
    int x=count(s.begin(),s.end(),'_');
    if((n-x)&1){
        cout<<1LL*(n-x)/2*((n-x)/2+1)*x<<'\n';
    }else{
        cout<<1LL*(n-x)/2*(n-x)/2*x<<'\n';
    }
}

C¶

数组的 $MEX$ 如果要达到 $x$ 那么一定会有 $[0,x-1]$ 之间的每一个数字。由于数组 $a$ 按位或要等于 $x$ ，每个数字每一位只有在 $x$ 为 $1$ 的位才能为 $1$ 。

我们直接从 $[0,n]$ 开始尝试能不能把 $i$ 加入数组，如果不行，那么可以直接不用看后面的数了，因为数组里不可能有 $i$ 了，$MEX$ 只能为 $i$ ，就没必要看其他的数字了，如果可以就加入答案中。

在上一步循环结束后，我们添加的数字个数一定小于等于 $n$ 。如果小于 $n$ ，那么我们可以往里面放 $x$ ，这样它们按位或一定会等于 $x$ 。如果等于 $n$ ，那么需要检查它们按位或能不能等于 $x$ ，不行则把最大的一个数字换成 $x$ 。

void solve() {
    int n,x;
    cin>>n>>x;
    vector<int>ans;
    int now=0;
    for(int i=0; i<n; i++) {
        if((i|x)==x) ans.push_back(i);
        else break;
        now|=i;
    }
    while(ans.size()==n&&now!=x)
        ans.pop_back();
    if(ans.size()<n){
        while(ans.size()<n)
            ans.push_back(x);
        now|=x;
    }
    //assert(now==x);
    for(auto y:ans)
        cout<<y<<' ';
    cout<<'\n';
}

D¶

只能做一次操作，可以把一个数字 $a_l$ 移动到 $a_r$ 的后面，要使得操作之后，数组中的逆序对最少。

计算 $i$ 移动到 $j$ 会使逆序对增加/减少多少。然后 $i$ 移动到 $j+1$ , 是可以通过移动到 $j$ 的答案算出来的。

贴一下 jiangly 的代码。~~非常的简洁啊，我确实没想到这种正常的做法...~~

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    int sum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            sum += (a[i] < a[j]);
        }
    }

    int ans = sum;
    int l = 0, r = 0;
    for (int i = 0; i < n; i++) {
        int cur = sum;
        for (int j = i + 1; j < n; j++) {
            cur -= (a[i] > a[j]);
            cur += (a[i] < a[j]);
            if (cur < ans) {
                ans = cur;
                l = i;
                r = j;
            }
        }
    }
    std::cout << l + 1 << " " << r + 1 << "\n";
}

我这做法太麻烦了。

由于数据很小，可以直接枚举每一对可能的交换，然后计算最大的贡献。把 $a_l$ 移动到 $a_r$ 的后面，会让答案减去 $[l+1,r]$ 之间小于 $a_l$ 的数字的数量，加上 $[l+1,r]$ 之间大于 $a_l$ 的数字的数量。

计算每一个区间的贡献，然后选出使答案减少最多的。

可以用前缀和预处理出每个前缀比 $i$ 小的数字的数量。

constexpr int N = 2000;

void solve() {
    int n;
    cin>>n;
    vector<int>a(n+1);
    vector<vector<int>>cnt(n+1,vector<int>(N+1)),tnc(n+1,vector<int>(N+1));
    for(int i=1; i<=n; i++) {
        cin>>a[i];
        cnt[i]=cnt[i-1];
        tnc[i]=tnc[i-1];
        for(int j=a[i]+1; j<=N; j++)
            cnt[i][j]++;//前面的比它小的数字
        for(int j=1; j<a[i]; j++)
            tnc[i][j]++;
    }
    auto calc=[&](int i,int j) {
        int res=0;
        res+=tnc[j][a[i]]-tnc[i][a[i]];//[i,j]之间的比a[i]大的数字
        res-=cnt[j][a[i]]-cnt[i][a[i]];
        return res;
    };
    vector<array<int,3>>ans;
    for(int i=1; i<=n; i++) {
        for(int j=i+1; j<=n; j++) {
            ans.push_back({i,j,calc(i,j)});
        }
    }
    sort(ans.begin(),ans.end(),[](array<int,3>x,array<int,3>y) {
        return x[2]<y[2];
    });
    if(ans.empty()||ans[0][2]>0)
        cout<<"1 1\n";
    else
        cout<<ans[0][0]<<" "<<ans[0][1]<<'\n';
}

E¶

稍微推一下或者想一下就能发现，满足条件的点对一定是 $x$ 相同或者 $y$ 相同。但是注意 $n$ 是有限制的，且比较小。

所以我们需要让有的水平的线上点尽量的多。

但是之后的也要考虑不要和它们横坐标或纵坐标相同。

其实可以递归，感觉会比较好看。

void solve()
{
    int k;
    cin>>k;
    if(!k){
        cout<<"0\n";
        return;
    }
    int X=1,Y=1;
    vector<pair<int,int>>ans;
    auto work=[&](int cnt){
        int sum=1;
        int x=2;
        ans.push_back({X,++Y});
        ans.push_back({X,++Y});
        while(sum+x<cnt){
            sum+=x;
            x++;
            ans.push_back({X,++Y});
        }
        ++X,Y+=2;
        return sum;
    };
    int now=0;
    while(now<k){
        now+=work(k-now);
    }
    cout<<ans.size()<<'\n';
    for(auto it:ans)
        cout<<it.first<<" "<<it.second<<'\n';
}

F¶

直接打表找规律，发现大小为2，4，8，16这些的三角形，都是由三个大小为它们二分之一的三角形拼成的，中间部分都是0。

然后就可以直接DFS了，当然还有其他很简单的方法，但是DFS也挺好写的。

int val;
vector<int>dfs(int k)
{
    if(k==1){
        return {0,val};
    }
    vector<int>res(k+1);
    int x=k-(1<<__lg(k));
    if(!x) x=k>>1;
    vector<int>nxt=dfs(x);
    for(int i=1;i<=x;i++)
        res[i]=nxt[i];
    auto it=nxt.rbegin();
    for(int i=k,j=x;i>=k-x+1;i--,j--)
        res[i]=nxt[j];
    return res;
}
void solve()
{
//  vector<vector<char>>a(100,vector<char>(100));
//  for(int i=1;i<=99;i++)
//      for(int j=1;j<=i;j++){
//          if(j==1||j==i) a[i][j]='k';
//          else{
//              if(a[i-1][j-1]==a[i-1][j])
//                  a[i][j]='0';
//              else
//                  a[i][j]='k';
//          }
//          cout<<a[i][j]<<" \n"[j==i];
//      }
    //every triangle consists of 3 small one ,and the center part are all 0
    //for example,if n=7:
    //size 8 triangle consists of 3 4-size triangle
    //so the problem is to find 3-size trangle
    //*
    //** so k0k k0k 0 k0k
    int k;
    cin>>k>>val;
    vector<int>res=dfs(k);
    for(int i=1;i<=k;i++)
        cout<<res[i]<<" \n"[i==k];
}

G¶

对于 $p\le \sqrt n$ 的部分，直接求解。

对于 $\sqrt n < p \le n$ 的部分， $n$ 的 $p$ 进制有且仅有2位数字。

低位是 $n$ mod $p$ = $n-p \cdot \lfloor \frac{n}{p} \rfloor $ , 高位是 $\lfloor\frac{n}{p}\rfloor$ .

此时 $rev(n,p) = $ $p(n-p\cdot \lfloor \frac{n}{p} \rfloor)+\lfloor\frac{n}{p}\rfloor=pn-p^2\lfloor\frac{n}{p}\rfloor+\lfloor\frac{n}{p}\rfloor$

对于 $i$ ，最后一个满足 $\lfloor\frac{n}{j}\rfloor= $ $\lfloor\frac{n}{i}\rfloor$ 的 $j$ 是 $\lfloor \frac{n}{\lfloor\frac{n}{i}\rfloor} \rfloor$ .

因为当 $\lfloor\frac{n}{i}\rfloor=k$ 时， $k \le \lfloor\frac{n}{i}\rfloor < k+1 $ ，可以变形为 $\frac {n}{k+1} < i \le \frac{n}{k}$ ，所以满足条件的最大整数即为 $\lfloor \frac{n}{k} \rfloor$ .

那么 $[i,j]$ 这一段的 $\lfloor\frac{n}{p}\rfloor$ 都是相等的。

整了好久样例都不对，然后看了眼题目发现mod取错了。。。。

#include <bits/stdc++.h>
using namespace std;

// #define int long long
constexpr int N = 3e5;
// constexpr int mod = 998244353;
constexpr int mod = 1e9 + 7;
//六百六十六 mod 取错了。。。

vector<long long> s1(N + 1);

void solve()
{
    int n;
    long long k;
    cin >> n >> k;
    // pn-p*p*(n/p)+n/p
    long long ans = 0;
    if (k > n) {
        ans += ((k - n) % mod) * n % mod;
        k = n;
    }
    for (int i = 2; i <= k; i++) {
        if (1LL * i * i <= n) {
            vector<int> v;
            int x = n;
            while (x) {
                v.push_back(x % i);
                x /= i;
            }
            for (auto j : v)
                x = x * i + j;
            ans = (ans + x) % mod;
        } else {
            int L = i;
            auto calc = [](int l, int r) {
                return 1LL * (r - l + 1) * (l + r) / 2 % mod;
            };
            while (L <= k) {
                int R = n / (n / L);
                if (R > k)
                    R = k;
                ans = (ans - ((s1[R] - s1[L - 1]) % mod) * (n / L) % mod) % mod;
                ans = (ans + 1LL * calc(L, R) * n % mod) % mod;
                ans = (ans + 1LL * (R - L + 1) * (n / L) % mod) % mod;
                ans = (ans + mod) % mod;

                L = R + 1;
            }
            break;
        }
    }
    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    for (int i = 1; i <= N; i++)
        s1[i] = (s1[i - 1] + 1LL * i * i % mod) % mod;
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}