头像

Qjwwww

cjy yyds




离线:3小时前


最近来访(87)
用户头像
正在加载中...
用户头像
yyl__
用户头像
Cabbage74
用户头像
小千层
用户头像
bxnya_miana
用户头像
JcWing
用户头像
Repetac
用户头像
辰chen
用户头像
咸鱼小孩
用户头像
bupt_forest
用户头像
yxc
用户头像
wo怎么什么都不会
用户头像
YikN
用户头像
半.透明.
用户头像
Axel_D
用户头像
Renaissance_0
用户头像
InvolutionZ
用户头像
Juventus_5
用户头像
sky-koi
用户头像
千千万万

活动打卡代码 AcWing 165. 小猫爬山

Qjwwww
3天前
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 20;
int c[N];
int d[N];
int n,w;
bool cmp(int a,int b)
{
    return a > b;
}
int ans;
void dfs(int x,int cnt)
{
    if(cnt >= ans) return;
    if(x==n+1) 
    {
        ans = min(cnt , ans);
        return ;
    }
    for(int i=1;i<=cnt;i++)
    {
        if(d[i]+c[x] <= w)
        {
            d[i]+=c[x];
            dfs(x+1,cnt);
            d[i]-=c[x];
        }
    }
    d[cnt+1]+=c[x];
    dfs(x+1,cnt+1);
    d[cnt+1]-=c[x];
}
signed main()
{
    cin>>n>>w;
    ans = n;
    for(int i=1;i<=n;i++) cin>>c[i];

    sort(c+1,c+1+n,cmp);

    dfs(1,0);

    cout<<ans<<endl;

    return 0;   
} 



Qjwwww
4天前


活动打卡代码 AcWing 1118. 分成互质组

Qjwwww
5天前
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 15;
int a[N];
int n;
int cnt;
int res;
vector<int> g[N];
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
bool check(int k,int x)
{
    for(auto t:g[k])
    {
        if(gcd(a[x],t) > 1) return false;
    }
    return true;
}
void dfs(int x)
{
    if(x==n+1)
    {
        res = min(res , cnt);
        return ;
    }

    for(int i=1;i<=cnt;i++)
    {
        if(check(i,x))
        {
            g[i].pb(a[x]);
            dfs(x+1);
            g[i].pop_back();
        }
    }
    g[++cnt].pb(a[x]);
    dfs(x+1);
    g[cnt--].pop_back();
}
int main()
{
    cin>>n;
    res = n;
    for(int i=1;i<=n;i++) cin>>a[i];

    dfs(1); 

    cout<<res<<endl;

    return 0;
}


活动打卡代码 AcWing 1117. 单词接龙

Qjwwww
5天前
#include<bits/stdc++.h>
using namespace std;
const int N = 25;
string s[N];
int len[N][N];
int n;
int res;
int st[N];
void dfs(int x,int cnt)
{
    st[x]+=1;
    res = max(res , cnt);
    for(int i=1;i<=n;i++)
    {
        if(st[i]>=2) continue;
        if(!len[x][i]) continue;
        dfs(i,cnt-len[x][i]+s[i].size());
    }
    st[x]-=1;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
    }
    char head;
    cin>>head;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int l1 = s[i].size() , l2 = s[j].size();
            for(int k=1;k<min(l1,l2);k++)
            {
                if(s[i].substr(l1-k,k)==s[j].substr(0,k))
                {
                    len[i][j] = k;
                    break;
                }
            }
//          cout<<len[i][j]<<endl;
        }
    }

    for(int i=1;i<=n;i++)
    {
        memset(st,0,sizeof st);
        if(s[i][0]==head)
        {
            dfs(i , s[i].size());
        }
    }
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 1116. 马走日

