D5考试代码
2025-10-05 17:44:34
发布于：浙江
110阅读
0回复
0点赞
第一题 20分
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
int arr[200024];
vector<int>seq;
bool panduanhuiwen(){
int syz = seq.size();
for(int i=0;i< syz;i++){
if(seq[i] != seq[syz - i - 1]){//当前对应的位置回文匹配不上
return 0;
}
}
return 1;
}
bool panduanshengj(){
int syz = seq.size();
int mid = syz / 2;//找出中间位置
for(int i=mid;i< syz -1;i++){
if(seq[i] > seq[i+1]){
return false;
}
}
return 1;
}
string to__str(){
string s="";
int syz = seq.size();
for(int i=0;i<syz;i++){
s+=(char)seq[i]+'0';
}
//cout<<s<<endl;
return s;
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>arr[i];
}
int strlen = 0;
set<string>st;//定义一个set、用于去重
int num = 1<<n;//2^n
for(int i=1;i<num;i++){//0 无意义 第几种情况，并且二进制下1表示当前第i个数字被选取
seq.clear();
for(int j=0;j<n;j++){
if(i & (1<<j)){//判断当前的这一个位置是否要选取
//cout<<i<<" "<<j<<" :"<<(i & (1<<j))<<":";
seq.push_back(arr[j]);//选取了当前的这个数
}
}
// for(int j=0;j<seq.size();j++){
// cout<<seq[j]<<' ';
// }cout<<endl;
if(seq.size() < strlen)continue;//如果当前你选取来的长度小于最长长度
if(!panduanhuiwen())continue;//判断一下是否是回文数，如果不是的话那么跳过
if(!panduanshengj())continue;//判断一下当前是否是上升或者下降
if(seq.size() > strlen){ //当前你的这个长度大于保存的最长，清空之前的储存
strlen = seq.size();
st.clear();
}
st.insert(to__str());//转化为字符串
}
int syz = st.size() % MOD;
cout << strlen << " " << syz <<endl;
return 0;
}
第一题 100分
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
int arr[5555];
int h[5555];
int nxt[5555][5555],pre[5555][5555];//5000
pair<int,int> dp[5555][5555];//5000
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
h[i]=arr[i];
}
sort(h+1,h+1+n);//将所有的数排序一遍
//记录一下有多少个不同的数值
int cnt = unique(h+1,h+n+1) - (h+1);//去重
//将当前每个数区替换掉有序数组的第几个
for(int i=1;i<=n;i++){
arr[i] = lower_bound(h+1,h+cnt+1,arr[i]) - h;
}
memset(pre,-1,sizeof pre);
memset(nxt,-1,sizeof nxt);
// i从0到n+1，net[i][x] 表示，从(i,n]第一个数为x的下标
// pre[i][x] 表示 从[1,i),第一个数为x的下标
for(int i=0;i<=n+1;i++){
for(int j=i+1;j<=n;j++){
if(nxt[i][arr[j]] == -1){
nxt[i][arr[j]] = j;
}
}
for(int j=i-1;j>=1;j--){
if(pre[i][arr[j]] == -1){
pre[i][arr[j]] = j;
}
}
}
pair<int,int>syz,ans;
for(int i=n;i>=1;i--){
//自己本身组成一个
syz ={1,1};
dp[i][i]=syz;
ans={0,1};//ans为区间最佳
for(int j=i+1;j<=n;j++){
dp[i][j]={0,0};//初始化一下
if(arr[i]==arr[j]){//对于原有符合条件的情况左右都加上一个
dp[i][j]={ans.first+2,ans.second};
}
if(arr[i]>=arr[j]){
int ii=nxt[i][arr[j]];//找到在i之后第一个和a[j]相同位置
if(ii == -1)continue;//找不到
if(dp[ii][j].first > ans.first){//如果ii到j的状态更好
ans=dp[ii][j];
}
else if(dp[ii][j].first == ans.first){
//如果长度相同，合并方案数，重复的部分减去
int jj =pre[j][arr[j]];
if(jj != -1 && dp[ii][jj].first == dp[ii][j].first){
ans.second -= dp[ii][jj].second;
}
if(ans.second < 0 ){
ans.second += MOD;
}
ans.second += dp[ii][j].second;
ans.second %= MOD;
}
}
}
}
pair<int,int>aans;
aans = {0,0};
for(int i=1;i<=n;i++){
int l = nxt[0][i],r=pre[n+1][i];
if(l == -1 || r == -1)continue;
if(dp[l][r].first > aans.first){
aans = dp[l][r];
}else if(dp[l][r].first == aans.first){
aans.second += dp[l][r].second;
aans.second %= MOD;
}
}
cout<<aans.first<<" "<<aans.second<<endl;
return 0;
}
第二题 100分
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
long long a[N];
int main() {
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
int count=1;
for (int i=n-2;i>=0;i--){
if(a[i+1]-a[i]>k){
break;
}
count++;
}
cout<<count<<endl;
return 0;
}
第三题 20分
#include <bits/stdc++.h>
using namespace std;
int arr[1002];
int zhao4(long long x){
int w=0;
if(x==0) return 0;
while(x>0){
if(x%10==4)w++;
x/=10;
}
return w;
}
int main() {
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>arr[i];
}
long long ans=0;//储存答案
long long total = 1 << n;
for(int i=0;i<total;i++){
long long w=0;//总和
for(int j=0;j<n;j++){
if(i & (1<<j)){//第j位被选取
w+=arr[j];
}
}
ans+=zhao4(w);
}
cout<<ans<<endl;
return 0;
}
第三题 40分
#include <bits/stdc++.h>
using namespace std;
int arr[1002];
int zhao4(long long x){
int w=0;
if(x==0) return 0;
while(x>0){
if(x%10==4)w++;
x/=10;
}
return w;
}
int main() {
int n;
cin>>n;
int syzmax=0;
for(int i=0;i<n;i++){
cin>>arr[i];
syzmax=max(syzmax,arr[i]);
}
if(syzmax>1000){
long long ans=0;//储存答案
long long total = 1 << n;
for(int i=0;i<total;i++){
long long w=0;//总和
for(int j=0;j<n;j++){
if(i & (1<<j)){//第j位被选取
w+=arr[j];
}
}
ans+=zhao4(w);
}
cout<<ans<<endl;
}
else{
long long syz=n*1000;
vector<long long >dp(syz+1,0);
dp[0]=1;
//01背包
for(int i=0;i<n;i++){ // 当前第i个数
for(int s = syz;s>=arr[i];s--){// 所容纳最大的上限
dp[s]+=dp[s-arr[i]];
}
}
long long ans=0;
for(long long s=0;s<=syz;s++){
int syzz=zhao4(s);
ans+=dp[s] * syzz;//dp[s] 的数量已经当前s 能找几个4
}
cout<<ans<<endl;
}
return 0;
}
第三题 100分
#include <bits/stdc++.h>
using namespace std;
long long n;
long long arr[1002];
vector<pair<long long ,long long>>a,b,c[10],d[10];// 1.最低位未处理的部分的子集和 各个位置上的值 贡献了几个4
int syz666(int x,int y){
for(int i=1;i<y;i++){
x/=2;
}
x=x%2;
if(x==1)return 1;
else return 0;
}
void solve(long long *axx,int k,vector<pair<long long,long long>>&c){
for(int i=0;i<(1<<k);i++){
long long s=0;
for(int j=0;j<k;j++){
if(i & (1<<j)){ // syz666(i,j)
s+=axx[j];
}
}
c.push_back({s,0});
}
}
//最开始各位的时候，10^0 = 1 base基准值最开始为1
// 不发生进位：a[i].second + b[j].second < base
// i + j (mod 10) 产生4 i + j == 4 mod 10
// j == (4 - i) mod 10
// k1 == (14 - i) mod 10
// 要发生进位：
// a[i].second + b[j].second >= base
// i+j+1 (mod 10) 产生4 i + j + 1 == 4 mod 10
// j == (3 - i) mod 10
// k2 == (13 - i) mod 10
long long get_jin0(vector<pair<long long,long long>>&a,vector<pair<long long,long long>>&b,long long base){//没有进位出现4到可能
int point =b.size()-1;
long long ans=0;
for(int i=0;i<a.size();i++){
while(point>=0 && a[i].second + b[point].second >= base)point--;
ans+=(point+1);
}
return ans;
}
long long get_jin1(vector<pair<long long,long long>>&a,vector<pair<long long,long long>>&b,long long base){//进位为1出现当前位置为4到可能
int point =0;
long long ans=0;
long long siz=b.size();
for(int i=a.size()-1;i>=0;i--){
while(point<=siz-1 && a[i].second + b[point].second < base)point++;
ans+=(b.size()-point);
}
return ans;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>arr[i];
solve(arr+1,n/2,a);
solve(arr+1+n/2,n-n/2,b);
long long ans=0;
long long base=1;
for(int w=0;w<=8;w++){
for(int i=0;i<10;i++) c[i].clear(),d[i].clear();
//如果你的最低位是a[i].first%10,那么你还剩下没处理的部分为a[i].first/10
for(int i=0;i<a.size();i++) c[a[i].first%10].push_back({a[i].first/10,a[i].second});
for(int i=0;i<b.size();i++) d[b[i].first%10].push_back({b[i].first/10,b[i].second});
for(int i=0;i<10;i++){// 左半边和右半边的情况相加
int syz1 = (14 - i) % 10; // 当前位数的总和
int syz2 = (13 - i) % 10; // 后面有进位情况的
ans+=get_jin0(c[i],d[syz1],base) + get_jin1(c[i],d[syz2],base);
}
int now = 0;
for(int i=0;i<10;i++){
for(int j=0;j<c[i].size();j++){
a[now++] = {c[i][j].first,c[i][j].second + i*base};
}
}
now =0;
for(int i=0;i<10;i++){
for(int j=0;j<d[i].size();j++){
b[now++] = {d[i][j].first,d[i][j].second + i*base};
}
}
base *=10;// 基准值 * 10
}
cout<<ans<<endl;
return 0;
}
第四题 20分
#include<bits/stdc++.h>
using namespace std;
int a[5001];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
long long ans=0;
for(int b1=1;b1<=n-3;b1++){
for(int b2=b1+1;b2<=n-2;b2++){
for(int b3=b2+1;b3<=n-1;b3++){
for(int b4=b3+1;b4<=n;b4++){
if((a[b1]^a[b2]^a[b3]^a[b4]) == 0){
ans++;
}
}
}
}
}
cout<<ans<<endl;
return 0;
}
第四题 100分
#include<bits/stdc++.h>
using namespace std;
int a[5001],c[2000008];
// 4个数里面有两对是一模一样的
// b1 < b2 && b3 < b4
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
long long ans=0;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
ans+=c[a[i] ^ a[j]];
}
for(int j=1;j<i;j++){
c[a[i] ^ a[j]]++;
}
}
cout<<ans<<endl;
return 0;
}
有帮助，赞一个