第五屆傳智杯-初賽【A組-題解】-創(chuàng)新互聯(lián)

B題： 題目背景

【 題目背景和題目描述的兩個(gè)題面是完全等價(jià)的，您可以選擇閱讀其中一部分?！?/p>創(chuàng)新互聯(lián)建站于2013年創(chuàng)立，是專(zhuān)業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目網(wǎng)站設(shè)計(jì)制作、做網(wǎng)站網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元梅縣做網(wǎng)站,已為上家服務(wù),為梅縣各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:13518219792

專(zhuān)攻超統(tǒng)一物理學(xué)的蓮子，對(duì)機(jī)械結(jié)構(gòu)的運(yùn)動(dòng)頗有了解。如下圖所示，是一個(gè)三進(jìn)制加法計(jì)算器的（超簡(jiǎn)化）示意圖。

初始時(shí)齒輪的狀態(tài)如上。

把第一個(gè)齒輪撥動(dòng)一個(gè)單位長(zhǎng)度，變?yōu)槿缟蠄D所示。

題解：

模擬題。按照題目要求輸入整數(shù)?a,b，模擬這個(gè)奇怪的進(jìn)位規(guī)則即可。

參考代碼?

版本?1：

#include#define up(l, r, i) for(int i = l, END##i = r;i<= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const int INF = 2147483647;
int qread(){
    int w=1,c,ret;
    while((c = getchar()) >'9' || c<  '0') w = (c == '-' ? -1 : 1); ret = c - '0';
    while((c = getchar()) >= '0' && c<= '9') ret = ret * 10 + c - '0';
    return ret * w;
}
const int MAXN = 2e5 + 3;
int A[MAXN], B[MAXN];
int main(){
    int n = qread(), m = qread(), l = max(n, m);
    dn(n, 1, i) A[i] = qread();
    dn(m, 1, i) B[i] = qread();
    up(1, l, i) A[i] += B[i], A[i + 1] += A[i] / (i + 1), A[i] %= i + 1;
    if(A[l + 1]) ++ l;
    dn(l, 1, i) printf("%d%c", A[i], " \n"[i == 1]);
    return 0;
}

版本2：

#includeusing namespace std;
int a[200050],b[200050];
int main()
{
    auto read=([&]{
        int x;cin >>x;
        return x;
    });
    int n=read(),m=read();
    int len=max(n,m)+1;
    generate_n(a+1,n,read);
    generate_n(b+1,m,read);
    reverse(a+1,a+n+1);
    reverse(b+1,b+m+1);
    for (int i=1;i<=len;i++)
    {
        a[i]+=b[i];
        a[i+1]+=(a[i]/(i+1));
        a[i]%=(i+1);
    }
    while (a[len]==0 && len>1)
        len--;
    reverse(a+1,a+len+1);
    for (int i=1;i<=len;i++)
        cout<< a[i]<< " ";
    return 0;
}

版本3：

import java.util.Scanner;

public class Main {

    public static int[] a = new int[200005];
    public static int[] b = new int[200005];
    public static int[] c = new int[200005];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();
        int maxLength = Math.max(n, m);
        for (int i = (maxLength - n) + 1; i<= maxLength; ++i)
            a[i] = scanner.nextInt();
        for (int i = (maxLength - m) + 1; i<= maxLength; ++i)
            b[i] = scanner.nextInt();
        for (int i = maxLength, cnt = 2; i >0; --i, ++cnt) {
            c[i] += a[i] + b[i];
            if (c[i] >= cnt) {
                c[i] -= cnt;
                c[i - 1] += 1;
            }
        }
        if (c[0] >0) {
            System.out.printf("%d ", c[0]);
        }
        for (int i = 1; i<= maxLength; ++i) {
            System.out.printf("%d ", c[i]);
        }
        System.out.println();
    }
}

C題 題目背景

你現(xiàn)在不能休息，周?chē)?deadline 在游蕩。

蓮子正在趕自己的程序設(shè)計(jì)作業(yè)。除了完成程序代碼的編寫(xiě)，對(duì)提交上去的作業(yè)進(jìn)行排版以對(duì)助教留下良好印象同樣重要。

