广东网站建设建站模板,龙岩网站推广公司,网络设计中网络设备选择的原则,上海搬家公司收费价目表第一题#xff1a;最小差值 给定 n 个数#xff0c;请找出其中相差#xff08;差的绝对值#xff09;最小的两个数#xff0c;输出它们的差值的绝对值。 输入格式 输入第一行包含一个整数 n。 第二行包含 n 个正整数#xff0c;相邻整数之间使用一个空格分隔。 输出格式 …第一题最小差值 给定 n 个数请找出其中相差差的绝对值最小的两个数输出它们的差值的绝对值。 输入格式 输入第一行包含一个整数 n。 第二行包含 n 个正整数相邻整数之间使用一个空格分隔。 输出格式 输出一个整数表示答案。 数据范围 对于所有评测用例2≤n≤1000每个给定的整数都是不超过 10000 的正整数。 输入样例1 5
1 5 4 8 20输出样例1 1样例1解释 相差最小的两个数是 5 和 4它们之间的差值是 1。 输入样例2 5
9 3 6 1 3输出样例2 0样例2解释 有两个相同的数 3它们之间的差值是 0。 解题思路
双重循环寻找即可
#includeiostreamusing namespace std;const int N 1010;
int n;
int a[N];int main()
{cin n;for(int i 0;i n;i )cin a[i];int res 0x3f3f3f3f;for(int i 0;i n;i )for(int j i 1;j n;j )res min(res , abs(a[i] - a[j]));cout res endl;return 0;
}
第二题游戏 有 n 个小朋友围成一圈玩游戏小朋友从 1 至 n 编号2 号小朋友坐在 1 号小朋友的顺时针方向3 号小朋友坐在 2 号小朋友的顺时针方向……1 号小朋友坐在 n 号小朋友的顺时针方向。 游戏开始从 1 号小朋友开始顺时针报数接下来每个小朋友的报数是上一个小朋友报的数加 1。 若一个小朋友报的数为 k 的倍数或其末位数即数的个位为 k则该小朋友被淘汰出局不再参加以后的报数。 当游戏中只剩下一个小朋友时该小朋友获胜。 例如当 n5,k2 时 1 号小朋友报数 12 号小朋友报数 2 淘汰3 号小朋友报数 34 号小朋友报数 4 淘汰5 号小朋友报数 51 号小朋友报数 6 淘汰3 号小朋友报数 75 号小朋友报数 8 淘汰3 号小朋友获胜。n 和 k请问最后获胜的小朋友编号为多少 输入格式 输入一行包括两个整数 n 和 k意义如题目所述。 输出格式 输出一行包含一个整数表示获胜的小朋友编号。 数据范围 对于所有评测用例1≤n≤10001≤k≤9。 输入样例1 5 2输出样例1 3输入样例2 7 3输出样例2 4 解题思路
像是约瑟夫环但是对于简单题直接模拟就行
#includeiostream
#includecstringusing namespace std;const int N 1010;
int n , k;
bool st[N];int main()
{cin n k;memset(st , 0 , sizeof st);int now 1;int cnt 0 , last n;while(last ! 1){if(now n 1) now 1;if(!st[now]){cnt ;if(cnt % k 0 || cnt % 10 k) {st[now] true;last --;}}now ;}for(int i 1;i n;i )if(!st[i]) cout i endl;return 0;
}
第三题Crontab 超级大模拟 // 总体思路遍历每一个时间点对每一个时间点遍历所有可能执行的命令
// Task List
// 1. 时间的存储// 1.1 能够实现next: next()// 1.2 能够打印: to_string()
// 2. 任务的存储// 2.1 所有可行时间: bool 数组 check()// 2.2 可读取特定格式的输入: work()# include iostream
# include unordered_map
using namespace std;int months[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
};struct Timer {int year, month, day, week, hour, minute;// 读入初始化Timer(string str) {sscanf(str.c_str(), %04d%02d%02d%02d%02d, year, month, day, hour, minute);}// 格式化打印string to_string() {char str[20];sprintf(str, %04d%02d%02d%02d%02d, year, month, day, hour, minute);return str;}bool operator (const Timer t) const {if (year ! t.year) return year t.year;if (month ! t.month) return month t.month;if (day ! t.day) return day t.day;if (hour ! t.hour) return hour t.hour;return minute t.minute;}int is_leap() {if (year % 400 0 || year % 100 ! 0 year % 4 0) return 1;return 0;}int get_day() {if (month 2) return months[month] is_leap();return months[month];}// nextvoid next() {if ( minute 60) {minute 0;if ( hour 24) {hour 0;week (week 1) % 7;if ( day get_day()) {day 1;if ( month 13) {month 1;year ;}}}}}};struct Task {bool minutes[60], hours[24], day_of_month[32], month[13], day_of_week[7];string name;bool check(Timer t) {return minutes[t.minute] hours[t.hour] day_of_month[t.day] month[t.month] day_of_week[t.week];}
}task[20];unordered_mapstring, int nums;
void init() {string keys[] {jan, feb, mar, apr, may, jun,jul, aug, sep, oct, nov, dec,sun, mon, tue, wed, thu, fri,sat};int values[] {1, 2, 3, 4, 5, 6,7, 8, 9, 10, 11, 12,0, 1, 2, 3, 4, 5,6};for (int i 0; i 19; i )nums[keys[i]] values[i];
}int get(string str) {if (str[0] 0 str[0] 9) return stoi(str);string s;for (auto c: str) s tolower(c);return nums[s];
}void work(string str, bool st[], int len) {if (str.find(*) ! -1) {for (int i 0; i len; i ) st[i] true;}else {// 双指针以,为分界单独处理每一部分for (int i 0; i str.size(); i ) {if (str[i] ,) continue;int j i 1;while (j str.size() str[j] ! ,) j ;string s str.substr(i, j - i);i j; // 不知道为什么不能写成i j 1// 处理单独部分int k s.find(-);if (k ! -1) {int l get(s.substr(0, k)), r get(s.substr(k 1));for (int u l; u r; u ) st[u] true;}else st[get(s)] true;}}
}int main() {init();int n;string start, end;cin n start end;for (int i 0; i n; i ) {string minutes, hours, day_of_month, month, day_of_week, name;cin minutes hours day_of_month month day_of_week name;work(minutes, task[i].minutes, 60);work(hours, task[i].hours, 24);work(day_of_month, task[i].day_of_month, 32);work(month, task[i].month, 13);work(day_of_week, task[i].day_of_week, 7);task[i].name name;}Timer t(197001010000), S(start), E(end);t.week 4;while (t E) {if (!(t S)) {for (int i 0; i n; i ) if (task[i].check(t))cout t.to_string() task[i].name endl;}t.next();}return 0;
}
第四题行车路线 小明和小芳出去乡村玩小明负责开车小芳来导航。 小芳将可能的道路分为大道和小道。 大道比较好走每走 1 公里小明会增加 1 的疲劳度。 小道不好走如果连续走小道小明的疲劳值会快速增加连续走 s 公里小明会增加 s2 的疲劳度。 例如有 5 个路口1 号路口到 2 号路口为小道2 号路口到 3 号路口为小道3 号路口到 4 号路口为大道4 号路口到 5 号路口为小道相邻路口之间的距离都是 2 公里。 如果小明从 1 号路口到 5 号路口则总疲劳值为 (22)^222^2162422。 现在小芳拿到了地图请帮助她规划一个开车的路线使得按这个路线开车小明的疲劳度最小。 输入格式 输入的第一行包含两个整数 n,m分别表示路口的数量和道路的数量。路口由 1 至 n 编号小明需要开车从 1 号路口到 n 号路口。 接下来 m 行描述道路每行包含四个整数 t,a,b,c表示一条类型为 t连接 a 与 b 两个路口长度为 c 公里的双向道路。其中 t 为 00 表示大道t 为 11 表示小道。 保证 1 号路口和 n 号路口是连通的。 输出格式 输出一个整数表示最优路线下小明的疲劳度。 数据范围 对于 30% 的评测用例1≤n≤81≤m≤10 对于另外 20% 的评测用例不存在小道 对于另外 20% 的评测用例所有的小道不相交 对于所有评测用例1≤n≤5001≤m≤1051≤a,b≤nt 是 0 或 1c≤1e5。保证答案不超过 1e6。 输入样例 6 7
1 1 2 3
1 2 3 2
0 1 3 30
0 3 4 20
0 4 5 30
1 3 5 6
1 5 6 1输出样例 76样例解释 从 1 走小道到 2再走小道到 3疲劳度为 5^225然后从 3 走大道经过 4 到达 5疲劳度为 203050最后从 5 走小道到 6疲劳度为 1。 总共为 76。 解题思路
题目给定所有答案不超过1e6其实也就保证了连续小路的长度不超过10001000的平方就是1e6
若要更新k点
大路dist[k][0] dist[i][j] w
小路dist[k][j w] dist[i][j] - j ^ 2 (j w) ^ 2 考虑连续小路的平方
#includeiostream
#includecstring
#includevector
#includequeue
#includealgorithmusing namespace std;const int N 5e5 10 , M 510 , INF 0x3f3f3f3f3f;
int n , m;
int h[N] , ne[N] , w[N] , e[N] , idx 0;
int f[N]; // 大路和小路
int dist[M][1010]; // 从1到点i的最短距离,第二维j表示1到i点这条路径上最后那段(连接i)的小路的长度
bool st[M][1010];struct node
{int x , y , v;bool operator (const nodet) const{return v t.v;}
};void add(int t , int a , int b , int c)
{e[idx] b , f[idx] t , w[idx] c , ne[idx] h[a] , h[a] idx ;
}void dij()
{memset(st , 0 , sizeof st);memset(dist , 0x3f , sizeof dist);priority_queuenodeq;q.push({1 , 0 , 0});dist[1][0] 0;while(!q.empty()){auto t q.top();q.pop();if(st[t.x][t.y]) continue;st[t.x][t.y] true;for(int i h[t.x];~i;i ne[i]){int j e[i] , y t.y;if(f[i]) // 小路{y w[i];// 小路更新if(y 1000){if(dist[j][y] t.v - t.y * t.y y * y){dist[j][y] t.v - t.y * t.y y * y;if(dist[j][y] INF) q.push({j , y , dist[j][y]});}}}else{if(dist[j][0] t.v w[i]){dist[j][0] t.v w[i];if(dist[j][0] INF) q.push({j , 0 , dist[j][0]});}}}}
}int main()
{memset(h , -1 , sizeof h);cin n m;while(m --){int t , a , b , c;cin t a b c;add(t , a , b , c) , add(t , b , a , c);}dij();int res INF;for(int i 0;i 1000;i ) res min(res , dist[n][i]);cout res endl;return 0;
} 第五题商路 dp图论线段树dfs #include string.h
#include iostream
#include vector
using namespace std;
typedef long long ll;
const ll mod 1e18;
const int N 1e5 5;struct Edge
{int t, s, ne;
} e[N];
int h[N], idx1;
void add(int u, int v, int s) { e[idx1] {v, s, h[u]}, h[u] idx1; }ll v[N], f[N];
ll d[N], dp[N];
int sz[N], ind[N], idx2;
void dfs1(int from, ll s)
{// 第一趟 dfs求出 dfs 序、到根节点的距离、子树大小ind[from] idx2, d[idx2] s, sz[from] 1;for (int i h[from]; i; i e[i].ne)dfs1(e[i].t, s e[i].s), sz[from] sz[e[i].t];
}#define sq(x) ((x) * (x)) // 求平方 square记得 x 要加括号(x)
#define ff(x) (dp[x] - sq(d[x])) // 凸包点的纵坐标值
#define dy(x1, x2) (ff(x1) - ff(x2)) // dy/dx 即斜率
#define dx(x1, x2) (d[x1] - d[x2]) // 凸包点的横坐标 d[x]用不上就不单独定义了
struct Node
{bool vis;vectorint q; // 维护的凸包void build(){ // 构造凸包就地算法一趟遍历即可int r 0;for (int i : q){while (r 1 (double)dy(q[r - 1], q[r - 2]) * dx(i, q[r - 1]) (double)dy(i, q[r - 1]) * dx(q[r - 1], q[r - 2]))r--;q[r] i;}q.resize(r);}ll find(int i){ // 二分搜索传入的 i 是原序号ind[i] 为 dfs 序if (!vis)vis 1, build();ll k -2 * (f[i] d[ind[i]]); // 斜率记得取负int l -1, r q.size() - 1; // 如果只有一个点直接取 r 即可while (r - l 1){ // 至少有两个点的时候二分搜索int mid l r 1;if ((double)dy(q[mid 1], q[mid]) (double)k * dx(q[mid 1], q[mid]))r mid; // r 一定是可取的elsel mid; // l 一定是不取的}return dp[q[r]] v[i] - sq(f[i] d[ind[i]] - d[q[r]]);}
} tr[N 2];#define cur tr[x] // 当前节点
#define lch tr[x 1] // 左孩子节点
#define rch tr[x 1 | 1] // 右孩子节点
#define mid (l r 1)
void merge(int x)
{ // 归并排序的 merge 算法cur.q.resize(lch.q.size() rch.q.size());int i 0, j 0, k 0;while (i lch.q.size() || j rch.q.size())if (i lch.q.size())cur.q[k] rch.q[j];else if (j rch.q.size())cur.q[k] lch.q[i];else if (d[lch.q[i]] d[rch.q[j]])cur.q[k] lch.q[i];elsecur.q[k] rch.q[j];
}
void build(int x, int l, int r)
{ // 构造线段树cur.vis 0;if (l r)cur.q.resize(1, l);elsebuild(x 1, l, mid), build(x 1 | 1, mid 1, r), merge(x);
}int L, R, n, T; // [L, R] 为查询的区间
ll query(int x, int l, int r, int i)
{ // [l, r] 为当前节点维护的区间if (l L r R)return cur.find(i);elsereturn max(mid L ? query(x 1, l, mid, i) : 0,mid R ? query(x 1 | 1, mid 1, r, i) : 0);
}
void dfs2(int from)
{if (!h[from])return;// 加引用h 数组用完即弃for (int i h[from]; i; i e[i].ne)dfs2(e[i].t);// from 为原标号ind[from] 为 dfs 序L ind[from] 1, R ind[from] sz[from] - 1;dp[ind[from]] query(1, 1, n, from);
}
int main()
{scanf(%d, T);while (T--){idx1 idx2 0;scanf(%d, n);for (int i 1, u, s; i n; i)scanf(%d%d%lld%lld, u, s, v i, f i), add(u, i, s);dfs1(1, 0), build(1, 1, n), dfs2(1);ll ans 0; // 斜率优化不能对 dp 值取模否则维护不了凸包for (int i 1; i n; i)ans (ans dp[i]) % mod, dp[i] 0;printf(%lld\n, ans);}
}
