头像

GRID




在线 


活动打卡代码 AcWing 1073. 树的中心

GRID
1小时前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10,INF = 0x3f3f3f3f;
int h[N],e[2*N],w[2*N],ne[2*N],idx;
int n,a,b,c,fa[N];
int d1[N],d2[N],p1[N],p2[N],up[N];
int ans=INT_MAX;
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;   
}
int dfsd(int u,int father)
{
    d1[u]=d2[u]=-INF;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j!=father)
        {
            int d=dfsd(j,u)+w[i];
            if(d>d1[u]){
                d2[u]=d1[u]; 
                p2[u]=p1[u];
                p1[u]=j;
                d1[u]=d;
            }
            else if(d>=d2[u]){
                d2[u]=d;
                p2[u]=j;
            }
        }
    }
    if(d1[u]==-INF) d1[u]=d2[u]=0;
    return d1[u];
}
void dfsu(int u,int father)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j==father) continue;
        if(p1[u]==j) up[j]=max(up[u],d2[u])+w[i];
        else up[j]=max(up[u],d1[u])+w[i];
        dfsu(j,u);
    }
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }

    dfsd(1,-1);
    dfsu(1,-1);
    for(int i=1;i<=n;i++) ans=min(ans,max(up[i],d1[i]));
    cout<<ans;
    return 0;
}




GRID
4小时前

分析

exam.png

向确定初始时蚂蚁的方向d,之后根据黑白块对d进行变化移动,循环k次即可得到答案。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
const int N = 110;
int g[N][N],n,m;
int getd(char c)    //确定初始方向
{
    if(c=='U') return 0;
    if(c=='R') return 1;
    if(c=='D') return 2;
    return 3;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>g[i][j];
        }
    }
    int x0,y0,k,d;
    char c;
    cin>>x0>>y0>>c>>k;
    d=getd(c);
    while(k--)  //蚂蚁循环k次
    {
        if(g[x0][y0]==0){
            d=((d-1)%4+4)%4;    //白块时要保证方向为正数
            g[x0][y0]=1;
            x0=x0+dx[d],y0=y0+dy[d];
        }
        else{
            d=(d+1)%4;          //%4保证方向区间始终在[0,3]
            g[x0][y0]=0;
            x0=x0+dx[d],y0=y0+dy[d];
        }
    }
    cout<<x0<<" "<<y0;

    return 0;
}


活动打卡代码 AcWing 1285. 单词

GRID
5小时前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n,tr[N][26],cnt[N],idx; 
int q[N],ne[N]; 
char str[N];
int id[210];  //存储第每个单词的位置
void insert(int x)  //插入第x个单词到Trie树中
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int t=str[i]-'a';
        if(!tr[p][t]) tr[p][t]=++idx;
        p=tr[p][t];
        cnt[p]++;   //统计单词的前缀出现的次数
    }
    id[x]=p;    //记录这个单词出现的位置
}
void build()    //建立AC自动机
{
    int hh=0,tt=-1;
    for(int i=0;i<26;i++)
        if(tr[0][i])
            q[++tt]=tr[0][i];

    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=0;i<26;i++)
        {
            int j=tr[t][i];
            if(!j) tr[t][i]=tr[ne[t]][i];
            else{
                ne[j]=tr[ne[t]][i];
                q[++tt]=j;
            }
        }
    }
}


int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%s",str);
        insert(i);  //插入单词
    }
    build();    //建立AC自动机

    for(int i=idx-1;i>=0;i--) cnt[ne[q[i]]]+=cnt[q[i]];     //倒序累加

    for(int i=0;i<n;i++) printf("%d\n",cnt[id[i]]); //输出第i个单词的位置的出现次数
    return 0;
}


活动打卡代码 AcWing 1282. 搜索关键词

