头像

薛微有点困




离线:2小时前


最近来访(23)
用户头像
草莓啵啵益菌多啦
用户头像
扮山妖走到半山腰
用户头像
Overthink
用户头像
洋.
用户头像
OI
用户头像
itdef
用户头像
mmmmm
用户头像
师天下_swy
用户头像
wKingYu
用户头像
zhengnengliang
用户头像
pacer
用户头像
就是要AC
用户头像
羽球帝
用户头像
尹范
用户头像
l_y_f
用户头像
看不到我
用户头像
NZX
用户头像
zufestudy12
用户头像
WA自由人
用户头像
干净又卫生胸弟们

活动打卡代码 AcWing 1112. 迷宫

#include<iostream>
#include<cstring>
using namespace std;
const int N=110;
char migong[N][N];
bool st[N][N];
pair<int,int> a,b;
int n;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
bool dfs(int x,int y){
    if(x==b.first && y==b.second) return true;
    st[x][y]=true;
    for(int i=0;i<4;i++){
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx<0||xx>=n||yy<0||yy>=n) continue;
        if(st[xx][yy]||migong[xx][yy]=='#') continue;
        if(dfs(xx,yy)) return true;//当前这个点能走到b点,返回true,好给上一层一个返回值,结束递归
    }
    return false;
}
int main(){
    int k;
    cin>>k;
    while(k--){
        cin>>n;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                cin>>migong[i][j];
        cin>>a.first>>a.second>>b.first>>b.second;
        if(migong[a.first][a.second]=='#'||migong[b.first][b.second]=='#'){//不讲武德,居然站在墙里
            puts("NO");
            continue;
        }
        memset(st,0,sizeof st);
        if(dfs(a.first,a.second)) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 1097. 池塘计数

#include<iostream>
using namespace std;
typedef pair<int,int> pii;
const int N=1010,M=N*N;//!!注意队列里的数据范围是N*N
bool st[N][N];
char farm[N][N];
pii duilie[M];//这里是M
int n,m,ans;
void bfs(int x,int y){
    int hh=0,tt=0;//自己建队列
    duilie[0]={x,y};
    st[x][y]=true;
    while(hh<=tt){//这里的队列里如果有值临界状态是hh==tt
        pii x=duilie[hh++];//队列头出队
        for(int i=x.first-1;i<=x.first+1;i++)
            for(int j=x.second-1;j<=x.second+1;j++)
                {
                    if(i==x.first && j==x.second) continue;//巧妙是不用写int dx[8]={1,1,1,0,0,-1,-1,-1};
                                                            //int dy[8]={1,0,-1,1,-1,1,0,-1};
                                                            //但是仍应注意不要把自己写进去
                    if(i<0||i==n||j<0||j==m) continue;
                    if(st[i][j]||farm[i][j]=='.') continue;
                    duilie[++tt]={i,j};//队尾入队
                    st[i][j]=true;
                }

    }
}
int main(){

    cin>>n>>m;
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
        cin>>farm[i][j];//这里只能用cin,scanf容易出错

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(farm[i][j]=='W' && !st[i][j])
                {
                    bfs(i,j);
                    ans++;
                }
    cout<<ans;
    return 0;
}



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

#include<iostream>
#include<algorithm>
using namespace std;
const int N=20;
int cat[N],taxi[N],ans=N;
    int n,w;
void dfs(int cat_num,int taxi_num){
    if(taxi_num>=ans) return;
    if(cat_num==n) {
    ans=taxi_num;
        return;
    }

    for(int i=0;i<taxi_num;i++){
        if(cat[cat_num]+taxi[i]<=w){
            taxi[i]+=cat[cat_num];
            dfs(cat_num+1,taxi_num);
            taxi[i]-=cat[cat_num];
        }
    }
    taxi[taxi_num]=cat[cat_num];
    dfs(cat_num+1,taxi_num+1);
    taxi[taxi_num]=0;
}
int main(){
    cin>>n>>w;
    for(int i=0;i<n;i++) cin>>cat[i];
    sort(cat,cat+n);
    reverse(cat,cat+n);
    dfs(0,0);
    cout<<ans;
    return 0;
}


活动打卡代码 AcWing 433. ISBN号码

#include<iostream>
using namespace std;
int main(){
    string str;
    int sum=0;
    int shibiema;
    cin>>str;
    for(int i=0,j=1;i+1<str.size();i++){
        if(str[i]!='-'){
            sum+=(str[i]-'0')*j;
            j++;
        }

    }
    shibiema=sum%11;
    if(shibiema==10 ) 
    {
        if(str.back()=='X') cout<<"Right";
        else  {
            str[str.size()-1]='X';
            cout<<str;
        }
    }else{
        if(shibiema==str.back()-'0') cout<<"Right";
        else  {
            str[str.size()-1]=shibiema+'0';
            cout<<str;
        }
    }

    return 0;
}



二叉树的深度遍历和先根遍历基本上是一样的,只是先根遍历有左右之分,而深度遍历没有左右之分。而且二叉树通常只用先根、中根、后根。一般树和图用广度和深度遍历。
无参数版本

`#include<iostream>
using namespace std;
int n,party[10];
bool st[10];
int cnt;
void dfs(){

    if(cnt==n){
        for(int i=1;i<=n;i++) cout<<party[i]<<" ";
        puts("");
        return;
    }
    for(int i=1;i<=n;i++){
        if(!st[i]){

            st[i]=true;
            party[++cnt]=i;
            dfs();
            st[i]=false;
            cnt--;
        }
    }

}
int main(){

    cin>>n;
    dfs();
    return 0;
}
`


活动打卡代码 AcWing 885. 求组合数 I

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2010, mod = 1e9 + 7;


int c[N][N];


void init()
{
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j <= i; j ++ )
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}


int main()
{
    int n;

    init();

    scanf("%d", &n);

    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);

        printf("%d\n", c[a][b]);
    }

    return 0;
}


