NOIP2023 国庆集训 A 组 Day2

• 头文件斜杠~写反了~，本地编译没挂，结果暴大零。
  ~喜提30下俯卧撑~

A. 叉叉计算（cross）

• 暴力

#include 
using namespace std;
string s;
int len;
long long sum[87][1000001];
long long ans;
vector sub;
int main() {
    freopen("cross.in", "r", stdin);
    freopen("cross.out", "w", stdout);
    cin >> s;
    len = s.size();
    sub.resize(887);
    for (int j = 0; j < 26; j++)
        for (int i = 0; i < len; i++) {
            if (i != 0)
                sum[j][i] = sum[j][i - 1];
            if (s[i] - 'a' == j) {
                sum[j][i]++;
                sub[j].push_back(i);
            }
        }
    for (int c = 0; c < 26; c++)
        for (int i = 0; i < sub[c].size(); i += 2)
            for (int j = 0; j  0 && sum[j][sub[c][i + 1]] % 2 == 1)
                        ans++;
                }
            }
    cout << ans;
    return 0;
}

B. 病毒分裂（split）

逆元70分,矩阵不会。

#include 
using namespace std;
long long k, n, p;
long long sum;
long long ans;
bool f;
long long quick(long long a, long long b) {
    long long now;
    if (b == 1)
        return a%p;
    if (b % 2 == 0) {
        now = quick(a, b / 2);
        return now%p * now%p;
    } else {
        now = quick(a, (b - 1) / 2);
        return now%p * now%p * a%p;
    }
}
int main() {
    freopen("split.in", "r", stdin);
    freopen("split.out", "w", stdout);
    cin >> k >> n >> p;
    k %= p;
    sum = quick(k, n - 1);
    ans=quick(k-1,p-2);
    cout << (sum - 1)*ans%p;
    return 0;
}

C. 慢跑问题（jogging）

• 广搜

#include 
using namespace std;
int n, l, d;
int ai, bi, ci;
struct note {
    int step, x;
};
note now, ne;
queue q;
vector  adj;
long long w[100001];
int main() {
    freopen("jogging.in", "r", stdin);
    freopen("jogging.out", "w", stdout);
    cin >> n >> l >> d;
    adj.resize(n + 114514);
    for (int i = 1; i > ai >> bi >> ci;
        if (ai > bi)
            swap(ai, bi);
        now.x=bi;
        now.step=ci;
        adj[ai].push_back(now);
    }
    for (int i = 1; i > ai >> bi >> ci;
        if (ai > bi)
            swap(ai, bi);
        now.x=bi;
        now.step=ci*(-1);
        adj[ai].push_back(now);
    }
    now.x = 1;
    now.step = 0;
    q.push(now);
    while (!q.empty()) {
        now = q.front();
        q.pop();
        for (int i = 0; i  ne.step || w[ne.x] == 0) {
                w[ne.x] = ne.step;
                q.push(ne);
            }
        }
    }
    cout << w[n] <= 0)
        cout << "NO";
    else
        cout << "YES";
    return 0;
}