头像

WBSLZF


访客:2823

离线:20小时前


活动打卡代码 AcWing 166. 数独

WBSLZF
2天前
#include <iostream>

using namespace std;
const int N  = 9, M = 1 << N ;
int ones[M],map[M];
string s;
int row[N],col[N],maze[3][3];
void init()
{
    int num = (1 << N) - 1;
    for(int i = 0;i<N;i++)  col[i] = row[i] = num;
    for(int i = 0;i < 3;i++)
        for(int j = 0;j < 3;j++) maze[i][j] = num;
}
void draw(int x,int y,int num,bool flag)
{
    if(flag) s[x * N + y] = num + '1';
    else s[x * N + y] = '.';
    int number = 1 << num;
    if(!flag) number = -number;
    row[x] -= number;
    col[y] -= number;
    maze[x / 3][y / 3] -= number;
}
int get(int i,int j)
{
    return row[i] & col[j] & maze[i / 3][j / 3];
}
int lowbit(int x)
{
    return x & -x;
}
bool dfs(int cnt)
{
    if(!cnt) return true;
    int minn = 10;
    int x,y;
    for(int i = 0;i<N;i++)
        for(int j = 0;j<N;j++)
        if(s[i * N + j] == '.')
        {
            int state = get(i,j);
            if(ones[state] < minn) 
            {
                x = i;
                y = j;
                minn = ones[state];
            }
        }
    int state = get(x,y);
    for(int i = state;i;i -= lowbit(i))    
    {
        int t = map[lowbit(i)];
        draw(x,y,t,true);
        if(dfs(cnt-1)) return true;
        draw(x,y,t,false);
    }
    return false;
}
int main(void)
{
    for(int i = 0;i<N;i++) map[1 << i] = i;
    for(int i = 0;i< M;i++) 
        for(int j = 0;j<N;j++) 
            if((i >> j) & 1) ones[i] ++;
    while(cin>>s && s[0] != 'e')
    {
        init();
        int cnt = 0;
        for(int i = 0;i < N;i++)
            for(int j = 0;j < N;j ++)
            if(s[i * N + j] == '.' ) cnt ++;
            else draw(i,j,s[i * N + j] - '1',true);

        dfs(cnt);
        cout<<s<<endl;
    }
    return 0;
}


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

WBSLZF
4天前
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 20;
int con[N],weight[N];
int n,w ,ans = N;
bool st[N];
void dfs(int u,int uc,int gc,int start)
{
    if(u >= ans) return ;
    if(gc == n) ans = u;
    bool flag = true; 
    for(int i = start;i < n;i++)
    if(!st[i] && weight[i] + con[u] <= w)
    {
        st[i] = true;
        con[u] += weight[i];
        dfs(u,uc+1,gc+1,i);
        st[i] = false;
        con[u] -= weight[i];
        flag = false;
        if(!uc) break;
    }
    if(flag) dfs(u+1,0,gc,0);
}
bool cmp(int a,int b)
{
    return a > b;
}
int main(void)
{
    cin>>n>>w;
    for(int i = 0;i<n;i++) cin>>weight[i];
    sort(weight,weight+n,cmp);
    dfs(1,0,0,0);
    cout<<ans<<endl;
    return 0;
}


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

WBSLZF
7天前
#include  <iostream>
#include <cstring>

using namespace std;
const int N = 20;
int n;
bool st[N];
int group[N][N],s[N],ans = N;
int gcd(int a,int b)
{
    return b?gcd(b,a % b):a;
}
bool check(int group[],int gc,int pos)
{
    for(int i = 0;i<gc;i++)
    if(gcd(s[group[i]],s[pos]) != 1) return false;
    return true;
}
void dfs(int g,int gc,int tc,int start)//g代表当前用到第几组,gc代表当前枚举到第g组第几个位置,tc代表当前枚举当第几个数
{
    if(g >= ans) return ;
    if(tc == n)
    {
        ans = g;
        return;
    }
    bool  flag = true;
    for(int i = start;i<n;i++)
    if(!st[i] && check(group[g],gc,i))
    {
        st[i] = true;
        group[g][gc] = i;
        dfs(g,gc+1,tc+1,i + 1);
        st[i] = false;
        flag = false;
        if(gc == 0) break;
    }
    if(flag) dfs(g+1,0,tc,0);
}
int main(void)
{
    cin>>n;
    for(int i = 0;i<n;i++) cin>>s[i];
    dfs(1,0,0,0);
    cout<<ans<<endl;
    return 0;
}


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

