头像

一秒刷完剑指Rejection


访客:1203

离线:6个月前


活动打卡代码 AcWing 91. 最短Hamilton路径

#include<bits/stdc++.h>
using namespace std;
const int maxn = 20;
int w[maxn][maxn];
int dp[1<<20][maxn];
int n;
int main(){
    cin >> n;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            cin >> w[i][j];
        }
    }
    memset(dp,0x3f,sizeof(dp));
    dp[1][0] = 0;
    for(int i = 1;i<(1<<n);i++){
        for(int j =0;j<n;j++){
            if((1<<j)&i){
                for(int k =0;k<n;k++){
                    dp[i][j] = min(dp[(i^(1<<j))][k]+w[k][j],dp[i][j]);
                }    
            }
        }
    }
    cout << dp[(1<<n)-1][n-1] << endl;
}


活动打卡代码 AcWing 118. 分形

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+7;
char grid[maxn][maxn];
int p[1000];
int n;
void prepare(int lvl,int x,int y){
    if(lvl == 1){
        grid[y][x] = 'X';
    }else{
        prepare(lvl-1,x,y);
        prepare(lvl-1,x+2*p[lvl-1],y);
        prepare(lvl-1,x+p[lvl-1],y+p[lvl-1]);
        prepare(lvl-1,x,y+2*p[lvl-1]);
        prepare(lvl-1,x+2*p[lvl-1],y+2*p[lvl-1]);
    }
}
void init(int lvl){
    memset(grid,0,sizeof(grid));
    for(int i = 1;i<=p[lvl];i++){
        for(int j = 1;j<=p[lvl];j++){
            grid[i][j] = ' ';
        }

    }
}
void print(int lvl){
    for(int i = 1;i<=p[lvl];i++){
        cout << grid[i]+1 << endl;
    }
    cout << "-" << endl;
}
int main(){
    p[1]=1;
    for(int i =2;i<=10;i++){
        p[i] = p[i-1]*3;
    }
    while(cin >> n){
        if(n<0) break;
        init(n);
        prepare(n,1,1);
        print(n);

    }
}


活动打卡代码 AcWing 278. 数字组合

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+7;
int n,m;
int dp[maxn],a[maxn];
int main(){
    cin >> n>>m;
    dp[0]=1;
    for(int i = 1;i<=n;i++){
        cin >> a[i];
        for(int j =m;j>=a[i];j--){
            dp[j] += dp[j-a[i]];
        }
    }
    cout << dp[m] << endl;
}



#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e2+7;
int selected[maxn];
int n;
void dfs(int i){
    if(i==n+1){
        for(int j=1;j<=n;j++){
            if(selected[j]) cout << j << " ";
        }
        cout << endl;
        return;
    }
    selected[i] = 1;
    dfs(i+1);
    selected[i] = 0;
    dfs(i+1);
}
int main(){
    cin >> n;
    dfs(1);
}


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

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e2+7;
int c[maxn],w,n;
int space[maxn];
int ans=1e9;
int tot;
void dfs(int x,int cost){
    if(cost>ans) return;
    if(x == n+1){
        ans = cost;
        return;
    }
    for(int i=1;i<=tot;i++){
        if(space[i]>=c[x]){
            space[i]-=c[x];
            dfs(x+1,cost);
            space[i]+=c[x];
        }
    }
    tot++;
    space[tot] = w-c[x];
    dfs(x+1,cost+1);
    tot--;
}
main(){
    cin >> n >> w;
    for(int i=1;i<=n;i++){
        cin >> c[i];
    }
    sort(c+1,c+1+n);
    reverse(c+1,c+1+n);
    dfs(1,0);
    cout <<ans << endl;
}


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

随便让dfs返回bitset就容易segmentation fault
我炸了好多次

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e4+7;
vector<int> g[maxn];
bitset<maxn> dp[maxn];

int n,m,x,y;
void dfs(int i){
    if(dp[i].any()) return;
    bitset<maxn> &cnt = dp[i];
    cnt[i]=1;
    for(auto to: g[i]){
        dfs(to);
        cnt |= dp[to];
    }
}

int main(){
    cin >> n >> m;
    for(int i = 1;i<=m;i++){
        cin >> x >> y;
        g[x].push_back(y);
    }
    for(int i =1;i<=n;i++){
        dfs(i);
        cout << dp[i].count() << endl;
    }

}



题目描述

求1+2+…+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。

样例

输入

10

输出

55

算法1

二逼做法,这已经是个梗了

时间复杂度

常数

C++ 代码

class Solution {
public:
    int getSum(int n) {
        char a[n][n+1];
        return sizeof(a)>>1;
    }
};



#pragma GCC optimize(2)

氧气优化日神仙
只用二进制优化就过了……