牛客练习赛133 o3 mini 测试

比赛链接

省流:ABC(DE还没测)(F没过)

方法:开启推理,关闭联网。

A

没有思考,直接给出结果。

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <string>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;
    
    // 用一个哈希表记录:小岛名称 -> 当前已发现的宝藏种类集合
    unordered_map<string, unordered_set<string>> island;
    // 记录至少有一个宝藏被发现的小岛数量
    int islandCount = 0;
    
    while(q--){
        int op;
        cin >> op;
        if(op == 1){
            // 事件1:在名称为 x 的小岛上发现种类为 y 的宝藏
            string x, y;
            cin >> x >> y;
            // 如果该小岛第一次出现,则初始化并更新岛屿数量
            if(island.find(x) == island.end()){
                island[x] = unordered_set<string>();
                islandCount++;
            }
            // 插入宝藏种类(重复的不会重复计数)
            island[x].insert(y);
        }
        else if(op == 2){
            // 事件2:查询名称为 x 的小岛上的宝藏种类数
            string x;
            cin >> x;
            if(island.find(x) == island.end()){
                cout << 0 << "\n";
            } else{
                cout << island[x].size() << "\n";
            }
        }
        else if(op == 3){
            // 事件3:查询名称为 x 的小岛上是否存在宝藏种类 y
            string x, y;
            cin >> x >> y;
            if(island.find(x) == island.end()){
                cout << 0 << "\n";
            } else{
                cout << (island[x].count(y) ? 1 : 0) << "\n";
            }
        }
        else if(op == 4){
            // 事件4:查询至少有一个宝藏被发现的小岛数量
            cout << islandCount << "\n";
        }
    }
    
    return 0;
}

B

给了两种解法:

alt

#include <iostream>
#include <string>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读入 n(以字符串形式)和 p
    string n_str;
    long long p;
    cin >> n_str >> p;
    
    // 模为 1 时,所有数对 1 取模均为 0
    if(p == 1){
        cout << 0;
        return 0;
    }
    
    // 将 p 转为字符串
    string p_str = to_string(p);
    // 判断 n 是否大于等于 p:
    // 如果 n_str 的长度大于 p_str 则 n > p,
    // 如果长度相同则字典序比较
    if(n_str.size() > p_str.size() || (n_str.size() == p_str.size() && n_str >= p_str)){
        // 当 n >= p 时,必有 p | n! ,故 n! mod p = 0
        cout << 0;
    } else {
        // 此时 n < p,可以将 n 转换为 int(此时 n 最多不超过 10^6)
        int n = stoi(n_str);
        long long res = 1;
        for (int i = 2; i <= n; i++){
            res = (res * i) % p;
        }
        cout << res;
    }
    
    return 0;
}

C

第一次尝试没有过样例。

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
 
    // 处理每个询问
    for (int query = 0; query < m; query++){
        string bin;
        cin >> bin;
        int L = bin.size();
        // 用 vector<int> 存储 k 位二进制数,cur[0] 为最低位,cur[k-1] 为最高位。
        vector<int> cur(k, 0);
        // 注意:输入的 bin 字符串最高位在前,如果不足 k 位则前面补 0。
        // 我们把 bin 的低位存到 cur[0],高位存到 cur[k-1]。
        // 对于 i=0..L-1,bin[i](i从 0 开始)对应的位应放到 cur[k - L + i]
        for (int i = 0; i < L; i++){
            cur[k - L + i] = (bin[i]=='1') ? 1 : 0;
        }
 
        // 依次“倒解”每一步:从最后一步 i=n 到第一步 i=1
        for (int idx = n - 1; idx >= 0; idx--){
            if(a[idx] > 0){
                int shift = a[idx];
                // 当 a>0 时,变换:B = x XOR (x << shift)
                // 倒解时,从低位向高位扫描
                for (int j = 0; j < k; j++){
                    if(j >= shift){
                        cur[j] ^= cur[j - shift];
                    }
                }
            } else { // a[idx] < 0
                int r = -a[idx];
                // 当 a<0 时,变换:B = x XOR (x >> r)
                // 倒解时,从高位向低位扫描
                for (int j = k - 1; j >= 0; j--){
                    if(j + r < k){
                        cur[j] ^= cur[j + r];
                    }
                }
            }
        }
 
        // 此时 cur 即为 x 的二进制位(LSB 在 cur[0],MSB 在 cur[k-1])
        // 我们需要从最高位开始输出,省去多余的前导 0(但 x=0 时输出 "0")
        int pos = k - 1;
        while(pos > 0 && cur[pos] == 0)
            pos--;
 
        string ans;
        for (int i = pos; i >= 0; i--){
            ans.push_back(cur[i] ? '1' : '0');
        }
        cout << ans << "\n";
    }
    return 0;
}