WBSLZF
8天前

#include <iostream>
#include <unordered_map>
#include <cstdio>

using namespace std;
const int N = 20  + 10;
int n;
unordered_map<string,int> vis;
string ss[N];
pair<string,bool> change(string str,string s)//第二个参数判断是否可以接在后面
{
    int n = str.size(), m = s.size();
    string ans = "";
    bool flag = false;
    if(str.size() == 1 && str[0] ==  s[0])//当为首字母时特判一下
    {
        ans = s;
        flag = true;
    }
    else
    {
        for(int  i =  1;i< min(n,m);i++)//在有许多重合部分时,枚举最短的重合部分达到最长
        {
            string temp = str.substr(n-i),temp2 =  s.substr(0,i);
            if(temp == temp2) 
            {
                ans = str + s.substr(i);
                flag = true;
                break;
            }
        }        
    }

    return  make_pair(ans,flag);
}
int dfs(string start)
{
    int len = 0;
    len = max(len,(int)start.size());
    for(int i = 0;i<n;i++)
    if(vis[ss[i]] < 2)
    {
        vis[ss[i]] ++;
        pair<string,bool> p = change(start,ss[i]);
        if(p.second) len = max(len,dfs(p.first));        
        vis[ss[i]] --;
    }
    return  len;
}
int main(void)
{
    scanf("%d",&n);

    for(int i = 0;i<n;i++) cin>>ss[i];
    string start;
    cin>>start;
    cout<<dfs(start)<<endl;
    return 0;
}


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

WBSLZF
8天前
#include <iostream>
#include <cstring>
using namespace  std;

const int N = 20;

bool st[N][N];
int n ,m;

int dx[] = {-2,-2,-1,1,2,2,1,-1},dy[] = {-1,1,2,2,1,-1,-2,-2};
int dfs(int sx,int sy,int step)
{
    int cnt= 0;
    st[sx][sy] = true;
    if(step == n * m)
    {
        cnt ++;
        return cnt;
    }
    for(int i = 0;i<8;i++)
    {
        int x = sx + dx[i],y = sy + dy[i];
        if(x < 0 || x >= n || y < 0 || y >= m) continue;
        if(st[x][y]) continue;
        cnt += dfs(x,y,step + 1);
        st[x][y] =false;
    }
    return cnt;
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int x,y;
        cin>>n>>m>>x>>y;
        memset(st,false,sizeof st);
        cout<<dfs(x,y,1)<<endl;
    }
    return 0;
}


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

WBSLZF
10天前
#include <iostream>
#include <cstring>
using namespace std;

