哈尔滨工程大学ACM预热赛

分类: IT文章 • 2025-02-04 19:29:49

https://ac.nowcoder.com/acm/contest/554#question

A

#include <bits/stdc++.h>
using namespace std;

int N;
long long dp[110][110];



int main() {
    scanf("%d", &N);
    memset(dp, 0, sizeof(dp));
    dp[1][1] = 1, dp[1][0] = 1;
    for(int i = 2; i <= N; i ++) {
        for(int j = 0; j <= i; j ++) {
            for(int k = 0; k <= j && k <= i - 1; k ++) {
                dp[i][j] += dp[i - 1][k];
            }
        }
    }
    long long ans = 0;
    for(int i = 0; i <= N; i ++)
        ans += dp[N][i];
    printf("%lld
", ans - 1);
    return 0;
}

dp （long long 爆掉了）

#include <bits/stdc++.h>
using namespace std;
 
string catalan[]= {
                "1",
                "1",
                "4",
                "13",
                "41",
                "131",
                "428",
                "1429",
                "4861",
                "16795",
                "58785",
                "208011",
                "742899",
                "2674439",
                "9694844",
                "35357669",
                "129644789",
                "477638699",
                "1767263189",
                "6564120419",
                "24466267019",
                "91482563639",
                "343059613649",
                "1289904147323",
                "4861946401451",
                "18367353072151",
                "69533550916003",
                "263747951750359",
                "1002242216651367",
                "3814986502092303",
                "14544636039226908",
                "55534064877048197",
                "212336130412243109",
                "812944042149730763",
                "3116285494907301261",
                "11959798385860453491",
                "45950804324621742363",
                "176733862787006701399",
                "680425371729975800389",
                "2622127042276492108819",
                "10113918591637898134019",
                "39044429911904443959239",
                "150853479205085351660699",
                "583300119592996693088039",
                "2257117854077248073253719",
                "8740328711533173390046319",
                "33868773757191046886429489",
                "131327898242169365477991899",
                "509552245179617138054608571",
                "1978261657756160653623774455",
                "7684785670514316385230816155",
                "29869166945772625950142417511",
                "116157871455782434250553845879",
                "451959718027953471447609509423",
                "1759414616608818870992479875971",
                "6852456927844873497549658464311",
                "26700952856774851904245220912663",
                "104088460289122304033498318812079",
                "405944995127576985730643443367111",
                "1583850964596120042686772779038895",
                "6182127958584855650487080847216335",
                "24139737743045626825711458546273311",
                "94295850558771979787935384946380124",
                "368479169875816659479009042713546949",
                "1440418573150919668872489894243865349",
                "5632681584560312734993915705849145099",
                "22033725021956517463358552614056949949",
                "86218923998960285726185640663701108499",
                "337485502510215975556783793455058624699",
                "1321422108420282270489942177190229544599",
                "5175569924646105559418940193995065716349",
                "20276890389709399862928998568254641025699",
                "79463489365077377841208237632349268884499",
                "311496878311103321137536291518809134027239",
                "1221395654430378811828760722007962130791019",
                "4790408930363303911328386208394864461024519",
                "18793142726809884575211361279087545193250039",
                "73745243611532458459690151854647329239335599",
                "289450081175264899454283846029490767264392229",
                "1136359577947336271931632877004667456667613939",
                "4462290049988320482463241297506133183499654739",
                "17526585015616776834735140517915655636396234279",
                "68854441132780194707888052034668647142985206099",
                "270557451039395118028642463289168566420671280439",
                "1063353702922273835973036658043476458723103404519",
                "4180080073556524734514695828170907458428751314319",
                "16435314834665426797069144960762886143367590394939",
                "64633260585762914370496637486146181462681535260999",
                "254224158304000796523953440778841647086547372026599",
                "1000134600800354781929399250536541864362461089950799",
                "3935312233584004685417853572763349509774031680023799",
                "15487357822491889407128326963778343232013931127835599",
                "60960876535340415751462563580829648891969728907437999",
                "239993345518077005168915776623476723006280827488229599",
                "944973797977428207852605870454939596837230758234904049",
                "3721443204405954385563870541379246659709506697378694299",
                "1465792935612957543701687784665703276171295495089975599",
                "57743358069601357782187700608042856334020731624756610999",
                "227508830794229349661819540395688853956041682601541047339",
                "896519947090131496687170070074100632420837521538745909319",
                "3533343320884635898708258511468514257188006702535057407319"
        };
int main() {
    int N;
    scanf("%d", &N);
    cout << catalan[N] << endl;
    return 0;
}

View Code

（下面的 code 是正解卡特兰数打表）

B

#include <bits/stdc++.h>
using namespace std;

int T;
int a[5][5], b[5][5];

int main() {
    scanf("%d", &T);
    while(T --){
        for(int i = 1; i <= 3; i ++) {
            for(int j = 1; j <= 3; j ++)
                scanf("%d", &a[i][j]);
        }

        for(int i = 1; i <= 3; i ++) {
            for(int j = 1; j <= 3; j ++)
                b[j][i] = a[i][j];
        }

        long long ans = b[1][1] * b[2][2] * b[3][3] +
                        b[1][2] * b[2][3] * b[3][1] +
                        b[2][1] * b[1][3] * b[3][2] -
                        b[1][3] * b[2][2] * b[3][1] -
                        b[2][3] * b[3][2] * b[1][1] -
                        b[3][3] * b[1][2] * b[2][1];

        printf("%lld
", abs(ans * ans));
    }
    return 0;
}

View Code

还要查一下什么是伴随矩阵线代已经学完一年了呀

C

#include <bits/stdc++.h>
using namespace std;
 
int T;
long long a, N, b;
 
long long Pow(long long a, long long b, long long mod) {
    long long ans = 1;
    a %= mod;
    while(b) {
        if(b % 2) {
            ans = (ans * a) % mod;
            b --;
        } else {
            a = (a * a) % mod;
            b /= 2;
        }
    }
    return ans % mod;
}
 
int main() {
    scanf("%d", &T);
    while(T --) {
        scanf("%lld%d%lld", &a, &N, &b);
        long long cnt = Pow(a, N, b);
        printf("%lld
", cnt % b);
    }
    return 0;
}

View Code

一个快速幂对 b 取 mod

H

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e6 + 10;
int sum[maxn], a[maxn];
int T, N;

int main() {
    for(int i = 2; i <= 1e6; i ++) {
        for(int j = i; j <= 1e6; j += i)
            a[j] = !a[j];
    }

    for(int i = 1; i <= 1e6; i ++) {
        if(a[i]) sum[i] = sum[i - 1] + 1;
        else sum[i] = sum[i - 1];
    }

    scanf("%d", &T);
    while(T --) {
        int x, y;
        scanf("%d%d%d", &N, &x, &y);
        printf("%d
", sum[y] - sum[x - 1]);
    }
    return 0;
}

View Code

先离线处理一下然后每次查询求一下前缀和

前一阵心情很差劲呀休息一阵之后发现真的不能停下来脑子明显锈住了这几天多动动脑子活过来吧！天梯赛的题目代码过两天贴上来吧还有半个月省赛要加油呢明天雷火的笔试希望有好运气

就算是深夜也有人乘着阳光呢

哈尔滨工程大学ACM预热赛

A

B

C

H

相关推荐