反馈后调试通过了:

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    
    // 处理每个询问
    // 注意:输入的二进制串从最高位到最低位(无前导 0,即使 y=0 时也输入 "0")
    // 我们内部把数字表示为一个长度为 k 的二进制数组 cur,其中 cur[0] 为最低位,cur[k-1] 为最高位。
    for (int query = 0; query < m; query++){
        string bin;
        cin >> bin;
        int L = bin.size();
        // 构造一个长度为 k 的位数组,低位在下标 0
        vector<int> cur(k, 0);
        // 将输入的二进制串转换进来:输入串的最后一个字符对应最低位
        // 若不足 k 位,则高位补 0
        for (int i = 0; i < k; i++){
            if(i < L)
                cur[i] = (bin[L - 1 - i] == '1');
            else
                cur[i] = 0;
        }
 
        // 逆向“解开” F 的变换:从最后一步到第一步
        // 每一步都是可逆的,且:
        // 1. 当 a > 0 时:正向为 x -> x XOR (x << a)
        //    逆向公式:对 j 从 0 到 k-1,如果 j>=a 则 x[j] = B[j] XOR x[j-a]
        // 2. 当 a < 0 时:记 r=-a,正向为 x -> x XOR (x >> r)
        //    逆向公式:对 j 从 k-1 到 0,如果 j+r < k 则 x[j] = B[j] XOR x[j+r]
        for (int idx = n - 1; idx >= 0; idx--){
            if(a[idx] > 0){
                int shift = a[idx];
                // 逆解时从低位向高位扫描
                for (int j = 0; j < k; j++){
                    if(j >= shift){
                        cur[j] ^= cur[j - shift];
                    }
                }
            } else { // a[idx] < 0
                int r = -a[idx];
                // 逆解时从高位向低位扫描
                for (int j = k - 1; j >= 0; j--){
                    if(j + r < k){
                        cur[j] ^= cur[j + r];
                    }
                }
            }
        }
 
        // 此时 cur 存储的就是 x 的二进制表示(低位在 cur[0],高位在 cur[k-1])
        // 输出时要求从最高位到最低位,且不输出多余前导 0,但若 x==0 则输出 "0"
        int pos = k - 1;
        while(pos > 0 && cur[pos] == 0)
            pos--;
 
        string ans;
        for (int i = pos; i >= 0; i--){
            ans.push_back(cur[i] ? '1' : '0');
        }
        cout << ans << "\n";
    }
 
    return 0;
}

(今天达上限了,TODO)

F

第一次尝试没有过样例。

#include <bits/stdc++.h>
using namespace std;
 
// 以下几个函数用于大整数(以字符串表示,保证不含前导零,除数字"0"外)之间的比较和加减运算。
 
// 返回 true 当且仅当 s1 < s2(均为非负整数的字符串表示)
bool lessThan(const string &s1, const string &s2) {
    if(s1.size() != s2.size()) return s1.size() < s2.size();
    return s1 < s2;
}
 
// s1, s2 均为非负整数的字符串表示,返回 s1+s2 的字符串表示
string addBig(const string &s1, const string &s2) {
    int i = s1.size()-1, j = s2.size()-1, carry = 0;
    string res;
    while(i>=0 || j>=0 || carry){
        int d1 = i>=0 ? s1[i]-'0' : 0;
        int d2 = j>=0 ? s2[j]-'0' : 0;
        int sum = d1+d2+carry;
        carry = sum/10;
        res.push_back('0'+(sum%10));
        i--; j--;
    }
    reverse(res.begin(), res.end());
    // 去除前导零(若有)
    int pos=0; while(pos<res.size()-1 && res[pos]=='0') pos++;
    return res.substr(pos);
}
 
