头像

废物宝宝

关注数
1
粉丝数
2
阅读量
2720


离线：1小时前

最近来访(29)
用户头像
冰中月
用户头像
77777777777
用户头像
Whynot.
用户头像
麦小蓝
用户头像
hxzz
用户头像
pdsutg06
用户头像
charley123
用户头像
clarifylcq
用户头像
一切随缘
用户头像
DueGin
用户头像
接你回家
用户头像
偶尔遐想未来
用户头像
云边有一个小卖部
用户头像
欧拉欧拉
用户头像
liyi09
用户头像
蓝色饭团
用户头像
Alphaville
用户头像
Never_Accepted
用户头像
BaoYiFanD
用户头像
好氧君的菌

活动打卡代码 AcWing 4486. 数字操作
废物宝宝的头像
废物宝宝
21小时前 
#include<iostream>
#include<vector>
using namespace std;
const int N=10005;

int n;
int main(){
    cin>>n;
    vector<int>a;
    int s=1,m=0;
    for(int i=2;i<=n/i;i++)
        if(n%i==0){
            int c=0;
            while(n%i==0)n/=i,c++;
            s*=i;
            a.push_back(c);
            while (1 << m < c) m ++ ;//找到一个最小的m使得 2^m要大于c
        }
    if(n>1){
        s*=n;
        a.push_back(1);
        while (1 << m < 1) m ++ ;
    }
    for (auto x: a)//只要有一个小于2^m就表示需要乘一个数
        if (x < 1 << m)
        {
            m ++ ;
            break;
        }
    cout<<s<<" "<<m;
    return 0;
}
  赞
  评论
  收藏
活动打卡代码 AcWing 4485. 比大小
废物宝宝的头像
废物宝宝
21小时前 
#include<iostream>
using namespace std;
int n;

int main(){
    int s=0,x;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x;
        s+=x;
    }
    while(n--){
        cin>>x;
        s-=x;
    }
    cout<<(s>=0?"Yes":"No");
    return 0;
}
  赞
  评论
  收藏
题解 AcWing 693. 行程排序
废物宝宝的头像
废物宝宝
1天前

觉得不错还请点个赞

本题难点是存储上数据上

  1. 怎么存每一站信息

用unordered_map<string,string>m来记录每一个航班的地点

m["SFO"]="DFW"表示有一个航班是从SFO飞向DFW

  1. 怎么找到起始站

在输入的过程中记录哪些地点是某一次航班的目的地

unordered_set<string>in;

对于SFO飞向DFW 我们需要in.insert("DFW")

表示DFW是一个航班的目的地 也表示着DFW一定不是起始地点

  1. 如何打印结果

找到起始地点 $q$以后只要m[p]!=""就说明$p$还有目的地就还要继续飞

#include<iostream>
#include<cstring>
#include<unordered_map>
#include<unordered_set>
using namespace std;
int T,n;
int main(){
    cin>>T;
    for(int t=1;t<=T;t++){
        unordered_map<string,string>m;//记录每一张票的信息
        unordered_set<string>in;//记录哪些站有前驱 用来后记找到起始地点
        cin>>n;
        for(int i=0;i<n;i++){
            string start,end;
            cin>>start>>end;
            m[start]=end;
            in.insert(end);
        }
        string q;
        for(auto [start,v]:m)
            if(!in.count(start)){//如果没有前驱 他就是起始站点
                q=start;
                break;
            }

        printf("Case #%d:",t);
        while(m[q]!=""){
            cout<<" "<<q<<"-"<<m[q];
            q=m[q];
        }
        printf("\n");
    }
    return 0;
}
  1
  1
  收藏
活动打卡代码 AcWing 693. 行程排序
废物宝宝的头像
废物宝宝
1天前 
#include<iostream>
#include<cstring>
#include<unordered_map>
#include<unordered_set>
using namespace std;
const int N=1005;
int T,n;
string f[N];
int main(){
    cin>>T;
    for(int t=1;t<=T;t++){
        unordered_map<string,string>m;//记录每一张票的信息
        unordered_set<string>in;//记录哪些站有前驱 用来后记找到起始地点
        cin>>n;
        for(int i=0;i<n;i++){
            string start,end;
            cin>>start>>end;
            m[start]=end;
            in.insert(end);
        }
        string q;
        for(auto [start,v]:m)
            if(!in.count(start)){//如果没有前驱 他就是起始站点
                q=start;
                break;
            }

        printf("Case #%d:",t);
        while(m[q]!=""){
            cout<<" "<<q<<"-"<<m[q];
            q=m[q];
        }
        printf("\n");
    }
    return 0;
}
  赞
  评论
  收藏
