头像

起きない皓流




离线:21小时前


最近来访(117)
用户头像
鸭梨打滚
用户头像
不高兴的兽奶
用户头像
就约在花海吧
用户头像
Fatin
用户头像
P4r4d0x
用户头像
sola选手心态良好
用户头像
垫底抽風
用户头像
xiaohu
用户头像
月亮供电不足
用户头像
Kazimierz
用户头像
incra
用户头像
冰之韵
用户头像
呐呐呐呐
用户头像
专注等于效率翻倍
用户头像
用户头像
菜狗一枚
用户头像
兜里有ke糖
用户头像
人生如戏ba
用户头像
-浪漫主义狗-
用户头像
大学才


106.png
107.png

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int M = 1e6+5,N=1e5+5;
char s[M],p[N];
int ne[N];
int m,n;
int main()
{
    cin>>n>>p+1>>m>>s+1;
    ne[1]=0;
    //求ne数组
    for(int i=2,j=0;i<=n;i++)
    {
        while(j&&p[j+1]!=p[i])
            j=ne[j];
        if(p[j+1]==p[i])
        {
            j++;
        }
        ne[i]=j;
    }
    for(int i=1,j=0;i<=m;i++)
    {
        while(j&&s[i]!=p[j+1])
        {
            j=ne[j];
        }
        if(s[i]==p[j+1])
        {
            j++;
        }
        if(j==n)
        {
            printf("%d ",i-n);
            // j=ne[j];
        }
    }
    cout << endl;
    return 0;
}



给一个题目,求这个最短的路径的点的路径
102.png
解法:看ppt
103.png
104.png
105.png
代码如下:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
struct node{int x,y;};
const int N = 120;
int g[N][N];
int n,m;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
node c[N][N];
void print(int x,int y)
{
    if(x==0&&y==0)
    {
        return;
    }
    auto q=c[x][y];
    print(q.x,q.y);
    cout << x<<" "<<y<<endl;
}
void dfs(int x,int y)
{
    queue<node> p;
    p.push({x,y});
    g[x][y]=1;
    while(p.size())
    {
        auto t=p.front();
        p.pop();
        for(int i=0;i<4;i++)
        {
            int x=t.x+dx[i];
            int y=t.y+dy[i];
            if(x<0||x>=n||y<0||y>=m||g[x][y])
            {
                continue;
            }
            c[x][y]=t;//将这个点的前驱节点进行标记
            g[x][y]=1;
            p.push({x,y});
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            scanf("%d", &g[i][j]);
        }
    }
    dfs(0,0);
    puts("0 0");
    print(n-1,m-1);
    return 0;
}



这个题绝了

 double z = sqrt(get(x1, y1, x2, y2));   //给定点跟给点圆心的距离 --> z
    double R = (z + r) / 2;   // 这是我们自己画的圆的新圆的半径,因为新圆从题意得,内切于给定圆

    double zmin = R - z;     //这是新圆到给定圆之间的距离

    double tx1 = x1 - x2, tx2 = y1 - y2;  //这是x跟y之间的变化量
    tx1 /= z; tx2 /= z;    //除以z,表示的是x的变化量,跟z这个变化量之间的比例,这个比例跟zmin / x1min
    tx1 *= zmin, tx2 *= zmin; //求出x1min只需要在 乘 一个zmin ,就能够求出x1min,就是新增加的距离,
    x1 += tx1, y1 += tx2; //所以只需要将题目给定圆的x1 加上我们算出来的新增加的距离就是新的圆心的横坐标,
                            // 纵坐标同理

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
// typedef long long LL;
double get(double x3,double y3,double x4,double y4)
{
    return abs(x3-x4)*abs(x3-x4)+abs(y3-y4)*abs(y3-y4);
}
int main()
{
    double R,x1,y1,x2,y2;
    cin>>R>>x1>>y1>>x2>>y2;
    if(x1==x2&&y1==y2)
    {
        printf("%.6f %.6f %.6f\n",x1+R/2,y2,R/2);
    }
    else if(sqrt(get(x1,y1,x2,y2))>=R)
    {
       printf("%.6f %.6f %.6f\n",x1,y1,R);
    }
    else
    {
        double dx=x1-x2;
        double dy=y1-y2;
        double z=sqrt(get(x1,y1,x2,y2));
        double r=(z+R)/2;
        double miz=r-z;
        dx/=z;
        dy/=z;
        x1+=dx*miz;
        y1+=dy*miz;
        printf("%.6f %.6f %.6f\n",x1,y1,r);
    }
    return 0;
}


活动打卡代码 AcWing 4498. 指针

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
int a[N];
int n;
bool flage;
void dfs(int ct,int sum)
{
    if(ct==n)
    {
        if(sum%360==0)
        {
            flage=true;
        }
        return;
    }
    dfs(ct+1,sum+a[ct+1]);
    dfs(ct+1,sum-a[ct+1]);
}
int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d", &a[i]);
    }
    dfs(0,0);
    if(flage)
    {
        puts("YES");
    }
    else
    {
     puts("NO");
    }
    return 0;
}


