作者:迷途小书童爱读书
目录:
编程比赛记录
//头文件
#include
using namespace std;
//接收输入整数
//实现输入两个整数,空格和回车效果是一样的
int a,b;
cin >> a >> b
cout << a <<b< span=""></b<>
//break后面需要加;
break;
//输出保留小数点2位 float
printf("¥%.2f\n",bb);
//输出保留小数点2位 double
printf("¥%.2lf\n",bb);
//获取一行 在获取了一个整数之后,会出现一个空字符串需要过滤掉
#include
string aa;
getline(cin,aa)
//while循环记得直接用输入的,不然无法退出
//cout 有换行符了
//printf 输出需要增加一个\n的换行符
//定义数组
int aa[9]
//可以把面向对象的思路引入进去,简化编程逻辑
//定义类,注意最后有一个;
class aa{
};
//字符大小写转换
tolower(a) //小写
toupper(a) //大写
//整数转string
to_string(42)
//char 赋值给string 需要一个结束符号表示结尾
//字符串转整数
string s = "12";
int a = atoi(s.c_str()); //参数需要是const char *
char s ='1';
int a = s -'0'; //速度较快 求单个整数的值
//字符串截取
auto year = strInput.substr(0, 4);
//vector的查找效率比数组底50%
//vector
#include
vectorinPut;
//输入
inPut.push_back(inData);
//Remove the last element
inPut.pop_back(inData);
//迭代
for (auto item : vecAA) {
cout << item <<endl;< span=""></endl;<>
}
for (auto item = vecAA.begin(); item != vecAA.end(); item++) {
cout << *item << endl;
}
//从小到大排序
#include
sort(vecAA.begin(), vecAA.end());
//删除一个,it是迭代器
vecAA.erase(it);
#include
//定义链表
listlistinput;
//插入数据
listinput.push_back(input);
//删除数据
listInput.erase(min);
//删除第一个数据
mininput.pop_front();
//遍历数据
for (auto item : mininput) {
cout << " " << item ;
}
//迭代器
list::iterator min = listInput.begin();
//迭代器遍历
for (auto item = listInput.begin(); item != listInput.end();item++) {
if ((*min) > (*item)) {
min = item;
}
}
//随机插入,只需要拿到迭代器就可以
auto item = listInput.begin();
listInput.insert(item, 88);
//排序
listInput.sort();
#include
//内存拷贝
memcpy(s1, s2,2001);
//计算char[]长度
int isize = strlen(s3);
//内存设置
int dp[102][50010] = { 0 };
memset(dp, 0, sizeof dp);
1、注意前后使用单纯的拼写
2、注意写完之后的“;”
3、注意头文件的拼写
4、注意重复使用的变量
5、标准输入输出的箭头需要注意方向 cin >> a >> b cout << a << b
6、整数除以整数还是一个整数,如果要得到double 需要先转换一个为double
7、检查变量是否前后一致
8、注意输入数的范围,大大数的时候需要用字符串
9、注意相等的=号和==号的检查防止笔误
10、字符串使用length()求长度 vector和list用size()求长度
11、注意检查函数是否都有返回值
12、迭代器在删除之前,需要把值取出来,删除之后再取就取不到了
13、当有多个测试数据样本的时候,需要记得还原初始值
//头文件
#include
//定义对象
mapmapCount;
//寻找key
if (mapCount.end() != mapCount.find(inPut))
//插入数据
mapCount[inPut] = 1;
//遍历
for (auto item : mapCount) {
if (1 == item.second) {
cout << item.first << endl;
break;
}
}
快捷键:
F9:编译
F5:调试
F10:运行
题目描述
你的任务是计算a+b。这是为了acm初学者专门设计的题目。你肯定发现还有其他题目跟这道题的标题类似,这些问题也都是专门为初学者提供的。
输入
输入包含一系列的a和b对,通过空格隔开。一对a和b占一行。
输出
对于输入的每对a和b,你需要依次输出a、b的和。
如对于输入中的第二对a和b,在输出中它们的和应该也在第二行。
样例输入
1 5
10 20
样例输出
6 30
解答:
#include
using namespace std;
int main() {
int a,b;
while (cin >> a >> b) {
cout << a+b << endl;
}
return 0;
}
题目描述
你的任务是计算a+b。
输入
第一行是一个整数N,表示后面会有N行a和b,通过空格隔开。
输出
对于输入的每对a和b,你需要在相应的行输出a、b的和。
如第二对a和b,对应的和也输出在第二行。
样例输入
2
1 5
10 20
样例输出
6 30
解答:
#include
using namespace std;
int main(){
int n =0;
cin >> n;
for(int i=0;i<n;i++){< span=""></n;i++){<>
int a,b;
cin >>a>>b;
cout << a+b <<endl;< span=""></endl;<>
}
return 0;
}
题目描述
小明毕业一年了,并且找到了一份好工作。这一年里他赚了很多钱,现在他想知道他这一年里的平均月薪是多少,请你写一个程序帮他计算。
输入
输入包括12行。第i行为第i个月的实际月薪。(i=1,2,3...)
输出
输出小明的平均月薪,保留两位小数,并且最前面输出一个¥符号。
样例输入
100.00
489.12
12454.12
1234.10
823.05
109.20
5.27
1542.25
839.18
83.99
1295.01
1.75
样例输出
¥1581.42
答案:
#include
using namespace std;
int main(){
double total=0;
for(int i=0;i<12;i++){< span="">
double a =0;
cin >> a;
total = total +a;
}
double bb = total /12;
printf("¥%.2f\n",bb);
return 0;
}
题目描述
每门课的成绩分为A、B、C、D、F五个等级,为了计算平均绩点,规定A、B、C、D、F分别代表4分、3分、2分、1分、0分。
输入
有多组测试样例。每组输入数据占一行,由一个或多个大写字母组成,字母之间由空格分隔。
输出
每组输出结果占一行。如果输入的大写字母都在集合{A,B,C,D,F}中,则输出对应的平均绩点,结果保留两位小数。否则,输出“Unknown”。
样例输入
A B C D F
B F F C C A
D C E F
样例输出
2.00
1.83
Unknown
答案:
#include
#include
using namespace std;
int main() {
string inData;
while (getline(cin, inData)) {
double sum = 0;
bool isOK = true;
int totalNum = 0;
for (int i = 0; i < inData.length(); i = i + 1) {
if(' ' == inData[i]){
continue;
}
totalNum = totalNum + 1;
if ('A' == inData[i]) {
sum = sum + 4;
continue;
}
if ('B' == inData[i]) {
sum = sum + 3;
continue;
}
if ('C' == inData[i]) {
sum = sum + 2;
continue;
}
if ('D' == inData[i]) {
sum = sum + 1;
continue;
}
if ('F' == inData[i]) {
sum = sum + 0;
continue;
}
isOK = false;
cout << "Unknown" << endl;
break;
}
if (isOK) {
printf("%.2lf\n", sum / totalNum);
}
}
return 0;
}
题目描述
相信大家一定有过在网上下载软件而碰到多个不同版本的情况。一般来说,软件的版本号由三个部分组成,主版本号(Major Version Number),子版本号(Minor Version Number)和修订号(Revision_Number)。当软件进行了重大的修改时,主版本号加一;当软件在原有基础上增加部分功能时,主版本号不变,子版本号加一;当软件仅仅修正了部分bug时,主版本号和子版本号都不变,修正号加一。
在我们比较软件的两个版本的新旧时,都是先比较主版本号,当主版本号相同时再比较子版本号,前两者都相同的情况下再比较修正号。版本号越大的软件越新。
现在,小明在下载软件的时候碰到了两个版本,请你告诉他哪个版本更新一些。
输入
输入的第一行有一个整数T,代表有T组测试。接下来有T组测试。
每组测试分两行,第一行有三个整数代表第一个软件版本的主版本号,子版本号和修订号。第二行也有三个整数代表第二个软件版本的主版本号,子版本号和修订号。
数据中出现的整数都在[0,1000]范围之内。
输出
对于每组测试,如果第一个软件的版本新点,请输出First,如果第二个软件的版本新点,请输出Second,否则输出Same。
样例输入
3
1 1 0
1 1 1
1 1 1
1 1 0
1 1 1
1 1 1
样例输出
Second
First
Same
解答:
#include
using namespace std;
int main(){
int count=0;
int v1,v2,v3;
int first,second;
cin >> count;
for(int i=0;i<count;i++){< span=""></count;i++){<>
cin >> v1 >>v2>>v3;
first = v1*1001*1001+v2*1001+v3;
cin >> v1 >>v2>>v3;
second = v1*1001*1001+v2*1001+v3;
if(first > second){
cout << "First" <<endl;< span=""></endl;<>
continue;
}
if(first == second){
cout << "Same" <<endl;< span=""></endl;<>
continue;
}
if(first < second){
cout << "Second" <<endl;< span=""></endl;<>
continue;
}
}
return 0;
}
题目描述
现请你构建一个N*N的矩阵,第i行j列的元素为i与j的乘积。(i,j均从1开始)
输入
输入的第一行为一个正整数C,表示测试样例的个数。
然后是C行测试样例,每行为一个整数N(1<=n<=9),表示矩阵的行列数。< span="">
输出
对于每一组输入,输出构建的矩阵。
样例输入
2
1
4
样例输出
1
1 2 3 4
2 4 6 8
3 6 9 12
4 8 12 16
答案:
#include
using namespace std;
int main() {
int count = 0;
cin >> count;
for (int i = 0; i < count; i++) {
int n = 0;
cin >> n;
for (int j = 0; j < n; j++) {
cout << (j + 1) * (1);
for (int k = 1; k < n; k++) {
cout << ' ' << (j + 1) * (k+1);
}
cout << endl;
}
}
return 0;
}
答案:
#include
#include
using namespace std;
class eleNum {
public:
string str1;
string str2;
string str3;
};
int main() {
eleNum total[10];
total[0].str1 = " _ ";
total[0].str2 = "| |";
total[0].str3 = "|_|";
total[1].str1 = " ";
total[1].str2 = " |";
total[1].str3 = " |";
total[2].str1 = " _ ";
total[2].str2 = " _|";
total[2].str3 = "|_ ";
total[3].str1 = " _ ";
total[3].str2 = " _|";
total[3].str3 = " _|";
total[4].str1 = " ";
total[4].str2 = "|_|";
total[4].str3 = " |";
total[5].str1 = " _ ";
total[5].str2 = "|_ ";
total[5].str3 = " _|";
total[6].str1 = " _ ";
total[6].str2 = "|_ ";
total[6].str3 = "|_|";
total[7].str1 = " _ ";
total[7].str2 = " |";
total[7].str3 = " |";
total[8].str1 = " _ ";
total[8].str2 = "|_|";
total[8].str3 = "|_|";
total[9].str1 = " _ ";
total[9].str2 = "|_|";
total[9].str3 = " _|";
int a1, a2, a3, a4;
while (cin >> a1 >> a2 >> a3 >> a4) {
string str1 = total[a1].str1 + total[a2].str1 + total[a3].str1 + total[a4].str1;
string str2 = total[a1].str2 + total[a2].str2 + total[a3].str2 + total[a4].str2;
string str3 = total[a1].str3 + total[a2].str3 + total[a3].str3 + total[a4].str3;
cout << str1 << endl;
cout << str2 << endl;
cout << str3 << endl;
}
return 0;
}
答案
#include
#include
using namespace std;
int main() {
int t = 0;
cin >> t;
string temp;
for (int i = 0; i < t; i++) {
char ca;
int ia;
cin >> ia;
ca = ia;
temp = temp + ca;
}
cout << temp << endl;
return 0;
}
答案
#include
#include
using namespace std;
int main() {
int t = 0;
cin >> t;
string temp;
getline(cin, temp);
for (int i = 0; i < t;i++) {
string strin;
string strout;
getline(cin, strin);
int getindex = 0;
for (int j = 0; j < strin.length(); j++) {
if (' ' == strin[j]) {
strout = strout + (char)toupper(strin[getindex]);
getindex = j + 1;
}
}
strout = strout + (char)toupper(strin[getindex]);
string strout2;
for (int i = 0; i < strout.length(); i++)
{
if (' ' == strout[i]) {
continue;
}
strout2 = strout2 + strout[i];
}
cout << strout2 << endl;
}
return 0;
}
答案
#include
#include
#include
using namespace std;
int main() {
int N;
while (cin >> N) {
if (0 == N) {
return 0;
}
vector inPut;
int inData;
for (int i = 0; i < N; i++) {
cin >> inData;
inPut.push_back(inData);
}
sort(inPut.begin(), inPut.end());
int m = inPut.size() / 2 + 1;
int totalCount = 0;
for (int i = 0; i < m; i++) {
totalCount = totalCount + inPut[i] / 2 + 1;
}
cout << totalCount << endl;
}
return 0;
}
答案:
#include
#include
using namespace std;
class MyRow {
public:
vector m_row;
};
bool IsOK(vector& tData, int n) {
bool isOK = true;
for (int i = 0; i < n; i++) {
int sum = 0;
for (auto item : tData[i].m_row) {
sum = sum + item;
}
if (1 == sum % 2) {
isOK = false;
return isOK;
}
sum = 0;
for (int j = 0; j < n; j++) {
sum = sum + tData[j].m_row[i];
}
if (1 == sum % 2) {
isOK = false;
return isOK;
}
}
return isOK;
}
int main() {
int n = 0;
while (cin >> n) {
if (0 == n) {
break;
}
vector tData;
for (int i = 0; i < n; i++) {
MyRow row;
for (int j = 0; j < n; j++) {
int inData = 0;
cin >> inData;
row.m_row.push_back(inData);
}
tData.push_back(row);
}
auto isOK = IsOK(tData, n);
if (true == isOK) {
cout << "OK" << endl;
continue;
}
bool isOK2 = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (0 == tData[i].m_row[j]) {
tData[i].m_row[j] = 1;
}
else {
tData[i].m_row[j] = 0;
}
isOK2 = IsOK(tData, n);
if (true == isOK2) {
cout << "Change bit (" << i + 1 << "," << j + 1 << ")" << endl;
break;
}
if (0 == tData[i].m_row[j]) {
tData[i].m_row[j] = 1;
}
else {
tData[i].m_row[j] = 0;
}
}
if (true == isOK2) {
break;
}
}
if (false == isOK2) {
cout << "Corrupt" << endl;
}
}
return 0;
}
答案,使用printf的时候记得加上一个换行符
#include
using namespace std;
int main(){
int t=0;
cin >>t;
for(int i=0;i<t;i++){< span=""></t;i++){<>
double y,q,e,f,g;
cin >> y >> q>>e>>f>>g;
double out1 = y*(1+e/100*q/365)*(1+g/100);
double out2 = y*(1+f/100*(q+365)/365);
printf("%.1f\n",out1);
printf("%.1f\n",out2);
}
return 0;
}
答案:
#include
using namespace std;
int getTime(int from,int to){
if(from > to){
return (from -to)*4 + 5;
}
if(from <to){< span=""></to){<>
return (to-from)*6 + 5;
}
return 5;
}
int main(){
int n=0;
while(cin >> n){
if(0 == n){
break;
}
int fromfloor =0;
int sum =0;
for(int i=0;i<n;i++){< span=""></n;i++){<>
int tofloor=0;
cin >> tofloor;
sum = sum + getTime(fromfloor,tofloor);
fromfloor = tofloor;
}
cout << sum<<endl;< span=""></endl;<>
}
return 0;
}
答案:
每行一共20*3+2= 62个字节
2010 从62-4 = 58 /2 =29字节开始 或者说前面有29个空格
接下来是一个一行
然后输出月份 3个一组
月份格式也较为固定
第一行是月份单词
第二行是星期
第三行是数字
判断星期几:
基姆拉尔森计算公式
W= (d+2*m+3*(m+1)/5+y+y/4-y/100+y/400) mod 7在公式中d表示日期中的日数,m表示月份数,y表示年数。
把一月和二月看成是上一年的十三月和十四月
case 0: printf("星期一\n"); break;
case 1: printf("星期二\n"); break;
case 2: printf("星期三\n"); break;
case 3: printf("星期四\n"); break;
case 4: printf("星期五\n"); break;
case 5: printf("星期六\n"); break;
case 6: printf("星期日\n"); break;
日期的位置 = 20/日期长度/2的位置开始
#include
#include
#include
using namespace std;
int getWeek(int year, int month, int day) {
if (1 == month || 2 == month) {
month = month + 12;
year = year - 1;
}
int week = 0;
week = day + month * 2 + (month + 1) * 3 / 5 + year + year / 4 - year / 100 + year / 400;
return (week + 1) % 7;
}
class Month {
public:
string name;
string weekname;
int dayNum;
vector vecDay;
int maxByte = 20;
Month(int year, int month) {
char cPace[21] = { 0 };
for (int i = 0; i < 20; i++) {
cPace[i] = ' ';
}
string strSpace = cPace;
vecDay.push_back(strSpace);
vecDay.push_back(strSpace);
vecDay.push_back(strSpace);
vecDay.push_back(strSpace);
vecDay.push_back(strSpace);
vecDay.push_back(strSpace);
weekname = "Su Mo Tu We Th Fr Sa";
if (1 == month) {
name = "January";
dayNum = 31;
}
else if (2 == month) {
name = "February";
dayNum = 28;
if ((0 == year % 4) && (0 != year % 100)) {
dayNum = 29;
}
else if ((0 == year % 100) && (0 == year % 400)) {
dayNum = 29;
}
}
else if (3 == month) {
name = "March";
dayNum = 31;
}
else if (4 == month) {
name = "April";
dayNum = 30;
}
else if (5 == month) {
name = "May";
dayNum = 31;
}
else if (6 == month) {
name = "June";
dayNum = 30;
}
else if (7 == month) {
name = "July";
dayNum = 31;
}
else if (8 == month) {
name = "August";
dayNum = 31;
}
else if (9 == month) {
name = "September";
dayNum = 30;
}
else if (10 == month) {
name = "October";
dayNum = 31;
}
else if (11 == month) {
name = "November";
dayNum = 30;
}
else if (12 == month) {
name = "December";
dayNum = 31;
}
string strName = cPace;
int index = (20 - name.length()) / 2;
for (int i = 0; i < name.length(); i++) {
strName[index + i] = name[i];
}
name = strName;
int weekIndex = getWeek(year, month, 1);
for (int i = 1; i < dayNum + 1; i++) {
int lineIndex = weekIndex / 7;
int lineWeek = weekIndex % 7;
string stri = to_string(i);
if (1 == stri.length()) {
vecDay[lineIndex][lineWeek * 3 + 1] = stri[0];
}
else {
vecDay[lineIndex][lineWeek * 3] = stri[0];
vecDay[lineIndex][lineWeek * 3 + 1] = stri[1];
}
weekIndex = weekIndex + 1;
}
}
};
int main() {
int y = 0;
while (cin >> y) {
vector totalMonth;
for (int i = 1; i < 13; i++) {
Month m(y, i);
totalMonth.push_back(m);
}
char temp[65] = { 0 };
for (int i = 0; i < 64; i++) {
temp[i] = ' ';
}
string strYear = to_string(y);
int index = (64 - strYear.length()) / 2;
for (int i = 0; i < strYear.length(); i++) {
temp[index + i] = strYear[i];
}
strYear = temp;
cout << strYear << endl;
cout << "" << endl;
for (int i = 0; i < 12; i = i + 3) {
auto month1 = totalMonth[i];
auto month2 = totalMonth[i + 1];
auto month3 = totalMonth[i + 2];
string str1 = month1.name + " " + month2.name + " " + month3.name;
cout << str1 << endl;
string str2 = month1.weekname + " " + month2.weekname + " " + month3.weekname;
cout << str2 << endl;
for (int j = 0; j < 6; j++) {
string str3 = month1.vecDay[j] + " " + month2.vecDay[j] + " " + month3.vecDay[j];
cout << str3 << endl;
}
}
}
return 0;
}
#include
using namespace std;
int winNumber(char cmd1, char cmd2) {
if (cmd1 == cmd2) {
return 0;
}
if ('R' == cmd1) {
if ('S' == cmd2) {
return 1;
}
else {
return -1;
}
}
if ('S' == cmd1) {
if ('P' == cmd2) {
return 1;
}
else {
return -1;
}
}
if ('P' == cmd1) {
if ('R' == cmd2) {
return 1;
}
else {
return -1;
}
}
return 0;
}
class Player {
public:
int m_winCount = 0;
};
int main() {
int t = 0;
cin >> t;
for (int i = 0; i < t; i++) {
int lineCount = 0;
Player player1, player2;
cin >> lineCount;
for (int j = 0; j < lineCount; j++) {
char P1, P2;
cin >> P1 >> P2;
auto myCount = winNumber(P1, P2);
player1.m_winCount = player1.m_winCount + myCount;
player2.m_winCount = player2.m_winCount - myCount;
}
if (player1.m_winCount == player2.m_winCount) {
cout << "TIE" << endl;
continue;
}
if (player1.m_winCount > player2.m_winCount) {
cout << "Player 1" << endl;
continue;
}
if (player1.m_winCount < player2.m_winCount) {
cout << "Player 2" << endl;
continue;
}
}
return 0;
}
#include
using namespace std;
int main() {
double VUL, D;
double minZero = 0.00000001;
while (cin >> VUL >> D) {
int i = 1;
int t = 0;
while (true) {
auto left1 = VUL - D * i;
if (left1 > minZero) {
t = t + i + 1;
i = i + 1;
VUL = left1;
continue;
}
int j = 1;
while (true) {
auto letf2 = VUL - D * j;
if (letf2 > minZero) {
j = j + 1;
continue;
}
break;
}
t = t + j;
break;
}
cout << t << endl;
}
return 0;
}
#include
#include
using namespace std;
bool isPalindrom(int input,int cmd){
auto myinput = input;
vector vecTemp;
while(true){
if(myinput <cmd){< span=""></cmd){<>
vecTemp.push_back(myinput);
break;
}
auto mode = myinput % cmd ;
vecTemp.push_back(mode);
myinput = (myinput - mode)/cmd;
}
int length = vecTemp.size();
myinput = 0;
int param =1;
for(int i=0;i<length;i++){< span=""></length;i++){<>
myinput =myinput + vecTemp[length-i-1]*param;
param = param * cmd;
}
if(myinput == input){
return true;
}
return false;
}
int main(){
int T =0;
while(cin >> T){
if(0 == T){
break;
}
vector jz;
for(int i=2;i<17;i++){< span="">
auto isTrue = isPalindrom(T,i);
if(true == isTrue){
jz.push_back(i);
}
}
if(0 == jz.size()){
cout << "Number " <<T<<" is not a palindrom"<<endl;< span=""></endl;<>
continue;
}
cout << "Number " <<T<<" is palindrom in basis";
for(auto item:jz){
cout<<" "<<item;< span=""></item;<>
}
cout << endl;
}
return 0;
}
#include
#include
using namespace std;
int main(){
int input =0;
while(cin >> input){
vector vec;
while(true){
if(input <8){< span="">
vec.push_back(input);
break;
}
auto mode = input%8;
vec.push_back(mode);
input = (input -mode)/8;
}
int length = vec.size();
for(int i=0;i<length;i++){< span=""></length;i++){<>
cout << vec[length-1-i];
}
cout <<endl;< span=""></endl;<>
}
return 0;
}
#include
#include
#include
using namespace std;
int main() {
int N = 0;
cin >> N;
for (int i = 0; i < N; i++) {
vector vecStr;
string strInput;
while (cin >> strInput) {
if ("0" == strInput) {
break;
}
vecStr.push_back(strInput);
}
int ilength = vecStr[0].length();
int isize = vecStr.size();
vector vecInt;
int ijin = 0;
for (int j = 0; j < ilength; j++) {
int iAdd = 0 + ijin;
for (int k = 0; k < isize; k++) {
string cItem = vecStr[k].substr(ilength - 1 - j, 1);
int iItem = atoi(cItem.c_str());
iAdd = iAdd + iItem;
}
ijin = iAdd / 10;
iAdd = iAdd % 10;
vecInt.push_back(iAdd);
}
if (0 != ijin) {
vecInt.push_back(ijin);
}
if (i != 0) {
cout << "" << endl;
}
auto totalSize = vecInt.size();
for (int j = 0; j < totalSize; j++) {
cout << vecInt[totalSize - 1 - j];
}
cout << endl;
}
return 0;
}
这里提供两种解决方案,一个是使用vector的方案,一种是使用数组的方案。在高性能计算的时候,尽量不要使用递归,尽量使用循环来替代,尽量使用数组来操作。
#include
#include
#include
using namespace std;
vectorvecAdd(vector& vec1, vector& vec2) {
int length1 = vec1.size();
int length2 = vec2.size();
if (length1 > length2) {
auto zeroCount = length1 - length2;
while (zeroCount > 0) {
vec2.push_back(0);
zeroCount = zeroCount - 1;
}
}
if (length2 > length1) {
auto zeroCount = length2 - length1;
while (zeroCount > 0) {
vec1.push_back(0);
zeroCount = zeroCount - 1;
}
}
int length = vec1.size();
vector vec3;
int ijin = 0;
for (int i = 0; i < length; i++) {
int ia1 = vec1[i];
int ia2 = vec2[i];
int sum = ia1 + ia2 + ijin;
ijin = sum / 10;
int imode = sum % 10;
vec3.push_back(imode);
}
if (0 != ijin) {
while (true) {
int imode = ijin % 10;
vec3.push_back(imode);
ijin = (ijin - imode) / 10;
if(0 == ijin){
break;
}
}
}
return vec3;
}
int main() {
int N = 0;
while (cin >> N) {
if(1 == N || 2 == N){
cout << 1 <<endl;< span=""></endl;<>
continue;
}
vector s1;
vector s2;
s1.push_back(1);
s2.push_back(1);
for (int i = 3; i < N; i++) {
auto s3 = vecAdd(s1,s2);
s1 = s2;
s2 = s3;
}
int isize = s2.size();
for(int i=0;i<isize;i++){< span=""></isize;i++){<>
cout << s2[isize -1 -i] ;
}
cout << endl;
}
return 0;
}
#include
#include
#include
#include
using namespace std;
void vecAdd(char* s1, char* s2, char* s3) {
int length1 = strlen(s1);
int length2 = strlen(s2);
if (length1 > length2) {
auto zeroCount = length1 - length2;
s2[length1] = '\0';
while (zeroCount > 0) {
s2[length1 - zeroCount] = '0';
zeroCount = zeroCount - 1;
}
}
if (length2 > length1) {
auto zeroCount = length2 - length1;
s1[length2] = '\0';
while (zeroCount > 0) {
s1[length2 - zeroCount] = '0';
zeroCount = zeroCount - 1;
}
}
int length = strlen(s1);
int ijin = 0;
for (int i = 0; i < length; i++) {
int ia1 = s1[i] - '0';
int ia2 = s2[i] - '0';
int sum = ia1 + ia2 + ijin;
ijin = sum / 10;
int imode = sum % 10;
s3[i] = imode + '0';
}
if (0 == ijin) {
s3[length] = '\0';
}
if (0 != ijin) {
int i = 0;
while (true) {
int imode = ijin % 10;
s3[length + i] = imode + '0';
i = i + 1;
ijin = (ijin - imode) / 10;
if (0 == ijin) {
s3[length + i] = '\0';
break;
}
}
}
return ;
}
int main() {
int N = 0;
char s1[2001], s2[2001], s3[2001];
while (cin >> N) {
if (1 == N || 2 == N) {
cout << 1 << endl;
continue;
}
s1[0] = '1';
s1[1] = '\0';
s2[0] = '1';
s2[1] = '\0';
for (int i = 3; i <= N; i++) {
vecAdd(s1, s2, s3);
memcpy(s1, s2,2001);
memcpy(s2, s3, 2001);
}
int isize = strlen(s3);
for (int i = 0; i < isize; i++) {
cout << s3[isize - 1 - i];
}
cout << endl;
}
return 0;
}
#include
#include
using namespace std;
int main() {
int n = 0;
while (cin >> n) {
if (0 == n) {
break;
}
map<int, </int,int> mapCount;
for (int i = 0; i < n; i++) {
int inPut = 0;
cin >> inPut;
if (mapCount.end() != mapCount.find(inPut)) {
auto value = mapCount[inPut];
mapCount[inPut] = value + 1;
continue;
}
mapCount[inPut] = 1;
}
for (auto item : mapCount) {
if (1 == item.second) {
cout << item.first << endl;
break;
}
}
}
return 0;
}
#include
#include
using namespace std;
vectorget2jinzhi(int input) {
vector vec;
while (true) {
if (input < 2) {
vec.push_back(input);
return vec;
}
auto mode = input % 2;
vec.push_back(mode);
input = (input - mode) / 2;
}
return vec;
}
int main() {
int a = 0;
while (cin >> a) {
if (0 == a) {
break;
}
auto vec = get2jinzhi(a);
int output = 1;
for (auto item : vec) {
if (1 == item) {
break;
}
output = output * 2;
}
cout << output << endl;
}
return 0;
}
这一题是一道二维费用的动态规划问题,我们可以这样转化这个问题:
将n个物品放到一个容量为n/2的背包,每个物品占一个空间,这个背包所能承受的重量是(所有物品总和)/2 ,然后求这个背包最多能放多重的物品,这样就成功转化成一个背包问题了,状态转移方程为 f[j][k]= f[j][k] || f[j-a[i]][k-1];
这个函数可以这么理解,定义f[j][k] :为1表示存在重量为J的值,由K个物品组成。我们的重量一定不会超过总和的一半,而且由于重量都是整数,所以我们通过递归递减的方式,来找到最终可以到达的重量。f[j-a[i]][k-1] 表示如果减掉一个物体,是否存在k-1个物体可以满足当前的重量。f[0][0]=1 表示存在0个物体的质量为0。
#include
#include
using namespace std;
int f[50010][102],a[1000];
int main()
{
int n;
while(cin >> n)
{
int sum = 0;
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)< span="">
{
cin >> a[i];
sum=sum+a[i];
}
f[0][0]=1;
for(int i=1;i<=n;i++)< span="">
{
for(int j=sum/2;j>=a[i];j--)
{
for(int k=(n+1)/2;k>=1;k--)
{
f[j][k] = f[j][k] || f[j-a[i]][k-1];
}
}
}
for(int i=sum/2;i>=0;i--)
if(f[i][(n+1)/2])
{
cout << i << " " << sum-i << endl;
break;
}
}
return 0;
}
#include
#include
using namespace std;
int main() {
char first;
while (cin >> first) {
string next;
cin >> next;
int count = 0;
for (int i = 0; i < next.length(); i++) {
if (tolower(first) == tolower(next[i])) {
count = count + 1;
}
}
double d = (double)count / next.length();
printf("%.5lf\n", d);
}
return 0;
}
#include
#include
using namespace std;
int main() {
int t = 0;
cin >> t;
for (int i = 0; i < t; i++) {
string input;
int number;
cin >> input >> number;
int index;
for (int j = 0; j < input.length(); j++) {
if (input[j] == '.') {
index = j;
}
}
if (index + number >= input.length()) {
cout << 0 << endl;
continue;
}
cout << input[index + number] << endl;
}
return 0;
}
#include
#include
using namespace std;
int getMinAndRemove(list& listInput) {
list::iterator min = listInput.begin();
for (auto item = listInput.begin(); item != listInput.end();item++) {
if ((*min) > (*item)) {
min = item;
}
}
listInput.erase(min);
return *min;
}
int main() {
int n = 0;
cin >> n;
list listinput;
for (int i = 0; i < n; i++) {
int input = 0;
cin >> input;
listinput.push_back(input);
}
list mininput;
while (listinput.size()>0)
{
auto min = getMinAndRemove(listinput);
mininput.push_back(min);
}
auto first = mininput.begin();
mininput.pop_front();
cout << *first;
for (auto item : mininput) {
cout << " " << item ;
}
cout << endl;
return 0;
}
#include
#include
using namespace std;
bool compute(list& listInput, int& value) {
if (listInput.size() < 2) {
return false;
}
auto value1 = *(listInput.begin());
listInput.pop_front();
auto value2 = *(listInput.begin());
listInput.pop_front();
value = value1 + value2;
bool insertOk = false;
for (auto item = listInput.begin(); item != listInput.end();item++) {
if (value < (*item)) {
listInput.insert(item, value);
insertOk = true;
break;
}
}
if (false == insertOk) {
listInput.push_back(value);
}
return true;
}
int main() {
int n = 0;
while (cin >> n) {
if (0 == n) {
break;
}
list listInput;
for (int i = 0; i < n; i++) {
int input = 0;
cin >> input;
listInput.push_back(input);
}
listInput.sort();
int sum = 0;
int value;
while (true == compute(listInput, value)) {
sum = sum + value;
}
cout << sum << endl;
}
return 0;
}
解题思路:
由于队列的顺序是不变的,而我们不知道中间点Ti到底在哪里。但是我们一定知道Ti的左边一定是逐渐升高的,Ti的右边一定是逐渐降低的。然后我们可以把这个问题变成,求规定i的左边逐渐升高的最大值 和求规定i的右边的逐渐降低的最大值。最后在遍历每个i将两边的最大值求出来,那么这个i就是我们要算出来的值。
接下来,求出逐步变大的最大数量,也需要构造一个状态函数,假设为dp[i]中保存的选择i点后,最大的数量。那么我们遍历之前所有的dp点,如果当前点当前点比其大的话,需要更新一下dp[i]。
#include
#include
using namespace std;
int a[101] ={0};
int dp_left[101] = {0};
int dp_right[101] = {0};
int main(int argc, char** argv) {
int n =0;
while(cin >> n){
if(0 == n){
break;
}
memset(a,0,sizeof(a));
memset(dp_left,0,sizeof(dp_left));
memset(dp_right,0,sizeof(dp_right));
for(int i =0;i<n;i++){< span=""></n;i++){<>
int input=0;
cin >> input;
a[i] = input;
}
for(int i =0;i<n;i++){< span=""></n;i++){<>
for(int j = 0;j<i;j++){< span=""></i;j++){<>
if(a[i]>a[j]){
if(dp_left[i] < dp_left[j] +1){
dp_left[i] = dp_left[j] +1;
}
}
}
}
for(int i =n-1;i>-1;i--){
for(int j = n-1;j> i;j--){
if(a[i]>a[j]){
if(dp_right[i] < dp_right[j] +1){
dp_right[i] = dp_right[j] +1;
}
}
}
}
int max =0;
for(int i =0;i<n;i++){< span=""></n;i++){<>
if((dp_left[i] + dp_right[i]) > max)
{
max = dp_left[i] + dp_right[i];
}
}
cout << n- max-1 << endl;
}
return 0;
}