头像

拉倒i


访客:198

离线:2天前


活动打卡代码 AcWing 96. 奇怪的汉诺塔

拉倒i
3天前
#include<iostream>
#include<cstring>
const int N  = 15;
using namespace std;
int main(){
    int d[N] , f[N];
    d[0] = 0;
    for(int i = 1 ; i <= 12; i++)
           d[i] = 2 * d[i - 1] + 1;  //当有三个盘子的时候 十二个塔的移动次数 d[1] 表示移动一个塔需要的次数
    memset(f , 0x3f , sizeof f);
    f[0] = 0;
    for(int i = 1 ;i <= 12; i++){
        for(int j = 0 ; j < i; j++){
            f[i] = min(f[i], f[j] * 2 + d[i - j] );  //先挪走j个塔 再挪走i - j 个塔 
        }
    }
    for(int i = 1; i <= 12; i++)
      cout<<f[i]<<endl;
      return 0;
}


活动打卡代码 AcWing 95. 费解的开关

拉倒i
1个月前
#include<iostream>
#include<cstring>
using namespace std;
const int N = 10;
const int INF = 0x3f3f3f3f;
char g[N][N]; 
int dx[] = {0, 1, 0, -1, 0};
int dy[] = {0, 0, -1, 0, 1};
int T;
void turn(int x, int y){
    for(int i = 0 ; i < 5 ;i ++){
        int nx = x + dx[i], ny = y + dy[i];
        if(nx >=0 && nx < 5 && ny >= 0 && ny < 5)
           g[nx][ny] ^= 1; //0 置为1 1 置为0
    }
}
int work(){
    int res = INF;
    for(int i = 0 ; i < 1 << 5;i++){
         char backup[N][N];
         int step = 0;
         memcpy(backup, g, sizeof g); //备份数组g
         for(int j = 0 ; j < 5 ; j++){
             if(i >>j & 1){  //如果这个点按
                 step ++;
                 turn(0,j);
             }
         }
         for(int k = 0 ; k < 4; k++){
             for(int j = 0 ; j < 5; j++){
                 if(g[k][j] == '0'){ //如果这个点还是0 则按下一排
                     step ++;
                     turn(k + 1,j);
                 }
             }
         }


         bool is_successful = true;
         for(int j = 0;  j < 5; j ++)
            if(g[4][j] == '0') {is_successful = false;break;} //判断最后一排

         if(is_successful)
            res = min(res,step);

         memcpy(g, backup, sizeof g); //将最开始的数组还原
    }
    return res > 6 ? -1:res;
}
int main(){
    cin>>T;
    while(T--){
        for(int i = 0 ; i < 5; i++) cin>>g[i];
        cout<<work()<<endl;
    }
    return 0;
}



拉倒i
1个月前
#include<iostream>
using namespace std;
const int N = 100005;
pair<string,int> a[N];
int n,m;
int calc(int bit , int now){
    for(int i = 1; i <= n;i++){
        int x = a[i].second >> bit & 1;
        if(a[i].first == "AND") now &= x;
        else if(a[i].first == "OR") now |= x;
        else now ^= x;
    }
    return now;
}
int main(){
    cin>>n>>m;
    string op;
    int t;
    for(int i = 1 ; i <= n ; i++){
         cin>>op>>t;
         a[i] = make_pair(op,t);
    }
    int val = 0, ans = 0;
    for(int bit = 29;bit >= 0 ;bit --){
        int res0 = calc(bit,0); //每一位比较0 和 1 计算最大值
        int res1 = calc(bit,1);
        if( val + (1 << bit) <= m && res0 < res1)
           val += 1 << bit, ans += res1 << bit;
        else 
           ans += res0 << bit;
    }
    cout<<ans<<endl;
    return 0;
}



拉倒i
1个月前
#include<iostream>
using namespace std;
int n,m;
void dfs(int u,int k,int state){ //k代表已经选了的数 u代表到了哪个数 
 if(k + n - u < m) return; // k + n - u 代表已经选了的数 加上还没有选过的数 
    if(k == m){
        for(int i = 0 ; i < n;i++)
           if(state >> i & 1) cout<< i + 1<<" ";
           cout<<endl;
           return;
    }

    if(u == n) return ;
    dfs(u + 1, k + 1, state | ( 1 << u));
    dfs(u + 1, k , state);
}

int main(){
    cin>>n>>m;
    dfs(0,0,0);

}


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

拉倒i
1个月前
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int  N = 20, M = 1 << 20;
int weight[N][N];
int dp[M][N];
int n;
int main(){
    cin>>n;
    for(int i = 0 ; i < n ; i++)
       for(int j = 0 ; j < n ; j++)
          cin>>weight[i][j];

    memset(dp,0x3f,sizeof dp);
    dp[1][0] = 0; //初始点距离为0
    for(int i = 0 ; i < M ; i++)
        for(int j = 0 ; j < n ; j++)
           if(i >> j & 1){ //i的第j位是否是1
               for(int k = 0; k < n; k++){
                   if(i - (1 << j) >> k & 1)
                      dp[i][j] = min(dp[i][j],dp[i - (1 << j)][k] + weight[k][j]);
               }
           }
      cout<<dp[(1 << n) - 1][n - 1];   
      return 0;
}



拉倒i
1个月前
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 200010;
int p[N];
struct Edge{
    int a,b,w;
    bool operator < (const Edge e) const{
        return w < e.w;
    };
}edges[N];
int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i = 0 ; i < m; i++){
        int a,b,w;
        cin>>a>>b>>w;
        edges[i] = {a,b,w};
    }
    for(int i = 1 ; i <= n;i++)
         p[i] = i;
    sort(edges,edges + m);
    int cnt = 0,res = 0;
    for(int i = 0 ; i < m ;i++){
         auto edge = edges[i];
         int a = edge.a, b = edge.b,w = edge.w;
         a = find(a), b = find(b);
         if(a != b){
             p[a] = b;
             cnt++;
             res += w;
         }
         if(cnt == n - 1)
            break;
    }
    if(cnt != n - 1) puts("impossible");
    else cout<<res<<endl;
    return 0;
}