活动打卡代码 AcWing 1927. 自动补全
废物宝宝的头像
废物宝宝
3天前 
#include<iostream>
#include<cstring>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef pair<string,int>PSI;
const int N=3e4+5;
PSI w[N];
int m,n,k;
string s;
int main(){
    cin>>m>>n;
    for(int i=1;i<=m;i++){
        cin>>w[i].x;
        w[i].y=i;//记录出现的位置
    }
    sort(w+1,w+m+1);
    while(n--){
        cin>>k>>s;
        //找到所有单词中第一个比s大的 相当于找到以他为前缀的第一个
        int l=1,r=m;
        while(l<r){
            int mid=l+r>>1;
            if(w[mid].x>=s)r=mid;
            else l=mid+1;
        }
        int t=l+k-1;//第k个补充
        if(t>=m||w[t].x.substr(0,s.size())!=s)
            puts("-1");
        else 
            cout<<w[t].y<<endl;
    }
    return 0;
}
  赞
  评论
  收藏
题解 AcWing 3311. 最长算术 差分+双指针 空间复杂度$O(1)$
废物宝宝的头像
废物宝宝
3天前

本题需要计算最长的连续等差数列的长度

我们可以转化为差分数组 最长连续相等的长度 最后在加1即可

例如

原数组 $10$ $7$ $4$ $6$ $8$ $10$ $11$

差分数组 $10$ $-3$ $-3$ $2$ $2$ $2$ $1$

我们可以看出差分数组最长有三个$2$相连 表示有相邻的三个数与前一个数的差都是2

所以对应的原数组就是 4 6 8 10 (表达不清楚 还请见谅)

记得差分数组找到最长连续的长度后要加一

c++ 代码

#include<iostream>
using namespace std;
const int N=2e5+5;

int T,n,a[N],d[N];

int main(){
    cin>>T;
    for(int t=1;t<=T;t++){
        cin>>n;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            d[i]=a[i]-a[i-1];//记录差分哦
        }
        int ans=0,l=1,r=1;
        while(r<=n){//找相邻且相同的最长序列
            if(d[r]!=d[l]){
                ans=max(ans,r-l+1);
                l=r;
            }
            r++;
        }
        ans=max(ans,r-l+1);
        printf("Case #%d: %d\n",t,ans);
    }
    return 0;
}

无数组版本

因为我们只用考虑相邻两项的差
根据上面的思路我们只需要记录a[i-1]-a[i-2]的值是否与a[i]-a[i-1]相同即可
我们用d=a[i-1]-a[i]
$l$的含义和上面一样指向差分数组相同元素的最左边的位置
$x$为当前元素值 $y$为上一个元素的值 为了计算a[i]-a[i-1]

#include<iostream>
using namespace std;
int T,n;
int main(){
    cin>>T;
    for(int t=1;t<=T;t++){
        cin>>n;
        int l=1,d=0,ans=2,y,x;
        for(int r=1;r<=n;r++){
            scanf("%d",&x);
            if(r==1)y=x;
            else if(x-y!=d)ans=max(ans,r-l+1),l=r;
            d=x-y,y=x;
        }
        ans=max(ans,(n+1)-l+1);
        printf("Case #%d: %d\n",t,ans);
    }
    return 0;
}
  8
  10
  收藏
活动打卡代码 AcWing 3311. 最长算术
废物宝宝的头像
废物宝宝
3天前

本题需要计算最长的连续等差数列的长度

我们可以转化为差分数组 最长连续相等的长度 最后在加1即可

例如

原数组 $10$ $7$ $4$ $6$ $8$ $10$ $11$

差分数组 $10$ $-3$ $-3$ $2$ $2$ $2$ $1$

我们可以看出差分数组最长有三个$2$相连 表示有相邻的三个数与前一个数的差都是2

所以对应的原数组就是 4 6 8 10 (表达不清楚 还请见谅)

记得差分数组找到最长连续的长度后要加一

c++ 代码

#include<iostream>
using namespace std;
const int N=2e5+5;

int T,n,a[N],d[N];

int main(){
    cin>>T;
    for(int t=1;t<=T;t++){
        cin>>n;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            d[i]=a[i]-a[i-1];//记录差分哦
        }
        int ans=0,l=1,r=1;
        while(r<=n){//找相邻且相同的最长序列
            if(d[r]!=d[l]){
                ans=max(ans,r-l+1);
                l=r;
            }
            r++;
        }
        ans=max(ans,r-l+1);
        printf("Case #%d: %d\n",t,ans);
    }
    return 0;
}

无数组版本

因为我们只用考虑相邻两项的差
根据上面的思路我们只需要记录a[i-1]-a[i-2]的值是否与a[i]-a[i-1]相同即可
我们用d=a[i-1]-a[i]
$l$的含义和上面一样指向差分数组相同元素的最左边的位置
$x$为当前元素值 $y$为上一个元素的值 为了计算a[i]-a[i-1]

#include<iostream>
using namespace std;
int T,n;
int main(){
    cin>>T;
    for(int t=1;t<=T;t++){
        cin>>n;
        int l=1,d=0,ans=2,y,x;
        for(int r=1;r<=n;r++){
            scanf("%d",&x);
            if(r==1)y=x;
            else if(x-y!=d)ans=max(ans,r-l+1),l=r;
            d=x-y,y=x;
        }
        ans=max(ans,(n+1)-l+1);
        printf("Case #%d: %d\n",t,ans);
    }
    return 0;
}
  赞
  评论
  收藏