// 返回 s1 - s2 的字符串表示(保证 s1>=s2)
string subBig(const string &s1, const string &s2) {
    int i = s1.size()-1, j = s2.size()-1, carry = 0;
    string res;
    while(i>=0){
        int d1 = s1[i]-'0';
        int d2 = j>=0 ? s2[j]-'0' : 0;
        int diff = d1 - d2 - carry;
        if(diff < 0){ diff += 10; carry = 1; }
        else carry = 0;
        res.push_back('0'+diff);
        i--; j--;
    }
    reverse(res.begin(), res.end());
    int pos=0; while(pos<res.size()-1 && res[pos]=='0') pos++;
    return res.substr(pos);
}
 
// 判断 s1 == s2
bool equalBig(const string &s1, const string &s2) {
    return s1 == s2;
}
 
// 判断 s1 <= s2
bool leqBig(const string &s1, const string &s2) {
    return lessThan(s1, s2) || equalBig(s1,s2);
}
 
// 将一个小整数(最多 10^6)转成字符串
string toStringLL(long long x){
    string s = "";
    if(x==0) return "0";
    while(x){
        s.push_back('0' + (x % 10));
        x /= 10;
    }
    reverse(s.begin(), s.end());
    return s;
}
 
// 模运算(这里 mod 为 int)
const long long MOD = 998244353;
 
// 注意:下面的函数仅用于处理那些不超过 10^6 的非负整数(以 long long 表示)
// 对于大数运算,我们只需要比较、加减、取模这些简单操作。
 
// 主函数
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T; cin >> T;
    // 对于每组测试数据,我们读入 n, a, b(以字符串形式)
    while(T--){
        string sn, sa, sb;
        cin >> sn >> sa >> sb;
        // 为了后面方便比较,我们认为 sn, sa, sb 都不含前导 0(除 "0" 外)。
 
        // 先判断非交情况:若 a + b <= n
        // 这里先计算 sum = sa + sb
        string sumAB = addBig(sa, sb);
        // 若 sumAB <= sn+"0"?不行,我们要比较 a+b 和 n.
        // 注意:a,b,n 均正整数,且 1<=a,b<=n。
        // 判断 a+b <= n 等价于 (a+b) < n 或 (a+b)==n.
        if( lessThan(sumAB, sn) || equalBig(sumAB, sn) ){
            // 非重叠情况
            long long cnt1 = (sa=="1" ? 1LL : 2LL);
            long long cnt2 = (sb=="1" ? 1LL : 2LL);
            long long ans = (cnt1 * cnt2) % MOD;
            cout << ans % MOD << "\n";
        } else {
            // 重叠情况,即 a+b > n
            // 先判断是否有“全区间反转”
            if( equalBig(sa, sn) || equalBig(sb, sn) ){
                cout << 2 << "\n";
            } else {
                // 定义 x = a+b - n
                string x = subBig(sumAB, sn);
                // 接下来我们需要计算 F(n,a,b)= 2*( min(a,b) - x + 1 ) + 2*x .
                // 注意 min(a,b)(两个大整数,但 a,b 的位数不超过 n 的位数,即最多 10^100,实际上取 min 后结果依然可能很大,
                // 但因为最后要求 mod 998244353,我们只需要将参与加法、乘法的部分对 998244353 取模)。
                // 这里我们把 min(a,b) 转换成一个小整数。事实上可以证明,当 a+b>n 且 a,b<n 时,答案只有两部分来源:
                // 一部分来自“仅在前/后区间反转”贡献 2*( min(a,b) - x + 1 ),
                // 一部分来自两者同时反转贡献 2*x 。
                // (证明见题解。)
 
                // 由于 a,b,x 可能非常大,我们只需要将它们对 MOD 取模。这里我们写一个简单的函数将大整数字符串对 MOD 取模。
                auto modBig = [&](const string &s) -> long long {
                    long long res = 0;
                    for (char c: s){
                        res = (res*10 + (c-'0')) % MOD;
                    }
                    return res;
                };
                long long mina = (lessThan(sa,sb) ? modBig(sa) : modBig(sb)); // min(a,b) mod MOD
                long long xmod = modBig(x); // x mod MOD
                // 计算 (min(a,b) - x + 1) mod MOD:
                long long term = ( (mina + MOD) - xmod + 1 ) % MOD;
                long long part1 = (2 * term) % MOD;
                long long part2 = (2 * xmod) % MOD;
                long long ans = (part1 + part2) % MOD;
                cout << ans % MOD << "\n";
            }
        }
    }
    return 0;
}

反馈后依旧没有通过,放弃尝试:

#include <bits/stdc++.h>
using namespace std;
 
