2025年2月26日

VP ，昨晚没打。

Codeforces Round 1006 (Div. 3)¶

唉唉，有点菜了。

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

A¶

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

C++

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

我赛时写的有点唐。

C++

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¶

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

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

C++

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\) 。

C++

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 的代码。~~非常的简洁啊，我确实没想到这种正常的做法...~~

C++

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\) 小的数字的数量。

C++

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\) 是有限制的，且比较小。

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

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

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

C++

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也挺好写的。

C++

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

Codeforces Round 1006 (Div. 3)¶

A¶

B¶

C¶

D¶

E¶

F¶

G¶