Test - 2 20260211
Test - 2
A [CSP-J 2025] 拼数
先提取出字符串 \(s\) 中的所有数字，然后输出由这些数字能拼成的最大正整数。
解法1：\(O(|s|\log |s|)\)
将这些数字从大到小排序，然后依次输出即可。
string s;
cin>>s;
int len=s.size();
vector<int> vec;
for(int i=0;i<len;i++)
{
int x=s[i]-'0';
if(0<=x&&x<=9) vec.push_back(x);
}
sort(vec.begin(),vec.end());
reverse(vec.begin(),vec.end());
for(int &x:vec)
printf("%d",x);
puts("");
解法2：\(O(|s|)\)
由于提取出的数字范围为 \(0\to 9\)，可以考虑桶排序。
用 \(cnt[i]\) 做桶，统计数字 \(i\) 累计出现了几次，然后从大到小输出即可。
string s;
cin>>s;
int len=s.size();
for(int i=0;i<len;i++)
if('0'<=s[i]&&s[i]<='9') cnt[s[i]-'0']++;
for(int i=9;i>=0;i--)
for(int j=1;j<=cnt[i];j++)
printf("%d",i);
puts("");
B [CSP-J 2025] 座位
根据座位分布规律，不难发现需要分为两种情况：
- 该考生所在列是奇数列（从下往上排）还是偶数列（从上往下排）
先把成绩从高到低排序，需要额外存储成绩对应的学号，这里使用结构体。
struct node
{
int val,id;
}a[N*N];
bool mycmp(node x,node y)
{
return x.val>y.val;
}
scanf("%d%d",&n,&m);
for(int i=1;i<=n*m;i++)
{
int x;
scanf("%d",&x);
a[i]={x,i};
}
sort(a+1,a+1+n*m,mycmp);
for(int i=1;i<=n*m;i++)
{
if(a[i].id==1)
{
pos=i;
break;
}
}
先判断是否为某一列的末尾，再根据奇偶性确定行数。
int x=pos/n,y=pos%n;
if(!y) // 在某一列的末尾（实际在第x列）
{
if(x&1) printf("%d %d\n",x,n); // 奇数列，末尾为最后一行
else printf("%d %d\n",x,1); // 偶数列，末尾为第一行
}
else // 不在某一列的末尾（实际在第x+1列）
{
if((x+1)&1) printf("%d %d\n",x+1,y); // 奇数列，从上往下排
else printf("%d %d\n",x+1,n+1-y); // 偶数列，从下往上排
}
C [CSP-J 2025] 异或和
前缀和 + 异或运算
题单：第2单元 前缀和与差分
拿到题目可能没有什么思路，先看数据范围与特殊性质，拿走部分分。
特殊性质 A：测试点 \(1,3\)，\(10\) 分
特殊性质 A：对于所有 \(1\leq i\leq n\)，均有 \(a_i=1\)。
由数据范围表格可以发现，\(k\) 都等于 \(0\)。
根据异或运算，\(1\ xor\ 1=0\)，连续两个数当作一个区间，异或和为 \(0\)。
所以最多能分成 \(\lfloor n/2\rfloor\) 个区间，直接输出 \(n/2\)。
printf("%d",n/2);
特殊性质 B：测试点 \(1-5,13\)（包含 A），\(30\) 分
特殊性质 B：对于所有 \(1\leq i\leq n\)，均有 \(0\leq a_i\leq 1\)。
由数据范围表格可以发现，\(k\) 都小于等于 \(1\)。
分 \(k=0\) 和 \(k=1\) 两种情况。
- \(k=0\) 时，把每一个 \(0\) 当作一个单独的区间，剩下连续两个 \(1\) 成为一个区间
- \(k=1\) 时，同 特殊性质 A
if(k==0)
{
for(int i=1;i<=n;i++)
if(a[i]==0) ans++;
for(int i=1;i<=n;i++)
{
int cnt=0;
while(a[i]==1) cnt++,i++;
ans+=cnt/2;
}
printf("%d\n",ans);
}
else if(k==1)
{
for(int i=1;i<=n;i++)
if(a[i]==1) ans++;
printf("%d\n",ans);
}
测试点 \(1-14\)，\(70\) 分
考虑贪心，从左到右遍历，如果存在某个区间异或和为 \(0\)，区间数加一。详见代码。
int pos=1; // pos 表示上个区间的末尾+1（当前区间最早可以当作开头的位置）
for(int i=1;i<=n;i++) // 遍历整个序列，i为当前区间的末尾
{
bool flag=false; // 标记是否有以i为结尾的区间异或和为k
for(int j=pos;j<=i;j++) // 枚举区间开头j
{
int temp=0;
for(int k=j;k<=i;k++) // 求当前区间异或和
temp=temp^a[k];
if(temp==k)
{
flag=true;
break;
}
}
if(flag) pos=i+1,ans++; // 存在以i结尾的区间异或和为k，更新pos和答案
}
printf("%d\n",ans);
测试点 \(1-14,16\)，\(75\) 分
异或运算的一个性质：异或运算满足前缀和的性质。
参考普通前缀和，定义一个前缀和数组为 \(s[n]\)，令 \(s[i] = s[i-1]\ xor \ a[i]\)，则对于一个区间 \([l,r]\) 的异或和为 \(s[r]\ xor \ s[l-1]\)。主要利用了 \(a\ xor\ a = 0\) 的这一性质。
有了这个性质，就可以省去每次计算区间异或和的一维循环，降低时间复杂度。
for(int i=1;i<=n;i++)
s[i]=s[i-1]^a[i];
int pos=1;
for(int i=1;i<=n;i++)
{
bool flag=false;
for(int j=pos;j<=i;j++)
{
int temp=s[i]^s[j-1];
if(temp==k)
{
flag=true;
break;
}
}
if(flag) pos=i+1,ans++;
}
printf("%d\n",ans);
正解：
考虑异或运算的另一个性质：
若 \(a\ xor\ b=c\)，则 \(a\ xor\ c=b\)
这样就可以对中间处理序列异或和进一步优化。
原来我们要寻找一个区间开头 \(j\)，与区间结尾 \(j\) 配对，使 \(s[i]\ xor\ s[j-1]=k\)。
现在可以换个思路，对于区间结尾 \(j\)，判断是否存在 \(j\in[pos,i]\)，使 \(s[j-1]=s[i]\ xor \ k\)
引入新数组 \(f[i]\) 表示最后一次 前缀异或和等于 \(i\) 出现的位置。
memset(f,-1,sizeof(f)); // 将f数组初值赋为-1
int pos=0; f[0]=0; // 前0个数的异或和为0
for(int i=1;i<=n;i++)
{
int temp=k^s[i];
if(f[temp]>=pos)
{
ans++;
pos=i;
}
f[s[i]]=i;
}
printf("%d\n",ans);
D [CSP-J 2025] 多边形
测试点 \(15-20\)，\(24\) 分
注意到，测试点 \(15-20\) 满足一个特殊性质 \(\max_{i=1}^{n}a_i\leq1\)
又因为 对于所有 \(1\leq i \leq n\)，均有 \(1\leq a_i \leq 5000\)，所以 \(a_i\) 恒等于 \(1\)。
那么满足题意的方案数为 \(C_n^3+C_n^4+\dots+C_n^n\)
根据二项式定理，\(C_n^3+C_n^4+\dots+C_n^n = (1+1)^n-C_n^0-C_n^1-C_n^2=2^n-1-n-n\times (n-1)/2\)
测试点 \(15-20\) 可以解决了，实际上测试点 \(1,3\) 也能通过，可以得到 \(32\) 分。
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
long long cnt=1;
for(int i=1;i<=n;i++)
cnt=cnt*2%Mod;
cnt=(cnt-1-n-n*(n-1)/2+Mod)%Mod;
printf("%lld\n",cnt);
测试点 \(1-10\)，\(40\) 分
注意到 \(n\) 很小，可以考虑枚举所有情况。
对于每一根木棍，只有两种可能性：选与不选。
这里使用 \(\text{DFS}\) 枚举每一种情况，并统计最大值和长度和。
void dfs(int x,int sum,int maxn)
{
if(x==n+1)
{
if(sum>2*maxn) ans++;
return;
}
dfs(x+1,sum+a[x],max(maxn,a[x]));
dfs(x+1,sum,maxn);
}
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
dfs(1,0,0);
printf("%d\n",ans);
测试点 \(1-10,15-20\)，\(64\) 分
将前两种做法结合起来，就有 \(64\) 分了。
bool flag=true;
int n,a[N],ans;
void dfs(int x,int sum,int maxn)
{
if(x==n+1)
{
if(sum>2*maxn) ans++;
return;
}
dfs(x+1,sum+a[x],max(maxn,a[x]));
dfs(x+1,sum,maxn);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]!=1) flag=false;
}
if(flag)
{
long long cnt=1;
for(int i=1;i<=n;i++)
cnt=cnt*2%Mod;
cnt=(cnt-1-n-n*(n-1)/2+Mod)%Mod;
printf("%lld\n",cnt);
}
else
{
dfs(1,0,0);
printf("%d\n",ans);
}
return 0;
}
正解：
每种木棍只有选或不选，类似于 背包\(\text{DP}\)。
状态：\(f[i][j]\) 表示前 \(i\) 个木棍可以组成长度和为 \(j\) 的方案数
状态转移：\(f[i][j]=\sum f[i-1][j-a[i]]\)
对题意进行一些数学推导：$$\sum_{i=1}^{m} l_i > 2 \times \max_{i=1}^{m} l_i$$
假设我们在选出的一堆木棍中，最长的那根长度为 \(Max\)，其余所有木棍的长度之和为 \(Sum_{other}\)。
那么总长度 \(\sum l_i = Sum_{other} + Max\)，代入公式：
由于只需要涉及到 \(Sum_{other}\)，枚举到第 \(i\) 个木棍时，先统计答案，再加上当前木棍的长度。
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
m=max(m,a[i]);
}
sort(a+1,a+1+n);
f[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=a[i]+1;j<=m+1;j++) // 先统计答案
ans=(ans+f[j])%Mod;
for(int j=m+1;j>=m+1-a[i];j--) // 为了避免数组越界，大于m的情况都累积到m+1
f[m+1]=(f[m+1]+f[j])%Mod;
for(int j=m;j>=a[i];j--) // 倒序遍历优化01背包
f[j]=(f[j]+f[j-a[i]])%Mod;
}
printf("%d\n",ans);
E 高精度加法
模板题，参考 高精度计算 - OI Wiki，不做过多解释。
浙公网安备 33010602011771号