algorithm_2024
src | ||
.gitignore | ||
CMakeLists.txt | ||
LICENSE | ||
README.md | ||
test.cpp |
algorithm_2024
algorithm_2024
错题本
Luogu某题
数组越界导致变量异常更改
OJ4980:拯救行动
未考虑无答案(特殊情况)时输出
优先队列是从大到小排序,重载运算符时需反向或者std::greater
for(ll i{0};i<4;i++){
const Point next {status.now.x+to_next[i][0],status.now.y+to_next[i][1]};
if(vis[next.x][next.y])continue;
const auto nextchar = [&next]()->char{return map[next.x][next.y];};
ll cost {1};
if(next.x>h || next.x<=0 || next.y > w || next.y<=0
|| nextchar()=='#')continue;
if(nextchar()=='x')cost++; // 因为这里有可能会遇到士兵,会改变最优解顺序,要使用priority_queue
const Status next_status {next,status.step+cost};
vis[next_status.now.x][next_status.now.y] = true;
q.push(next_status);
}
struct Status{
Point now;
ll step;
bool operator<(const Status &that)const noexcept{
return this->step > that.step;
}
};
std::priority_queue<Status> q;
P1330
BFS时注意初始化一开始的去重数组
void bfs(){
for(ll i{1};i<=n;i++){
color_sum[1]=color_sum[2]=0;
if(vis[i])continue;
q.push(i);
set_color(i, 1);
vis[i]=true; // 注意初始化错误
while(!q.empty()){
P3957
初始状态依赖已走过的部分时注意起始点状态
for(ll coin{0};coin<=(points[n].posit-d);++coin){
for(ll i{0};i<max_n;i++)dp[i]=ll_min;
dp[0]=0; // 注意第0个点是能到达的reachable
非最优解时注意骗分卡时间
const ll max_coin{(ll)1e5+5};//d+g = x[n] -> g = x[n]-d我的推导是这样的,但是错了,必须将max_coin设置为1e5+5也就是s[i]最大值,注意超时问题,可以自己生成样例测试
ll l{0},r{max_coin},ans{ll_max};
while(l<=r){
ll mid{(l+r)/2};
const bool check_ret{check(mid)};
if(check_ret){
ans = mid;
r=mid-1;
}else{
l=mid+1;
}
}
P7414
区间DP思路
/*
区间动态规划解题步骤:
1.根据问题推测dp[i][j]的含义
问题:将第1个到第N个位置涂上指定颜色的最小次数
dp[i][j]的含义:将第i个到第j个位置涂上指定颜色的最小次数
2.根据规则推出dp[i][j]的状态转移公式
在i-j之间找一个中间值k,将i-j这一段分成两段i-k和k+1~j)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
3.边界问题(比如设定dp[0][0],dp[0][j],dp[i][0]初始值)
dp[i][j]=dp[i][j-1]+(a[i]!=a[j]);
dp[i][i]=1;
*/
oj8782
/*
区间动态规划解题步骤:
1.根据问题推测dp[i][j]的含义
问题:长度为N的数字串,要求选手使用K个乘号将它分成K+1个部分
dp[i][j]的含义:长度为i的数字串,要求选手使用j个乘号将它分成j+1个部分
2.根据规则推出dp[i][j]的状态转移公式
在1-i之间找一个中间值k,将1-i这一段分成两段1-k(有j-1个乘号)和k+1~i(没有乘号)
dp[i][j]=max(dp[i][j],dp[k][j-1]*num[k+1][i]);
3.边界问题(比如设定dp[0][0],dp[0][j],dp[i][0]初始值)
num[i][j]
*/