吉比特9.19笔试

第一题

给出n,d,m,分别代表多项式个数、维度和修改次数。
接下来n行以t开头，接下来t+1个数分别代表0次1次--的项系数
接下来m行以p,l,r开头分别代表修改第l个到第r个多项式的前p+1项系数。
最后输出n个多项式f(233)的结果，要求结果对1e7 + 9取模。

最后计算结果的次数上限设置为500的时候偶尔超时，多提交几次就AC了

#include <bits/stdc++.h>  
using namespace std;  
const int mod = 1e7 + 9;  
  
int main() {  
    int n, d,m;  
    cin >> n >> d >> m;  
    long long diff[5005][505];  
    long long nums[5005][505];  
    int time[5005];  
  
    for (int i = 0; i < n; i++) {  
        cin >> time[i];  
        for (int j = 0; j <= time[i]; j++) {  
            cin >> nums[i][j];  
        }  
    }  
    for (int i = 0; i < m; i++) {  
        int p,l,r;  
        cin >> p >> l >> r;  
        for (int j = 0; j <= p; j++) {  
            long long tmp;  
            cin >> tmp;  
            if (i % 2 == 0) tmp *= -1;  
            diff[l - 1][j] = (diff[l - 1][j] + tmp + mod) % mod;  
            diff[r][j] = (diff[r][j] - tmp + mod) % mod;  
        }  
    }  
    //依次计算每个多项式的数值  
  
    for (int i = 0; i < n; i++) {  
        long long res = 0;  
        long long base = 1;  
        for (int j = 0; j <= 500; j++) {  
            res = (res + ((nums[i][j] + diff[i][j]) * base) % mod) % mod;  
            base = (base * 233)%mod;  
            diff[i + 1][j] = (diff[i + 1][j] +  diff[i][j]) % mod;  
        }  
        if (i != n - 1) cout << res << " ";  
        else cout << res;  
    }  
}  
// 64 位输出请用 printf("%lld")

第二题

给定一个有正有负的序列，求其中的连续序列的最小和，不能为空序列。
直接贪心求解，注意不能为空。

#include <bits/stdc++.h>  
using namespace std;  
  
int main() {  
    int n;  
    cin >> n;  
    vector<int> nums;  
    long long now = 0;  
    long long res = 1e7;  
    for (int i = 0; i < n; i++) {  
        long long tmp;  
        cin >> tmp;  
        now = now + tmp;  
        res =min(res, now);  
        now = min(0LL, now);  
    }  
    cout << res;  
}  
// 64 位输出请用 printf("%lld")

第三题

给定一个\(n*m\)大小的地图，给出A和B分别所处的位置\(x1,y1,x2,y2\),地图上同时还存在k个水源。每一秒水源都会往四个方向扩张，请问A和B在多少秒后能够相遇，如果不能相遇输出-1
逃离火灾变种问题，暴力求解即可。

#include <bits/stdc++.h>  
using namespace std;  
  
int main() {  
    int T;  
    cin >> T;  
    while (T--) {  
        int n,m;  
        cin >> n >> m;  
        vector<vector<int>> vim(n + 1, vector<int>(m + 1, 0));  
        deque<pair<int, int>>dqw;  
        deque<pair<int, int>>dq1;  
        deque<pair<int, int>>dq2;  
        int x1,y1,x2,y2;  
        cin >> x1 >> y1 >>x2 >> y2;  
        dq1.push_back(make_pair(x1,y1));  
        dq2.push_back(make_pair(x2,y2));  
        vim[x1][y1] = 1;  
        vim[x2][y2] = 2;  
        int k;  
        cin >> k;  
        for (int i = 0; i < k; i++) {  
            int x,y;  
            cin >> x >> y;  
            vim[x][y] = 3;  
            dqw.push_back(make_pair(x,y));  
        }  
        vector<vector<int>> dir{{0,1},{0,-1},{1,0},{-1,0}};  
        int step = 0;  
        int flag = false;  
        int res = -1;  
        while ((!flag) && (!dq1.empty()) || (!dq2.empty())) {  
            step += 1;  
            int t = dqw.size();  
            for (int i = 0; i < t; i++) {  
                int x = dqw.front().first;  
                int y = dqw.front().second;  
                dqw.pop_front();  
                for (int j = 0; j < 4; j++) {  
                    int xx = x + dir[j][0];  
                    int yy = y + dir[j][1];  
                    if (xx <= 0 || xx > n || yy <= 0 || yy > m || vim[xx][yy] == 3) continue;  
                    vim[xx][yy] = 3;  
                    dqw.push_back(make_pair(xx,yy));  
                }  
            }  
            t = dq1.size();  
            for (int i = 0; i < t; i++) {  
                int x = dq1.front().first;  
                int y = dq1.front().second;  
                dq1.pop_front();  
                for (int j = 0; j < 4; j++) {  
                    int xx = x + dir[j][0];  
                    int yy = y + dir[j][1];  
                    if (xx <= 0 || xx > n || yy <= 0 || yy > m || vim[xx][yy] == 3|| vim[xx][yy] == 1) continue;  
                    if (vim[xx][yy] == 2) {  
                        flag = true;  
                        if (res == -1) res = step;  
                    }  
                    if (vim[xx][yy] == 0) {  
                        vim[xx][yy] = 1;  
                        dq1.push_back(make_pair(xx,yy));  
                    }  
                }  
            }  
            t = dq2.size();  
            for (int i = 0; i < t; i++) {  
                int x = dq2.front().first;  
                int y = dq2.front().second;  
                dq2.pop_front();  
                for (int j = 0; j < 4; j++) {  
                    int xx = x + dir[j][0];  
                    int yy = y + dir[j][1];  
                    if (xx <= 0 || xx > n || yy <= 0 || yy > m || vim[xx][yy] == 3 || vim[xx][yy] == 2) continue;  
                    if (vim[xx][yy] == 1) {  
                        flag = true;  
                        if (res == -1) res = step;  
                    }  
                    if (vim[xx][yy] == 0) {  
                        vim[xx][yy] = 2;  
                        dq2.push_back(make_pair(xx,yy));  
                    }  
                }  
            }  
        }  
        if (flag) cout << res << endl;  
        else cout << -1 << endl;  
    }  
}  
// 64 位输出请用 printf("%lld")