而眾所周知，文章里面的代碼和一些特殊性質(zhì)的文本是要附上行號(hào)的，然而它們的篇幅往往都很長(zhǎng)，手動(dòng)去加容易出現(xiàn)失誤。因此，蓮子決定自力更生造輪子，寫(xiě)一個(gè)行號(hào)生成器。

輸入格式

輸入包含若干行，為原始的文本文件。

輸出格式

輸出包含若干行，為加上行號(hào)后的文本文件。

輸入輸出樣例

題解：

參考代碼?

版本1：

#include#define up(l, r, i) for(int i = l, END##i = r;i<= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const int INF = 2147483647;
const int MAXN= 2e4 + 3;
char S[MAXN], c; int l, m;
int main(){
    m = count(S + 1 , S + 1 + fread(S + 1, 1, MAXN, stdin), '\n');
    int s = log10(m) + 1 + 1e-9, p = 0;
    up(1, m, i){
        int t = log10(i) + 1 + 1e-9;
        for(int j = 1;j<= s - t;++ j) putchar( ' '); printf("%d ", i);
        for(p = p + 1;S[p] != 10;++ p) putchar(S[p]); putchar('\n');
    }
    return 0;
}

版本2：

#include#include#includeusing namespace std;
char buf[200050];
vectors[200050];
int cnt;
int get_digit(int x)
{
    int digit=1,ret=1;
    while (ret<=x)
    {
        digit++;
        ret*=10;
    }
    return digit;
}
int main()
{
    while(fgets(buf,200000,stdin)!=NULL)
    {
        cnt++;
        for (int i=0;buf[i]!='\n';i++)
            s[cnt].push_back(buf[i]);
    }
    int cnt_digit=get_digit(cnt);
    for (int i=1;i<=cnt;i++)
    {
        for (int j=1;j<=cnt_digit-get_digit(i);j++)
            putchar(' ');
        cout<< i<< ' ';
        for (int j=0;j

版本3：?

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;

public class Main {

    public static Listlist = new ArrayList<>();

    public static int getBit(int x) {
        int cnt = 0;
        while (x >0) {
            x /= 10;
            ++cnt;
        }
        return cnt;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            list.add(scanner.nextLine());
        }
        int size = list.size();
        int len = getBit(size);
        for (int i = 0; i< size; ++i) {
            System.out.printf("%" + len + "d %s\n", i + 1, list.get(i));
        }
    }
}

D題 題目背景

蓮子正在研究分子的運(yùn)動(dòng)。

每個(gè)分子都有一個(gè)速度，約定正方向?yàn)檎?，?fù)方向?yàn)樨?fù)。分子的數(shù)量極多，速度又并不一致，看上去雜亂無(wú)章。于是蓮子希望調(diào)整部分分子的速度，使得最終分子們看上去整齊。

題解：

參考代碼?

版本1：

#include#define up(l, r, i) for(int i = l, END##i = r;i<= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const int INF = 2147483647;
int qread(){
    int w=1,c,ret;
    while((c = getchar()) >'9' || c<  '0') w = (c == '-' ? -1 : 1); ret = c - '0';
    while((c = getchar()) >= '0' && c<= '9') ret = ret * 10 + c - '0';
    return ret * w;
}
const int MAXN = 1e5 + 3;
int A[MAXN], ans = INF;
int main(){
    int n = qread(), m = qread();
    up(1, n, i) A[i] = qread();
    sort(A + 1, A + 1 + n);
    int j = 1;
    up(1, min(n, m + 1), i){
        j = max(i, j);
        while((i - 1) + (n - j) + min(i - 1, n - j) >m) ++ j;
        ans = min(ans, A[j] - A[i]);
    }
    printf("%d\n", ans);
    return 0;
}

版本2：

import java.util.Scanner;
import java.util.Arrays;

public class Main {

    public static int[] a = new int[100005];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();
        for (int i = 1; i<= n; ++i)
            a[i] = scanner.nextInt();
        Arrays.sort(a, 1, n + 1);
        int j = 1, ans = Integer.MAX_VALUE;
        for (int i = 1; i<= Math.min(n, m + 1); ++i) {
            j = Math.max(j, i);
            while((i - 1) + (n - j) + Math.min(i - 1, n - j) >m) 
                ++j;
            ans = Math.min(ans, a[j] - a[i]);
        }
        System.out.println(ans);
    }
}

