头像

eugoualice




离线:14小时前


最近来访(22)
用户头像
啊北
用户头像
jion0.0
用户头像
广东理工学院_第一届ACC决赛
用户头像
@1@_8
用户头像
笠笠日记
用户头像
hellozmc
用户头像
人生如戏ba

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

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

using namespace std;

const int N = 30;
char q[N][N];
int n ,m,res;

int dx[4] = {1, 0 , -1 , 0} , dy[4] = {0 , 1 , 0 ,-1};

int dfs(int sx ,int sy){
    int res = 1;
    q[sx][sy] = '#';
    for (int i = 0; i < 4; i++) {
        int a = sx + dx[i], b = sy + dy[i];
        if (a >= 0 && a < n && b >= 0 && b < m && q[a][b] == '.')
            res += dfs(a, b);
    }
    return res;
}

int main(){

   while(cin >> m >> n , m || n){
    for(int i = 0 ; i< n ; i++)cin >> q[i];
    int x , y;

    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m; j++){
            if(q[i][j] == '@'){
             x = i;
             y = j;
            }
        }
    }
    cout << dfs(x , y) << endl;
   }
   return 0;
}


活动打卡代码 AcWing 1112. 迷宫

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

using namespace std;

const int N = 110;
int n;
char a[N][N];

typedef pair<int , int> PII;

int dx[4] = {0 , 1 , 0 , -1} , dy[4] = {1 , 0 , -1 , 0};

bool dfs(int a1,int b1,int a2,int b2,int n){
    if(a1 == a2 && b1 == b2) return 1;

    a[a1][b1] = '#';
    for(int i = 0 ; i< 4 ; i++){
        int x = dx[i] + a1 , y = dy[i] + b1;
        if(x >= 0 && x < n && y >= 0 && y < n && a[x][y] == '.'){
            if(dfs(x , y , a2 , b2 , n)) return 1;
        }
    }

    return 0;
}

int main(){
    int k ;
    scanf("%d" , &k);

    while(k--){
    scanf("%d" , &n);
    for(int i = 0 ; i < n ; i++){
        scanf("%s" , &a[i]);
    }

    int a1 , b1 , a2 , b2;
    scanf("%d%d%d%d" , &a1 , &b1 , &a2 , &b2);

    if(a[a1][b1] == '#' || a[a2][b2] == '#'){
        puts("NO");
        continue;
    }

    puts(dfs(a1 , b1 , a2 , b2 ,n)?"YES":"NO");  

    }
    return 0;
}




算法1

不知道怎么说,感觉就是这样吧,大于n - 1 , 小于0的就返回-1.如果有重复的就返回重复的值,然后啥条件都没有满足就返回-1

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        sort(nums.begin() , nums.end());

        for(auto x : nums)
        if(x < 0 || x > nums.size() - 1) return -1;

        for(int i = 1 ; i <= nums.size() ; i++){
            if(nums[i - 1] == nums[i]){
                int x = nums[i];
                return x;
            }
        }
        return -1;
    }
};



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

using namespace std;

const int N = 1010;

int n;
int a[N] , f[N];

int main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i++) cin >> a[i];

    int res = 0;

    for(int i = 1 ; i <= n ; i++){
        f[i] = a[i];
        for(int j = 1 ; j < i ; j++){
            if(f[i] > f[j]) f[i] = max(f[i] , f[j] + a[i]);
        }
        res = max(res , f[i]);
    }

    cout << res <<endl;
    return 0;
}


活动打卡代码 AcWing 1012. 友好城市

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

using namespace std;

const int N = 5010;
int a[N];
int n ,res;

typedef pair<int , int> PII;

PII q[N];

int main(){
    cin >> n;
    for(int i = 0; i < n ; i++) cin >> q[i].first >> q[i].second;

    sort(q , q + n);

    for(int i = 0; i <= n ; i++){
        a[i] = 1;
        for(int j = 0; j < i ; j++){
            if(q[i].second > q[j].second) a[i] = max(a[i] , a[j] + 1);
        }
        res = max(a[i] , res);
    }
    cout <<res <<endl;
    return 0;
}



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

using namespace std;

const int N = 10010;

int n , m  ,res;
int f[N] , a[N] , dp[N];

int main(){
    cin >> n;
    while(n --){

        cin >> m;
        for(int i = 1; i <= m ; i++) cin >> f[i];

        res = 0;
        for(int i = 1 ; i <= m ; i++){
            a[i] = 1;
            for(int j = 1; j < i ; j++){

                if(f[i] > f[j])a[i] = max(a[i] , a[j] + 1); 
                res = max(a[i] , res);
            }
        }

        for(int i = m; i ; i--){
            a[i] = 1;
            for(int j = m; j > i ; j--){

                if(f[i] > f[j])a[i] = max(a[i] , a[j] + 1);
                res = max(a[i] , res);
            }
        }
        cout << res <<endl;

    }
    return 0;
}


活动打卡代码 AcWing 482. 合唱队形

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

using namespace std;

const int N = 110;
int f[N] , g[N] , dp[N];
int n ,res;

int main(){
    cin >> n;
    for(int i = 1; i <= n ; i++) cin >> f[i];

    for(int i = 1; i <= n ; i++){
        g[i] = 1;
        for(int j = 1; j < i ; j++){
            if(f[i] > f[j])g[i] = max(g[i] , g[j] + 1); 
        }
    }

    for(int i = n ; i > 0; i--){
        dp[i] = 1;
        for(int j = n ; j > i ;j --){
            if(f[i] > f[j])dp[i] = max(dp[i] , dp[j] + 1);
        }
    }

    res = 0;
    for(int i = 1; i <= n ; i ++){
        res = max(res , g[i] + dp[i] - 1);
    }

    cout << n - res <<endl;
    return 0;
}


活动打卡代码 AcWing 1014. 登山

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

using namespace std;

const int N= 1010;
int a[N] , f[N] , dp[N];
int n , res , cnt;

int main(){
    cin >> n;
    for(int i = 1; i <= n ; i++)cin >> a[i];

    for(int i = 1; i <= n ; i++){
        f[i] = 1;
        for(int j = 1; j < i ; j++){
            if(a[i] > a[j]) f[i] = max(f[j] + 1 , f[i]); 
        }
    }

    for(int i = n; i >= 1  ; i--){
        dp[i] = 1;
        for(int j = n; j > i ; j--){
            if(a[i] > a[j])dp[i] = max(dp[j] + 1 , dp[i]);
        }
    }


    for(int i = 1 ; i <= n ; i++){
        res = max(res , f[i] + dp[i] - 1);
    }
    cout << res <<endl;
    return 0;
}


活动打卡代码 AcWing 423. 采药

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

using namespace std;

const int N = 1010;

int n , m;
int f[N];
int v , w;

int main(){
    cin >> n >> m;
    for(int i = 1; i <= m ;i++){ 
        cin >> v >> w;
        for(int j = n; j >= v ; j--){
            f[j] = max(f[j] , f[j - v] + w);
        }

    }

    cout <<f[n] <<endl;
    return 0;
}



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

using namespace std;

const int N = 100010;
int n;
long long a[N];

int main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i++) cin >> a[i];
    int max_ = -1e18;


    int res = 1;
    int depth = 1;
    for(int i = 1; i <= n ; i*=2){
        long long s = 0;
        for(int j = i ; j <= i*2 - 1 && j  <= n; j++){
            s += a[j];
        }

        if(s > max_){
            max_ = s;
            res = depth;
        }

        depth++;
    }

    cout << res <<endl;
    return 0;
}