CodeTON Round 9 赛后解析：Div.1+Div.2 题目思路与实现
A 题
直接构造奇数序列即可。因为要求严格递增，且每个位置对模数运算后余数必须互异，我们从小开始贪心选取。
- 当 i=1 时，余数必为 0，最小符合的数是 1。
- 当 i=2 时，需要余数为 1，最小可行数为 3。
- 当 i=3 时，余数应为 2，最小数是 5。
归纳可得通项 ai = 2i-1。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=55;
int n;
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cout<<i*2-1<<' ';
cout<<'\n';
}
int main ()
{
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}
B 题
考虑子串数目 f(t) 为偶数的情况。按字符串长度分类：
- 长度 1：只有一个子串，不符。
- 长度 2：若两字符不同，则有 3 个子串；若相同则有 2 个不同子串，满足题意。
- 长度 3：仅当三个字符全部相同时有 6 个不同子串。
因此只需在原串中寻找三个互不相同的连续字符或两个相同的连续字符。只有形如 "ababab..." 的交替模式才没有符合条件的子串。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=1e5+5;
string s;
void solve()
{
cin>>s;
int n=s.size();
for(int i=0;i<n-2;i++)
if(s[i]!=s[i+1]&&s[i]!=s[i+2]&&s[i+1]!=s[i+2])
{
cout<<s[i]<<s[i+1]<<s[i+2]<<'\n';
return ;
}
for(int i=0;i<n-1;i++)
if(s[i]==s[i+1])
{
cout<<s[i]<<s[i+1]<<'\n';
return ;
}
cout<<-1<<'\n';
}
int main ()
{
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}
C1 题
核心性质：异或可看作不进位的加法。当 y > x 时，y ⊕ x 落在 [y-x, y+x] 区间内。
若 y > 2x，则 y ⊕ x > x，不可能是 x 的因子；且 y ⊕ x > y/2，又因 x ≥ 1 故 y ⊕ x ≠ y，所以也不是 y 的因子。因此只需枚举 y ∈ [1, min(2x, m)] 暴力判断即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=1;
int x;
ll m;
void solve()
{
cin>>x>>m;
ll n=1,cnt=0;
while(n<=x) n<<=1;
for(int y=1;y<=min(n-1,m);y++)
{
int t=x^y;
if(t==0) continue;
if(x%t==0||y%t==0) cnt++;
}
cout<<cnt<<'\n';
}
int main ()
{
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}
C2 题
通过打表可发现规律：小于 m 的 x 的倍数几乎都符合条件。设 t = x ⊕ y：
- 若 t 为 y 的倍数：当 y > x 时 t ∈ [y-x, y+x) 且 t ≠ y，最小倍数为 2y 超出上界，故只需考虑 y ≤ x，暴力枚举 y 判断。
- 若 t 为 x 的倍数：y = x ⊕ t ≤ x + t，因此 t ≤ m - x 时所有 x 的倍数均可行，但排除 t = x 时 y = 0 的情况；t = 0 时 y = x 会在另一分支计算。
- 区间 [m-x, m+x) 内最多有两个 x 的倍数，单独检查 y 是否在 (x, m] 范围内即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=1;
ll x,m;
void solve()
{
cin>>x>>m;
ll ans=0,t;
if(m>x)
{
ans+=max((m-x)/x-1,0ll);
t=m/x*x;
ll y=x^t;
if(y>x&&y<=m) ans++;
t+=x,y=x^t;
if(y>x&&y<=m) ans++;
}
for(int y=1;y<=min(x,m);y++)
{
t=x^y;
if(t%y==0) ans++;
}
cout<<ans<<'\n';
}
int main ()
{
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}
D 题
将条件转化：若 gcd(i,j) = i 即 i 整除 j，则要求 ai ≠ gcd(ai, aj)。
构造方法：将 s 数组从大到小排序后，从 1 到 n 枚举每个位置 i，用它所有倍数 j 来更新 aj = max(aj, ai + 1)。最终若某个 ai 超过 m 则无解；否则输出 s[ai]。
由于总枚举次数约 n log n，复杂度 O(n log n)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m;
int s[N],a[N];
bool cmp(int x,int y) { return x>y; }
void solve()
{
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>s[i];
sort(s+1,s+m+1,cmp);
for(int i=1;i<=n;i++) a[i]=0;
a[1]=1;
int mx=0;
for(int i=1;i<=n;i++)
for(int j=i*2;j<=n;j+=i)
{
a[j]=max(a[j],a[i]+1);
mx=max(mx,a[j]);
}
if(mx>m) { cout<<-1<<'\n'; return; }
for(int i=1;i<=n;i++) cout<<s[a[i]]<<' ';
cout<<'\n';
}
int main ()
{
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}
