洛师ACM20级能力测试

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

洛师ACM20级能力测试

作者：

史一帆 , 2022-03-12 18:06:51 , 所有人可见 , 阅读 314

你的飞碟在这儿{:targer=”_blank”}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
typedef long long LL;

int main()
{
    string a, b;
    cin >> a >> b;
    int sum_a = 1, sum_b = 1;
    for (int i = 0; i < a.size(); i++)
        sum_a *= a[i] - 'A' + 1;
    for (int i = 0; i < b.size(); i++)
        sum_b *= b[i] - 'A' + 1;
    if (sum_a % 47 == sum_b % 47)
        puts("GO");
    else
        puts("STAY");
    return 0;
}

多项式输出{:targer=”_blank”}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 110;

int a[N];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = n; i >= 0; i--)
    {
        scanf("%d", &a[i]);
    }
    for (int i = n; i >= 0; i--)
    {
        if (!a[i]) // 系数为0
            continue;
        if (i == n)
        { // n次项系数
            if (a[i] < 0)
                printf("-");
        }
        else
        { // 其他次项系数符号
            if (a[i] > 0)
                printf("+");
            else
                printf("-");
        }

        if (!i) // 0次项系数
            printf("%d", abs(a[i]));
        else
        { // 其他次项系数
            if (a[i] == 1 || a[i] == -1)
                ;
            else
                printf("%d", abs(a[i]));
        }
        if (i)
        {
            printf("x");
            if (i != 1)
                printf("^%d", i);
        }
    }
    return 0;
}

DD 爱数数{:targer=”_blank”}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;

int l, r, n, m;
int cnt, res;
int primes[N];
bool vis[N];
int arr[N], pos;

void get_primes()
{
    for (int i = 2; i < N; i++)
    {
        if (vis[i])
            continue;
        primes[cnt++] = i;
        for (int j = i + i; j < N; j += i)
            vis[j] = true;
    }
}

bool is_palindrome(int x)
{
    int t = x;
    int y = 0;
    while (t)
    {
        y = y * 10 + t % 10;
        t /= 10;
    }
    if (y == x)
        return true;
    else
        return false;
}

int main()
{
    get_primes();
    for (int i = 0; i < cnt; i++)
        if (is_palindrome(primes[i]))
            arr[pos++] = primes[i];
    scanf("%d%d", &n, &m);
    int l = lower_bound(arr, arr + pos, n) - arr;
    for (int i = l; i < pos; i++)
    {
        if (arr[i] > m)
            break;
        res++;
    }
    cout << res << endl;
    return 0;
}

魔法宝石{:targer=”_blank”}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 110;

int f[3010][10010];
int w[3010], v[3010];
int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            if (j >= v[i])
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    int res = 0;
    for (int i = 0; i <= m; i++)
        res = max(res, f[n][i]);
    printf("%d\n", res);

    return 0;
}

最短路{:targer=”_blank”}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
using namespace std;
typedef long long LL;
const int N = 110;

int g[N][N];
int dist[N];
bool vis[N];
int n, m;

void dijkstra()
{
    memset(vis, false, sizeof vis);
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        vis[t] = true;

        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
}

int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        if (!n && !m)
            break;
        memset(g, 0x3f, sizeof g);
        while (m--)
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            g[a][b] = g[b][a] = c;
        }
        dijkstra();
        printf("%d\n", dist[n]);
    }

    return 0;
}

红与黑{:targer=”_blank”}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
using namespace std;
typedef long long LL;
const int N = 30;

char g[N][N];
int n, m;
int a, b;
bool vis[N][N];
int res;
int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};

void dfs(int x, int y)
{
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && g[nx][ny] == '.')
        {
            vis[nx][ny] = true;
            res++;
            dfs(nx, ny);
        }
    }
}

int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 0; i < n; i++)
        cin >> g[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == '@')
            {
                a = i, b = j;
                break;
            }
    dfs(a, b);

    printf("%d\n", res + 1);
    return 0;
}

程序设计：引爆炸弹{:targer=”_blank”}

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1009;
int n, m;
int map[N][N];
bool row[N], col[N];
int sum;
void dfs(int x, int y) // 将与(x,y)处于同一连通块的炸弹引爆
{
    if(!col[y]) // 剪枝
    {   
        col[y] = 1;
        for(int i=0; i<n; i++)
        {
            if(map[i][y] == 1)
            {
                map[i][y] = 0;
                dfs(i, y);
            }
        }
    }
    if(!row[x]) // 剪枝
    {
        row[x] = 1;
        for(int i=0; i<m; i++)
        {
            if(map[x][i] == 1)
            {
                map[x][i] = 0;
                dfs(x, i);
            }
        }
    }

    return;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            scanf("%1d",&map[i][j]); 
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(map[i][j] == 1)
            {
                sum++;
                map[i][j] = 0;
                dfs(i, j);
            }
        }
    }
    cout << sum << endl;
    return 0;
}

二叉树{:targer=”_blank”}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < n; ++ i)
#define fornn(i, n) for (int i = 1; i <= n; ++ i)
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define LL long long
#define DB double
#define PB push_back

using namespace std;

const DB EPS = 1e-6;
const LL INFI = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10, MOD = 1e9 + 7, INF = 0x3f3f3f3f;

int n;
int a[110], b[110];
bool vis[110];
stack<int> ans;

void dfs(int l, int r) {
    if (l > r) return ;
    for (int i = 1; i <= n; ++ i) {
        if (vis[a[i]]) continue;

        for (int j = l; j <= r; ++ j)
            if (a[i] == b[j]) {
            //  cout << l << ' ' << r << ' ' << a[i] << endl;
                ans.push(a[i]);
                vis[a[i]] = 1;
                dfs(j + 1, r);
                dfs(l, j - 1);

            }
    }
}

void sol() {
    memset(vis, 0, sizeof vis);
    while (ans.size()) ans.pop();
    for (int i = 1; i <= n; ++ i) cin >> a[i];
    for (int i = 1; i <= n; ++ i) cin >> b[i];

    for (int i = 1; i <= n; ++ i) {
        if (!vis[a[i]]) {

            for (int j = 1; j <= n; ++ j)
                if (b[j] == a[i]) {
                    ans.push(a[i]);
                    vis[a[i]] = 1;
                    dfs(j + 1, n);
                    dfs(1, j - 1);
                }

        }
    }

    while (ans.size()) {
        cout << ans.top();
        ans.pop();
        if (ans.size() > 0) cout << ' ';
    }
    cout << endl;
}

int main() {
    while (cin >> n) sol();
    return 0;
}

3 评论

史一帆 2022-03-13 09:46

密码：lynuacm20

2010 2022-03-12 18:10

求关注

Nan97 2022-03-12 18:08

飞碟没有秘法(密码)，登录不上

App 内打开