头像

浮沉茶客


访客:45

在线 



滚动数组

class Solution {
public:
    vector<int> numberOfDice(int n) {
        vector<vector<int>> f(2,vector<int>(n*6+1));
        f[0][0]=1;
        int a=1;
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=6*i;j++) {
                f[a&1][j]=0;  // 必须有这一步 将该位置的值清零 上一步结果干扰计数准确
                for(int k=1;k<=min(6,j);k++) {
                    if(j-k<i-1) continue; // i-1步所掷出的点数至少为i-1 
                    else f[a&1][j]+=f[a^1][j-k];
                }
            }
            a^=1;
        }
        vector<int> res;
        for(int i=n;i<=6*n;i++) res.push_back(f[a^1][i]);
        return res;
    }
};

分组背包

vector<int> numberOfDice(int n) {
        vector<int> f(6*n+1);
        f[0]=1;
        for(int i=1;i<=n;i++) {
            for(int j=i*6;j>=0;j--) {
                f[j]=0;
                for(int k=1;k<=min(j,6);k++) {
                    if(j-k<i-1) continue;
                    else f[j]+=f[j-k];
                }
            }
        }
        vector<int> res;
        for(int i=n;i<=n*6;i++) res.push_back(f[i]);
        return res;
    }



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
        dfs_s(root,res);
        return res;
    }
    /* 前序
    void dfs_s(TreeNode* root,string &res) {
        if(root==NULL) {
            res+="null ";
            return;
        }
        res += (to_string(root->val)+' ');
        dfs_s(root->left,res);
        dfs_s(root->right,res);
    }*/
    /* 后序
    void dfs_s(TreeNode* root,string &res) {
        if(!root) {
            res+=" null";
            return;
        }
        dfs_s(root->left,res);
        dfs_s(root->right,res);
        res+=(' '+to_string(root->val));
    } */
    /* 层序*/
    void dfs_s(TreeNode* root,string &res) {
        queue<TreeNode*> q;
        q.push(root);
        while(q.size()) {
            auto t=q.front();
            q.pop();
            if(!t) {
                res+="null ";
            }
            else {
                res+= (to_string(t->val)+' ');
                q.push(t->left);
                q.push(t->right);
            }            
        }
        return;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        // 后序 int u=data.size()-1;
        // 前序 int u=0;
        // 层序 int u=0;
        return dfs_d(data,u);
    }
    /*层序*/
    TreeNode* dfs_d(string data,int &u) {
        if(data[u]=='n') return NULL;
        int k=u;
        while(data[k]!=' ') k++;
        int val=0;
        for(int i=0;i<k;i++) {
            if(data[i]=='-') continue;

            val = val*10+data[i]-'0';
        }
        u=k+1;
        if(data[0]=='-') val=-val;
        TreeNode* root=new TreeNode(val);
        queue<TreeNode*> q;
        q.push(root);
        while(q.size()) {
            auto t=q.front();
            q.pop();
            int k=u;
            while(data[k]!=' ') k++;
            if(data[u]=='n') t->left=NULL;
            else {
                int val=0;
                for(int i=u;i<k;i++) {
                    if(data[i]=='-') continue;
                    val = val*10+data[i]-'0';
                }
                if(data[u]=='-') val=-val;
                t->left = new TreeNode(val);
                q.push(t->left);
            }
            u=k+1;
            k=u;
            while(data[k]!=' ') k++;
            if(data[u]=='n') t->right=NULL;
            else {
                int val=0;
                for(int i=u;i<k;i++) {
                    if(data[i]=='-') continue;
                    val=val*10+data[i]-'0';
                }
                if(data[u]=='-') val=-val;
                t->right=new TreeNode(val);
                q.push(t->right);
            }
            u=k+1;
        }
        return root;
    }
    /* 后序
    TreeNode* dfs_d(string data,int &u) {
        if(u==3) return NULL;
        int k=u;
        while(data[k]!=' ') k--;
        if(data[k+1]=='n') {
            u=k-1;
            return NULL;
        }
        int val=0;
        bool minus=false;
        for(int i=k+1;i<=u;i++) {
            if(data[i]=='-') {
                minus=true;
                continue;
            }
            val=val*10+data[i]-'0';
        }
        if(minus) val=-val;
        u=k-1;
        TreeNode* root=new TreeNode(val);
        root->right=dfs_d(data,u);
        root->left=dfs_d(data,u);
        return root;
    }*/
    /* 前序
    TreeNode* dfs_d(string data,int &u) {
       if(u==data.size()) return NULL;
       int k=u;
       while(data[k]!=' ') k++;
       if(data[u]=='n') {
           u=k+1;
           return NULL;
       }
       int val=0;
       bool minus=false;
       for(int i=u;i<k;i++) {
           if(data[i]=='-') {
               minus=true;
               continue;
           }
           val = val*10+data[i]-'0';
       }
       u=k+1;
       if(minus) val=-val;
       auto root=new TreeNode(val);
       root->left = dfs_d(data,u);
       root->right = dfs_d(data,u);
       return root;
    }*/
};


