2025牛客寒假算法基础集训营5（补题）

C 小L的位运算

        显然，如果两次反置的价格小于等于交换的价格，那么直接全部反置就好了。

        反之，由于交换一定低于两次反置，我们尽可能用交换来消去不正确的位置。不正确的位置类型只有00，01，10，11，我们发现，交换任意两个不同类型的某一位，一定可以使得这两个位置正确。那么我们要做的就是尽量使其两两配对，循环O（n）的时间复杂度就能解决。

        

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e6+7;
int n, m, k;
// int a[N];
// bool v[N];void sovle()
{cin>>n>>m>>k;string a,b,c;cin>>a>>b>>c;vector<int>v(4);for(int i=0;i<n;i++){if(c[i]=='1'&&a[i]==b[i]||c[i]=='0'&&a[i]!=b[i]){v[(a[i]-'0')*2+(b[i]-'0')]++;}}if(2*m<=k){cout<<m*(v[0]+v[1]+v[2]+v[3])<<endl;return;}else{int sum=0;sort(v.begin(),v.end());for(int i=0;i<v[0];i++){int u=max(v[1],max(v[2],v[3]));if(u==v[1]) v[1]--;else if(u==v[2]) v[2]--;else v[3]--;sum+=k;}for(int i=0;i<v[1];i++){int u=max(v[2],v[3]);if(u==v[2]) v[2]--;else v[3]--;sum+=k;}sum+=v[2]*k+(v[3]-v[2])*m;cout<<sum<<endl;}
}signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int ING = 1;// cin>>ING;while (ING--){sovle();}return 0;
}

L 小L的构造

        构造，打表找规律

        

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e6+7;
int n, m, k;
// int a[N];
// bool v[N];void sovle()
{cin>>n;if(n<4){cout<<0<<endl;}else if(n%6<=2){int x=1,y=2,z=4,xx=3,yy=5,zz=6;cout<<n/3<<endl;for(int i=0;i<n/6;i++){cout<<x+i*6<<" "<<y+i*6<<" "<<z+i*6<<endl;cout<<xx+i*6<<' '<<yy+i*6<<' '<<zz+i*6<<endl;}}else{if(n==4||n==5){cout<<1<<endl;cout<<1<<" "<<2<<' '<<4<<endl;return;}cout<<n/3<<endl;cout<<1<<" "<<2<<' '<<4<<endl;cout<<3<<' '<<5<<' '<<9<<endl;cout<<6<<' '<<7<<' '<<8<<endl;int x=10,y=11,z=14,xx=12,yy=13,zz=15;for(int i=0;i<n/3-3;i++){if(i%2==0){cout<<x+i/2*6<<' '<<y+i/2*6<<' '<<z+i/2*6<<endl;}else cout<<xx+i/2*6<<' '<<yy+i/2*6<<' '<<zz+i/2*6<<endl;}}
}signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int ING = 1;cin>>ING;while (ING--){sovle();}return 0;
}