-
算法课作业1
https://vjudge.net/contest/581138
A - Humidex
模拟题
题目大意
给三个类型数字通过公式来回转化
思路
求e的对数有log函数，不懂为什么不会出精度错误，很迷，给的三个数字也没有顺序，需要多判断。
#include#include #include //Sometimes weather reports give the temperature and dewpoint, // or the temperature and humidex /* D 15.0 H 34.0 D 25.0 H 42.3 E */ using namespace std; int main() { char a,b; double a1,b1; while(1) { cin>>a; if(a=='E') break; cin>>a1>>b>>b1; if(a=='T'&&b=='D'||a=='D'&&b=='T') { if(a=='D'&&b=='T') swap(a1,b1); double e=6.11*(pow(2.718281828,5417.7530*((1/273.16)-(1/(b1+273.16))))); double h=0.5555*(e-10.0); double humidex = a1+h; printf("T %.1lf D %.1lf H %.1lf\n",a1,b1,humidex); } else if(a=='T'&&b=='H'||a=='H'&&b=='T') { if(a=='H'&&b=='T') swap(a1,b1); double dewpoint; double h=b1-a1; double e=h/0.5555+10.0; double x=log(e/6.11)/5417.753; dewpoint=1/(1/273.16-x)-273.16; printf("T %.1lf D %.1lf H %.1lf\n",a1,dewpoint,b1); } else // d h { if(a=='H'&&b=='D') swap(a1,b1); double e=6.11*pow(2.718281828,5417.7530*((1/273.16)-(1/(a1+273.16)))); double h=(0.5555)*(e - 10.0); double temperature=b1-h; printf("T %.1lf D %.1lf H %.1lf\n",temperature,a1,b1); } } } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
B - Moving Tables
题目大意
两排都是房间，一排两百个房间，上面按奇数，下面按偶数编号，之后房间两两之间要搬桌子，搬桌子期间中间通道全部占用，可同步进行，搬一次10分钟，求最小时间
思路
就把中间通道编号，奇数和偶数的编号调成1-200，之后对区间进行累加，重合次数最多的就是最小时间。注意坑就是，区间不一样从小到大，l,r要判断一下大小。
#include#include #include #include using namespace std; int box[205]; /* 3 4 10 20 30 40 50 60 70 80 2 1 3 2 200 3 10 100 20 80 30 50 */ int main() { int T; cin>>T; while(T--) { int n; cin>>n; memset(box,0,sizeof(box)); int maxx=0; for(int i=1; i<=n; i++) { int l,r; cin>>l>>r; if(l%2==1) l=l+1; if(r%2==1) r=r+1; l=l/2; r=r/2; if(l>r) swap(l,r); for(int j=l; j<=r; j++) { box[j]++; maxx=max(box[j],maxx); } } printf("%d\n",maxx*10); } } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
C - Counterfeit Dollar
题意
有12个硬币，现在知道其中有一个假的，已知称三次天平可以找出来假硬币，假硬币有可能轻或重，每次给三组称量结果，求出哪个是硬币，是轻是重。
思路
好丑陋的代码，不懂为啥我写的这么长，思路不太好吧，我的思路就是去暴力枚举每一个假硬币，并且枚举它是轻的假还是重的假，用box数组记录每次天平上各个位置的重量，真硬币就算重量1，假轻硬币就重量0，假重硬币就重量10，最后判断，找出来就行，模拟题，写的是真费劲，OJ还不支持string 用的char还查了一堆函数，费劲，代码能力现在下降严重。
#include#include #include #include using namespace std; /* 1 ABCDEF GHIJKL up ABC DEF even I J down */ int box[20]; int main() { int n; cin>>n; while(n--) { char a[3][15],b[3][15],c[3][15]; memset(box,0,sizeof(box)); for(int i=0; i<3; i++) { scanf("%s %s %s",a[i],b[i],c[i]); strcat(a[i],b[i]); } for(int i=1; i<=12; i++) // 枚举每个都是假币 { char x='A'+i-1; // 假币轻 int flagt=0; int pos,lenn; char t[20]; for(int j=0; j<3; j++) { memset(box,0,sizeof(box)); int len=strlen(a[j]); for(int k=0; k<len; k++) { if(a[j][k]!=x) box[k]++; if(a[j][k]==x) { pos=k; lenn=len; // t=c[j]; strcpy(t,c[j]); } } int box1=0,box2=0; for(int k=0; k<len/2; k++) box1+=box[k]; for(int k=len/2; k<len; k++) box2+=box[k]; if(strcmp(c[j],"even")==0&&box1==box2) flagt++; if(strcmp(c[j],"up")==0&&box1>box2) flagt++; if(strcmp(c[j],"down")==0&&box1<box2) flagt++; // printf("%d %d %c %d len=%d\n",box1,box2,x,flagt,len); } //假币重 if(flagt!=3) { flagt=0; for(int j=0; j<3; j++) { memset(box,0,sizeof(box)); int len=strlen(a[j]); for(int k=0; k<len; k++) { if(a[j][k]!=x) box[k]++; if(a[j][k]==x) { box[k]+=10; pos=k; lenn=len; // t=c[j]; strcpy(t,c[j]); } } int box1=0,box2=0; for(int k=0; k<len/2; k++) box1+=box[k]; for(int k=len/2; k<len; k++) box2+=box[k]; if(strcmp(c[j],"even")==0&&box1==box2) flagt++; if(strcmp(c[j],"up")==0&&box1>box2) flagt++; if(strcmp(c[j],"down")==0&&box1<box2) flagt++; } } if(flagt==3) { if(pos<lenn/2) { if(strcmp(t,"up")==0) printf("%c is the counterfeit coin and it is heavy.\n",x); else printf("%c is the counterfeit coin and it is light.\n",x); } else { if(strcmp(t,"up")==0) printf("%c is the counterfeit coin and it is light.\n",x); else printf("%c is the counterfeit coin and it is heavy.\n",x); } break; } } } } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
D - Radar Installation
题目大意
雷达部署在x轴，给出半径，陆地在任意位置，现在已知所有陆地位置，要求使用最少雷达覆盖所有陆地。
思路
以每个陆地为圆心画圆，交x轴出现线段，线段长度即为这个陆地所需要的雷达区间，对每个陆地转化为一个线段，将线段按右端点排序，之后从左往右遍历线段，每次呢取端点的最右端作为雷达，下一个线段出现左端点在雷达左右两边的情况，在左边呢就不用管，在右边呢就更新右端点为新的雷达。
这个题，输入格式好奇怪，我觉得是个错题。思路对了，照着别的代码硬改出来。为什么n=0能过？不应该n0&&d0吗？#include#include #include #include #include using namespace std; struct node { double l,r; } a[1005]; int cmp(node a,node b) { return a.r - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
E - Truck History
题目大意
给n个卡车，每个卡车的编号由一个七个小写字母的字符串组成，每个卡车的编号唯一，已知一开始只有一辆卡车的编号，一个卡车可以向另一个卡车转换，代价是对应七个位置的不同字母的个数，现在要求出出现所有卡车编号出现的最小代价，最后结果取倒数。
思路
对于每一个卡车都可以当作是一个结点，做一个完全图，卡车两两转换的代价就是边权，求所有卡车出现的最小代价就是最小生成树，因为是点稠密所以选prim。
#include#include #include #include #include using namespace std; int a[2005][2005]; char truck[2005][10]; int n; int v[2005]; int d[2005]; void prim() { memset(d,0x3f,sizeof(d)); memset(v,0,sizeof(v)); d[1]=0; for(int i=1;i - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
F - Wormholes
题意
给n个顶点，m个权值为正的边，w个权值为负的边，现在问图中有没有一个环为负
思路
用简单的bellman-ford做，对边进行n-1轮松弛，在没有负边的情况下，可以得到一个点到所有点的最短路径，如果第n轮还能发现更短的路径，说明存在一个环为负。
#include#include #include #include #include using namespace std; struct node { int u,v,w; }e[5500]; int dist[1005]; int tot; void add(int u,int v,int w) { e[++tot].u=u; e[tot].v=v; e[tot].w=w; } int main() { int f; cin>>f; while(f--) { int n,m,w; cin>>n>>m>>w; memset(dist,0x3f,sizeof(dist)); dist[1]=0; tot=0; for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; add(x,y,z); add(y,x,z); } for(int i=1;i<=w;i++) { int x,y,z; cin>>x>>y>>z; add(x,y,-z); } for(int k=1;k<=n-1;k++) for(int i=1;i<=tot;i++) if(dist[e[i].v]>dist[e[i].u]+e[i].w) dist[e[i].v]=dist[e[i].u]+e[i].w; int flag=0; for(int i=1;i<=tot;i++) if(dist[e[i].v]>dist[e[i].u]+e[i].w) { flag=1; break; } if(flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; } } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
G - Balance
题目大意
一个天平，左右可以放一些砝码，不同的位置会有不同的力矩，给定c个位置，天平中间是0，给g个砝码，砝码的重量各个不同。求一共有多少种方案使得天平平衡。
思路
dp题，设dp[i][j]表示，使用了前i个砝码，目前天平右边减去左边重量的差值为j的方案数，枚举所有砝码，枚举所有重量差值，再枚举所有位置，差值存在负数，范围为 -15 * 20 * 25 到15 * 20 * 25 ，最远力臂15* 最大砝码20* 25最多数量，范围改为 0-15000，默认7500为平衡点。之后转移方案就行。
#include#include #include #include #include using namespace std; int dp[21][15005]; //dp[i][j]: 放了前i个物品，砝码右边减去砝码左边重量的差值为j时候的方案数 int pos[25]; int fama[25]; int main() { int c,g; scanf("%d%d",&c,&g); for(int i=1;i<=c;i++) scanf("%d",&pos[i]); for(int i=1;i<=g;i++) scanf("%d",&fama[i]); dp[0][7500]=1; for(int i=1;i<=g;i++) for(int j=0;j<=15000;j++) { for(int k=1;k<=c;k++) if(j+fama[i]*pos[k]<=15000) dp[i][j+fama[i]*pos[k]]+=dp[i-1][j]; } printf("%d",dp[g][7500]); } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
H - Cow Bowling
题目大意
从顶点往下向左或向右，走到最下面，找到一条累加和最大的值。
思路
数字三角形经典题
#include#include #include #include #include using namespace std; int dp[355][355]; int m[355][355]; int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) scanf("%d",&m[i][j]); } for(int i=1;i<=n;i++) dp[n][i]=m[n][i]; for(int i=n-1;i>=1;i--) for(int j=1;j<=i;j++) { dp[i][j]=m[i][j]+max(dp[i+1][j],dp[i+1][j+1]); } printf("%d",dp[1][1]); } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
J - Beat the Spread!
简单题，注意非负可以为0
#include#include #include #include #include int main() { int T; scanf("%d",&T); while(T--) { int a,b; scanf("%d%d",&a,&b); if((a+b)%2) { printf("impossible\n"); continue; } int maxx=(a+b)/2; int minn=a-maxx; if(maxx<0||minn<0) { printf("impossible\n"); continue; } printf("%d %d\n",maxx,minn); } } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
数据建模 - 概念模型，逻辑模型，物理模型 的区别以及建模方式
平衡树：AVL树
[免费专栏] Android安全之剪贴板+键盘缓存+UI界面+自动截屏敏感信息挖掘
计算机毕业设计（附源码）python疫情状态下的图书馆座位预约系统
单片机实验（二）
每日一题python85：合并两个有序链表
一次JAVA频繁写大文件的记录
SonarQube介绍和安装
【Python案例】——利用Django搭建一个钓鱼网站【轻松入门】