acm罚坐5个小时,太难受了,连签到都不让签
现在陆续复盘acm省赛试题,当时最有希望做出来的应该是 k题 然后a题比较简单,但是我们没有看出来
e 和 h 题看赛后情况也不难,但是e题不知道怎么判0 ,h题没有读懂
A题:
大意是, 输入n给定 1-n这样n个数,通过+-*() 这几种运算 使值 等于 17
这个题应该是想办法凑出17,然后令后面所有的数都乘以0,就可以解出来,可能是题做的太少导致比赛的时候没有思路
E题:
大意是,给定一个序列 ai 和 和一个数 x , 求区间内的数相乘 mod 998244353 = x
这个题是我负责做的,做了很长时间,最后0的判断上找不到很好的解决方法,另外一个队在0判断上也卡住了。我当时做的时候用的前缀积的思想,这个方法在复杂度上肯定是能过去的,但是需要考虑0的特判,在这个点上卡住了。
思路:没研究明白,晚点更
H题:
大意是,在一个n*m的方格里,有k个人, 然后k次操作,每组操作是一个长度为t的字符串,字符串的每个字符是每秒移动的位置。
思路:我们在维护上一次操作的基础上进行这一秒的判断,可以用map来看看当前位置重叠的人对数,然后减去这个位置重叠的人数,在这个基础上加上新位置重叠的人数。需要求的是重叠的对数,这也就是需要我们先在res加上,再来维护。另外在移动的同时应该判断防止越界。
大佬代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; ll res=0; int mp[2020][2020]; char opt[3020][3020]; pii a[2020]; int main(){ int n,m,k,t; scanf("%d%d%d%d",&n,&m,&k,&t); for(int i=1;i<=k;i++){ int x,y; scanf("%d%d",&x,&y); res+=mp[x][y]; mp[x][y]++; a[i]={x,y}; } for(int i=1;i<=k;i++){ scanf("%s",opt[i]); } printf("%lld\n",res); for(int i=0;i<t;i++){ for(int j=1;j<=k;j++){ char op=opt[j][i]; mp[a[j].first][a[j].second]--; res-=mp[a[j].first][a[j].second]; if(op == 'L') a[j].second = max(a[j].second-1,1); if(op == 'R') a[j].second = min(a[j].second+1,m); if(op == 'U') a[j].first = max(a[j].first-1,1); if(op == 'D') a[j].first = min(a[j].first+1,n); res+=mp[a[j].first][a[j].second]; mp[a[j].first][a[j].second]++; } printf("%lld\n",res); } }
K题:
遗憾程度仅次于A题,这个题差一丢丢就做出来了。
大意是,有a有4种硬币2,13,17,19 然后 b 有4种硬币 5,7,11,13
然后若干组x ,询问谁能用最少的硬币凑出x
思路:首先呢这个题测试输出比较弱,光输入 a的那个 就能通过。但是,补题嘛,咱还是要研究明白。
这个题数据量很大,但是我的对友还是不死心坚持要用完全背包,结果爆了。然后我和另一名队友在研究数论(也就是整数关系,甚至上升到的素数)
说实话,这个题并不是这样。在最后大概一个小时左右的时间我说了句好像到达某个值之后就一直是a用的少,也就是会有一个阈值。
这里其实就是我想到的和正解比较靠近的一个点,正解的做法是 先利用我说的这个性质缩小范围(大概100之外的所有数答案都是a),然后再100以内的区间内进行完全背包的dp。大概就是这样==,感觉亏大了