F題

作為大學(xué)生，蓮子和梅莉有著比高中時(shí)更為閑暇的課余時(shí)光。在沒(méi)有課的時(shí)候，她們喜歡玩大富翁這一游戲，在游玩過(guò)程中交流自己的喜怒哀樂(lè)。

輸入輸出樣例

題解

模擬題。沒(méi)什么好說(shuō)的。這里就講幾個(gè)細(xì)節(jié)：

參考代碼?

版本1：

#include#define up(l, r, i) for(int i = l, END##i = r;i<= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const int INF = 2147483647;
int qread(){
    int w=1,c,ret;
    while((c = getchar()) >'9' || c<  '0') w = (c == '-' ? -1 : 1); ret = c - '0';
    while((c = getchar()) >= '0' && c<= '9') ret = ret * 10 + c - '0';
    return ret * w;
}
int n, m, q, maxl; bool o = 1;
const int MAXN = 100 + 3;
int C[MAXN][MAXN], A[MAXN], D[MAXN], L[MAXN], O[3], T[MAXN];
i64 M[2];
int main(){
    n = qread(), m = qread(), q = qread(), maxl = qread();
    M[0] = M[1] = m, O[0] = O[1] = 1;
    up(1, n, i) L[i] = 0, T[i] = -1;
    up(1, n, i)
        up(0, maxl - 1, j) C[i][j] = qread();
    up(1, n, i) D[i] = qread();
    for(int op, k;~scanf("%d%d", &op, &k);){
        if(op == 1){
            if(o == 1){
                up(1, n, i) if(T[i] != -1) M[T[i]] += D[i];
            }
            o ^= 1;
            up(1, k, i){
                O[o] = (O[o]) % n + 1;
                int p = O[o];
                if(T[p] ==  o) M[o] += A[p]; else 
                if(T[p] == !o){
                    M[!o] += A[p], M[o] -= A[p];
                    if(M[o]< 0)
                        puts(o ? "Merry" : "Renko"), exit(0);
                }
            }
        } else {
            int p = O[o];
            while(k && L[p]< maxl && M[o] >= C[p][L[p]] && T[p] != !o){
                A[p] += C[p][L[p]], M[o] -= C[p][L[p]];
                ++ L[p], T[p] = o, -- k;
            }
        }
    }
    up(1, n, i) if(T[i] != -1) M[T[i]] += D[i];
    printf("%lld %lld\n", M[0], M[1]);
    return 0;
}

版本2：

#include#include#include#include 
#include#include#includeusing namespace std;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int n,m,q,L,C[105][105],d[105],a[105],lv[105],pos[2],belong[105];

long long money[2];

const string name[2]={"Renko","Merry"};

inline void putfail(int id)
{
    cout<< name[id]<< endl;
    exit(0);
}

inline void forward(int id,int k)
{
    for (int i=1;i<=k;i++)
    {
        int &p=pos[id];
        p++;
        if (p>n)
            p-=n;
        if (belong[p]==id)
            money[id]+=a[p];
        else if (belong[p]==(id^1))
        {
            money[id]-=a[p];
            money[id^1]+=a[p];
        }
        if (money[id]<0)
            putfail(id);
    }
}

