Skip to content

_1

2025年

2月8日

牛客寒假4C

这是怎么想到的... 为什么我想不到呢。。。

我都没有想到过如果字符串的第一个和最后一个字符相同，那么 01 和 10 的数量一定相同。。。

这个怎么想到呢？？？

101010 像这样的，其实 01 和 10 的数量就会不一样，那么最后加一个 1 就能数量一样了，是可以发现是头尾是否相同才会影响，中间的字符是什么都是无所谓的。

所以如果第一个字符和最后一个字符相同，那么中间的每一个字符反转过来都是不影响结果的。好吧。。。

牛客寒假4D

老实说我真有点还是没看懂题解。。。

我们会先拿两个字符串直接匹配，然后看短的这个，我们需要多少次。这个数量记为 sum ，然后之后长的会多出一段来。

这一段可以两两之间进行匹配，剩单个就得额外花一次机会，这个数量记为 ans 。

如果 ans \(\le\) sum 那么可以调整位置使得这些要改的地方，可以一起改，所以需要操作的次数可以变成 ans 次。否则就是 \(ans+\frac{\lfloor sum-ans \rfloor}{2}\) 。。。

也是差不多理解了。。。

2月16日

1

CF1041C

确实水题，因为每一天都是相对独立的，所以直接贪心就行了。

C++
void solve()
{
    int n,m,d;
    cin>>n>>m>>d;
    d++;
    vector<pii>a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i].fi;
        a[i].se=i;
    }
    sort(ALL(a));
    dbg(a);
    set<pii>st;
    st.insert({a[1].fi,a[1].se});
    vi ans(n+1);
    ans[a[1].se]=1;
    int tot=1;
    for(int i=2;i<=n;i++){
        dbg(st);
        if(st.begin()->fi>a[i].fi-d){
            ans[a[i].se]=++tot;
            st.insert({a[i].fi,a[i].se});
        }else{
            // auto [x,y]=*st.lower_bound({a[i].fi-d,0});
            //哦哦是这里 上一行写错了 因为咱们这里是需要找第一个比a[i].fi-d小的数字。。。

            auto [x,y]=*prev(st.upper_bound({a[i].fi-d+1,0}));
            //注意这里得改成a[i].fi-d+1。。。 多注意，不然真的不好找出来如果看不了样例
            ans[a[i].se]=ans[y];
            st.erase({x,y});
            st.insert({a[i].fi,a[i].se});
        }
    }
    cout<<tot<<'\n';
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" \n"[i==n];
}

CF698B

甚至是一个洛谷蓝题，但是cf *1700。

但是这题约等于抄的题解。

C++
void solve()
{
    int n;
    cin>>n;

    vi p(n+1);
    int root=0;
    for(int i=1;i<=n;i++)
        cin>>p[i];
    for(int i=1;i<=n;i++){
        if(i==p[i]){
            root=i;
            break;
        }
    }
    vi q(p);
    vector<int>vis(n+1);
    int tot=0;
    auto dfs=[&](auto &&self,int u){
        if(vis[u]) return;
        vis[u]=tot;
        if(q[u]==u){
            if(root){
                q[u]=root;
            }else{
                root=u;
            }
            return;
        }
        if(vis[q[u]]){
            if(vis[q[u]]==tot){
                //成环了
                if(root){
                    q[u]=root;
                }else{
                    root=u;
                    q[u]=u;
                }
                return;
            }
        }
        self(self,q[u]);
    };
    for(int i=1;i<=n;i++){
        ++tot;
        dfs(dfs,i);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=q[i]!=p[i];
    }
    cout<<ans<<'\n';
    for(int i=1;i<=n;i++)
        cout<<q[i]<<" \n"[i==n];
}

就是直接DFS，如果走到环了，那么就需要把环上一点拆开，有根节点就连根，没有就选一个根节点。如果有一个它本来就是父节点为自身，那么要么让它做根节点，要么让它连到跟根节点。最后统计修改次数和输出方案也是非常的方便。

但是为什么vis要弄成int型，且要每次dfs都不一样的值呢。因为这是单向边，可能是其他方式访问过的点。

2月17日

CF691D

什么水题，直接DFS就过了。。。

CF1721D

最烧脑的一集。。。

我们是比较容易判断最高位能不能取到1的，只需要 \(c\) 数组全为 1 ，即 \(a\) 和 \(b\) 种这一位的 1 的个数刚好为 n 。但是后面的位却不能这样，因为你可能为了使下一位为1而使得高位的可以得到的1变成0。

假设当前的答案是 ans ，那么如果新的一位要选 1 ，那么

