2021 ICPC 江西省大学生程序设计竞赛【ABJHKL】

先补这么多吧。

目录

比赛链接

A Mio visits ACGN Exhibition

B Continued Fraction

J LRU

H Hearthstone So Easy

K Many Littles Make a Mickle

L It Rains Again

比赛链接

牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

A Mio visits ACGN Exhibition

题意：

有n * m个格子，每个格子都有一个数字：0 或 1 。现在我们要从（1,1）走到（n,m），只能往右或者往下走，问存在多少种路线使得至少经过p个0和q个1

思路：

        这题应该还是比较简单的动态规划，就是有两个地方需要优化，我没有想到
        这题主要还是内存限制，数据范围是1 <= n, m <= 500，0 <= p, q <=10000。而我们需要记录他的位置信息以及经过了多少个0和1。因为已知每次经过的总数等于i + j - 1，所以这里只需要记录经过了多少个0或者经过了多少个1就可以了，但也至少需要三维才可以实现，空间复杂度在1e9。

        我用f[ i ][ j ][ k ]来表示当走到第 i 行第 j 列，经过 k 个 1 时的方案总数

        第一个优化：虽然这里p和q的范围给到了10000，但因为每次只能往右或者往左走，所以其实p和q最多只能是1000（这也要欺骗我呜）。但这样复杂度仍然是1e8
        第二个优化：因为最多只可能走到下一行或者当前行，所以当前状态只与这一行和上一行有关，所以可以用滚动数组优化。那dp数组第一维的大小就可以优化到2。现在复杂度只有1e6啦

        ∵  0 ^ 1 = 1；1 ^ 0 = 0
        ∴ 可以用异或来进行这二维的转换

        用s表示当前的行状态，那s ^ 1就表示上一行的状态，s ^= 1就表示走到了下一行。

#include
using namespace std;
const int N = 510;
const int M = 1010;
const int mod = 998244353;
int f[2][N][M];//记录当坐标在(i,j)的时候，经过数字为1的次数是k次
int g[N][N];
int main()
{
    int n, m, p, q;
    cin >> n >> m >> p >> q;
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= m; ++ j)
            cin >> g[i][j];
    int s = 0;
    if(g[1][1]) f[s][1][1] = 1;
    else f[s][1][0] = 1;
    for(int i = 1; i <= n; ++ i)
    {
        for(int j = 1 ; j <= m; ++ j)
        {
            if(i == 1 && j == 1)
                continue;
            for(int k = 0; k <= i + j - 1; ++ k)
            {
                if(g[i][j])
                    f[s][j][k] = (f[s^1][j][k-1] + f[s][j-1][k-1])%mod;
                else
                    f[s][j][k] = (f[s^1][j][k] + f[s][j-1][k])%mod;
            }
        }
        s ^= 1;
    }
    s ^= 1;
    long long ans = 0;
    for(int k = q; k <= n + m - 1; ++ k)
    {
        if(n + m - 1 - k >= p)
            ans = ( ans + f[s][m][k] )%mod;
    }
    cout << ans << endl;
}

B Continued Fraction

每次保存x/y，之后交换分子分母。

#include
#include
using namespace std;
const int N = 110;
int a[N];
int main()
{
    int t;
    cin >> t;
    while( t -- )
    {
        int k = 0;
        int x, y;
        cin >> x >> y;
        while(y)
        {
            int t = x / y;
            a[++k] = t;
            x %= y;
            swap(x, y);
        }
        cout << k - 1 << ' ';
        for(int i = 1; i <= k  ; ++ i)
            cout << a[i] << ' ';
        cout << endl;
    }
    
}

J LRU

参考题解： 2021 ICPC 江西省大学生程序设计竞赛 J.LRU 二分_HeartFireY的博客-CSDN博客

题意：

        感觉这题比较难看懂吧我看了好久 但是看懂了之后题意还是很简单的。
        就是有一个缓存块，里面的容量只有有限个，现在给了n个数字，n个数字一个个放进缓存块里。
        如果缓存块里已有相同的数字，就会发生缓存命中，进行替换；
        如果缓存块里没有相同的数字且缓存块容量满了，新的数字就和放入时间最早的缓存块进行替换；
        如果缓存块里没有相同的数字且缓存块没有满，直接放进去就行了。
        另给了一个数字k，问容量最小为多少，可以发生至少k次的缓存命中。

思路：

        显然是要二分。
        因为放进去的时间先后，其实就是a[i]的编号先后，我们可以用一个set来维护编号先后，map来快速寻找数字对应的下标及缓存块里有没有这个数字。那如果要替换的话，最早进入的其实就是set的第一个，替换后也把对应的map更新就可以了。