// 我们把大整数均以不含前导零的字符串表示("0" 除外)。
 
// 比较两个非负整数(字符串形式),返回 true 当且仅当 s1 < s2
bool lessThan(const string &s1, const string &s2) {
    if(s1.size() != s2.size()) return s1.size() < s2.size();
    return s1 < s2;
}
 
// 判断 s1 == s2
bool equalBig(const string &s1, const string &s2) {
    return s1 == s2;
}
 
// s1+s2(字符串形式)
string addBig(const string &s1, const string &s2) {
    int i = s1.size()-1, j = s2.size()-1, carry = 0;
    string res;
    while(i >= 0 || j >= 0 || carry){
        int d1 = (i >= 0 ? s1[i]-'0' : 0);
        int d2 = (j >= 0 ? s2[j]-'0' : 0);
        int sum = d1 + d2 + carry;
        carry = sum / 10;
        res.push_back('0' + (sum % 10));
        i--; j--;
    }
    reverse(res.begin(), res.end());
    // 去除前导零
    int pos = 0; while(pos < res.size()-1 && res[pos]=='0') pos++;
    return res.substr(pos);
}
 
// s1 - s2 (保证 s1>=s2)
string subBig(const string &s1, const string &s2) {
    int i = s1.size()-1, j = s2.size()-1, carry = 0;
    string res;
    while(i >= 0){
        int d1 = s1[i]-'0';
        int d2 = (j >= 0 ? s2[j]-'0' : 0);
        int diff = d1 - d2 - carry;
        if(diff < 0){ diff += 10; carry = 1; } else carry = 0;
        res.push_back('0' + diff);
        i--; j--;
    }
    reverse(res.begin(), res.end());
    int pos = 0; while(pos < res.size()-1 && res[pos]=='0') pos++;
    return res.substr(pos);
}
 
// s1 * s2, 但此处 s2保证不超过10^6,结果以字符串返回
string mulBig(const string &s1, long long s2) {
    int carry = 0;
    string res;
    for (int i = s1.size()-1; i >= 0; i--){
        long long prod = (s1[i]-'0') * s2 + carry;
        carry = prod / 10;
        res.push_back('0' + (prod % 10));
    }
    while(carry){
        res.push_back('0' + (carry % 10));
        carry /= 10;
    }
    reverse(res.begin(), res.end());
    int pos = 0; while(pos < res.size()-1 && res[pos]=='0') pos++;
    return res.substr(pos);
}
 
// s1 除以 2,s1 为偶数,返回商(字符串)
string div2(const string &s1) {
    string res;
    int rem = 0;
    for (char c: s1) {
        int cur = rem*10 + (c-'0');
        res.push_back('0' + cur/2);
        rem = cur % 2;
    }
    int pos = 0; while(pos < res.size()-1 && res[pos]=='0') pos++;
    return res.substr(pos);
}
 
// 计算 s1 mod mod,其中 s1 为较大的正整数(字符串),mod 为 int
long long modBig(const string &s1, long long mod) {
    long long res = 0;
    for (char c: s1){
        res = (res*10 + (c-'0')) % mod;
    }
    return res;
}
 
// 将一个大整数(字符串)加上一个小整数 x(用 long long 表示),返回字符串(结果保证非负)
string addBigLL(const string &s1, long long x) {
    string xStr = to_string(x);
    return addBig(s1, xStr);
}
 
// 将一个大整数(字符串)减去一个小整数 x (s1 >= x),返回字符串
string subBigLL(const string &s1, long long x) {
    string xStr = to_string(x);
    return subBig(s1, xStr);
}
 
// 模 998244353
const long long MOD = 998244353;
 
// 下面的函数用于计算组合数形如 C(t+1,2)= t*(t+1)/2 mod MOD,其中 t 为大整数(字符串),t 不超过 10^100。
// 我们只需要将 t mod MOD 取出,然后计算 (t*(t+1)/2) mod MOD 。
long long comb2(const string &t) {
    long long tm = modBig(t, MOD);
    long long t1 = (tm + 1) % MOD;
    long long prod = (tm * t1) % MOD;
    // 因为 MOD 为质数且 2 的逆元存在(inv2=499122177)
    long long inv2 = 499122177;
    return (prod * inv2) % MOD;
}
 
// 我们还需要对大整数做加减运算后取模运算。为方便起见,我们只对那些不超过 10^6 的数直接转换为 long long。
 