活动打卡代码 AcWing 177. 噩梦

#include<bits/stdc++.h>
using namespace std;

int n,m;
int st[805][805];
char g[805][805];
pair<int,int> boy,girl;
pair<int,int> ghost[2];

bool check(int x,int y,int step) {
    if(x<0||x>=n||y<0||y>=m||g[x][y]=='X') return false;
    for(int i=0;i<2;i++) {
        if(abs(x-ghost[i].first)+abs(y-ghost[i].second)<=step*2) return false;
    }
    return true;
}

int bfs() {
    int dx[4]={-1,0,1,0};
    int dy[4]={0,-1,0,1};
    int cnt=0;
    memset(st,0,sizeof(st));
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(g[i][j]=='M') boy={i,j};
            else if(g[i][j]=='G') girl={i,j};
            else if(g[i][j]=='Z') ghost[cnt++]={i,j};
        }
    }
    int step=0;
    queue<pair<int,int>> qb,qg;
    qb.push(boy),qg.push(girl);
    while(qb.size()||qg.size()) {
        step++;
        for(int i=0;i<3;i++) {
            for(int j=0,len=qb.size();j<len;j++) {
                auto t=qb.front();
                qb.pop();
                int x=t.first,y=t.second;
                if(!check(x,y,step)) continue;
                for(int k=0;k<4;k++) {
                    int a=x+dx[k],b=y+dy[k];
                    if(check(a,b,step)) {
                        if(st[a][b]==2) return step;
                        if(!st[a][b]) {
                            st[a][b]=1;
                            qb.push({a,b});
                        }
                    }
                }
            }
        }
        for(int i=0;i<1;i++) {
            for(int j=0,len=qg.size();j<len;j++) {
                auto t=qg.front();
                qg.pop();
                int x=t.first,y=t.second;
                if(!check(x,y,step)) continue;
                for(int k=0;k<4;k++) {
                    int a=x+dx[k],b=y+dy[k];
                    if(check(a,b,step)) {
                        if(st[a][b]==1) return step;
                        if(!st[a][b]) {
                            st[a][b]=2;
                            qg.push({a,b});
                        }
                    }
                }
            }
        }
    }
    return -1;
}

int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        scanf("%d %d",&n,&m);
        for(int i=0;i<n;i++) {
            scanf("%s",g[i]);
        }
        printf("%d\n",bfs());
    }
    return 0;
}


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

#include<bits/stdc++.h>
using namespace std;

const int N=1010;
const int M=20010;
const int C=1010;
struct Point {
    int d,u,c;
    bool operator< (const Point&W) const {
        return d>W.d;
    }
};

int h[N],e[M],ne[M],w[M],price[N],idx=0;
int n,m;
int dist[N][C];
int st[N][C];

void add(int a,int b,int c) {
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx;
    idx++;
}

int dijkstra(int c,int start,int end) {
    priority_queue<Point> heap;
    memset(st,false,sizeof st);
    memset(dist,0x3f3f,sizeof dist);
    heap.push({0,start,0});
    while(heap.size()) {
        Point t=heap.top();
        heap.pop();
        if(t.u==end) return t.d;
        if(st[t.u][t.c]) continue;
        st[t.u][t.c]=true;
        if(t.c<c) {
            if(dist[t.u][t.c+1]>t.d+price[t.u]) {
                dist[t.u][t.c+1]=t.d+price[t.u];
                heap.push({dist[t.u][t.c+1],t.u,t.c+1});
            }
        }
        for(int i=h[t.u];i;i=ne[i]) {
            if(t.c>=w[i]) {
                int j=e[i];
                if(dist[j][t.c-w[i]]>t.d) {
                    dist[j][t.c-w[i]]=t.d;
                    heap.push({t.d,j,t.c-w[i]});
                }
            }
        }
    }
    return -1;
}


int main() {
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++) {
        scanf("%d",&price[i]);
    }
    for(int i=0;i<m;i++) {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }
    int query;
    scanf("%d",&query);
    while(query--) {
        int c,s,e;
        scanf("%d %d %d",&c,&s,&e);
        int t=dijkstra(c,s,e);
        if(t==-1) printf("impossible\n");
        else printf("%d\n",t);
    }
}


活动打卡代码 AcWing 90. 64位整数乘法

浮沉茶客
1个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<bits/stdc++.h>
using namespace std;

int main() {
    long long a,b,p,ans=0;
    scanf("%lld %lld %lld",&a,&b,&p);
    for(;b;b>>=1) {
        if(b&1) ans=(ans+a)%p;
        a=a*2%p;
    }
    printf("%lld\n",ans);
    return 0;
}


活动打卡代码 AcWing 89. a^b

浮沉茶客
1个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<bits/stdc++.h>
using namespace std;

int main() {
    int a,b,p;
    scanf("%d %d %d",&a,&b,&p);
    int ans=1%p;
    for(;b;b>>=1) {
        if(b&1) ans= (long long)ans*a%p;
        a=(long long)a*a%p;
    }
    printf("%d\n",ans);
    return 0;
}