头像

羊羊圆又圆

吉林大学




离线:2天前


最近来访(35)
用户头像
e.Gravity
用户头像
wac@jack
用户头像
78岁扶墙对抗
用户头像
Amaryllis_
用户头像
wangyinuo23
用户头像
不高兴的兽奶
用户头像
iiiiiiiiii
用户头像
camel
用户头像
小杨爱算法
用户头像
Uebb
用户头像
Ra1nbow
用户头像
远峰
用户头像
V1
用户头像
狗蛋他爸
用户头像
Andrew1729
用户头像
201003060713
用户头像
咖啡无糖
用户头像
hh666
用户头像
lumoumou
用户头像
一塌糊涂

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

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Long a = in.nextLong();
        Long b = in.nextLong();
        Long p = in.nextLong();
        Long ans = 1L;
        for (; b > 0; b >>= 1) {
            if ((b & 1) == 1) {
                ans = ans * a % p;
            }
            a = a * a % p;
        }
        System.out.println(ans % p);
    }
}






活动打卡代码 AcWing 903. 昂贵的聘礼

#include <iostream>
#include <cstring>
#include <algorithm>


using namespace std;


const int N = 110,inf = 0x3f3f3f3f;

int n,m;
int w[N][N],level[N];
int dist[N];
bool st[N];

int dijkstra(int down ,int up)
{
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    dist[0]=0;
    for(int i=1;i<=n;i++){
        int t=-1;
        for(int j=0;j<=n;j++){
            if(st[j]==0&&(t==-1||dist[j]<dist[t])){
                t=j;
            }
        }
        st[t]=true;
        for(int j=0;j<=n;j++){
            if(level[j]>=down&&level[j]<=up){
                dist[j]=min(dist[j],dist[t]+w[t][j]);
            }
        }
    }
    return dist[1];
}
int main(){
    cin>>m>>n;
    memset(w,0x3f,sizeof w);
    for(int i=1;i<=n;i++){
        w[i][i]=0;
    }
    for(int i=1;i<=n;i++){
        int price;
        int cnt;
        cin>>price>>level[i]>>cnt;
        w[0][i] = min(price,w[0][i]);
        while(cnt--){
            int id,cost;
            cin>>id>>cost;
            w[id][i]=min(w[id][i],cost);
        }
    }
    int res=inf;
    for(int i = level[1]-m;i<=level[1];i++)res = min(res, dijkstra(i,i+m));
    cout<<res<<endl;
    return 0;
}


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

#include<bits/stdc++.h>

using namespace std;

const int N = 6;

int n;
string A,B;
string a[N],b[N];
int extend(queue<string> &q,unordered_map<string,int> &da,unordered_map<string,int> &db,string a[],string b[]){
        auto t=q.front();
        q.pop();

        for(int i=0;i<t.size();i++){
            for(int j=0;j<n;j++){
                if(t.substr(i,a[j].size())==a[j]){
                    string state = t.substr(0,i)+b[j]+t.substr(i+a[j].size());
                    if(da.count(state))continue;
                    if(db.count(state))return da[t]+1+db[state];
                    q.push(state);
                    da[state]=da[t]+1;
                }
            }
        }
    return 11;
}

int bfs(){

    if(A==B){
        return 0;
    }
    queue<string> qa,qb;
    qa.push(A);
    qb.push(B);

    unordered_map<string,int> da,db;
    da[A]=0;
    db[B]=0;
    while(qa.size()&&qb.size()){
        int t;
        if(qa.size()<=qb.size()){
            t=extend(qa,da,db,a,b);
        }
        else{
            t=extend(qb,db,da,b,a);
        }
        if(t<=10){
            return t;
        }
    }
    return -1;
}

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

    if(bfs()==-1)cout<<"NO ANSWER!"<<endl;
    else cout<<bfs()<<endl;

    return 0;
}


活动打卡代码 AcWing 175. 电路维修

#include<cstring>
#include<algorithm>
#include<iostream>
#include<deque>

using namespace std;

typedef pair<int, int> PII;

const int N = 510;

int n,m;
char g[N][N];
int d[N][N];
bool st[N][N];