活动打卡代码 AcWing 4497. 分糖果

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int n;
int main()
{
    scanf("%d",&n);
    while (n -- )
    {
        LL a,b,c;
        scanf("%lld%lld%lld", &a, &b,&c);
        LL d=(a+b+c)/2;
        printf("%lld\n",d);
    }
    return 0;
}



99.png
100.png
101.png

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 500010,M=2*N;
int dep[N];//表示N这个点的层数
int f[N][20];//表示i这个点移动2^20次幂的移动的点
// int e[M],ne[N],h[N],idx;//这里只需要找到一个临边就ok了
int n,m,root;
vector<int> e[N];
// void Add(int a,int b)
// {
//     e[++idx]=b;
//     ne[idx]=h[a];
//     h[a]=idx;
// }
void dfs(int u,int father)
{
    dep[u]=dep[father]+1;//儿子节点的深度=父亲结点的深度+1
    f[u][0]=father;
    for(int i=1;i<=19;i++)
    {
        f[u][i]=f[f[u][i-1]][i-1];//进行遍历
    }
    for(auto v:e[u])
    {
        if(v!=father)//如果这个点不是父亲结点的话,我们就dfs下去
        {
            dfs(v,u);
        }
    }
}
int lca(int u,int v)
{
    if(dep[u]<dep[v])
    {
        swap(u,v);
    }
    for(int i=19;i>=0;i--)
    {
        if(dep[f[u][i]]>=dep[v])
        {
            u=f[u][i];
        }
    }
    if(u==v)
    {
        return v;
    }
    for(int i=19;i>=0;i--)
    {
        if(f[u][i]!=f[v][i])
        {
            u=f[u][i];
            v=f[v][i];
        }
    }
    return f[u][0];
}
int main()
{
    scanf("%d%d%d", &n, &m,&root);
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        e[a].push_back(b);
        e[b].push_back(a);
    }
    dfs(root,0);
    while (m -- )
    {
        int a,b;
        scanf("%d%d", &a,&b);
        cout<<lca(a,b)<<endl;
    }
    return 0;
}



97.png
98.png

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010,M=2*N;
int h[N],e[M],ne[M],idx,ans=N;
bool st[N];
int n;
void Add(int a,int b)
{
    e[++idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
}
int dfs(int u)
{
    st[u]=true;
    int num=1;
    int size=0;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(st[j])
        {
            continue;
        }
        int s=dfs(j);
        size=max(size,s);
        num+=s;
    }
    ans=min(ans,max(size,n-num));
    return num;
}
int main()
{
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d", &a, &b);
        Add(a,b);
        Add(b,a);
    }
    dfs(1);
    cout<<ans<<endl;
    return 0;
}



大佬太多了呜呜
96.png

C++ 代码

#include<iostream>
using namespace std;
const int N=5e5+5;
int q,x,a[N],k,n;
double s;
int main(){
    scanf("%d",&q);
    while(q--){
        scanf("%d",&x);
        if(x==1)scanf("%d",&a[++n]);
        else{
            while(k+1<=n&&a[k+1]<(s+a[n])/(k+1))s+=a[++k];
            printf("%0.6f\n",a[n]-(a[n]+s)/(k+1));
        }
    }
    return 0;
}


活动打卡代码 AcWing 4502. 集合操作

#include<iostream>
using namespace std;
const int N=5e5+5;
int q,x,a[N],k,n;
double s;
int main(){
    scanf("%d",&q);
    while(q--){
        scanf("%d",&x);
        if(x==1)scanf("%d",&a[++n]);
        else{
            while(k+1<=n&&a[k+1]<(s+a[n])/(k+1))s+=a[++k];
            printf("%0.6f\n",a[n]-(a[n]+s)/(k+1));
        }
    }
    return 0;
}



这个题目非常有意思,这个题目我是这样想的,用a[i]表示牌编号为i的牌有多少张,f[i]表示第i副牌现在已经收集了多少张,如果现在打开第i+1包面的编号为1,在此之前我抽到的编号为1的卡牌的数量为1,那现在的话我就又多了一张牌1,那么我就可以算在f2,用语句f[a[1]]表示,f[2]就多了一张牌,假如我下一张牌又抽到1,那么它可以给f[3],还是f[a[1]],那么其他的牌也是如此的记录,个数为1自然算在第一幅牌中,假如f[1]==n,就表示第一副牌收集满了,这个时候用用num++,表示开始收集第二副牌了(开始的num当然是为1的),如此遍历下去在一次时间复杂范围内就可以实现.

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100010;
int a[N];
int f[N];
int n,m;
int num=1;
int main()
{
    scanf("%d%d", &n, &m);
    while (m -- )
    {
        int x;
        scanf("%d", &x);
        f[++a[x]]++;
        if(f[num]==n)
        {
            printf("1");
            num++;
        }
        else
        {
            printf("0");
        }
    }
    cout<<endl;
    return 0;
}