// 为了方便,我们将“比较大小”运算用于 a,b,n均为字符串。
 
// 主思路:先判断区间是否重叠,即比较 a+b 与 n。
// 注意:a,b,n均为正整数(字符串)且 1 <= a,b <= n。
 
// 最后证明(见题解)得到:
//
// ─ 若 a+b <= n,答案 = ((a==1)?1:2)*((b==1)?1:2) mod MOD.
// ─ 若 a+b > n,则令 x = a+b-n:
//
//     • 若 a==n 或 b==n:
//         - 若 a==n 且 b==n,答案 = 2.
//         - 否则答案 = 8.
//     • 否则(即 a,b<n 且 a+b>n),答案为
//
//         ans = 2 * ( comb2( subBig( addBig(n, "1"), subBigLL(x,0) ) ) - comb2( subBig( addBig(n, "1"), subBig(a, "0") ) )
//                 - comb2( subBig( addBig(n, "1"), subBig(b, "0") ) ) + 2 ) mod MOD .
// 
// (证明过程较长,此处只给出最终公式;读者可参考相关文献。) 
//
// 注意:上式中的所有减法、加法均在大整数(字符串)意义下进行,然后再取模。
 
// 为简化,我们先计算 T = n + 1 (大整数加法)
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
    while(T--){
        string sn, sa, sb;
        cin >> sn >> sa >> sb;
        // 首先判断 a+b 与 n 的大小:计算 sum = sa+sb
        string sumAB = addBig(sa, sb);
        // 若 sumAB <= sn,则非重叠情况
        if( lessThan(sumAB, sn) || equalBig(sumAB, sn) ){
            long long f1 = ( (sa=="1") ? 1LL : 2LL );
            long long f2 = ( (sb=="1") ? 1LL : 2LL );
            long long ans = (f1 * f2) % MOD;
            cout << ans % MOD << "\n";
        } else { // 重叠情况,即 a+b > n
            // 判断是否有全区间反转
            if( equalBig(sa, sn) || equalBig(sb, sn) ){
                if( equalBig(sa, sn) && equalBig(sb, sn) )
                    cout << 2 << "\n";
                else
                    cout << 8 << "\n";
            } else {
                // 令 x = a+b - n
                string x = subBig(sumAB, sn);
                // 接下来令 T = n + 1
                string Tn = addBig(sn, "1");
                // 计算组合数 C(Tn,2) = Tn*(Tn-1)/2 模 MOD
                long long combT = comb2( subBig(Tn, "1") ); // 注意:这里仅作辅助计算,不直接用
                // 同理,计算 U = n - a + 1 及 V = n - b + 1
                string Ua = subBig(sn, sa);
                Ua = addBig(Ua, "1"); // Ua = n - a + 1
                string Vb = subBig(sn, sb);
                Vb = addBig(Vb, "1"); // Vb = n - b + 1
                // 计算组合数 C(Ua+1,2) 与 C(Vb+1,2)
                string UaPlus = addBig(Ua, "1");
                string VbPlus = addBig(Vb, "1");
                long long combUa = comb2( subBig(UaPlus, "1") );
                long long combVb = comb2( subBig(VbPlus, "1") );
                // 同时计算 W = n - x + 1
                string Wx = subBig(sn, x);
                Wx = addBig(Wx, "1");
                string WxPlus = addBig(Wx, "1");
                long long combWx = comb2( subBig(WxPlus, "1") );
 
                // 最终答案公式为
                //    ans = 2 * ( combWx - combUa - combVb + 2 ) mod MOD.
                long long ans = (2 * (( ( (combWx - combUa) % MOD - combVb) % MOD + MOD ) % MOD + 2)) % MOD;
                if(ans < 0) ans = (ans % MOD + MOD) % MOD;
                cout << ans % MOD << "\n";
            }
        }
    }
    return 0;
}
全部评论

相关推荐

07-07 17:06
已编辑
深圳技术大学 golang
点赞 评论 收藏
分享
06-10 21:15
门头沟学院 Java
宁阿:好多这种没🧠的公司,他们估计都不知道毕业的人不能给安排实习岗
实习吐槽大会
点赞 评论 收藏
分享
07-09 18:28
门头沟学院 Java
写着提前批,结果还要实习4个月以上???
程序员牛肉:这种不用看,直接投了,面试的时候问对应的HR就行。有可能他们是直接复制的暑期实习的模板。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务