活动打卡代码 AcWing 754. 平方矩阵 II

#include <iostream>
#include <algorithm>

using namespace std;

int n;

int main()
{
    while (cin >> n)
    {
        for (int i = 0; i < n; i ++ )
        {
            for (int j = 0; j < n; j ++ )
                cout << abs(i - j) + 1 << ' ';  // 规律

            cout << endl;
        }

        if (n) cout << endl;
    }

    return 0;
}  




活动打卡代码 AcWing 737. 数组替换

#include <cstdio>

int main()
{
    int x[10];

    for (int i = 0; i < 10; i ++ ) scanf("%d", &x[i]);

    for (int i = 0; i < 10; i ++ )
        if (x[i] <= 0)
            x[i] = 1;

    for (int i = 0; i < 10; i ++ ) printf("X[%d] = %d\n", i, x[i]);

    return 0;
}


活动打卡代码 AcWing 419. FBI树

#include<iostream>
#include<string.h>
using namespace std;
void dfs(string str,int l,int r){
    int qujian=r-l;
    int zero=0,one=0;
    int mid=l+qujian/2;
    if(r!=l){
        dfs(str,l,mid);
        dfs(str,mid+1,r);
    }
    for(int i=l;i<=r;i++){
        if(str[i]=='0') zero++;
        else one++;
    }
    if(zero && one) cout<<"F";
    else if(zero) cout<<"B";
    else cout<<"I";

}
int main(){
    int N;
    string str;
    cin>>N>>str;
    dfs(str,0,str.size()-1);
    return 0;

}



区间dp麻烦版

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int i=1;
        int res[1010],f[1010][1010];
        memset(res,0,sizeof res);
        memset(f,0,sizeof f);
        for(int i=0;i<nums.size();i++) res[i]=nums[i];
        for(int i=0;i<nums.size();i++) f[i][i]=nums[i];
        for(int len=2;len<=nums.size();len++){
        for(int i=0;i+len-1<=nums.size();i++){
            int l=i,r=i+len-1;
            f[l][r]=max(res[r],f[l][r-1]+res[r]);
        }
    }
    int max_res=INT_MIN;
    for(int i=0;i<nums.size();i++) max_res=max(max_res,f[0][i]);
    return max_res;
    }
};