Qjwwww
5天前
#include<bits/stdc++.h>
using namespace std;
const int N = 12;
string g[N];
int n,m;
int dx[8]={2,1,-1,-2,-2,-1,1,2};//方向数组
int dy[8]={1,2,2,1,-1,-2,-2,-1};//方向数组
int st[N][N];
int T;
int cnt;
void dfs(int x,int y,int num)
{
    st[x][y] = 1;
    if(num == n*m)
    {
        cnt++;
//      return ;
    }

    for(int i=0;i<8;i++)
    {
        int a = x + dx[i] , b = y + dy[i];
        if(st[a][b]) continue;
        if(a<1||b<1||a>n||b>m) continue;
        dfs(a,b,num+1);
    }
    st[x][y] = 0;
}
int main()
{
    cin>>T;
    int x,y;
    while(T--)
    {
        cnt = 0;
        memset(st,0,sizeof st);
        cin>>n>>m>>x>>y;
        x+=1,y+=1;
        dfs(x,y,1);
        cout<<cnt<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 1113. 红与黑

Qjwwww
5天前
#include<bits/stdc++.h>
using namespace std;
const int N = 25;
string g[N];
int W,H;
int dx[4] = {0,1,0,-1} , dy[4] = {1,0,-1,0};
int st[N][N];
int cnt;
void dfs(int x,int y)
{

    st[x][y] = 1;
    cnt++;
    for(int i=0;i<4;i++)
    {
        int a = x + dx[i] , b = y + dy[i];
        if(st[a][b]||g[a][b]!='.') continue;
        if(a<1||b<1||a>H||b>W) continue;

        dfs(a,b);
    }
}
int main()
{
    while(cin>>W>>H)
    {
        cnt = 0;
        memset(st,0,sizeof st);
        if(W==0&&H==0) break;
        for(int i=1;i<=H;i++)
        {
            cin>>g[i];
            g[i] = '#' + g[i];
        }
        int x,y;
        for(int i=1;i<=H;i++)
        {
            for(int j=1;j<=W;j++)
            {
                if(g[i][j]=='@') x = i , y = j;
            }
        }
        dfs(x,y);
        cout<<cnt<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 1112. 迷宫

Qjwwww
5天前
#include<bits/stdc++.h>
using namespace std;
const int N = 150;
string g[N];
int T;
int xa,ya,xb,yb;
int n;
int fg;
int st[N][N];
int dx[4] = {0,1,0,-1} , dy[4] = {1,0,-1,0};
void dfs(int x,int y)
{
    if(x==xb&&y==yb)
    {
        fg = 1 ;
        return ;
    } 
    st[x][y] = 1;
    for(int i=0;i<4;i++)
    {
        int a = x + dx[i] , b = y + dy[i];
        if(st[a][b]||g[a][b]=='#') continue;
        if(a<1||b<1||a>n||b>n) continue;
        dfs(a,b);
    }
}
int main()
{
    cin>>T;
    while(T--)
    {
        fg = 0;
        memset(st,0,sizeof st);
        cin>>n;
        for(int i=1;i<=n;i++) cin>>g[i] , g[i] = '#' + g[i];

        cin>>xa>>ya>>xb>>yb;
        xa+=1 , ya+=1 , xb+=1 , yb+=1;
        if(g[xa][ya]=='#'||g[xb][yb]=='#') cout<<"NO"<<endl;
        else
        {
            dfs(xa,ya);
            if(fg) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 190. 字串变换

Qjwwww
9天前
#include<bits/stdc++.h>
using namespace std;
string A[10],B[10];
string a,b;
int n;
#define x first
#define y second
unordered_map<string,int> da,db;
typedef pair<string,int> PSI;
int res;
queue<PSI> qa,qb;
int dbfs()
{
    if(a==b) return 0;

    qa.push({a,0}) , qb.push({b,0});
    da[a] = 0 , db[b] = 0;
    while(qa.size()&&qb.size())
    {
        auto ta = qa.front() , tb = qb.front();
        //注意此处的小优化,哪个队列数量小,就优先扩展哪个
        if(qa.size() < qb.size())
        {
            qa.pop();
            string s = ta.first;
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<s.size();j++)
                {
                    if(s.substr(j,A[i].size()) == A[i])
                    {
                        string s2 = s.substr(0,j) + B[i] + s.substr(j+A[i].size());
                        // cout<<s2<<" "<<"A"<<" "<<db.count(s2)<<" "<<qa.size()<<endl;
                        if(da.count(s2)) continue;
                        if(db.count(s2))
                        {
                            return  db[s2] + ta.y + 1;
                        }

                        qa.push({s2 , 1 + ta.y});
                        da[s2] = 1 + ta.y;
                    }
                }
            }

        }
        else
        {
            qb.pop();
            string s = tb.first;
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<s.size();j++)
                {
                    if(s.substr(j,B[i].size()) == B[i])
                    {
                        string s2 = s.substr(0,j) + A[i] + s.substr(j+B[i].size());
                        // cout<<s2<<" "<<"B"<<" "<<qb.size()<<endl;
                        if(db.count(s2)) continue;
                        if(da.count(s2))  return  da[s2] + tb.y + 1;

                        qb.push({s2 , 1 + tb.y});
                        db[s2] = 1 + tb.y;
                    }
                }
            }

        }
    }
    return -1;
}
int main()
{
    cin>>a>>b;
    while(cin>>A[n]>>B[n]) n++;

    int res = dbfs();
    // cout<<db["xy"]<<" "<<da["xy"]<<endl;
    if(res==-1) cout<<"NO ANSWER!";
    else cout<<res;
    return 0;
}


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

Qjwwww
12天前

很棒的树形DP题目

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 50 , M = 2*N;
int h[N],e[M],ne[M],w[M];
int idx;
void add(int a,int b,int c)
{
    e[idx] = b , ne[idx] = h[a] , w[idx] = c , h[a] = idx++;
}
int res = 1e18;
int d1[N],d2[N],p1[N],up[N],fa[N];
int dfs_down(int x,int u)
{
    fa[x] = u;
    d1[x] = d2[x] = -1e16;
    for(int i=h[x];i!=-1;i=ne[i])
    {
        int j = e[i];
        if(j==u) continue;
        int d = dfs_down(j,x) + w[i];
        if(d > d1[x])
        {
            d2[x] = d1[x] , d1[x] = d ;
            p1[x] = j;
        }
        else if(d > d2[x])
        {
            d2[x] = d;
        }
    }
    if(d1[x]==-1e16) d1[x] = d2[x] = 0;
    return d1[x];
}
int dfs_up(int x)
{
    for(int i=h[x];i!=-1;i=ne[i])
    {
        int j = e[i];
        if(j==fa[x]) continue;

        if(p1[x]==j)
        {
            up[j] = max(up[x] , d2[x]) + w[i];
        }
        else up[j] = max(up[x] , d1[x]) + w[i];
        dfs_up(j);
    }
}
signed main()
{
    int n;
    memset(h,-1,sizeof h);
    cin>>n;
    int a,b,c;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    dfs_down(1,0);
    dfs_up(1);
    for(int i=1;i<=n;i++)
    {
        // cout<<d1[i]<<" "<<p1[i]<<" "<<d2[i]<<" "<<up[i]<<endl;
        res = min(res , max(d1[i] , up[i]));
    }
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 1072. 树的最长路径

Qjwwww
12天前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 1e4 + 10;
ll f[N];
int n;
int h[N],e[N*2],ne[N*2],w[N*2];
int idx;
int res;
void add(int a,int b,int c)
{
    e[idx] = b , ne[idx] = h[a] , w[idx] = c , h[a] = idx++;
}
int dfs(int x,int u)
{
    int dist = 0;
    int d1 = 0,d2 = 0;
    for(int i=h[x];i!=-1;i=ne[i])
    {
        int j = e[i];
        if(j==u) continue;
        int tt = dfs(j,x) + w[i];
        dist = max(dist , tt);
        if(tt > d1) d2 = d1,d1 = tt;
        else if(tt > d2) d2 = tt;
    }
    res = max(res , d1 + d2);
    return dist;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    memset(h,-1,sizeof h);
    int a,b,c;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }

    dfs(1,-1);

    cout<<res;
    return 0;
}