int bfs(){
    memset(st, 0, sizeof st);
    memset(d,0x3f,sizeof d);
    deque<PII> q;
    q.push_back({0,0});
    d[0][0]=0;
    int dx[4]={-1,-1,1,1};
    int dy[4]={-1,1,1,-1};
    int ix[4]={-1,-1,0,0};
    int iy[4]={-1,0,0,-1};
    char cs[]="\\/\\/";

    while(q.size()){
        auto t = q.front();
        q.pop_front();

        int x=t.first;
        int y=t.second;
        if(st[x][y]==true)continue;
        st[x][y]=true;
        for(int i=0;i<4;i++){
            int a=x+dx[i];
            int b=y+dy[i];
            int j=x+ix[i];
            int k=y+iy[i];
            if(a>=0&&a<=n&&b>=0&&b<=m){
                int w=0;
                if(g[j][k]!=cs[i]){
                    w=1;
                }
                if(d[a][b]>d[x][y]+w){
                    d[a][b]=d[x][y]+w;
                    if(w){
                        q.push_back({a,b});
                    }else{
                        q.push_front({a,b});
                    }
                }
            }
        }
    }
    if(d[n][m]==0x3f3f3f3f){
        return  -1;
    }
    return d[n][m];
}

int main(){
    int T;
    cin>>T;
    while(T--){
        cin>>n>>m;
        for(int i=0;i<n;i++){
            scanf("%s",g[i]);
        }
        int t=bfs();
        if(t==-1){
            cout<<"NO SOLUTION"<<endl;
        }else{
            cout<<t<<endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 173. 矩阵距离

#include<iostream>
#include<cstring>
#include<algorithm>

#define x first
#define y second

using namespace std;
typedef pair<int,int> PII;

const int N = 1010,M =N * N;

int n,m;
char g[N][N];
PII q[M];
int dist[N][N];

void bfs(){
    int hh=0;
    int tt=-1;
    memset(dist,-1,sizeof(dist));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(g[i][j]=='1'){
                dist[i][j]=0;
                q[++tt]={i,j};
            }
        }
    }
    int dx[4]={0,0,1,-1};
    int dy[4]={-1,1,0,0};
    while(hh<=tt){
        PII t = q[hh++];
        for(int i=0;i<4;i++){
            int a=t.x+dx[i];
            int b=t.y+dy[i];
            if(a<0||a>=n||b<0||b>=m){
                continue;
            }
            if(dist[a][b]!=-1){
                continue;
            }
            dist[a][b] = dist[t.x][t.y]+1;
            q[ ++ tt] = {a,b};
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>g[i];
    }
    bfs();
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<dist[i][j]<<" ";
        }
        puts("");
    }
    return 0;
}


活动打卡代码 AcWing 164. 可达性统计

#include<iostream>
#include<cstring>
#include<algorithm>
#include<bitset>
#include <queue>

using namespace std;

const int N = 30100;

int n,m;
int h[N],e[N],ne[N];
int d[N],seq[N];
bitset<N> f[N];
int idx;

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

void toposort(){
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(d[i]==0){
            q.push(i);
        }

    }
    int k=0;
    while(q.size()){
        int t=q.front();
        q.pop();
        seq[k++]=t;
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(--d[j]==0){
                q.push(j);
            }
        }
    }
}
int main(){
    cin>>n>>m;
    memset(h, -1, sizeof h);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
        d[b]++;
    }
    toposort();
    for(int i=n-1;i>=0;i--){
        int j=seq[i];
        f[j][j]=1;
        for(int k=h[j];~k;k=ne[k]){
            f[j]|=f[e[k]];
        }
    }
    for(int i=1;i<=n;i++){
        cout<<f[i].count()<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 172. 立体推箱子

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 510;

struct state{
    int x;
    int y;
    int lie;
};

int n,m;
char g[N][N];
int dist[N][N][3];

bool check(int x,int y){
    if(x<0||x>=n||y<0||y>=m)return false;
    return g[x][y]!='#';
}

int bfs(state start,state end){
    queue<state> q;
    memset(dist,-1,sizeof dist);
    dist[start.x][start.y][start.lie]=0;
    q.push(start);

    int d[3][4][3]={
        {{-2,0,2},{0,1,1},{1,0,2},{0,-2,1}},
        {{-1,0,1},{0,2,0},{1,0,1},{0,-1,0}},
        {{-1,0,0,},{0,1,2},{2,0,0},{0,-1,2}}
    };
    while (q.size())
    {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4; i ++ )
        {
            state next = {t.x + d[t.lie][i][0], t.y + d[t.lie][i][1], d[t.lie][i][2]};

            int x = next.x, y = next.y;
            if (!check(x, y)) continue;
            if (next.lie == 0)
            {
                if (g[x][y] == 'E') continue;
            }
            else if (next.lie == 1)
            {
                if (!check(x, y + 1)) continue;
            }
            else
            {
                if (!check(x + 1, y)) continue;
            }

            if (dist[next.x][next.y][next.lie] == -1)
            {
                dist[next.x][next.y][next.lie] = dist[t.x][t.y][t.lie] + 1;
                q.push(next);
            }
        }
    }
    return dist[end.x][end.y][end.lie];
}
int main()
{
    while (scanf("%d%d", &n, &m), n || m)
    {
        for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);

        state start = {-1}, end;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (g[i][j] == 'X' && start.x == -1)
                {
                    if (g[i + 1][j] == 'X') start = {i, j, 2};
                    else if (g[i][j + 1] == 'X') start = {i, j, 1};
                    else start = {i, j, 0};
                }
                else if (g[i][j] == 'O') end = {i, j, 0};

        int res = bfs(start, end);
        if (res == -1) puts("Impossible");
        else printf("%d\n", res);
    }

    return 0;
}


