日常训练(2021.11.15)

A - Lucky Numbers

题目：

思路：

将所有的可能性分成三种情况：

1.当前位数是奇数—>进位输出偶数长度数值最小的那个数

2.当前位数是偶数&&找不到比它大的幸运数字—>进两位找它在该长度数值最小的数

3.当前位数是偶数&&能找到该长度上数值恰好大于它的幸运数字—>输出该幸运数字的值

如何找该长度上能否找到恰好大于它的幸运数字：

1.记录位数下还有多少个4和7需要被填入

2.搜索从最高位出发，每一位与填入的数字与给定的字符串进行比较，判断哪些数字可以被填入

3.特判，如果某一位数字上的数字满足幸运数字的条件且比原来的大，那就不需要继续搜索了，直接贪心输出后续的最小值即可

代码：

#include<iostream>
#include<cstring>

using namespace std;
char strA[100005] = {'\0'};
char strRes[100005] = {'\0'};
int len = 0;

bool dfs(int nowIndex, int sum4, int sum7, bool isU){
    if(nowIndex >= len) return true;//表示能找到
    if(isU == true){
        for(int i = 0; i < sum4; i++){
            strRes[nowIndex + i] = '4';
        }
        for(int i = 0; i < sum7; i++){
            strRes[nowIndex + sum4 + i] = '7';
        }
        return true;
    }
    // 先向下探 找到合适的数字在在往前填入  
    if(strA[nowIndex] <= '4' && sum4){
        if(dfs(nowIndex + 1, sum4 - 1, sum7, strA[nowIndex] < '4'))
        {
            strRes[nowIndex] = '4';
            return true;
        }
    }
    if(strA[nowIndex] <= '7' && sum7){
        if(dfs(nowIndex + 1, sum4, sum7 - 1, strA[nowIndex] < '7'))
        {
            strRes[nowIndex] = '7';
            return true;
        }
    }
    return false;
}


int main() {
    cin>>strA;
    len = strlen(strA);//找到字符串长度
    if((len % 2 == 1) || !dfs(0,len / 2, len / 2, false)) 
    {
        // 奇数或者是同位数不能找到比原数大的数了 
        if(len % 2 == 1) len++;//如果是奇数
        else len += 2;//如果是偶数且同位数中无法找到
        for(int i = 0; i < len / 2; i++) {//遍历输出
            strRes[i] = '4';
            strRes[i + (len / 2)] = '7';
        }
    }

cout<<strRes;
    return 0;
}

B - The Meeting Place Cannot Be Changed

题目：

思路：

一、二分查找判断答案，通过维持一个左边最大右边最小的框，若发现存在框外的区间，则直接报错，否则返回true

ps:若是使用数组对每个点染色，判断哪些点被经过n次，会因为循环次数太多而超时

二、可以遍历枚举所有点，暴力计算所有人到达该点的最大时间，找最小的时间即可

代码:

#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<set>

#define INF 0x3f3f3f3f
#define mod 1000000007
#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;
typedef unsigned long long ull;
typedef long long ll;
const int N=60005,M=1e7+5;
const double DInf=1e20;
const double eps=1e-8;
int n;
int maxpoint;
struct student
{
    int point;
    int v;
}a[N];
int cnt[N];
bool canmeet(double time)
{
    double left,right;
    for(int i=1;i<=n;i++)
    {
        if(i==1)
        {
            right = a[i].point + a[i].v*time;
            left =a[i].point - a[i].v*time;
        }
        else 
        { 
             double ri =a[i].point + time*a[i].v;
             double le =a[i].point - time*a[i].v;
             if( le > right || ri < left )
             {
                return false;
             }
            left = max(le ,left);     // 维持最大的左边 值 
            right = min(right, ri);   // 维持最小的右边 值 
        }
    }
    return true;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].point);
        maxpoint=max(maxpoint,a[i].point);
    }
    for(int i=1;i<=n;i++)scanf("%d",&a[i].v);
    double l=0,r=1e9;
    while(r-l>1e-6)
    {
        double mid=(l+r)/2.0;
        if(canmeet(mid))r=mid;
        else l=mid;
    }
    printf("%.12llf",r);
    return 0;
}

C - Xenia and Weights

题目：

思路：

模拟搜索题目：

对于每次放置：

①记录上次放置的位置

②记录上次放置的重量

③判断这次放置的重量能否是这边的总重量最大

④记录每次放置的重量是多少

代码：

#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<set>

#define INF 0x3f3f3f3f
#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;
typedef unsigned long long ull;
typedef long long ll;
const int N=3e3+5,M=1e7+5;
const double DInf=1e20;
const double eps=1e-8;
int target;
string s;
int q[N],idx;
bool dfs(int cnt,int l,int r,bool flag,int pre)
{
    if(cnt==target)
    {
        return true;
    }
    for(int i=0;i<=9;i++)
    {   
        if(s[i]=='0')continue;
        if(pre==i+1)continue; 
        if(flag)
        {
            int t=l+i+1;
            if(t<=r)continue;
            q[idx++]=i+1;
            if(dfs(cnt+1,t,r,false,i+1))return true;
            idx--;
        }
        else
        {
            int t=r+i+1;
            if(t<=l)continue;
            q[idx++]=i+1;
            if(dfs(cnt+1,l,t,true,i+1))return true;
            idx--;
        }
    }
    return false;
}