#include
using namespace std;
typedef pair PII;
int n, k;
const int N = 1e5 + 10;
int a[N];
bool check(int x)
{
    setst;//放缓存中的数字
    mapmp;//帮助找到每个元素最后一次出现的位置
    int cnt = 0;
    for(int i = 1; i <= n; ++ i)
    {
        if(mp.count(a[i]))//如果缓存里已经有这个数字了 就更新一下坐标
        {
            ++ cnt ;//次数++
            //删除a[i]元素最后一次出现的位置
            st.erase(make_pair(mp[a[i]],a[i]));
            mp[a[i]] = i;
            st.insert(make_pair(i,a[i]));
            continue;
        }
        else if(st.size() == x)//如果缓存已经满了 且缓存里没有该数字 就要删除最早出现的元素然后插入新元素
        {
            PII t = *st.begin();
            st.erase(st.begin());
            mp.erase(t.second);
            mp[a[i]] = i;
            st.insert(make_pair(i,a[i]));
            continue;
        }
        else//如果缓存没有满 且没有相同数字 直接插入就可以了
        {
            mp[a[i]] = i;
            st.insert(make_pair(i,a[i]));
        }
    }
    return cnt >= k;
}
int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; ++ i)
        cin >> a[i];
    int l = 1, r = n, ans = -1;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid))
            r = mid , ans = r;
        else
            l = mid + 1;
    }
    if(ans < 0)
        puts("cbddl");
    else
        cout << ans << endl;
}

H Hearthstone So Easy

题意：

        是轮到每个人的回合时都要经历draw cards，play cards两个过程。如果自己没有牌然后draw cards的话就会消耗一定的体力，play cards可以让对方减k点血量，也可以让自己恢复k点血量。

思路：

        一道博弈论的题吧 不知道为什么看榜单好像没有很多人写出来 但是感觉还是比较容易想到的。

        其实不知道为什么这里说如果玩家牌组没牌的话，抽牌时会将疲劳值增加一倍，然后生命值减去疲劳值。因为其实玩家一直在抽牌和玩牌吧，手里应该是一直没有牌的。

        因为k值以及玩家生命值都是固定且相同的，所以如果慢慢耗下去的话，先手肯定会先死。

        如果先手选择恢复生命值的话，后手肯定选择攻击，这样往复下来，只是玩家对疲劳值的消耗，对先手是不利的，所以先手不会选择恢复。

        由此可知，先手是会一直选择攻击的，而后手一定是会一直选择恢复的，除非到最后轮到后手的时候，先手体力不支，只需要攻击一次先手就“死”了。但这样其实也是对疲劳值的消耗，因为先手攻击多少，后手就可以恢复多少，而先手的体力是先消耗的。

        这样可以推断，如果先手第一次不能把后手攻击死的话，先手必败。

#include
using namespace std;
int main()
{
    int t;
    cin >> t;
    while(t -- )
    {
        int n, k;
        cin >> n >> k;
        if(n == 1)
            puts("freesin");
        else
        {
            if(n-k > 1)
                puts("freesin");
            else
                puts("pllj");
        }
    }
}

K Many Littles Make a Mickle

说签到题就是真签到题

#include
using namespace std;
int main()
{
    
    int t;
    cin >> t;
    while(t --)
    {
        int n, m;
        cin >> n >> m;
        long long ans = 0;
        for(int i = 1; i <= n; ++ i)
            ans += i*i*m;
        cout << ans < 
L It Rains Again 
差分
 
但是这题又有两个小小的不一样
 
1.赛时差点就写出来了 但是一直写的num[x2+1] --。但是这题因为是算的是单位长度而不是有多少个数字，所以应该是num[x2]--。就比如区间[1,2]，其实只挡了1个单位长度的雨
 
2.这题不是求区间和，所以不管区间覆盖多少次，只要覆盖了，就只算一个单位长度。所以下面遍历的时候，只要num[i]>0，ans就只加一
 
#include
#include
using namespace std;
const int N = 100010;
bool st[N];
int num[N];
int main()
{
    int n;
    cin >> n;
    int ans = 0;
    while(n --)
    {
        int x1,x2,y1,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if(x2 < x1) swap(x1, x2);
        num[x1] ++;
        num[x2] --;
    }
    for(int i = 1; i <= 100000; ++ i)
    {
        num[i] += num[i-1];
        if(num[i] > 0) ans++ ;
    }
    cout << ans <