GRID
17小时前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10,M = 1e6+10;
int n;
int tr[50*N][26],cnt[50*N],idx;
char str[M];
int q[N*50],ne[N*50];
void init()
{
    memset(tr,0,sizeof tr);
    memset(cnt,0,sizeof cnt);
    memset(ne,0,sizeof ne);
    idx=0;
}
void insert()
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int t=str[i]-'a';
        if(!tr[p][t]) tr[p][t]=++idx;
        p=tr[p][t];
    }
    cnt[p]++;
}
void build()
{
    int hh=0,tt=-1;
    for(int i=0;i<26;i++)
        if(tr[0][i])
            q[++tt]=tr[0][i];

    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=0;i<26;i++)
        {
            int j= tr[t][i];
            if(!j) tr[t][i]=tr[ne[t]][i];
            else{
                ne[j]=tr[ne[t]][i];
                q[++tt]=j;
            }
        }
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        init();

        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%s",str);
            insert();
        }

        build();
        scanf("%s",str);
        // puts(str);
        int ans=0;
        for(int i=0,j=0;str[i];i++)
        {
            int t=str[i]-'a';
            j=tr[j][t];

            int p=j;
            while(p)
            {
                ans+=cnt[p];
                cnt[p]=0;
                p=ne[p];
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}



GRID
1天前

wxinc.png

  1. 按下+1按钮,系统会自动加一并显示:1.png
  2. 按下-1按钮,系统会自动减一并显示:_1.png
  3. 按下*2按钮,系统会自动乘二并显示:2.png
  4. 按下/2按钮,系统会自动除以二并显示: _2.png

根据上述基本操作,可以实现类似于计算器的功能。

in.js

Page({

  /**
   * 页面的初始数据
   */
  data: {
    num:0   //设定初值,方便在页面上显示
  },

  onLoad: function (options) {

  },

  inc1: function(event){
      var that=this
      this.setData({
        num:that.data.num+1
      })
  },

  dec1: function(event){
    var that=this
    this.setData({
      num:that.data.num-1
    })    
  },

  mul2: function(event){
    var that=this
    this.setData({
      num:that.data.num*2
    })
  },

  div2: function(event){
    var that=this
    this.setData({
      num:that.data.num/2
    })
  },
})

in.json

{
  "usingComponents": {}
}

in.wxml

<view class="background">
      <text class="title">{{num}}</text>
      <!-- <text class="text">{{infomation}}</text> -->
</view>
<view class="btn1">
    <text bindtap="inc1">加一</text>
</view>
<view class="btn2">
    <text bindtap="dec1">减一</text>
</view>
<view class="btn3">
    <text bindtap="mul2">乘二</text>
</view>
<view class="btn4">
    <text bindtap="div2">除二</text>
</view>

in.wxss

.background{
  display: flex;
  flex-direction: column;
  justify-content: center;
  background-color: rgb(255, 255, 255);
  width: 90%;
  border-radius: 20rpx;
  margin-top: 50rpx;
  margin-left: auto;
  margin-right: auto;
  box-shadow:0rpx 0rpx 20rpx 1rpx gray;
}

.title{
  margin: auto;
  margin-top: 50rpx;
  color: red;
  font-size: 130%;
}

.btn1{
  font-size: 13pt;
  height: 55rpx;
  background: #7B68EE;
  color: black;
  text-align: center;
  border-radius: 50px;
  margin: 10% 20% 10% 20%;
}

.btn2{
  font-size: 13pt;
  height: 55rpx;
  background: #00FA9A;
  color: black;
  text-align: center;
  border-radius: 50px;
  margin: 10% 20% 10% 20%;
}

.btn3{
  font-size: 13pt;
  height: 55rpx;
  background: #F0E68C;
  color: black;
  text-align: center;
  border-radius: 30px;
  margin: 10% 20% 10% 20%;
}

.btn4{
  font-size: 13pt;
  height: 55rpx;
  background:   #FF4500;
  color: black;
  text-align: center;
  border-radius: 30px;
  margin: 10% 20% 10% 20%;
}



GRID
1天前

分析

dfs()整个字符串即可。

C++ 代码

class Solution {
public:
    int n;
    vector<vector<string>> ans;
    bool check(string s)    //判断当前字符串是否为回文串
    {
        return s==string(s.rbegin(),s.rend());
    }
    void dfs(int u,vector<string> &v,string s)  //当前下标 当前字符串数组 字符串s
    {
        if(u==n){
            ans.push_back(v);
            return ;
        }
        string temp;
        for(int i=u;i<n;i++)
        {
            temp+=s[i];
            if(check(temp))
            {
                v.push_back(temp);
                dfs(i+1,v,s);
                v.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        n=s.size();
        vector<string> v;
        dfs(0,v,s);
        return ans;
    }
};



GRID
2天前

分析

本题要求从1点出发,找到一条到达终点n的最短路。(单源最短路)
设type为路的种类,当路的type为0是代表是大路,此外所有的type都是代表小路。
因为题目保证答案不会超过1e6,所以type*type<=1e6,即type<=1000

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 510,M = 2e5+10;
int h[N],e[M],T[M],w[M],ne[M],idx;      //T用来表示路的种类
int n,m,dist[N][1010];  //dist[x][y]:到x点,类型为y的最短距离(<=1000)
bool st[N][1010];   //st[x][y]:到x点,类型为y的路是否遍历过(<=1000)
void add(int a,int b,int c,int type)
{
    e[idx]=b,w[idx]=c,T[idx]=type,ne[idx]=h[a],h[a]=idx++;
}
struct node{
    int x,type,w;   //x点为当前点x,type为路的种类

    bool operator<(const node &p)const{
        return w>p.w;       //当路的类型为大路时,它的w值通常会比小路的w大很多,所以优先选取大路来走
    }
};
void spfa()
{
    memset(dist,0x3f,sizeof dist);

    priority_queue<node> q; //用一个优先队列存储所有节点
    q.push({1,0,0});    //1:1号点,0:种类为0,到起点1的距离为0
    dist[1][0]=0;

    while(q.size())
    {
        auto t=q.top();
        q.pop();
        if(st[t.x][t.type]) continue;   //此状态遍历过,直接跳过
        st[t.x][t.type]=1;
        for(int i=h[t.x];~i;i=ne[i])    //枚举所有出边
        {
            int j=e[i];
            if(!T[i])       //如果type为0,说明为大路,按照平常求最短路逻辑进行计算即可
            {
                if(dist[j][0]>dist[t.x][t.type]+w[i])
                {
                    dist[j][0]=dist[t.x][t.type]+w[i];
                    if(dist[j][0] <= 1e6)   //答案保证不超过1e6
                        q.push({j,0,dist[j][0]});
                }
            }
            else if(t.type+w[i]<=1000){     //路的种类为小路,且总和不超过1000
                int tt=t.type+w[i];     //新的小路的种类为tt
                if(dist[j][tt]>dist[t.x][t.type]-t.type*t.type+tt*tt) 
                {
                    dist[j][tt]=dist[t.x][t.type]-t.type*t.type+tt*tt;
                    if(dist[j][tt]<=1e6)    //答案保证不超过1e6
                        q.push({j,tt,dist[j][tt]});
                }
            }
        }
    }
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    int type,a,b,c;
    for(int i=0;i<m;i++)
    {
        cin>>type>>a>>b>>c;
        add(a,b,c,type),add(b,a,c,type);
    }

    spfa();

    int res = 1e6;
    for (int i=0;i<=1000;i++ )  
    {
        res = min(res, dist[n][i]); //起点达到终点n,状态为i的最短距离
    }
    printf("%d\n", res);

    return 0;
}



GRID
4天前

分析

本题是判断一个无向图是否具有欧拉路径,或者欧拉回路(起点和终点相同的欧拉路径)
对于无向图:

  1. 欧拉路径存在的充分必要条件:度数为奇数的点个数为2个或0个
  2. 欧拉回路存在的充分必要条件:度数为奇数的点个数为0个

度数为奇数的点有2个时,起点的度数不能是偶数:
2.png
由于本题要求求出字典序最小的路口顺序(点集合),所以需要将所有点加入到一个数组中进行排序,保证能得到最小字典序。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e4+10,M = 2e5+10;
int h[N],e[M],ne[M],idx;
int d[M],ans[M / 2],cnt;
int n,m;
bool used[M];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u)
{
    vector<PII> v;  //数组v存储所有可以走的边
    for(int i=h[u];~i;i=ne[i])
    {
        if(!used[i])    //此边没有被用过
            v.push_back({e[i],i});
    }
    sort(v.begin(),v.end());    //排序,让点按大小顺序进行排列(最小字典序)
    for(auto &t :v)
    {
        if(used[t.second]) continue;
        used[t.second]=used[t.second^1]=1;  //该边和该边的反边都标记用过
        dfs(t.first);       //向下一个点j进行搜索
    }
    ans[++cnt]=u;   //当前点加入到答案中
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    int a,b;
    for(int i=0;i<m;i++)
    {
        cin>>a>>b;
        add(a,b);
        add(b,a);
        d[a]++,d[b]++;  
    }

    int co=0;
    for(int i=1;i<=n;i++)   //计算每个点的度数
    {
        if(d[i]%2) co++;
    }

    //co==0位欧拉回路,co==2为欧拉路径,当co==2时,要确保起点的度数不等于偶数,不满足条件,直接输出-1
    if(co!=0 && co!=2 || (co == 2 && d[1] % 2 == 0) ){
        puts("-1");
        return 0;
    }
    dfs(1);  //根据题意,从起点1开始走

    if(cnt<n) {  //最终不能将所有的点走到,则输出-1
        puts("-1");
        return 0;
    }

    for(int i=cnt;i;i--)    //由于dfs是最后再加入当前点u的,所以最小字典序应该为逆序,所以倒着输出
        cout<<ans[i]<<" ";
    return 0;
}



GRID
4天前

分析

对于无向图中边的编号t的说明
rela.png

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10,M = 4e5+10;
int n,m,ans[M / 2],cnt,type;;
int h[N],e[M],ne[M],idx;
int din[N],dout[N];
bool used[M];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u)
{
    for(int &i=h[u];~i;)
    {
        if(used[i])
        {
            i=ne[i];    //删除这条边
            continue;
        }

        used[i]=true;
        if(type==1) used[i^1]=true;

        int t;
        if(type==1)     //无向图时,正边是t=i/2+1,反边是-t
        {
            t=i/2+1;
            if(i&1) t=-t;
        }
        else t=i+1;

        int j=e[i]; 
        i=ne[i];        //删除这条边
        dfs(j);         
        ans[++cnt]=t;   //该边加入欧拉回路
    }
}
int main()
{
    memset(h,-1,sizeof h);

    scanf("%d",&type);
    scanf("%d%d",&n,&m);

    int a,b;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&a,&b);
        add(a,b);
        if(type==1) add(b,a);       //无向边要加上反边
        dout[a]++,din[b]++;
    }

    if(type==1)     //无向图欧拉回路要求每个点的度数(入度+出度)不能为奇数
    {
        for(int i=1;i<=n;i++)
        {
            if((din[i]+dout[i])%2)
            {
                puts("NO");
                return 0;
            }
        }
    }
    else{           //有向图要求每个点度数的出度等于入度
        for(int i=1;i<=n;i++)
        {
            if(din[i]!=dout[i])
            {
                puts("NO");
                return 0;
            }
        }
    }

    for(int i=1;i<=n;i++)   //从第一个有边连接的点开始进行走欧拉回路的流程
    {
        if(h[i]!=-1)
        {
            dfs(i);
            break;
        }
    }

    if(cnt<m)       //如果最后遍历到边的数量小于m,说明图不是连通图,直接输出NO
    {
        puts("NO");
        return 0;
    }

    puts("YES");
    for(int i=cnt;i;i--)        //输出欧拉回路
        printf("%d ",ans[i]);
    return 0;
}


活动打卡代码 AcWing 1123. 铲雪车

GRID
4天前
#include<bits/stdc++.h>
using namespace std;

int main()
{
    double x1,y1,x2,y2;
    cin>>x1>>y1;
    double sum=0;
    while(cin>>x1>>y1>>x2>>y2)
    {
        double dx = x1 - x2;
        double dy = y1 - y2;
        sum += sqrt(dx * dx + dy * dy) * 2;
    }

    int minutes = round(sum / 1000 / 20 * 60);
    int hours = minutes / 60;
    minutes %= 60;

    printf("%d:%02d\n", hours, minutes);
    return 0;
}