int main()
{
    cin>>s;
    cin>>target;
    if(dfs(0,0,0,true,-1))cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    for(int i=0;i<idx;i++)
    {
        printf("%d ",q[i]);
    }
    return 0;
}

D - k-Tree

题目：

思路：

一开始以为是搜索专场，所以没有往别的算法上想，写了一个搜索，过到第五个点超时了，然后一直往剪枝的方向想，结果导致这个题目没过。

考下来翻题解，才发现这是一道多重背包求方案数的题目（草），其实挺明显的，可惜还是练得少了

代码（超时的搜索）：

#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<set>

#define INF 0x3f3f3f3f
#define mod 1000000007
#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;
typedef unsigned long long ull;
typedef long long ll;
const int N=3e3+5,M=1e7+5;
const double DInf=1e20;
const double eps=1e-8;
int n,k,d;

ll dfs(int ans,int cnt,bool flag)
{
    if(!flag&&ans+d>n)return 0;
    if(ans==n&&flag)return 1;
    if(!flag&&ans+d==n)return 1;
    ll res=0;
    for(int i=k;i>=1;i--)
    {

if(ans+i<=n)
        {
            if(i>=d)res+=dfs(ans+i,(cnt+1)%mod,true);
            else res+=dfs(ans+i,(cnt+1)%mod,flag);
            res%=mod;
        }
    }
    return res;
}

int main()
{
    scanf("%d%d%d",&n,&k,&d);
    ll ans=dfs(0,0,false);
    printf("%lld",ans);
    return 0;
}

代码（多重背包）

#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<set>

#define INF 0x3f3f3f3f
#define mod 1000000007
#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;
typedef unsigned long long ull;
typedef long long ll;
const int N=3e3+5,M=1e7+5;
const double DInf=1e20;
const double eps=1e-8;
int n,k,d;
ll dp[2][105];
//dp[0][i]:表示从1~k中选择所有的边最终路径和为i的所有方案数
//dp[1][i]:表示从1~d-1中选择所有的边最终路径和为i的所有方案数
int main()
{
    scanf("%d%d%d",&n,&k,&d);
    memset(dp,0,sizeof dp);
    dp[0][0]=dp[1][0]=1;
    for(int i=1;i<=n;i++)//从小到大枚举所有路径长度
    {
        for(int j=1;j<=k;j++)//枚举1~k的边，以此更新dp[0][i];
        {
            if(j>i)break;
            dp[0][i]=(dp[0][i]+dp[0][i-j])%mod;
        }
        for(int j=1;j<d;j++)//枚举1~d-1的边，以此更新dp[1][i];
        {
            if(j>i)break;
            dp[1][i]=(dp[1][i]+dp[1][i-j])%mod;
        }
    }
    printf("%lld",((dp[0][n]-dp[1][n])%mod+mod)%mod);
    return 0;
}

E - Three Base Stations

题目：

思路：

二分查找合适的d值，从恰好未被辐射的村庄开始，以该村庄为边缘，开始长度为2d的辐射，更新找到恰好未被辐射的村庄，知道所有的村庄被辐射，返回所需要的基站数目，最后找到最小的d，然后输出即可

代码:

#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
int n;
int x[maxn];
double pos[3];

int judge(int d) {//二分查找2d为'd'的情况下，至少要设置多少个基站
    int cur = 0, cnt = 0;
    for (int i = 0; i < n; i++) {
        if (x[i] > cur) {
            cur = x[i] + d;
            cnt++;
        }
    }
    return cnt;
}

void printPos(double d) {//输出所有的答案
    double ans = d / 2.0;
    printf("%.6f\n", ans);

int cnt = 0, cur = 0;
    for (int i = 0; i < n; i++) {
        if (x[i] > cur) {
            cur = x[i] + d;
            cnt++;
            printf("%.6f ", ans + x[i]);
        }
    }
    while (cnt < 3) {
        printf("%.6f ", 0);
        cnt++;
    }
    cout << endl;
}

void solve() {
    sort(x, x + n);//给所有村庄排序

int a = 0, b = x[n - 1];//说明二分范围，查找2d
    while (a < b) {
        int mid = (b + a) / 2 ;
        if (judge(mid) > 3)//判断mid是否满足条件
            a = mid + 1;
        else
            b = mid;
    }
    //因为d只能为整数或者X.5所以2d一定为整形
    printPos((double)a);//输出解
    return;
}

int main( ) {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> x[i];//读入所有的村庄
    solve();
    return 0;
}

