AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 校园
  • 应用
  • 文章
    • 题解
    • 分享
    • 问答
  • 吐槽
  • 登录/注册

2022/6/22

作者: 作者的头像   史一帆 ,  2022-06-22 09:04:58 ,  所有人可见 ,  阅读 22


0


[NOIP2002]选数

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

using namespace std;

const int N = 30;

int n, k;
int a[N];
int res;

bool is_prime(int x){
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
            return false;
    return true;
}

void dfs(int u, int cnt, int sum){
    if (cnt + n - u + 1 < k) return;
    if (cnt == k){
        if (is_prime(sum)) res ++ ;
        return;
    }
    dfs(u + 1, cnt + 1, sum + a[u]);
    dfs(u + 1, cnt, sum);
}

int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    dfs(1, 0, 0);
    cout << res << endl;
    return 0;
}

Prime Path

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

using namespace std;

const int N = 1100;

int cnt;
int primes[N];
map<int,int> ver;
int g[N][N];
int dist[N];
bool st[N];

bool is_prime(int x){
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
            return false;
    return true;
}

bool get(int a, int b){
    int p = primes[a], q = primes[b];
    int cnt = 0;
    while (p){
        int x = p % 10;
        int y = q % 10;
        if (x != y) cnt ++ ;
        p /= 10;
        q /= 10;
    }
    if (cnt == 1) return true;
    return false;
}

void dijkstra(int a, int b){
    a = ver[a], b = ver[b];
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    dist[a] = 0;
    for (int i = 0; i < cnt; i ++ ){
        int t = -1;
        for (int j = 0; j < cnt; j ++ )
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        st[t] = true;
        for (int j = 0; j < cnt; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    if (dist[b] == 0x3f3f3f3f) puts("Impossible");
    else cout << dist[b] << endl;
}

int main(){
    for (int i = 1000; i <= 9999; i ++ )
        if (is_prime(i))
            primes[cnt ++ ] = i, ver[i] = cnt-1;
    memset(g, 0x3f, sizeof g);
    for (int i = 1; i < cnt; i ++ )
        for (int j = 0; j < i; j ++ )
            if (get(i, j))
                g[i][j] = g[j][i] = 1;
    int T;
    cin >> T;
    while (T -- ){
        int a, b;
        cin >> a >> b;
        dijkstra(a, b);
    }
    return 0;
}

八皇后问题

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

using namespace std;

const int N = 10;

int g[N][N];
bool col[N], dg[N<<1], udg[N<<1];
int res;

void dfs(int u, int sum){
    if (u == 8){
        res = max(res, sum);
        return;
    }
    for (int i = 0; i < 8; i ++ )
        if (!col[i] && !dg[i-u+8] && !udg[i+u]){
            col[i] = dg[i-u+8] = udg[i+u] = true;
            dfs(u+1, sum + g[u][i]);
            col[i] = dg[i-u+8] = udg[i+u] = false;
        }
}

int main(){
    int T;
    cin >> T;
    while (T -- ){
        for (int i = 0; i < 8; i ++ )
            for (int j = 0; j < 8; j ++ )
                cin >> g[i][j];
        res = 0;
        dfs(0, 0);
        cout << res << endl;
    }
    return 0;
}

0 评论

你确定删除吗?

© 2018-2022 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息