XP03B - day03
2026-08-04 20:59:50
发布于：广东
93阅读
0回复
0点赞
考试 T2
#include<bits/stdc++.h>
using namespace std;
string a, b;
char ans[25];
int cnt[10], n;
bool ok=false;
void dfs(int pos,bool tight){
if(ok)return;
if(pos==n){
ok=true;
return;
}
int up=tight?b[pos]-'0':9;
for(int d=up;d>=0;d--){
if(cnt[d]==0)continue;
if(pos==0&&d==0)continue;
cnt[d]--;
ans[pos]=char('0'+d);
dfs(pos+1,tight&&d==up);
// 已经找到答案，不再回溯
if(ok)return;
// 当前数字不能得到合法答案，撤销选择
cnt[d]++;
}
}
int main() {
cin >> a >> b;
if (a.size() < b.size()) {
sort(a.begin(), a.end(), greater<char>());
cout << a << '\n';
return 0;
}
n = a.size();
for (char c : a) cnt[c - '0']++;
dfs(0, true);
for (int i = 0; i < n; i++) cout << ans[i];
return 0;
}
#include<bits/stdc++.h>
using namespace std;
string a,b;
int cnt[10];
int main(){
cin>>a>>b;
if(a.size()<b.size()){
sort(a.begin(),a.end(),greater<char>());
cout<<a<<'\n';
return 0;
}
if(a.size()>b.size()){
cout<<-1;
return 0;
}
for(char c:a)cnt[c-'0']++;
string ans="";
int n=b.size();
// 前k个数字和b完全相同
for(int k=0;k<=n;k++){
int sum[10];
for(int i=0;i<=9;i++)sum[i]=cnt[i];
bool ok=true;
string now="";
// 前k位和b相同
for(int i=0;i<k;i++){
int x=b[i]-'0';
if(sum[x]<=0){
ok=false;
break;
}
sum[x]--;
now+=b[i];
}
// 前k位都无法组成，后面更长的前缀也无法组成
if(!ok)break;
// k==n，说明可以直接组成b
if(k==n){
ans=b;
break;
}
// 第k位选择一个比b[k]小的最大数字
int x=-1;
for(int i=b[k]-'0'-1;i>=0;i--){
// 第一位不能是0
if(k==0&&i==0&&n>1)continue;
if(sum[i]>0){
x=i;
sum[i]--;
break;
}
}
// 当前第k位无法选得更小
if(x==-1)continue;
now+=char('0'+x);
for(int i=9;i>=0;i--){
while(sum[i]>0){
now+=char('0'+i);
sum[i]--;
}
}
ans=now;
}
if(ans=="")cout<<-1;
else cout<<ans;
return 0;
}
考试 T5
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
const int INF=1e9;
int n,m,sx,sy,ex,ey;
char g[N][N];
int d[N][N];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
struct node{
int x,y;
};
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>g[i][j];
d[i][j]=INF;
if(g[i][j]=='S'){
sx=i;
sy=j;
}
if(g[i][j]=='T'){
ex=i;
ey=j;
}
}
}
deque<node> q;
d[sx][sy]=0;
q.push_front({sx,sy});
while(q.size()){
node u=q.front();
q.pop_front();
int x=u.x;
int y=u.y;
// 普通移动，代价为0
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<1||nx>n||ny<1||ny>m)continue;
if(g[nx][ny]=='#')continue;
if(d[nx][ny]>d[x][y]){
d[nx][ny]=d[x][y];
q.push_front({nx,ny});
}
}
for(int nx=x-2;nx<=x+2;nx++){
for(int ny=y-2;ny<=y+2;ny++){
if(nx<1||nx>n||ny<1||ny>m)continue;
if(g[nx][ny]=='#')continue;
if(d[nx][ny]>d[x][y]+1){
d[nx][ny]=d[x][y]+1;
q.push_back({nx,ny});
}
}
}
}
if(d[ex][ey]==INF)cout<<-1;
else cout<<d[ex][ey];
return 0;
}
考试T4
松弛 + 普通队列 错误代码
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,m,sx,sy,ex,ey;
int h[N][N];
int d[N][N];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
struct node{
int x,y;
};
int main(){
cin>>n>>m;
int mx=0;
// 最小值最大
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>h[i][j];
cin>>sx>>sy>>ex>>ey;
queue<node> q;
q.push({sx,sy});
d[sx][sy] = h[sx][sy];
while(q.size()){
int x = q.front().x,y = q.front().y;
q.pop();
for(int i=0;i<4;i++){
int nx = x+dx[i];
int ny = y+dy[i];
if(nx<1 || nx>n || ny<1 || ny>m)continue;
if(d[nx][ny] < min(d[x][y],h[nx][ny])){
d[nx][ny] = min(d[x][y],h[nx][ny]);
q.push({nx,ny});
}
}
}
cout<<d[ex][ey]-1;
return 0;
}
考试T5
01DFS
二进制枚举
// 递归
// 状态压缩 动态规划 二进制枚举
// 4
// 1 2 2 4
// 0000
// 0001
// 0010
// 0011
// 0100
// ...
// 1111
// 0 - 2^4 - 1
// i 十进制
// i = 7 0111
// 第0物品选
// 第1物品选
// 第2物品选
// 第3物品不选
// 枚举二进制i每一位是否是 1/0
#include<bits/stdc++.h>
using namespace std;
int n;
int a[13];
// 第u个魔力水晶，sum 是魔力水晶总和
int ans = 0;
bool isprime(int x){
if(x<=1)return false;
for(int i=2;i<=x/i;i++){
if(x%i==0)return false;
}
return true;
}
int main(){
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
//考虑每个魔力水晶的情况
// 选/不选
for(int i=0;i<(1<<n);i++){
int sum = 0;
for(int j=0;j<n;j++){
if(i>>j&1){
sum+=a[j];
}
}
if(isprime(sum))ans++;
}
cout<<ans;
return 0;
}
斐波那契记忆化
#include<bits/stdc++.h>
using namespace std;
int n;
long long f[51];
long long dfs(int x){
//之前已经算过了
if(f[x])return f[x];
//答案存储一下
f[x] = dfs(x-1)+dfs(x-2);
return f[x];
}
int main(){
cin>>n;
f[1] = f[2] = 1;
cout<<dfs(n);
return 0;
}
滑雪暴力做法
#include<bits/stdc++.h>
using namespace std;
int g[110][110];
int n,m,mx,sum;
int dx[] = {0,0,1,-1};//x的偏移量
int dy[] = {1,-1,0,0};//y的偏移量
void dfs(int x,int y,int d){
sum = max(sum,d);
for(int i=0;i<4;i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx<1 || nx>n || ny<1 || ny>m)continue;
if(g[nx][ny]>=g[x][y])continue;
dfs(nx,ny,d+1);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>g[i][j];
//枚举每个点作为起点，dfs
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
sum = 0;
dfs(i,j,1);
mx = max(sum,mx);
}
}
cout<<mx;
return 0;
}
滑雪记忆化方法
#include<bits/stdc++.h>
using namespace std;
int g[110][110];
int dist[110][110];
int n,m,mx;
int dx[] = {0,0,1,-1};//x的偏移量
int dy[] = {1,-1,0,0};//y的偏移量
//求(x,y)作为起点的最远滑雪路径长度
int dfs(int x,int y){
if(dist[x][y])return dist[x][y];
dist[x][y] = 1;
for(int i=0;i<4;i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx<1 || nx>n || ny<1 || ny>m)continue;
if(g[nx][ny]>=g[x][y])continue;
dist[x][y] = max(dist[x][y], dfs(nx,ny)+1);
}
return dist[x][y];
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>g[i][j];
//枚举每个点作为起点，dfs
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dfs(i,j);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
mx = max(mx,dist[i][j]);
}
}
cout<<mx;
return 0;
}
双端队列
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
long long g[N][N];
bool vis[N][N];
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
struct node{
int x,y;
};
bool check(long long k){
memset(vis,0,sizeof(vis));
queue<node> q;
q.push({1,1});
vis[1][1]=true;
while(q.size()){
node u=q.front();
q.pop();
int x=u.x;
int y=u.y;
if(x==n&&y==m){
return true;
}
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<1||nx>n||ny<1||ny>m)continue;
if(vis[nx][ny])continue;
long long w=abs(g[nx][ny]-g[x][y]);
if(w>k)continue;
vis[nx][ny]=true;
q.push({nx,ny});
}
}
return false;
}
int main(){
cin>>n>>m;
long long mn=4e18;
long long mx=-4e18;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>g[i][j];
mn=min(mn,g[i][j]);
mx=max(mx,g[i][j]);
}
}
long long l=0;
long long r=mx-mn;
long long ans=r;
while(l<=r){
long long mid=(l+r)>>1;
if(check(mid)){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
cout<<ans;
return 0;
}
有帮助，赞一个