F - Fair

题目:

思路：

起初思路是bfs硬搜，但是发现会超时。

查看别人的思路：选择一次性将所有生产i型商品的城市加入队列，一次bfs，将所有到其他城市的最短路算出来！(借用vector即可在很小的时间复杂的以内加入所有的城市)

我的优化后代码：

#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<set>

#define INF 0x3f3f3f3f
#define mod 1000000007
#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;
typedef unsigned long long ull;
typedef long long ll;
const int N=1e5+5,M=1e7+5;
const double DInf=1e20;
const double eps=1e-8;

int n,m,s,k;
int goods[N];
int dist[N][105];
vector<int> E[N];
int h[N],e[M],ne[M],idx;

void bfs(int cnt)
{
  queue<int>Q;
  for(auto a:E[cnt])
  {
     Q.push(a);
     dist[a][cnt]=0;
  }
  while(!Q.empty())
  {
     int t=Q.front();
     Q.pop();
     for(int i=h[t];~i;i=ne[i])
     {
        int j=e[i];
        if(dist[j][cnt]==INF)
        { 
          dist[j][cnt]=dist[t][cnt]+1;
          Q.push(j);
        }
     }
  }
}

void add(int a,int b)
{
  e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&k);
    for(int i=1;i<=n;i++)
    {
      scanf("%d",&goods[i]);
      E[goods[i]].push_back(i);
    }
    memset(h,-1,sizeof h);
    memset(dist,0x3f,sizeof dist);
    while(m--)
    {
      int a,b;
      scanf("%d%d",&a,&b);
      add(a,b);
      add(b,a);
    }
    for(int i=1;i<=s;i++)bfs(i);
    int ans;
    for(int i=1;i<=n;i++)
    {
      ans=0;
      sort(dist[i]+1,dist[i]+1+s);
      for(int j=1;j<=k;j++)
      ans+=dist[i][j];
      printf("%d ",ans);
    }
    return 0;
}

大佬代码：

//我们直接将所有生产i型商品的城市一次性全加入队列，然后bfs
 #include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include "algorithm"
using namespace std;
const int MAX=1e6+5;
int n,m,k,s;
int good[MAX];//记录每个城市所生产的商品种类
int mov[MAX][105];//mov[i][j]记录以生产j商品的城市为举办地，到i城市的最小花费
vector<int> E[MAX];//记录存储某个商品的所有城市
void bfs(int x)
{
    queue<int> Q;
    int i,u,v;
    Q.push(x+n);
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        for(i=0;i<E[u].size();i++){
            v=E[u][i];
            if(mov[v][x]==0){
                mov[v][x]=mov[u][x]+1;
                Q.push(v);
            }
        }
    }
}
int main()
{
    int i,j;
    int u,v,cnt;
    scanf("%d%d%d%d",&n,&m,&k,&s);
    for(i=1;i<=n;i++){
        scanf("%d",&good[i]);
        E[good[i]+n].push_back(i);//如果我们直接用一个for循环将生产good[i]型商品的城市加入队列的话，就会超时，所以，我们借用这个vector来处理！
    }
    for(i=0;i<m;i++){
        scanf("%d%d",&u,&v);
        E[u].push_back(v);
        E[v].push_back(u);
    }
    for(i=1;i<=k;i++) bfs(i);//遍历所有生产i商品的城市，记录他到各各商品城市最短的距离
    for(i=1;i<=n;i++){
        cnt=0;
        sort(mov[i]+1,mov[i]+k+1);//从小到大排序所有最近商品城市到i的距离
        for(j=1;j<=s;j++)//取前s个商品城市
            cnt+=mov[i][j]-1;//因为每个城市之前多加了1，所以现全都减去
        printf("%d ",cnt);
    }
    return 0;
}

A - Lucky Numbers

题目：

思路：

代码：

B - The Meeting Place Cannot Be Changed

题目：

思路：

代码:

C - Xenia and Weights

题目：

思路：

代码：

D - k-Tree

题目：

思路：

代码（超时的搜索）：

代码（多重背包）

E - Three Base Stations

题目：

思路：

代码:

F - Fair

题目:

思路：

我的优化后代码：

大佬代码：

Recommend

Three.js 之 18 使用 Blender 设计和导出模型

Three.js 之 19 realistic render 真实渲染

磁盘问题宕机后 docker 的 containerd 无法启动

独家：火币真正收购者仍为孙宇晨

羊绒毛衣“鄂尔多斯”发布新Logo，设计越来越时尚了

10月11日电商报/淘特公布双11玩法主推搜索比价功能

PC shipments fall for HP, Lenovo and Dell but Apple shipments rise in Q3

Biden's AI Bill of Rights Is Toothless Against Big Tech | WIRED

Google's affordable Pixel 6a hits an all-time low of $329 in Amazon Prime Early...

苹果iOS内购30%全球大涨价落地，玩家直呼氪不起！厂商态度不一

About Joyk