活动打卡代码 AcWing 4279. 笛卡尔树
废物宝宝的头像
废物宝宝
3天前 
//dfs
#include<iostream>
#include<vector>
using namespace std;
const int N=35;
int n,f[N];
vector<int> res[N];
int getmin(int l,int r){
    int m=l;
    for(int i=l;i<=r;i++)
        if(f[m]>f[i])
            m=i;
    return m;
}
void dfs(int l,int r,int d){
    if(l>r)return;
    int root=getmin(l,r);
    res[d].push_back(f[root]);

    dfs(l,root-1,d+1);
    dfs(root+1,r,d+1);

}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>f[i];

    dfs(0,n-1,0);

    for(int i=0;res[i].size();i++){
        for(auto t:res[i])
            printf("%d ",t);
    }
    return 0;
}
  赞
  评论
  收藏
题解 AcWing 691. $dfs$ 极简
废物宝宝的头像
废物宝宝
3天前

如果觉得不错 请帮忙点个赞赞 QAQ

搜索方式

相同的步长只需要最小的起点号就行

所以我们就从最小的起点开始找

剪枝

假设一条从$k$可以向走$len$时候

$k\to k+1\to k+2\to \cdots \to k+len-1$

那么再从$k+1$走也只能走到$k+len-1$

所以下一次直接从 $k+len$ 结点向后找就行

存储方式

存每个点在图中的编号是多少

f[k]=(i-1)*n+j-1

这样存储方便找到他属于哪一行哪一列

x=f[k]/n+1 y=f[k]%k+1

存储的规则不唯一 只要能在找到第几行第几列即可

判断是否可以走到相邻的格子

因为只有相邻的格子比自己的数恰好大1才能走到

所以我们可以直接看 下一个能走的数是否就是在我四周

具体代码如下

    int x=f[k]/n+1,y=f[k]%n+1;//取出当前元素的原坐标
    int nx=f[k+1]/n+1,ny=f[k+1]%n+1;//下一个能走到的元素的坐标
    if(x==nx&&(y==ny-1||y==ny+1))return 1+dfs(k+1);//是否在上边或者下边
    if(y==ny&&(x==nx-1||x==nx+1))return 1+dfs(k+1);//是否在左边或者右边

c++代码

#include<iostream>
using namespace std;
const int N=1005;
int t,n;
int f[N*N];
int dfs(int k){//从k开始最多能走多少步
    if(k==n*n)return 1;//走到最后一步了

    int x=f[k]/n+1,y=f[k]%n+1;
    int nx=f[k+1]/n+1,ny=f[k+1]%n+1;
    if(x==nx&&(y==ny-1||y==ny+1))return 1+dfs(k+1);//加上该步走向下一步
    if(y==ny&&(x==nx-1||x==nx+1))return 1+dfs(k+1);

    return 1;//走到k就终止了 就返回1
}
int main(){
    cin>>t;
    for(int u=1;u<=t;u++){
        cin>>n;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                int x;
                scanf("%d",&x);
                f[x]=(i-1)*n+j-1;//存每一个数字所在的位置编号
            }

        int k=1,res,step=0;//k当前走到哪 res最长的起点编号 step最大能走几步
        while(k<=n*n){
            int len=dfs(k);//从k开始能走几步
            if(len>step){//如果比当前最大步数要大就更新答案
                res=k;
                step=len;
            }
            k+=len;//直接从 k+len开始向后计算
        }
        printf("Case #%d: %d %d\n",u,res,step);
    }
    return 0;
}
  2
  评论
  收藏
活动打卡代码 AcWing 691. 立方体IV
废物宝宝的头像
废物宝宝
3天前 
#include<iostream>
using namespace std;
const int N=1005;
int t,n;
int f[N*N];
int dfs(int k){
    if(k>n*n)return 0;
    if(k==n*n)return 1;

    int x=f[k]/n+1,y=f[k]%n+1;
    int nx=f[k+1]/n+1,ny=f[k+1]%n+1;
    if(x==nx&&(y==ny-1||y==ny+1))return 1+dfs(k+1);
    if(y==ny&&(x==nx-1||x==nx+1))return 1+dfs(k+1);

    return 1;

}
int main(){
    cin>>t;
    for(int u=1;u<=t;u++){
        cin>>n;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                int x;
                scanf("%d",&x);
                f[x]=(i-1)*n+j-1;
            }

        int k=1,res,step=0;
        while(k<=n*n){
            int len=dfs(k);
            if(len>step){
                res=k;
                step=len;
            }

            k+=len;
        }
        printf("Case #%d: %d %d\n",u,res,step);
    }
    return 0;
}
  1
  评论
  收藏