每日算法
those times when you get up early and you work hard; those times when you stay up late and you work hard; those times when don’t feel like working — you’re too tired, you don’t want to push yourself — but you do it anyway. That is actually the dream. That’s the dream. It’s not the destination, it’s the journey. And if you guys can understand that, what you’ll see happen is that you won’t accomplish your dreams, your dreams won’t come true, something greater will. mamba out
那些你早出晚归付出的刻苦努力，你不想训练，当你觉的太累了但还是要咬牙坚持的时候，那就是在追逐梦想，不要在意终点有什么，要享受路途的过程，或许你不能成就梦想，但一定会有更伟大的事情随之而来。 mamba out~
2020.3.22
luogu -P3915 树的分解
没话说 ，只能说数据太水 有的直接取模过不了样例就能ac,感觉是正确的做法但是不能ac，嗯 绝了破坏心情的一道题 题解做法是剪掉合法子树统计剪掉的个数
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int N = 100005;
int t , n , k;
vector<int> a[N];
int dfs(int now , int last)
{
int ans = 1;
for(int i = 0;i < a[now].size();i ++)
{
if(a[now][i] == last)continue;
int t = dfs(a[now][i],now);
if(t == -1 || t > k)return -1;
else if(t == k)continue;
ans += t;
}
return ans;
}
int main()
{
cin >> t;
while(t--)
{
cin >> n >> k;
for(int i = 0;i <= n;i ++)a[i].clear();
for(int i = 0;i < n - 1;i ++)
{
int x, y ;
scanf("%d %d", &x ,& y);
a[x].push_back(y);
a[y].push_back(x);
}
int ans = dfs(1,1);
if(ans == k){
cout << "YES" << endl;
}else cout << "NO" << endl;
}
return 0;
}
P3956 棋盘
这题 唉 不说了 debug了两三个小时终于给我整出来了，就是考验你的心态。而且判断分支也是很不好判断得需要对每一个条件把控得很好，而且纯暴力搜索是肯定过不了得，需要进行剪枝，总的来说是一道非常好得题目 就是太让人恼火了
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
const int N = 105;
int a[N][N];
int n , m;
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
/*
可执行操作
1. 只能走到有颜 色的位置上去
2. 只能向上下左右走
3. 相邻两个格子如果颜色相同不需要花费金币
颜色不同需要花费一个金币
4. 花费两个金币施展魔法让下一个无色格子变成指定颜色
5. 魔法不能连续使用当你离开了施展魔法的格子之后这个格子
会自动变成无色
求从左上角到右下角花费的最小金币？
1 --- 黄色 2 ---- 红色
*/
/*
分支策略：
1. 如果其旁边存在颜色相同的就直接走
2. 如果其旁边存在颜色不同的画一个金币走过去
3. 如果其旁边存在空白格子的话捡起变成根该位置相同颜色
在过去走过之后要恢复这个格子的颜色
*/
struct node{
int x, y ,cost, color;
bool gc;
node(int a,int b,int c,int col): x(a) ,y(b),cost(c),color(col){
this->gc = false;
}
};
int mincost = 0x3f3f3f;
int f[N][N] ; // 记录来到当前位置上的最小金币数
void output()
{
cout << endl;
for(int i = 1;i <= m ;i ++)
{
for(int j = 1;j <= m; j++)
{
printf("%d ",f[i][j]);
}
cout << endl;
}
}
bool inmap(int x,int y)
{
return x >= 1 && x <= m && y >= 1 && y <= m;
}
void bfs(node start)
{
fill(f[0],f[0] + N * N, -1); // 初始化每个点都不能到达
f[1][1] = 0;
queue<node> q;
q.push(start);
while(!q.empty())
{
node now = q.front();
for(int i = 0;i < 4 ;i ++)
{
int nx = now.x + dir[i][0];
int ny = now.y + dir[i][1];
if(now.color == a[nx][ny] && a[nx][ny] > 0 && now.color > 0)
{
if(f[nx][ny] == -1 || f[nx][ny] > f[now.x][now.y])
{
f[nx][ny] = now.cost;
q.push(node(nx,ny,f[nx][ny],now.color));
}
}
if(now.color > 0 && a[nx][ny] > 0 && now.color != a[nx][ny])
{
if(f[nx][ny] == -1 || f[nx][ny] > f[now.x][now.y] + 1)
{
f[nx][ny] = f[now.x][now.y] + 1;
q.push(node(nx,ny,f[nx][ny],a[nx][ny]));
}
}
if(a[nx][ny] == 0)
{
// 当前位置本来既有颜色
if(a[now.x][now.y] > 0)
{
if(f[nx][ny] == -1 || f[nx][ny] > f[now.x][now.y] + 2)
{
f[nx][ny] = f[now.x][now.y] + 2;
q.push(node(nx,ny,f[nx][ny],now.color));
}
}//当前位置是施展魔法得来的
if(a[now.x][now.y] == 0)
{
continue;
}
}
}
q.pop();
}
//output();
}
void input()
{
cin >> m >> n;
for(int i = 0;i < n ;i ++)
{
int x, y , c;
scanf("%d %d %d",&x , &y, &c);
a[x][y] = c == 1 ? 1 : 2;
}
}
void work()
{
bfs(node(1,1,0,a[1][1]));
}
int main()
{
input();
/*for(int i = 1;i <= m ;i ++)
{
for(int j = 1;j <= m ;j ++)
{
printf("%d ",a[i][j]);
}
printf("\n");
} */
work();
cout << f[m][m];
return 0;
}