标签：cur int texttt long mp 2023 游记 now CSP

Day X

做了一次模拟赛，考得都很烂，有几次都没有上\(~200~\)。
听说赛前模拟赛发挥失常RP++？

Day 1

7:30

考点就在SCZ，离家不远，但是仍然开车到达考点，在考场边排好队等待，遇到许多大佬，倍感压力，赶紧膜拜以吸收RP。

8:00

进入机房，找到自己的机位，试机。啥都没写出来，随便打几个板子，结果发现自己背的快读有问题，应该是太紧张了:(

8:30

下发密码了，但是木有第一时间看到，过了2分钟才反应过来，打开题目。

8:40

\(\texttt{T1}~\texttt{100pts}\)

第一题好像很简单的样子，一眼就是\(~O(log_3^n)~\)的算法。10分钟切掉，样例和大样例一遍过。代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, ans1, ans2;
bool flag = false;
int main()
{
    freopen("apple.in", "r", stdin);
    freopen("apple.out", "w", stdout);
    cin >> n;
    while(n)
    {
        ans1 ++;
        if((n - 1) % 3 == 0 && !flag) ans2 = ans1, flag = true;
        n -= 1 + (n - 1) / 3;
    }
    cout << ans1 << " " << ans2;
    return 0;
}

9:00

\(\texttt{T2}~\texttt{50pts}\)

第二题一眼DP，推了一会儿发现超时，第二眼贪心，改了半天发现没写前缀和。代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll len[100010], ans;
int n, d, tmp, pay[100010], now, pre;
int main()
{
    freopen("road.in", "r", stdin);
    freopen("road.out", "w", stdout);
    cin >> n >> d;
    for(int i = 1; i < n; i ++) cin >> len[i], len[i] += len[i - 1];
    for(int i = 1; i <= n; i ++) cin >> pay[i];
    pre = pay[1];
    for(int i = 2; i <= n; i ++)
    {
        tmp = (ceil((len[i - 1] - now) * 1.0 / d));
        now += tmp * d, ans += pre * tmp, pre = min(pre, pay[i]);
    }
    cout << ans;
    return 0;
}

样例大样例一遍过，以为第二题\(~\texttt{AC}~\)了结果\(~\texttt{WA}~\)掉了。

11:00

\(\texttt{T3}~\texttt{100pts}\)

第三题一眼大模拟，开干。

写了半天发现就是调不对，结果是化简根号时有问题。

样例过了，大样例发现当\(~\texttt{a}~\)为负数时，自己代码有问题调试。

输出过于繁琐，容易出问题，重构输出部分。

用\(~\texttt{5~min}~\)把自己的答案和大样例答案对照了一下（\(~\texttt{NOI Linux 2.0}~\)不会用）

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
    int a, b, c;
    cin >> a >> b >> c;
    if((b * b - 4 * a * c) < 0)
    {
        cout << "NO\n";
        return;
    }
    if(sqrt(b * b - 4 * a * c) == (int)sqrt(b * b - 4 * a * c))
    {
        int t = (int)sqrt(b * b - 4 * a * c);
        if(2 * a < 0) t = - t;
        if((- b + t) % (2 * a) == 0)
        {
            cout << (- b + t) / (2 * a) << "\n";
            return;
        }
        int p, q, tt = __gcd(- b + t, 2 * a);
        p = (- b + t) / tt;
        q = 2 * a / tt;
        if(p < 0 && q < 0) p = abs(p), q = abs(q);
        else if(q < 0) p -= 2 * p, q = abs(q);
        cout << p << "/" << q << "\n";
        return;
    }
    else
    {
        int t = b * b - 4 * a* c, othr = 1, othr2 = 2 * a, ret = 1;
        if(othr2 < 0) othr2 = - othr2;
        for(int i = 2; i <= t; i ++)
        {
            int cnt = 0;
            while(t % i == 0) cnt ++, t /= i;
            if(cnt % 2 == 0) othr *= pow(i, cnt / 2);
            else othr *= pow(i, cnt / 2), ret *= i;
        }
        int p, q, tt = __gcd(- b, 2 * a);
        p = (- b) / tt;
        q = 2 * a / tt;
        if(p < 0 && q < 0) p = abs(p), q = abs(q);
        else if(q < 0) p -= 2 * p, q = abs(q);
        int ttt = __gcd(othr, othr2);
        othr = othr / ttt;
        othr2 = othr2 / ttt;
        if(p % q == 0)
        {
            if(p / q == 0) cout << "";
            else cout << p / q << "+";
        }
        else cout << p << "/" << q << "+";
        if(othr != 1) cout << othr << "*";
        cout << "sqrt(" << ret << ")";
        if(othr2 != 1) cout << "/" << othr2;
        cout << "\n";
    }
    return;
}
int main()
{
    freopen("uqe.in", "r", stdin);
    freopen("uqe.out", "w", stdout);
    int T, m;
    cin >> T >> m;
    while(T --) solve();
    return 0;
}

