网站系统jsp模板,wordpress智能插件,广州企业网站建设报价,crm是什么意思啊比赛链接
菜鸡的我#xff0c;第四名。。
A 矛盾激化
题意
给定地图#xff0c;这个地图有两个出口#xff0c;现在我们需要求出从所有点到任意一个出口的距离中的最短路径的最大值 本题为输出答案题#xff0c;给定你一种情况#xff0c;然后输出它的答案
题解
如果…比赛链接
菜鸡的我第四名。。
A 矛盾激化
题意
给定地图这个地图有两个出口现在我们需要求出从所有点到任意一个出口的距离中的最短路径的最大值 本题为输出答案题给定你一种情况然后输出它的答案
题解
如果实在不会可以手查滑稽 如果直接从每个点开始搜一遍最短距离不现实 因为只有两个出口所以我们可以从出口出发然后跑两边BFS每个点都维护一个距离的最小值 有几个坑点 1.从出口往里面跳的时候只能跳一个格子 2.从别的格子跳往其他格子时只能跳两个格子 3.跳两格的时候还要判断中间隔过去的一格是不是空格 4.输入的格子有些恶心人
代码
#include iostream
#include cstdio
#include queue
#include cstringconst int INF 2147483647;using namespace std;int n, m, sx[3], sy[3], cnt, ans;
char map[208][90];
int dis[208][90];
int dx[5] {0, 2, 0, -2};
int dy[5] {2, 0, -2, 0};int rx[5] {0, 1, 0, -1};
int ry[5] {1, 0, -1, 0};
struct node {int x, y, sum;
}temp, now;
queuenode Q;
bool vis[208][90];inline void BFS(int num) {memset(vis, 0, sizeof(vis));while (!Q.empty()) Q.pop();vis[sx[num]][sy[num]] 1;temp.sum 0, temp.x sx[num], temp.y sy[num];Q.push(temp);while (!Q.empty()) {now Q.front();int x now.x, y now.y, s now.sum;Q.pop();dis[x][y] min(s, dis[x][y]);for(int i0; i4; i) {int xx dx[i]x, yy dy[i]y;//走两格 int zx rx[i]x, zy ry[i]y;//走一格 if(!vis[xx][yy] map[xx][yy] xx 2*n1 xx 0 yy 2*m1 yy 0 map[zx][zy] (x ! sx[num] || y ! sy[num])) {//普通跳两格 vis[xx][yy] 1;temp.x xx, temp.y yy, temp.sum s1;Q.push(temp);}if(!vis[zx][zy] map[zx][zy] x sx[num] y sy[num] zx 2*n1 zy 2*m1 zx 0 zy 0) {//当从出口往里跳 vis[zx][zy] 1;temp.x zx, temp.y zy, temp.sum s1;Q.push(temp);}}}
}int main() {scanf(%d%d, m, n);for(int i1; i2*n1; i) {for(int j1; j2*m1; j) {dis[i][j] INF;}}gets(map[0]);for(int i1; i2*n1; i) {gets(map[i]1);for(int j1; j2*m1; j) {if(i 1 || j 1 || i 2*n1 || j 2*m1)//边界 if(map[i][j] ) {//记录出口 sx[cnt] i;sy[cnt] j;}}}BFS(1);BFS(2);//从两个出口开始bfs for(int i1; i2*n1; i) {for(int j1; j2*m1; j) {if(dis[i][j] ! INF)ans max(ans, dis[i][j]);}}printf(%d, ans);
}B 我去前面探探路
题意
对于一个树我们可以进行两种操作第一种选择一个节点与该节点相连的边会被标记。第二种:选择第一个节点与该节点相连的边会被标记同时与该节点相连的节点的相连的边也会被标记。这两种操作有各自的花费。问将所有边标记所需花费是多少
题解
树形dp 我们可以发现在儿子节点操作2,与自己操作1对父亲节点的影响一样的 也就是这两种情况在后效性上是等价的 也就是他自己其实也可以被对兄弟操作2给影响 我们可以得到
dp[u][0] 以点u为根的子树下的边全部被覆盖且没有向u节点上方覆盖。也就是u不放u的子节点只能进行操作1
dp[u][1]以点u为根的子树下的边全部覆盖且向上覆盖长度为1。u进行操作1或者u为空u的子节点进行操作2
dp[u][2]以点u为根的子树下的边全部覆盖且向上覆盖长度为2。u进行操作2
dp[u][3]以点u为根的子树的子树里的边都被覆盖但是u和子树间的边不一定被覆盖。也就是父亲节点进行操作2 v是u的儿子节点 dp[u][3]是为了处理 1-2-3-4-5-6-7-8-9c110,c215这种极端的情况只要c2覆盖3和7就能覆盖所有的边
dp[u][j]是不同情况 覆盖以u为节点的子树的最小代价
int tmin(dp[v][0],min(dp[v][1],dp[v][2]));dp[u][0]dp[v][1]; //u的子节点v是1u才能是0向上覆盖长度0不能有2否则就会向上覆盖dp[u][1]t; //向上覆盖长度是1有两种选择 1.在u上放置c1v上123随意 2.u上不放在一个v上放置c2然后其他的v上随意dp[u][2]min(t,dp[v][3]); //u放置了c2子节点v处于什么状态0123都行dp[u][3]t; //因为是状态3所以u和v之间的边被它的父节点覆盖所以v不受上面影响可以当作一个单独的树看待optimalmin(optimal,dp[v][2]-t); //其中一个v上放置c2选择增加费用最小的一个v代码
#includeiostream
#include cstdio
#include cstring
#include cmath
#include algorithm
#include vector
using namespace std;
const int maxn10005,maxc1005,INF0x3f3f3f3f;
int n,c1,c2,a,b,dp[maxn][4];
//dp[u][v]v2,1,0,把放置的装置看作势也就是v的值然后势向周围逐层减小
// 当u上放置c2v2u上放置c1或者离c2一跳是v1当u离c1一跳或者c2两跳时v0
//当v0时u的子节点不能全为0u可以放置东西如果一个点上内有多个v值取最高的
//
//dp[u][0]为在u不部署,而且父节点不为0的情况
// dp[u][1]为在u部署C1dp[u][2]为在u部署C2
// dp[u][3]为在u不部署,而且父节点为0的情况也就是说子节点有一个必须为2
// 覆盖以u为节点的子树的最小代价//dp[u][0]为覆盖子树且向上覆盖长度为0就是u不放u的子节点只能放c1
// dp[u][1]为覆盖子树且向上覆盖长度为1就是在u放置c1或者在u的子节点放c2
// dp[u][2]为覆盖子树且向上覆盖长度为2也就是在u放置c2
// dp[u][3]为u的儿子节点为根的子树被全部覆盖但是u和它的儿子之间的边可能没被完全覆盖就是说父节点上有c2所以不需要
// [3]是为了处理 1-2-3-4-5-6-7-8-9c110,c215这种极端的只要c2覆盖3和7就能覆盖所有的边
// 覆盖以u为节点的子树的最小代价
vectorint graph[maxn];void dfs(int u,int fa){dp[u][0]0;dp[u][1]c1;dp[u][2]c2;dp[u][3]0;if(graph[u].empty()) return;int optimalINF,total0;for(auto itergraph[u].begin();iter!graph[u].end();iter){ //遍历子节点int v*iter;if(vfa) continue;dfs(v,u);int tmin(dp[v][0],min(dp[v][1],dp[v][2]));dp[u][0]dp[v][1]; //u的子节点v是1u才能是0向上覆盖长度0不能有2否则就会向上覆盖dp[u][1]t; //向上覆盖长度是1有两种选择 1.在u上放置c1v上123随意 2.u上不放在一个v上放置c2然后其他的v上随意dp[u][2]min(t,dp[v][3]); //u放置了c2子节点v处于什么状态0123都行dp[u][3]t; //因为是状态3所以u和v之间的边被它的父节点覆盖所以v不受上面影响可以当作一个单独的树看待optimalmin(optimal,dp[v][2]-t); //其中一个v上放置c2选择增加费用最小的一个v}totaloptimaldp[u][3];dp[u][1]min(dp[u][1],total);
}int main(void){while(cinnc1c2 n){
// memset(dp,INF,sizeof(dp));for(int i1;in;i) graph[i].clear();for(int i1;in;i){scanf(%d%d,a,b);graph[a].push_back(b);graph[b].push_back(a);}dfs(1,-1);printf(%d\n,min(dp[1][0],min(dp[1][0],dp[1][1])));}
}
C 数列
题意 题解
题目中说最后的时候a0b0c0作为结束标志 最后一行的元素一定是上一行的答案 那我们就可以逆着往前推导 根据公式 lastans就是上一行的答案把下一行的三个式子带入第一行就可以求出公式可以解出再上个提问的答案。。。
代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int maxn50004;
const int man5e53;
ll w[maxn];
struct node{ll a,b,c;
}x[man];
ll a1;
ll sum[man];
int main()
{
// freopen(in.txt,r,stdin);int n;scanf(%d,n);for(int i1;in;i){scanf(%lld,w[i]);}int tot1;while(~scanf(%lld%lld%lld,x[tot].a,x[tot].b,x[tot].c)){tot;
// if(x[tot-1].a-3x[tot-1].b-3x[tot-1].c-3)break; }tot--;sum[tot]-x[tot].a;for(int i tot-1; i;i--) {a1 (0ll w[sum[i1]] * sum[i1] w[sum[i1]] *w[sum[i1]] * (sum[i1] 1) 1);if(a1 0) sum[i] 1;else sum[i] -(0ll x[i].a * (sum[i1] 1) * w[sum[i1]] * w[sum[i1]] w[sum[i1]] * sum[i1] * (x[i].b 1) x[i].c sum[i1]) / a1;}for(int i2;itot;i){printf(%lld\n,sum[i]);}return 0;}D 点名
题目
在体育课上同学们常常会迟到几分钟但体育老师的点名却一直很准时。 老师只关心同学的身高他会依次询问当前最矮的身高次矮的身高第三矮的身 高等等。在询问的过程中会不时地有人插进队伍里。你需要回答老师每次的询问
题解
使用大根堆和小根堆来解决第k小的问题 建立一个大根堆qu2(大元素在上面)建立一个小根堆qu1 然后大根堆qu2来维护第k小 每次有学生入队新增元素进入我们的两个堆 我们先让学生进入大根堆qu2之后让qu2中最大的元素进入小 根堆qu1这一步目的是为了时刻保持我们大根堆qu2中最大值是我们的第k大也时刻保持qu2中元素只有k个。 如果我们想求第k1大只需将qu1中的最小值调入我们qu2中 。我们qu2中的最大值就是我们的第k1大。
代码
#includeiostream
#includealgorithm
#includecstdio
#includequeue
typedef long long ll;
using namespace std;
const int maxn3e49;
long long a[maxn];
long long b[maxn];
priority_queue ll,vectorll,greaterll q1;
priority_queue ll,vectorll,lessll q2;
int main()
{int n,m;scanf(%d%d,n,m);for(int i1;in;i){scanf(%lld,a[i]);}for(int i1;im;i){scanf(%lld,b[i]);}for(int i1;im;i){for(int jb[i-1]1;jb[i];j){q2.push(a[j]);q1.push(q2.top());q2.pop();}q2.push(q1.top());q1.pop();printf(%lld\n,q2.top());}return 0;
}E 蚂蚁
F 耐久度
G 内存管理
H 采集香料
I 青蛙过河
J 膜法区间
