先补这么多吧。
目录
比赛链接
牛客竞赛_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<iostream>
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<iostream>
#include<cstring>
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<bits/stdc++.h>
using namespace std;
typedef pair<int, int > PII;
int n, k;
const int N = 1e5 + 10;
int a[N];
bool check(int x)
{
set<PII>st;//放缓存中的数字
map<int, int>mp;//帮助找到每个元素最后一次出现的位置
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<iostream>
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<iostream>
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 <<endl;
}
}L It Rains Again
差分
但是这题又有两个小小的不一样
1.赛时差点就写出来了?但是一直写的num[x2+1] --。但是这题因为是算的是单位长度而不是有多少个数字，所以应该是num[x2]--。就比如区间[1,2]，其实只挡了1个单位长度的雨
2.这题不是求区间和，所以不管区间覆盖多少次，只要覆盖了，就只算一个单位长度。所以下面遍历的时候，只要num[i]>0，ans就只加一
#include<iostream>
#include<cstring>
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 <<endl;
}