$(a_i \& x ) \oplus (b_i \& x)=x $ .

这样不会影响前面的位了，非常巧妙的一个位运算题啊。

C++
void solve()
{
    int n;
    cin>>n;
    vi a(n+1),b(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    // (ai&x)^(bi&x)=x
    int ans=0;
    auto check=[&](int x){
        vi v1,v2;
        for(int i=1;i<=n;i++)
            v1.push_back(a[i]&x);
        for(int i=1;i<=n;i++)
            v2.push_back(b[i]&x^x);
        sort(all(v1));
        sort(all(v2));
        return v1==v2;
    };
    for(int i=29;i>=0;i--){
        if(check(ans|(1<<i)))
            ans|=(1<<i);
    }
    cout<<ans<<'\n';
}

还是一个1800的题啊，下次遇到这种，还是很难写出来，但是无所谓，我写50个写80个。

CF1281B

不知道对了没，偶遇 queueforces ，拼尽全力无法战胜。

但是看着感觉应该不难。。。

WA了几次，但是这太简单吧。

C++
void solve()
{
    string s,c;
    cin>>s>>c;
    int n=sz(s);
    vi f(26);
    for(int i=0;i<n;i++)
        f[s[i]-'A']=i;
    if(s<c){
        cout<<s<<'\n';
        return;
    }
    vi suf(n);
    suf[n-1]=s[n-1]-'A';
    for(int i=n-2;i>=0;i--){
        suf[i]=min(suf[i+1],s[i]-'A');
    }
    //记录后缀的最小字母
    //否则s一定有一个字母比c大的，或者长度更长
    for(int i=0;i<min(sz(s),sz(c));i++){
        if(s[i]>c[i]){
            char ch=*min_element(s.begin()+i,s.end());
            swap(s[i],s[f[ch-'A']]);
            // cerr<<ch<<" "<<f[ch-'a']<<'\n';
            if(s<c)
                cout<<s<<'\n';
            else
                cout<<"---\n";
            return;
        }else{
            //等于的情况也可以交换
            if(suf[i]<s[i]-'A'){
                // cerr<<i<<" "<<suf[i]<<" "<<s[i]<<'\n';
                swap(s[i],s[f[suf[i]]]);
                cout<<s<<'\n';
                return;
            }
        }
    }
    cout<<"---\n";
}

讨论一下就行，这也能有1600。

洛谷P3371

因为CF刚才在queue，于是随手打个dijkstra，10分钟。

但是就突然发现我好像真忘记了怎么定义greater<>的优先队列了。。。

C++
void solve()
{
    int n,m,s;
    cin>>n>>m>>s;
    vector<vector<pii>>adj(n+1,vector<pii>());
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
    }
    vector<int>dis(n+1,(1LL<<31)-1);
    dis[s]=0;
    auto dij=[&](){
        priority_queue<pii>pq;
        pq.push({0,s});
        while(!pq.empty()){
            auto [dist,u]=pq.top();
            // cerr<<dist<<" "<<u<<'\n';
            dist=-dist;
            pq.pop();
            if(dist>dis[u]) continue;
            for(auto [v,w]:adj[u]){
                if(dis[u]+w<dis[v]){
                    dis[v]=dis[u]+w;
                    pq.push({-dis[v],v});
                }
            }
        }
    };
    dij();
    for(int i=1;i<=n;i++)
        cout<<dis[i]<<" \n"[i==n];
}

CF1619F

感觉好难的来着。。。

不是，看题解之后怎么这么简单。。。

因为 \(nk \le 2\cdot 10^5\) ，所以直接暴力就行了，用一个优先队列来存当前的状态，\(b_i\) 大的坐小桌子，\(b_i\) 小的坐大桌子。。。没想到实现这么简单。

C++
void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    vi b(n + 1);
    for (int i = 1; i <= k; i++) {
        priority_queue<pii> pq;
        for (int j = 1; j <= n; j++)
            pq.push({ b[j], j });
        for (int j = 1; j <= m - (n % m); j++) {
            cout << n / m << " ";
            for (int l = 1; l <= n / m; l++) {
                // assert(!pq.empty());
                auto x = pq.top().se;
                pq.pop();
                cout << x << " ";
            }
            cout << '\n';
        }
        for (int j = 1; j <= n % m; j++) {
            cout << n / m + 1 << " ";
            for (int l = 1; l <= n / m + 1; l++) {
                // assert(!pq.empty());

                auto x = pq.top().se;
                pq.pop();
                cout << x << " ";
                b[x]++;
            }
            cout << '\n';
        }
    }
    cout << '\n';
}