const int N = 30;
char g[N][N];
bool st[N][N];
int n,m,cnt;
int  dx[]  = {-1,0,1,0},dy[] = {0,1,0,-1};
void dfs(int sx,int sy)
{
    cnt++;
    st[sx][sy] = true;

    for(int i = 0;i<4;i++)
    {
        int x = sx + dx[i],y = sy + dy[i];
        if(x < 0 || x >= n || y < 0 || y >= m) continue;
        if(g[x][y] != '.') continue;
        if(st[x][y])    continue;
        dfs(x,y);
    }
}
int  main(void)
{
    while(cin>>m>>n,n && m)
    {
        cnt = 0;
        memset(st,false,sizeof st);
        int sx,sy;
        for(int i = 0;i<n;i++) scanf("%s",g[i]);
        for(int i = 0;i<n;i++)
            for(int j = 0;j<m;j++) if(g[i][j] == '@') sx = i,sy = j;
        dfs(sx,sy);
        cout<<cnt<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 1112. 迷宫

WBSLZF
10天前
#include <cstring>
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 110;
char g[N][N];
int n,ex,ey;
bool st[N][N];
int dx[] = {-1,0,1,0},dy[] =  {0,1,0,-1};
bool dfs(int sx,int sy)//两种到达终点的方式,本身就到达,或者通过其他方式到达
{

    st[sx][sy] = true;
    if(g[sx][sy] != '.')  return false;
    if(sx == ex && sy == ey) return true;
    for(int i = 0;i<4;i++)
    {
        int x = sx + dx[i],y = sy + dy[i];
        if(x < 0 || x >= n || y < 0 || y >= n) continue;
        if(st[x][y]) continue;
        st[x][y] = true;
        if(dfs(x,y)) return true;//如果只是dfs(x,y)则少了一条可以到达的点
        //为什么不加st[x][y] = false,因为通过(x,y)不能到达的点不需要状态还原
    }
    return false;
}
int main(void)
{
    int k;
    scanf("%d",&k);
    while(k--)
    {
        scanf("%d",&n);
        memset(st,false,sizeof st);
        for(int i =  0;i<n;i++)  scanf("%s",g[i]);
        int sx,sy;
        scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
        if(dfs(sx,sy)) puts("YES");
        else puts("NO");
    }
    return 0;
}


活动打卡代码 AcWing 176. 装满的油箱

WBSLZF
11天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1e3 + 10,C = 110,M = 2e4 + 10;
int h[N],e[M],ne[M],w[M],idx = 1,n,m,price[N];
void add(int a,int b,int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++;
}
struct po{
    int d,n,c;
    bool operator < (const po &t) const{
        return d > t.d;
    }
    po (int d,int n,int c)
    {
        this->d = d;this->n = n;this->c = c;
    }
};
bool st[N][C];
int dis[N][C];
int dijkstra(int s,int end,int c)
{
    memset(dis,0x3f,sizeof(dis));
    memset(st,false,sizeof(st));
    priority_queue<po> heap;
    heap.push(po(0,s,0));
    dis[s][0] = 0;

    while(heap.size())
    {
        po s = heap.top();
        heap.pop();

        int d = s.d,now = s.n,sav = s.c;
        if(st[now][sav]) continue;
        st[now][sav] = true;
        if(now == end) return dis[now][0];

        if(sav < c)
        {
            if(dis[now][sav + 1] > dis[now][sav] + price[now])
            {
                dis[now][sav + 1] = dis[now][sav] + price[now];
                heap.push(po(dis[now][sav + 1] ,now,sav+1));
            }
        }
        for(int i = h[now];~i;i = ne[i])
        {
            int b = e[i];
            if(sav >= w[i])
            {
                if(dis[b][sav - w[i]] > dis[now][sav])
                {
                    dis[b][sav-w[i]] = dis[now][sav];
                    heap.push(po(dis[b][sav-w[i]],b,sav-w[i]));
                }
            }
        }
    }
    return  -1;
}
int main(void)
{
    memset(h,-1,sizeof(h));
    scanf("%d%d",&n,&m);
    for(int i = 0;i<n;i++) scanf("%d",&price[i]);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    int q;
    scanf("%d",&q);
    while(q--)
    {
        int c,s,e;
        scanf("%d%d%d",&c,&s,&e);
        int t = dijkstra(s,e,c);
        if(t == -1) puts("impossible");
        else printf("%d\n",t);
    }
    return 0;
}


活动打卡代码 AcWing 178. 第K短路

WBSLZF
13天前
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#define x first
#define y second
using namespace std;
const int N = 1e3 + 10,M = 2e5 + 10;
int h[N],rh[N],ne[M],e[M],w[M],idx;
bool st[N];
int dist[N],S,T,K;
typedef pair<int,int> pll;
int cnt[N];
void add(int t[],int a,int b,int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = t[a];
    t[a] = idx ++;
}
void dijkstra()
{
    memset(dist,0x3f3f3f3f,sizeof dist);
    priority_queue<pll,vector<pll>,greater<pll> > heap; 
    heap.push(make_pair(0,T));
    dist[T] = 0;

    while(heap.size())
    {
        pll s = heap.top();
        heap.pop();

        int ver = s.y;
        if(st[ver]) continue;
        st[ver] = true;

        for(int i = rh[ver];~i;i = ne[i])
        {
            int b = e[i];
            if(dist[b] > dist[ver] + w[i])
            {
                dist[b] = dist[ver] + w[i];
                heap.push(make_pair(dist[b],b));
            }
        }
    }
}

int astar()
{

    pll p = make_pair(dist[S],S);
    priority_queue<pll,vector<pll>,greater<pll>> heap;
    heap.push(p);
    if(dist[0] == dist[S]) return -1;
    while(heap.size())
    {
        pll s = heap.top();
        heap.pop();
        int ver = s.y,distance = s.x - dist[ver];
        cnt[ver] ++;
        if(cnt[T] == K) return distance;
        for(int i = h[ver];~i;i = ne[i])
        {
            int b = e[i];
            if(cnt[b] < K) heap.push(make_pair(distance + w[i] + dist[b],b));
        }
    }
    return -1;
}
int main(void)
{
    int n, m;
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    memset(rh,-1,sizeof rh);

    for(int i = 0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(h,a,b,c);
        add(rh,b,a,c);
    }
    scanf("%d%d%d",&S,&T,&K);
    if(S == T) K++;
    dijkstra();
    printf("%d\n",astar());
    return 0;
}




WBSLZF
13天前

代码如下

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#define x first
#define y second
using namespace std;
const int N = 1e3 + 10,M = 2e5 + 10;
int h[N],rh[N],ne[N],e[N],w[N],idx;
bool st[N];
int dist[N],S,T,K;
typedef pair<int,int> pll;
int cnt[N];
void add(int t[],int a,int b,int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = t[a];
    t[a] = idx ++;
}
void dijkstra()
{
    memset(dist,0x3f3f3f3f,sizeof dist);
    priority_queue<pll,vector<pll>,greater<pll> > heap; 
    heap.push(make_pair(0,T));
    dist[T] = 0;

    while(heap.size())
    {
        pll s = heap.top();
        heap.pop();

        int ver = s.y;
        if(st[ver]) continue;
        st[ver] = true;

        for(int i = rh[ver];~i;i = ne[i])
        {
            int b = e[i];
            if(dist[b] > dist[ver] + w[i])
            {
                dist[b] = dist[ver] + w[i];
                heap.push(make_pair(dist[b],b));
            }
        }
    }
}

int astar()
{

    pll p = make_pair(dist[S],S);
    priority_queue<pll,vector<pll>,greater<pll>> heap;
    heap.push(p);
    if(dist[0] == dist[S]) return -1;
    while(heap.size())
    {
        pll s = heap.top();
        heap.pop();
        int ver = s.y,distance = s.x - dist[ver];
        cnt[ver] ++;
        if(cnt[T] == K) return distance;
        for(int i = h[ver];~i;i = ne[i])
        {
            int b = e[i];
            if(cnt[b] < K) heap.push(make_pair(distance + w[i] + dist[b],b));
        }
    }
    return -1;
}
int main(void)
{
    int n, m;
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    memset(rh,-1,sizeof rh);

    for(int i = 0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(h,a,b,c);
        add(rh,b,a,c);
    }
    scanf("%d%d%d",&S,&T,&K);
    if(S == T) K++;
    dijkstra();
    printf("%d\n",astar());
    return 0;
}