inline void build(int id,int k)
{
    int p=pos[id],cost=C[p][lv[p]];
    for (int i=1;(money[id]>=cost && lv[p]

G題 題目背景

梅莉買(mǎi)到了一張?zhí)厥獾膸в谢y的紙。整張紙的圖案可以視為，由一個(gè)較小的圖案，沿著橫向與縱向無(wú)限循環(huán)而成。同時(shí)，這個(gè)基本圖案部分透明，部分不透明。

于是，如果將這張紙覆蓋在書(shū)本上，那么一些字可以被看見(jiàn)，另一些字看不見(jiàn)。

蓮子突發(fā)奇想：假使她制作一張很大很大的數(shù)表，將花紋紙覆蓋在上面，那么就會(huì)有很多數(shù)字被遮擋。那些沒(méi)有被遮擋的數(shù)字的和是多少呢？

題目描述

題解：

參考代碼：
#include#define up(l, r, i) for(int i = l, END##i = r;i<= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const int INF = 2147483647;
int n, m, r, c, q;
int qread(){
    int w=1,c,ret;
    while((c = getchar()) >'9' || c<  '0') w = (c == '-' ? -1 : 1); ret = c - '0';
    while((c = getchar()) >= '0' && c<= '9') ret = ret * 10 + c - '0';
    return ret * w;
}
const int MAXN = 2e3 + 3;
const int MAXM =  50 + 3;
const int MOD  = 998244353;
int A[MAXN][MAXN], S[MAXN][MAXN]; bool B[MAXN][MAXN];
int calc(int a1, int b1, int a2, int b2){
    int ret = S[a2][b2];
    if(a1 >r) ret = (ret - S[a1 - r][b2] + MOD) % MOD;
    if(b1 >c) ret = (ret - S[a2][b1 - c] + MOD) % MOD;
    if(a1 >r && b1 >c) ret = (ret + S[a1 - r][b1 - c]) % MOD;
    return ret;
}
int main(){
    n = qread(), m = qread();
    up(1, n, i) up(1, m, j) A[i][j] = qread();
    r = qread(), c = qread();
    up(1, r, i) up(1, c, j) B[i][j] = qread();
    up(1, n, i) up(1, m, j){
        S[i][j] = A[i][j];
        if(i >r) S[i][j] = (S[i][j] + S[i - r][j]) % MOD;
        if(j >c) S[i][j] = (S[i][j] + S[i][j - c]) % MOD;
        if(i >r && j >c)
            S[i][j] = (S[i][j] - S[i - r][j - c] + MOD) % MOD;
    }
    q = qread();
    up(1, q, i){
        int _x1 = qread(), _y1 = qread();
        int _x2 = qread(), _y2 = qread();
        int ans = 0;
        up(1, min(r, _x2 - _x1 + 1), a)
            up(1, min(c, _y2 - _y1 + 1), b) if(B[a][b] == 0){
                int a1 = _x1 + a - 1, a2 = a1 + (_x2 - a1) / r * r;
                int b1 = _y1 + b - 1, b2 = b1 + (_y2 - b1) / c * c;
                ans = (ans + calc(a1, b1, a2, b2)) % MOD;
        }
        printf("%d\n", ans);
    }

    return 0;
}
I題

學(xué)校正在組織宴會(huì)。

蓮子和梅莉發(fā)現(xiàn)，學(xué)校的結(jié)構(gòu)十分復(fù)雜。學(xué)生之間存在著部門(mén)與上司的關(guān)系。每一個(gè)部門(mén)內(nèi)部，都呈現(xiàn)出連成一條線的上司關(guān)系。一個(gè)部門(mén)內(nèi)等級(jí)最高的學(xué)生，又可能受限于另外某個(gè)部門(mén)內(nèi)的某個(gè)學(xué)生。

蓮子和梅莉同樣參加了宴會(huì)。但是她們對(duì)參加學(xué)生有自己的評(píng)判。例如，她對(duì)某些部門(mén)比較喜歡，對(duì)另一些部門(mén)則不感興趣。同時(shí)對(duì)位居不同等級(jí)的學(xué)生同樣有著不同的看法。

正如某個(gè)經(jīng)典問(wèn)題所描述的一樣，每個(gè)學(xué)生都不希望與自己的直接上司共同參加宴會(huì)。

梅莉想要知道，最好情況下，有多少個(gè)參加宴會(huì)的學(xué)生是她喜歡的。

題目描述

題解：

壓軸題。

參考代碼?

#include#define up(l, r, i) for(int i = l, END##i = r;i<= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const i64 INF = 1e18;
int n;
int qread(){
    int w=1,c,ret;
    while((c = getchar()) >'9' || c<  '0') w = (c == '-' ? -1 : 1); ret = c - '0';
    while((c = getchar()) >= '0' && c<= '9') ret = ret * 10 + c - '0';
    return ret * w;
}
const int MAXN = 1e6 + 3;
const int MAXM = 2e6 + 3;
int R[MAXN], C[MAXN], A[MAXN], F[MAXN], G[MAXM], W[MAXM], o = 0;
int X[MAXM]; i64 U[MAXM][4];
int Y[MAXM]; i64 V[MAXM][4];
int P0[MAXN], Q0[MAXN], P1[MAXN], Q1[MAXN];
int value(int w){return w % 2 == 1 ? w / 2 + 1 : w / 2;}
void calc(int l, int r, i64 &w, bool t){    // [l, r] 區(qū)間
    if(r - l + 1 ==  0){w = 0   ; return;}
    if(r - l + 1 == -1){w = 0   ; return;}
    if(r - l + 1 == -2){w = -INF; return;}
    if(t == false){
        int u = min(Q0[l], r); w = P0[r] - P0[u] + ( R[l] == 1 ? value(u - l + 1) : 0);
    } else {
        int u = min(Q1[l], r); w = P1[r] - P1[u] + (!R[l] == 1 ? value(u - l + 1) : 0);
    }
}
void calc(int l, int r, i64 O[4], bool t){  // [l + (0~1), r - (0~1)] 區(qū)間
    calc(l    , r    , O[0b11], t);
    calc(l    , r - 1, O[0b10], t);
    calc(l + 1, r    , O[0b01], t);
    calc(l + 1, r - 1, O[0b00], t);
}
i64 I[MAXM], J[MAXM];   // I 是必須選上，J 是必須不選
void dfs(int u){
    if(X[u] == 0) I[u] = W[u], J[u] = 0; else {
        int l = X[u], r = Y[u]; dfs(l), dfs(r);
        I[u] = W[u]
            + max(U[u][0b00] + I[l], U[u][0b01] + J[l])
            + max(V[u][0b00] + I[r], V[u][0b01] + J[r]);
        J[u] =
            + max(U[u][0b10] + I[l], U[u][0b11] + J[l])
            + max(V[u][0b10] + I[r], V[u][0b11] + J[r]);
    }
}
int main(){ 
    n = qread();
    up(1, n, i) R[i] = qread();
    up(1, n, i) C[i] = qread();
    up(2, n, i) A[i] = qread();
    P0[1] = R[1], P1[1] = !R[1];
    up(2, n, i){
        P0[i] = max(P0[i - 1], P0[i - 2] +  R[i]);
        P1[i] = max(P1[i - 1], P1[i - 2] + !R[i]);
    }
    Q0[n] = Q1[n] = n;
    dn(n - 1, 1, i){
        if( R[i] == 0) Q0[i] = i; else
            if( R[i + 1] == 0) Q0[i] = i; else Q0[i] = Q0[i + 1];
        if(!R[i] == 0) Q1[i] = i; else
            if(!R[i + 1] == 0) Q1[i] = i; else Q1[i] = Q1[i + 1];
    }
    up(1, n - 1, i){
        int t = A[i + 1], f = F[t]; // (i, t) 是特殊點(diǎn)
        F[t] = F[i + 1] = ++ o;     // 給特殊點(diǎn)分配編號(hào)
        if(f)
            if(X[f]) Y[f] = o, calc(G[f] + 1, i - 1, V[f], C[t]);
            else     X[f] = o, calc(G[f] + 1, i - 1, U[f], C[t]);
        W[o] = R[i] ^ C[t], G[o] = i;
    }
    up(1, n, i){    // 最后一層都是特殊點(diǎn)
        int t = i, f = F[t]; ++ o, W[o] = R[n] ^ C[i];
        if(f)
            if(X[f]) Y[f] = o, calc(G[f] + 1, n - 1, V[f], C[t]);
            else     X[f] = o, calc(G[f] + 1, n - 1, U[f], C[t]);
    }
    dfs(1); printf("%lld\n", max(I[1], J[1]));
    return 0;
}

💖?喜歡我的文章，記得點(diǎn)贊👍+評(píng)論💬+收藏??+關(guān)注😙の，你的反饋就是我不斷更新的動(dòng)力！

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享題目：第五屆傳智杯-初賽【A組-題解】-創(chuàng)新互聯(lián)
本文路徑：http://muchs.cn/article48/cdcihp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站設(shè)計(jì)、自適應(yīng)網(wǎng)站、服務(wù)器托管、網(wǎng)頁(yè)設(shè)計(jì)公司、外貿(mào)建站、動(dòng)態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)