ABC469
2026-08-01 22:10:26
发布于：广东
29阅读
0回复
0点赞
C
@cjdst教我E！
高桥总是有个袋子，我们只需记录的个数与判断一下就行。
#include <bits/stdc++.h>
using namespace std;
namespace CZW
{
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
void init(){
// freopen("1.in","r",stdin);
// freopen("my.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
void Main()
{
int n;
cin>>n;
string s; cin>>s;
vec<int> a;
for (int i=0;i<n;++i) if (s[i]=='x') a.pb(i+1);
for (int k=1;k<=n;++k){
if (k<=(int)a.size()) cout<<a[k-1]<<endl;
else cout<<n<<endl;
}
}
}
int main()
{
CZW::init();
int Test = 1;
// cin >> Test;
while (Test--)
CZW::Main();
return 0;
}
D
比较神秘的题目，与肯定是之中一个，或者全部。
因为和选择是对称的，我们从分析：
注：我们称“自由”表示这个在场都出现过，反之为“固定”。
1.为自由，为自由：有个选择，有个选择，但两者有重复。
2.为自由，为固定：有个选择，方面在固定搭档中选的方案。
3.为固定，为固定：用求二者交集即可。
同理，这样就做完了。
#include <bits/stdc++.h>
using namespace std;
namespace CZW
{
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
using lb=long double;
constexpr lb eps=1e-9;
void init(){
// freopen("1.in","r",stdin);
// freopen("my.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
void Main()
{
int n,m; cin>>n>>m;
vec<int> a(m),b(m);
for (int i=0;i<m;++i) cin>>a[i]>>b[i];
auto chk=[&](int u,int v){
for (int i=0;i<m;++i){
if (a[i]!=u&&b[i]!=u&&a[i]!=v&&b[i]!=v){
return false;
}
}
return true;
};
auto get=[&](int x) -> vec<int>{
int k=-1;
for (int i=0;i<m;++i)
if (a[i]!=x&&b[i]!=x){
k=i;
break;
}
if (k==-1) return {-1};
vec<int> res;
if (chk(x,a[k])) res.pb(a[k]);
if (chk(x,b[k])) res.pb(b[k]);
return res;
};
vec<int> p1=get(a[0]),p2=get(b[0]);
if (!p1.empty()&&p1[0]==-1&&!p2.empty()&&p2[0]==-1){
cout<<2ll*n-3;
}else if (!p1.empty()&&p1[0]==-1){
ll ans=n-1;
for (int i:p2){
if (i!=a[0]) ++ans;
}
cout<<ans;
}else if (!p2.empty()&&p2[0]==-1){
ll ans=n-1;
for (int i:p1) if (i!=b[0]) ++ans;
cout<<ans;
}else{
set<pair<int,int>> ans;
for (int i:p1) ans.insert({min(a[0],i),max(a[0],i)});
for (int i:p2) ans.insert({min(b[0],i),max(b[0],i)});
cout<<ans.size();
}
}
}
int main()
{
CZW::init();
int Test = 1;
// cin >> Test;
while (Test--)
CZW::Main();
return 0;
}
E
不会
F
竟然是codeforces的原题？？！
先考虑减小无效边的情况，再考虑到连自己质数倍数一定最优（当然要自己手玩数据的），而且从编号大的往小的枚举一定不劣。
#include <bits/stdc++.h>
using namespace std;
namespace CZW
{
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
constexpr int N=1e7+5;
ll primes[700003],k;
bool isp[N];
void init(){
// freopen("1.in","r",stdin);
// freopen("my.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
for (int i=2;i<N;++i){
if (!isp[i]) primes[++k]=i;
for (int j=1;j<=k&&i*primes[j]<N;++j){
isp[i*primes[j]]=true;
if (i%primes[j]==0) break;
}
}
}
void Main()
{
int n;
cin>>n;
// vec<ll> a(n+1,0);
// for (int i=1;i<=n;++i) cin>>a[i];
vec<ll> fa(n+1,0);
for (int i=1;i<=n;++i) fa[i]=i;
auto find=[&](ll x)->ll{
while(x!=fa[x]) x=fa[x]=fa[fa[x]];
return x;
};
ll sum=0;
for (int i=n/2;i>=0;--i){
for (int j=1;j<=k&&i*primes[j]<=n;++j){
ll u=i,v=i*primes[j],val=i;
ll fu=find(u),fv=find(v);
if (fu!=fv){
fa[fu]=fv;
sum+=val;
}
}
}
cout<<sum;
}
}
int main()
{
CZW::init();
int Test = 1;
// cin >> Test;
while (Test--)
CZW::Main();
return 0;
}
接着看这道题，它加入了边权，这怎么办呢？
还是想去运用上道题的思路，显然找质数倍数肯定不行了，注意到这道题，我们可以考虑枚举边权底数，从大到小枚举一定不劣。枚举此底数的倍数，能连就尽量连，直至连通，这样我们就做完了。
时间复杂度为调和级数
#include <bits/stdc++.h>
using namespace std;
namespace CZW
{
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
void init(){
// freopen("1.in","r",stdin);
// freopen("my.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
void Main()
{
int n;
cin>>n;
vec<ll> a(n+1,0);
ll ma=0;
for (int i=1;i<=n;++i) cin>>a[i],ma=max(ma,a[i]);
vec<vec<int>> p(ma+1);
for (int i=1;i<=n;++i) p[a[i]].pb(i);
vec<int> fa(n+1,0),rk(n+1,0);
for (int i=1;i<=n;++i) fa[i]=i;
auto find=[&](int x)->int{
while(x!=fa[x]) x=fa[x]=fa[fa[x]];
return x;
};
auto merge=[&](int x,int y)->bool{
int fx=find(x),fy=find(y);
if (fx==fy) return false;
if (rk[fx]<rk[fy]) swap(fx,fy);
fa[fy]=fx;
if (rk[fx]==rk[fy]) ++rk[fx];
return true;
};
ll sum=0;
for (int d=ma;d>=1;--d){
int rt=-1;
for (int i=d;i<=ma;i+=d){
for (int idx:p[i]){
if (rt==-1){
rt=idx;
}else {
if (merge(rt,idx)){
sum+=d;
}
}
}
}
}//这段我觉得是可以剪枝的，你们可以试一下？
cout<<sum;
}
}
int main()
{
CZW::init();
int Test = 1;
// cin >> Test;
while (Test--)
CZW::Main();
return 0;
}
全部评论 9
考虑二分答案，判断是否有频率 且出现次数 的。
令
o的权值为 ，x的权值为 （其实权值设置为其它的也行，只要保证o比总为 即可），这样就转化成求总和 的最长子段。显然可以前缀最小值。。
赛时糖丸了排了一下序， 极限卡过了，还好不是老爷机（
2026-08-01 来自 浙江
1
有帮助，赞一个