第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛（同步赛）

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

B 小宝的幸运数组

题目

对于小宝来说，如果一个数组的总和能够整除他的幸运数字k，就是他的幸运数组，而其他数组小宝都很讨厌。现在有一个长度为n的数组，小宝想知道这个数组的子数组中，最长的幸运子数组有多长。

对于子数组的定义，如果可以通过从开头和从结束分别删除若干个（可以为零或全部，前后删除个数不必相同）元素来从数组b获得数组a，则称数组a是数组b的子数组。（子数组包含原数组，但不包含空串）

Code

#include<bits/stdc++.h>

typedef long long ll;
using namespace std;

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        for(int i=0;i<n;++i) cin>>a[i];
        int cur=0,ans=-1;
        vector<int> lst(k, -1);
        lst[0]=0;
        for(int i=1;i<=n;++i) {
            cur=(cur+a[i-1])%k;  
            //当前所有数之和 %k的值
            if(lst[cur]!=-1) ans=max(ans,i-lst[cur]); 
            //当相同的余数cur再次出现时，说明两次出现 这中间数的和%k==0，更新ans
            else lst[cur]=i;       
            //lst[cur]记录上次出现该余数的位置
        }
        cout<<ans<<endl;
    }
}

D Seek the Joker I（想了很久都不会，头秃）

题目

一共n张扑克牌作为牌堆，每人每次至多从牌堆顶部抽k张牌，至少抽1张牌。牌堆底部的最后一张牌作为乌龟，抽中的将输掉这一轮比赛，始终都是芳方先抽。
如果芳乃必胜，则输出“yo xi no forever!”，
否则输出 “ma la se mi no.1!”。

Code(附上其他大佬代码)

#include <iostream>
using namespace std;
int main() {
    int T;
    cin >> T;
    while(T--)
    {
        int n,k;
        cin >> n >> k;
        if(!((n-1)%(k+1))) cout<<"ma la se mi no.1!"<<endl; 
    //因为芳方先抽，只要能保证芳方抽完我再抽一次之和，满足k+1，这样最后肯定能使芳方抽到最一张牌

        else cout<<"yo xi no forever!"<<endl;               
    }
    return 0;
}

H 数羊(自己写一直爆内存)

题目

憨憨小杨晚上睡不着觉，就开始数羊，她觉得一只一只数太慢了，想出了一种新的数羊方式，羊羊数量A(n,m)由两个整形变量n和m决定，计算方式如下:

a(1,0)=2
a(0,m)=1 m>=0
a(n,0)=n+2 n>=2
a(n,m)=a(a(n-1,m),m-1) n,m>=1
现在给出n和m的值，请你帮小杨数数一共有多少只羊。

多组输入：
第一行包含一个整数T(1≤T≤1000)，表示有T组测试数据。
每组测试数据包含一行，包含两个整数n(1≤n≤10^9)和m(0≤m≤2).

输出描述:
对每一组输入，在一行中输出A(n,m)的值,由于输出的结果可能会很大，答案对998244353取模

Code

#include<bits/stdc++.h>

typedef long long ll;
using namespace std;

const int mod = 998244353;

ll fpow(ll a,ll b){
    ll r=1;
    for(a%=mod;b;b>>=1){   //>>1位运算，相当于b的各二进制位右移1位，即/2
        if(b&1)      //与运算，若b为奇数，则b&1==1，否则为0
        r=r*a%mod;

        a=a*a%mod;
        }
        return r;
    }
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--) {
        ll n,m;
        cin>>n>>m;
        if(m==0 && n==1) cout<<2<<endl;
        else if(m==0) cout<<n+2<<endl;
        else if(m==1) cout<<2*n%mod<<endl;
        else if(m==2) cout<<fpow(2,n)<<endl;
    }
}