12:00

\(\texttt{T4}~\texttt{5pts}\)

第四题一眼\(~\texttt{SPFA}~\)但是没时间调了，打了个暴力\(~\texttt{+~Dij}~\)结束。应该有点分。

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, k, x, y, z, dis[10010], vis[10010], ans = 0x3f3f3f3f, t;
vector<pair<int, int> > mp[10010];
bool flag = true;
void dij()
{
    memset(dis, 0x3f, sizeof dis);
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
    q.push({1, 1});
    while(q.size())
    {
        pair<int, int> cur = q.top();
        q.pop();
        if(cur.second == n)
        {
            cout << cur.first;
            return;
        }
        if(dis[cur.second] < cur.first) continue;
        for(int i = 0; i < mp[cur.second].size(); i ++)
        {
            if(vis[mp[cur.second][i].first] || mp[cur.second][i].second > cur.first) continue;
            dis[cur.second] = min(dis[cur.second], cur.first + 1);
            q.push({cur.first + 1, mp[cur.second][i].first});
        }
    }
    return;
}
void dfs(int tim, int now)
{
    if(tim >= ans) return;
    if(now == n)
    {
        if(tim % k == 0) ans = min(ans, tim);
        return;
    }
    for(int i = 0; i < mp[now].size(); i ++)
    {
        if(vis[mp[now][i].first]) continue;
        if(mp[now][i].second > tim) continue;
        vis[mp[now][i].first] = true;
        dfs(tim + 1, mp[now][i].first);
        vis[mp[now][i].first] = false;
    }
    return;
}
int main()
{
    freopen("bus.in", "r", stdin);
    freopen("bus.out", "w", stdout);
    cin >> n >> m >> k;
    for(int i = 0; i < m; i ++)
    {
        cin >> x >> y >> z, mp[x].push_back({y, z});
        if(z != 0) flag = false;
    }
    if(k == 1 && flag)
    {
        dij();
        return 0;
    }
    for(int i = 0; i <= 5; i ++)
    {
        int strt = i * k;
        dfs(strt, 1);
        if(ans != 0x3f3f3f3f)
        {
            cout << ans;
            return 0;
        }
    }
    cout << -1;
    return 0;
}

Day 2

估分结果如下：

你谷：100 + 50 + 90 + 25 = 265
图灵：100 + 85 + 80 + 10 = 275
云斗：100 + 75 + 80 + 0 = 255
最低：100 + 50 + 80 + 0 = 220
最高：100 + 85 + 90 + 25 = 300

考虑到\(~\texttt{CCF}~\)不会出太大数据，\(\texttt{T3}~\)应该能\(~\texttt{AC}~\)

10.29

拿到成绩，十分伤感：

100 + 50 + 100 + 5 = 255

CSP-J2023 第二轮遗憾落幕。

标签：cur,int,texttt,long,mp,2023,游记,now,CSP
From： https://www.cnblogs.com/Liu-Tao-Chang/p/18343886

CSP-J 2023第二轮游记