活动打卡代码 AcWing 802. 区间和

拉倒i
1个月前
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
vector<int> alls;
const int N = 300010;
int a[N],s[N]; //a[N]放入下标映射之后存的值,s是前缀和
typedef pair<int,int> PII;
vector<PII> add,query;
int n,m;
int find(int x){
    int  l = 0 ,r = alls.size() - 1;
    while( l < r){
        int mid = (l + r) >> 1;
        if(alls[mid] >= x) r = mid ;
        else l = mid + 1;
    }
    return l + 1;
}
int main(){
       cin>>n>>m;
       for(int i = 0 ; i < n ; i++){
           int x,c;
           cin>>x>>c;
           alls.push_back(x);
           add.push_back({x,c});
       }
       for(int i = 0 ; i < m ; i++){
           int l,r;
           cin>>l>>r;
           alls.push_back(l);
           alls.push_back(r);
           query.push_back({l,r});
       }
       sort(alls.begin(),alls.end());
       alls.erase(unique(alls.begin(),alls.end()),alls.end()); //重复元素去重
       for(auto item:add){
           int idx = find(item.first);
           a[idx] += item.second;
       }
       for(int i = 1 ; i <= alls.size();i++) s[i] = s[i - 1] + a[i]; //前缀和
       for(auto item:query){
           int l = find(item.first),r = find(item.second); //找到左右区间对应的下标
           cout<<s[r] - s[l - 1]<<endl;
       }
}



拉倒i
1个月前
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int g[N][N];
bool st[N];
int dist[N];
int n,m;
int prim(){
    memset(dist,0x3f,sizeof dist);
    int res = 0 ;
    for(int i = 0 ; i < n ; i++){
        int t =  - 1;
        for(int j =  1;  j <= n ; j++){
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                  t = j;
          }
         st[t] = true; //将t这个点加入集合中
         if(i && dist[t] == INF) return INF; //第一次一个点 i为0 后面如果有两个以上的点则构成边了
         if(i) res += dist[t]; //加入这条边
         for(int j = 1; j <= n; j++)
             dist[j] = min(dist[j],g[t][j]); //更新集合里的边
    }
    return res;
}
int main(){
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    while( m -- ){
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b] = g[b][a] = min(g[a][b],c);
    }
    int res = prim();
    if(res == INF) puts("impossible");
    else  cout<<res<<endl;
    return 0;
}

堆优化版本
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

const int MAXN = 510, MAXM = 2 * 1e5 + 10, INF = 0x3f3f3f3f;
typedef pair<int, int> PII;
int h[MAXM], e[MAXM], w[MAXM], ne[MAXM], idx;
bool vis[MAXN];
int n, m;

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

int Prim()
{
    memset(vis, false, sizeof vis);
    int sum = 0, cnt = 0;
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, 1});

    while (!q.empty())
    {
        auto t = q.top();
        q.pop();
        int ver = t.second, dst = t.first;
        if (vis[ver]) continue;
        vis[ver] = true, sum += dst, ++cnt;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (!vis[j]) {
                q.push({w[i], j});
            }
        }
    }

    if (cnt != n) return INF;
    return sum;
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; ++i)
    {
        int a, b, w;
        cin >> a >> b >> w;
        add(a, b, w);
        add(b, a, w);
    }

    int t = Prim();
    if (t == INF) cout << "impossible" << endl;
    else cout << t << endl; 
}


活动打卡代码 AcWing 803. 区间合并

拉倒i
1个月前
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int> P;
int main(){
    int n;
    cin>>n;
    vector<P> vec;
    int a,b;
    for(int i = 0 ; i < n ;i++){
        cin>>a>>b;
        vec.push_back({a,b});
    }
    sort(vec.begin(),vec.end());
    // for(int i = 0 ; i < vec.size();i++)
    //     cout<<vec[i].first<<" "<<vec[i].second<<endl;
    vector<P> res;
    res.push_back(vec[0]);
    for(int i = 1; i < n;i++){
        if(vec[i].first <= res.back().second)
        res.back().second = max(res.back().second,vec[i].second);
        else
        res.push_back(vec[i]);
    }
    // for(int i = 0 ; i < res.size();i++)
    //     cout<<res[i].first<<" "<<res[i].second<<endl;
    cout<<res.size();
}


活动打卡代码 AcWing 852. spfa判断负环

拉倒i
1个月前
#include<bits/stdc++.h>
using namespace std;

const int N=2010,M=10010;
int h[N],e[M],ne[M],w[M],idx;
bool st[N];
int d[N],cnt[N];  //cnt数组表示到达当前这个点最短路的边数
int n,m;

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

bool spfa(){
    memset(d,0,sizeof(d));    //本题可以不做初始化
    memset(cnt,0,sizeof(cnt));    
    memset(st,false,sizeof(st));

    queue<int> q;
    for(int i=1;i<=n;i++){     //判整个图的负环要将每个节点都加入
        st[i]=true;
        q.push(i);
    }

    while(!q.empty()){
        int t=q.front();
        q.pop();

        st[t]=false;
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(d[j]>d[t]+w[i]){
                d[j]=d[t]+w[i];
                cnt[j]=cnt[t]+1;

                if(cnt[j]>=n) return true;
                if(!st[j]){
                    st[j]=true;
                    q.push(j);
                }
            }
        }
    }

    return false;
}

int main(){
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }

    if(spfa()) puts("Yes");
    else puts("No");
}