南宁周赛第1周
认为比较水的题目就不说了。官方大佬也有详细的题解。
hjm的卡牌游戏
首先可能会想到RMQ相关，维护一个线段树保存区间和以及最大值，这样能方便查询每个区间的区间和减去最大值的结果。但是即便维护了这样的线段树，每个区间查询也需要n2的复杂度。
所以这道题肯定需要一个性质优化复杂度。看到数据的范围【-30,30】，且如果最大值是非正数，区间和减去一定是负数了，那还不如L==R取0来的好，于是最大值一定是正数，我们从1开始枚举最大值，数组就只需要遍历一遍了。
其次可能会想到双指针，因为是一个区间范围【l,r】嘛，而且这样也好存前缀和。设定本轮最大值为maxx，r指针不断往后走，当到达一个大于maxx的值时，我们把它放到maxx为其他值的时候再遍历。所以跳过这个数，让l=r+1。
如果【l，r】的区间和本身都小于0了，不如不取这一段，于是让l=r+1，跳过负数区间和的部分。
代码如下：
#include
using namespace std;
const int N=1e5+10;
int a[N],s[N];
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){s[i]=s[i-1]+a[i];}int ans=0;for(int maxx=1;maxx<=30;maxx++){int l=0;for(int r=1;r<=n;r++){if(a[r]>maxx||s[r]-s[l-1]<=0){l=r+1;}if(l hjm学姐想要摸鱼
一道博弈论。博弈论考虑的是必胜状态，最朴素的想法是胜利=还剩一个堆或者每个堆有只有1个果。然后正向递推出胜负状态。
如果我们拿一堆或者拿一排果，对方都走到了胜利点，我们就是失败点。否则，我们只要用最优策略，都是胜利点。可以用递推去推断每个状态是胜负点，进而得到我们的结论。
但是这样的想法不行在于：当每堆抽走一个果的时候，有些堆会被抽没，我们很难把这样的信息表示在低维的数组上。
这道题我认为是这次周赛最难的一题，关键在于会抽象出一个“走格子”的模型。把排序过的数组看做一个果子堆
0
0 0 0
0 0 0 0
0 0 0 0 0
拿掉最多的一堆相当于无效最左边一列，每一堆拿一个相当于抽走最下面一行。
所以当抽掉一行或者一列，就相当于往右或者往上走了一格，走到边界的人必胜。
用一个二维数组status[i][j]表示状态。i代表最大的一堆有多少果，j代表还有多少堆，即我们走到的格子的位置。
了解了这个一切都很好懂了，代码如下：
#include
using namespace std;
const int N=1e5+10;
int a[N],s[N];
bool status[21][21];
int main()
{int n,temp;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);for(int i=n; i>=1; i--) {status[a[i]][i]=1;temp=a[i];while(temp!=a[i-1]) {temp--;status[temp][i]=status[a[i]][i];}}for(int i=2;i<=n;i++){for(int j=a[i]-1;j>=1;j--){if(status[j+1][i]&&status[j][i-1]){status[j][i]=0;}elsestatus[j][i]=1;}}if(status[1][n])cout<<"Yes";elsecout<<"No";return 0;
}
Peach想开邮轮之白嫖篇
看着觉着是个DFS，但是会TLE，要用记忆化搜索去写。
是个基础题，但是我交着错了好几次：）
#include
using namespace std;
int mapp[16][16];
bool vis[16][16];
int oilstore[16][16];
int dp[16][16][10];
int n,m;
int sx,sy,ex,ey;
int d[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int dfs(int x,int y,int oil)
{if(dp[x][y][oil])return dp[x][y][oil];if(oil<=0)return 0x3c;if(x==ex&&y==ey){return 0;}if(mapp[x][y]==4)oil=6;int temp=0x3c;for(int i=0;i<4;i++){int xx=x+d[i][0];int yy=y+d[i][1];if(xx>=0 && yy>=0 && xx1)){//cout<>n>>m;for(int i=0;i>mapp[i][j];if(mapp[i][j]==2){sx=i;sy=j;}if(mapp[i][j]==3){ex=i;ey=j;}}}int ans=dfs(sx,sy,6);if(ans>0x3a){cout<<-1< 小金的猫城堡
一个很简单的Floyd裸题。
数据不大，只要最后敢于暴力地把每两个点之间距离变成零试一遍，利用Floyd的结论就能得到结果。
#include}}cout<<ans<<endl;return 0;
}
小西的卷师
第一眼看是个线段树的维护，单点修改，区间查询。对每个区间，存储前后两个数相乘相加的值。
最后分数取mod，肯定还涉及快速幂求逆元。
代码还没过，未完待续。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！