Sample Output 2
2+1i -1i 1+1i
Hint
代码
#include<iostream> #include<cstdio> using namespace std; class Complex { public: int m, n; Complex operator+(Complex& c2) { Complex res; res.m = m + c2.m; res.n = n + c2.n; return res; } Complex operator-(Complex& c2) { Complex res; res.m = m - c2.m; res.n = n - c2.n; return res; } Complex operator*(Complex& c2) { Complex res; res.m = m * c2.m - n * c2.n; res.n = n * c2.m + m * c2.n; return res; } void cprint() { if (m == 0 && n == 0) printf("0\n"); else if (m == 0 && n != 0) printf("%di\n", n); else if (m != 0 && n == 0) printf("%d\n", m); else printf("%d%+di\n", m, n); } }; int main() { Complex c1, c2; cin >> c1.m >> c1.n >> c2.m >> c2.n; Complex c3 = c1 + c2; c3.cprint(); c3 = c1 - c2; c3.cprint(); c3 = c1 * c2; c3.cprint(); return 0; }
大二组
韭菜
Description
在今后的几天内Jerry将学习美元与人民币的汇率。编写程序帮助Jerry何时应买或卖人民币或美元，使他从100美元开始，最后能获得最高可能的价值。
Input
第一行是一个自然数N，1≤N≤100，表示Jerry学习汇率的天数。
接下来的N行中每行是一个自然数A，1≤A≤1000。第i+1行的A表示预先知道的第i+1天的平均汇率，在这一天中，Jerry既能用100美元买A人民币也能用A人民币购买100美元。
Output
第一行也是唯一的一行应输出要求的钱数(单位为美元，保留两位小数)。
注意：Jerry必须在最后一天结束之前将他的钱都换成美元。
Sample Input 1
5 400 300 500 300 250
Sample Output 1
266.67
Hint
样例解释
Day 1 … changing 100.0000美元= 400.0000人民币
Day 2 … changing 400.0000人民币= 133.3333美元
Day 3 … changing 133.3333美元= 666.6666人民币
Day 5 … changing 666.6666人民币= 266.6666美元
题解
状态机dp
钱有两种状态：美元，记为0状态。RMB，记为1状态。记i,0}fi,0表示最优策略下第i ii天的美元数量，fi,1表示最优策略下第i ii天的人民币数量。
设第i ii天汇率汇率为a i a_iai，在最优策略下：当第i − 1 i-1i−1天汇率>第i ii天，可以把人民币兑换成美元{i-1,1}/a_ifi,0=fi−1,1/ai。当第i − 1 i-1i−1天汇率<第i ii天，可以把美元兑换为人民ifi,1=fi−1,0∗ai。
把i ii的维度优化掉，得到最终递推关系:
在最后一天，一定会把所有的钱都换成美元，则值为f 0 f_0f0或f 1 / a n f_1/a_nf1/an
代码
#include<iostream> using namespace std; double f[2];//0为美元，1为rmb double a[1005]; double st=1; int n; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; a[i]=a[i]/100.0; } f[0]=100; f[1]=100*a[1]; for(int i=2;i<=n;i++){ if (a[i-1]<a[i]){ f[1]=f[0]*a[i]; } if (a[i-1]>a[i]){ f[0]=f[1]/a[i]; } // cout<<"day"<<i<<":"<<f[0]<<"美元"<<f[1]<<"人民币\n"; } double res=max(f[0],f[1]/a[n]); printf("%.2f",res); return 0; }
闭合区域面积统计
Description
编程计算由‘*’号围成的下列图形的面积。面积的计算方法是统计*号所围成
的闭合曲线中水平线和垂直线交点的数目。如图所示，在10*10的二维数组中，
有*围住了15个点，因此面积为15。
Input
一个10*10的二维数组，里面的数为0和1,1代表着*号 。
Output
一个整数，代表被围住的点个数。
Sample Input 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
Sample Output 1
15
题解
bfs，从左上角、右上角、左下角、右下角为起点找到外圈的0，再找出1的个数，则剩下的0的个数就是被1包围的0
代码
#include<iostream> #include<queue> #define x first #define y second using namespace std; typedef pair<int,int> PII; int map[10][10]; int dx[4]={-1,0,1,0}; int dy[4]={0,1,0,-1}; int cnt0=0,cnt1=0; int st[10][10]; void bfs0(){ queue<PII> q; if (map[0][0]==0) q.push({0,0}); if (map[0][9]==0) q.push({0,9}); if (map[9][0]==0) q.push({9,0}); if (map[9][9]==0) q.push({9,9}); while(!q.empty()){ PII p=q.front(); q.pop(); st[p.x][p.y]=1; cnt0++; // cout<<p.x<<" "<<p.y<<endl; for(int k=0;k<4;k++){ int newx=p.x+dx[k]; int newy=p.y+dy[k]; if (newx<0||newx>=10||newy<0||newy>=10) continue; if (st[newx][newy]) continue; if (map[newx][newy]==1) continue; q.push({newx,newy}); st[newx][newy]=1; } } } int main(){ for(int i=0;i<10;i++) for(int j=0;j<10;j++) cin>>map[i][j]; bfs0(); for(int i=0;i<10;i++) for(int j=0;j<10;j++){ if (map[i][j]==1) cnt1++; } // cout<<cnt0<<endl<<cnt1<<endl; int res=100-cnt0-cnt1; cout<<res; }
晒衣服
Description
熊大妈需要给宝宝们晒衣服。
衣服在自然条件下用 1 的时间可以晒干 A 点湿度。抠门的熊大妈买了 1 台烘衣机。使用烘衣机可以让你用单位 1 时间使 1件衣服除开自然晒干的 A 点湿度外，还可烘干 B 点湿度，但在单位 1 时间内只能对 1 件衣服使用。
N 件的衣服因为种种原因而不一样湿，现在告诉你每件衣服的湿度，要你求出弄干所有衣服的最少时间（湿度为 0 为干）。
Input
第一行N，A ，B ， 接下来N行 ，每行一个正整数 ，表示衣服的湿度（1<= 湿度,A,B<=500000,1<=N<=500000）。
Output
一个正整数，表示弄干衣服的最小时间
Sample Input 1
3 2 1 1 2 3
Sample Output 1
1
Hint
对于40%的测试用例，n <= 5000
对于70%的测试用例，n <= 10000
对于全部的测试用例，n <= 500000
【样例解析】
第 1 个时间内，用机器处理第 3 件衣服，此外，所有衣服自然晒干 2。花费 1 时间全部弄干。
题解
代码
#include<iostream> #include<queue> #include<vector> using namespace std; int main(){ int n,a,b; cin>>n>>a>>b; priority_queue<int> q; for(int i=1;i<=n;i++){ int shidu; cin>>shidu; q.push(shidu); } int t=0; do{ int p=q.top(); q.pop(); if (p-a*t<=0) break; t++; p-=b; q.push(p); }while(1); cout<<t<<endl; }
奶酪
Description
