cf集合***

当周cf集合，我也不知道是不是当周的了，麻了，下下周争取写到e补f

C. Kevin and Puzzle（999）

题解：一眼动态规划，但是具体这个状态应该如何传递呢？

关键点：撒谎的人不相邻，

于是，就有以下两种情况

如果前一个不是liar，那么当前这个人和前一个人的a[i]都一定相同，满足a[i]==a[i-1]，则可以状态转移

前一个人是liar，那么当前这个人和前一个的前一个人一定不是liar，满足a[i]==a[i-2]+1，则可以状态转移

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int n,m;
vector<int>a;
void solve() {
    cin>>n;
    a.clear();
    int dp[n+10];
    memset(dp,0,sizeof dp);
    a.push_back(0);
    for(int i=0;i<n;i++) {
        int x;
        cin>>x;
        a.push_back(x);
    }
    dp[0]=1;
    for(int i=1;i<=n;i++) {
        if(a[i]==a[i-1]) dp[i]+=dp[i-1];
        if(a[i]==a[i-2]+1) dp[i]+=dp[i-2];
        dp[i]%=mod;
    }
    cout<<(dp[n]+dp[n-1])%mod<<endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

D. Kevin and Numbers（999）

题解：

突破点：a中(abs(x-y)<=1)可以合并 == b中所有数都可以拆成x/2+(x-x/2)

b中不需要拆分的元素就是与a共有的元素,其余数都需要拆分，且拆分的过程和结果一定，用优先队列对a,b从大到小拆分，每次拆b中最大且a中没有的元素可保证b的拆分是必要的

所以逆向思维很重要<_>

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int n,m;
map<int,int>ma;
map<int,int>mb;
bool com() {
    for(auto it=ma.begin();it!=ma.end();it++) {
        if(mb.find(it->first)!=mb.end()) {
            int num=min(it->second,mb[it->first]);
            it->second-=num;
            mb[it->first]-=num;
        }
    }
    priority_queue<int,vector<int>,less<int> >p;
    priority_queue<int,vector<int>,less<int> >q;
    for(auto it=ma.begin();it!=ma.end();it++) {
        while(it->second!=0) {
            p.push(it->first);
            it->second--;
        }
    }
    for(auto it=mb.begin();it!=mb.end();it++) {
        while(it->second!=0) {
            q.push(it->first);
            it->second--;
        }
    }
    while(q.size()) {
        if(!q.size()||!p.size()||q.size()>p.size()) {
            break;
        }
        //cout<<q.top()<<" "<<p.top()<<endl;
        if(q.top()==p.top()) {
            q.pop();
            p.pop();
        }
        else if(q.top()>p.top()) {
            int temp=q.top();
            q.pop();
            q.push(temp/2);
            q.push(temp-temp/2);
        }
        else {
            return false;
        }
    }
    if(q.size()||p.size()) return false;
    return true;
}
void solve() {
    cin>>n>>m;
    ma.clear();
    mb.clear();
    for(int i=0;i<n;i++) {
        int x;
        cin>>x;
        ma[x]++;
    }
    for(int j=0;j<m;j++) {
        int x;
        cin>>x;
        mb[x]++;
    }
    if(com()) {
        cout<<"YES"<<endl;
    }
    else {
        cout<<"NO"<<endl;
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

E. Kevin and And（999）

 题解：贪心的思路，每一个数可以更新cnt<m次，我们可以通过二进制枚举算出进行k次操作的最大贡献，对于单个 i，操作的收益是单调减的，因此可以用堆维护这个操作过程。

其次，这个题reminded me of BD202401（简单版）

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int n,m;
int k;
#define PII pair<int,int>
vector<int>a;
vector<int>b;
int c[1<<11];
int s[100010][12];
int num[100010];
void solve() {
    cin>>n>>m;
    cin>>k;
    a.clear();
    b.clear();
    //memset(num,0,sizeof(num));
    //memset(s,0,sizeof(s));
    for(int i=0;i<n;i++) {
        int x;cin>>x;
        a.push_back(x);
    }
    for(int i=0;i<m;i++) {
        int x;cin>>x;
        b.push_back(x);
    }
    for(int i=0;i<1<<m;i++) {//二进制枚举1-m次操作
        c[i]=(1<<30)-1;
        for(int j=0;j<m;j++) {
            if(i>>j&1) c[i]&=b[j];
        }
    }
    priority_queue<PII,vector<PII>,less<PII> > q;
    int ans=0;
    for(int i=0;i<n;i++) {//s[i][k]表示a[i]进行k次操作的最大贡献
        for(int j=0;j<=m;j++) {s[i][j]=0;}
        for(int j=0;j<1<<m;j++) {
            int k=__builtin_popcount(j);
            s[i][k]=max(s[i][k],a[i]-(a[i]&c[j]));
        }
        ans+=a[i];
        num[i]=0;
    }
    for(int i=0;i<n;i++) {
        q.push({s[i][1],i});
    }
    while(k--) {//每次操作保证是最大贡献
        int p=q.top().second;
        ans-=q.top().first;
        q.pop();
        ++num[p];
        if(num[p]<m) {
            q.push({s[p][num[p]+1]-s[p][num[p]],p});
        }
    }
    cout<<ans<<endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

E. Divisor Paths(ECR85)

思路：不愧是2200的题，对于我来说，确实是有点难的，相关很多知识点，单独拎一个出来，我都要思考好久

这个题，按照常规思路先建图，再求最短路数量（废话），但是，我们发现无论是空间还是时间都不够我们建图，所以我们考虑直接找最短路

最新学的一种思维方式，先列重点

1.y/x必须为素数

2.每走一条边都是增加或者减少一个质因子，边权也就是增加或者减少的因子个数，于是我们可以推测出：x→y的最优路径一定是x→gcd(x,y)→y （相反我认为也可以走最小公倍数（错的），但是质因子就不一定在D里面了，cf评论区有相关的证明）

因为这样能保证减少或增加的质因子是其他所有方案减少或增加的质因子的子集，那么显然减少或增加的因数个数是最少的。

x→gcd(x,y)这个过程中因数个数是在减少的，所以删去质因子的顺序可随意排列

gcd(x,y)→y 这个过程中同上

所以我们可以先分解D的因子，然后将x/gcd(x,y)进行质因数分解，因为x,gcd(x,y)都是D的因子，所以可以直接用D的质因子试，我们只需要知道x/gcd(x,y)​质因数分解出的质因子个数cnt即可（在这里提醒一下，我们要求的是方案数，所以最短路是多少是不需要计算的）

最后将x→gcd(x,y)以及gcd(x,y)→x的路径数相乘即可

（实际上这个题补完，我都不知道要怎么去写我的题解，我也有点懵）

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int n,m;
#define PII pair<int,int>
const int mod = 998244353;
int f[N];
int inv[N];
vector<int>p;
int qpow(int a,int b) {
    int res=1;
    while(b) {
        if(b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
void init(int n) {
    f[0]=1;
    for(int i = 1; i <= n; i++) {
        f[i]=f[i-1]*i%mod;
    }
    inv[n] = qpow(f[n], mod - 2);
    for (int i = n; i; --i) {
        inv[i - 1] =  inv[i] * i % mod;//阶乘的逆元
    }
}
int get(int x) {
    int z = 1,tot=0;
    for(int i=0;i<p.size();i++) {
        int cnt=0;
        while(x%p[i]==0) x/=p[i],cnt++;//这里是组合数学，很细节了，没想到就wa吧
        z=z*inv[cnt]%mod;
        tot+=cnt;
    }

    return z*f[tot]%mod;
}
void solve() {
    cin>>n;
    init(210);
    int tmp = n;
    for(int i=2; i* i <= n; i++ ) {
        if(tmp % i == 0) {
            p.push_back(i);
        }
        while(tmp % i == 0) tmp/=i;
    }
    if(tmp > 1) p.push_back(tmp);//巧妙求质因数集合

    cin >> m;
    while( m-- ) {
        int  x, y;
        cin >> x>> y;
        int g = gcd (x,y);
        cout << get(x / g) *get(y / g) % mod << "\n";
    }

}
signed main() {
    int t=1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D. Game With Triangles（1000）

思路：用g(p,q)表示面积和吗，可得kmax

由于f(k)=max(g(x,k-x)) 

• 2x+k−x=x+k≤n⟷x≤n−k;
• x+2(k−x)=2k−x≤m⟷x≥2k−m;
• x≥0;
• k−x≥0⟷x≤k.
• 所以x的范围：max(0,2k−m)≤x≤min(k,n−k)

用两个前缀和统计两个面积最大值，由于f(k)的函数是一个凸函数，所以用三分求出最大值区间

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int k;
const int N=1e5+10;
#define PII pair<int,int>
vector<int>a;
vector<int>b;
int asum[N];
int bsum[N];
void solve() {
    cin>>n>>m;
    for(int i=0;i<n;i++) {
        int x;
        cin>>x;
        a.push_back(x);
    }
    for(int i=0;i<m;i++) {
        int x;
        cin>>x;
        b.push_back(x);
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    asum[0]=0;
    bsum[0]=0;
    for(int i=1;i<=n;i++)asum[i]=asum[i-1]+(a[n-i]-a[i-1]);
    for(int i=1;i<=m;i++)bsum[i]=bsum[i-1]+(b[m-i]-b[i-1]);
    vector<int >ans;
    for(int i=1;2*i-m<=n-i;i++)
    {
        int L=max((int)0,2*i-m),R=min(i,n-i);
        if(L>R)break;
        auto f=[&](int ka){return asum[ka]+bsum[i-ka];};
        while(R-L>3)
        {
            int mL=(L*2+R)/3,mR=(L+R*2)/3;
            if(f(mL)>f(mR))R=mR;
            else L=mL;
        }
        int mans=0;
        for(int i=L;i<=R;i++)
        {
            mans=max(mans,f(i));
        }
        ans.push_back(mans);
    }
    int kmax=(int)size(ans)-1;
    cout<<kmax<<"\n";
    for(int i=1;i<=kmax;i++)cout<<ans[i]<<" \n"[i==kmax];
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

E. Graph Composition（998）

题解：

1.并查集。我们用fu,gu表示点u在两个图所在的集合。首先如果(u,v)∈f，并且g（u）≠g（v），那么这条边一定要删，g（u）≠g（v），在f中添加这条边；然后在枚举g的集合，如果v∈g并且v∉f,添加这条边

从无向图转换成集合，能够直接联想到并查集（但是我没有想到）

2.dfs。

代码：

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
int n,m,k;
const int N=2e5+10;
vector<PII>a;
vector<PII>b;
int f1[N];
int f2[N];
void solve() {
    cin>>n>>m>>k;
    a.clear();
    b.clear();
    for(int i=0;i<=n;i++) f1[i] = i,f2[i] = i;

    function<int(int)> find1 =[&](int x)->int {
        return  x == f1[x] ? x : f1[x] = find1(f1[x]);
    };
    function<int(int)> find2 =[&](int x)->int {
        return  x == f2[x] ? x : f2[x] = find2(f2[x]);
    };
    for(int i=0;i<m;i++) {
        int x,y;
        cin>>x>>y;
        a.push_back({x,y});
    }
    for(int i=0;i<k;i++) {
        int x,y;
        cin>>x>>y;
        f2[find2(x)]=find2(y);
        b.push_back({x,y});
    }
    int ans=0;
    for(auto [x,y]:a) {
       // cout<<find1(x)<<" "<<find2(y)<<endl;
        if(find2(x) != find2(y)) {
            ans++;
        }
        else {
            f1[find1(x)]=find1(y);
        }
    }
    map<int,vector<int>>mp;

    for(int i=1;i<=n;i++) {
        mp[find2(i)].push_back(i);
    }
    for(int i=1;i<=n;i++) {
        for(auto & x:mp[i]) {
            if(find1(x) != find1(i)) {
                ans++;
                f1[find1(x)]=find1(i);
            }
        }
    }
    cout << ans << endl;


}
int main() {
    int _=1;
    cin>>_;
    while (_--) {
        solve();
    }
    return 0;
}

B. Find the Permutation(997)

题解：我是万万没想到哈，我居然这题能写不出来，真是一天比一天菜了

代码：

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<string> g(n);
    for(auto &i : g) {
        cin >> i;
    }
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(),
    [&](int x, int y) {
        if(g[x][y] == '1') return x < y;
        else return x > y;
    });
    for(auto i : p) cout << i + 1 << " "; cout << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
    cin >> ttt;
    while(ttt--) {
        solve();
    }
}

C. Palindromic Subsequences（997）

题解：构造，赛时没想出来，蠢

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m;
#define PII pair<int,int>

int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n ;
        cout << 1<<" "<<1 <<" ";
        for(int i = 3;i <= n-1;i += 1) cout<< i <<" ";
        cout << 1 << endl;
    }
    return 0;
}