活动打卡代码 AcWing 181. 回转游戏

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 24;

int op[8][7] = {
    {0, 2, 6, 11, 15, 20, 22},
    {1, 3, 8, 12, 17, 21, 23},
    {10, 9, 8, 7, 6, 5, 4},
    {19, 18, 17, 16, 15, 14, 13},
    {23, 21, 17, 12, 8, 3, 1},
    {22, 20, 15, 11, 6, 2, 0},
    {13, 14, 15, 16, 17, 18, 19},
    {4, 5, 6, 7, 8, 9, 10}
};

int opposit[8] = {5,4,7,6,1,0,3,2};
int center[8] = {6, 7, 8, 11, 12, 15, 16, 17};

int path[100];
int q[24];

int f(){
    static int sum[4];
    memset(sum,0,sizeof sum);
    for (int i = 0; i < 8; i ++ ){

        sum[q[center[i]]]++;
    }
    int mx=0;
    for(int i=1;i<=3;i++){
        mx=max(mx,sum[i]);
    }
    return 8-mx;
}

void operate(int x){
    int t = q[op[x][0]];
    for(int i=0;i<6;i++){
        q[op[x][i]]=q[op[x][i+1]];
    }
    q[op[x][6]]=t;
}

bool dfs(int u,int depth,int last){
    if(u+f()>depth){
        return false;
    }
    if(f()==0){
        return true;
    }
    for (int i = 0; i < 8; i ++ ){
        if(opposit[i]!=last){
            operate(i);
            path[u]=i;
            if(dfs(u+1,depth,i))return true;
            operate(opposit[i]);
        }
    }
    return false;
}

int main(){
    while(cin>>q[0],q[0]){
        for (int i = 1; i < N; i ++ ){
            cin>>q[i];
        }
        int depth=0;
       while(!dfs(0,depth,-1))depth++;
        if(!depth)cout<<"No moves needed"<<endl;
        else{
            for (int i = 0; i < depth; i ++ ){
                cout<<(char)(path[i]+'A');
            }
            cout<<endl;
        }
        cout<<q[6]<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 180. 排书

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15;

int w[5][N];
int q[N];
int n;

int f(){
    int tot=0;
    for(int i=0;i+1<n;i++){
        if(q[i+1]!=q[i]+1){
            tot++;
        }
    }
    return (tot+2)/3;
}

bool dfs(int u,int depth){
    if(u+f()>depth){
        return false;
    }
    if(f()==0){
        return true;
    }
    for(int len=1;len<=n;len++){
        for(int l=0;l+len-1<n;l++){
            int r=l+len-1;
            for(int k=r+1;k<n;k++){
                memcpy(w[u],q,sizeof q);
                int y=l;
                for(int x=r+1;x<=k;x++,y++){
                    q[y]=w[u][x];
                }
                for(int x=l;x<=r;x++,y++){
                    q[y]=w[u][x];
                }
                if(dfs(u+1,depth))return true;
                memcpy(q,w[u],sizeof q);
            }
        }
    }
    return false;
}

int main(){
    int T;
    cin>>T;
    while(T--){
        cin>>n;
        for (int i = 0; i < n; i ++ )cin>>q[i];
        int depth=0;
        while(depth<5&&!dfs(0,depth))depth++;
        if(depth>=5)puts("5 or more");
        else cout<<depth<<endl;
    }
    return 0;
}