入门（一）"/>
ACM入门（一）
ACM入门(一)
P1421 小玉买文具
把元化为角即可
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
int a, b;
int main()
{scanf("%d %d", &a, &b);int res = a * 10 + b;int one = 19;printf("%d", res / one);return 0;
}
P1909 买铅笔
这里要使用到排序，并且由于具有多关键字，所以要用pair,考虑使用vector来存放
其中自己重写sort的cmp函数时，>代表降序，<代表升序
原来只能买一种，都不需要排序了。。。
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
int a, b;
int n;
int cmp(const pair<int,int>&x, const pair<int,int>&y)
{return double(x.second)/x.first < double(y.second)/y.first;
}
int main()
{scanf("%d", &n);vector<pair<int, int>> res;for (int i = 0; i < 3; i++){int num, price;scanf("%d %d", &num, &price);res.push_back(make_pair(num, price));}//sort(res.begin(), res.end(), cmp);long long int min = 0x3f3f3f3f;vector<pair<int, int>>::iterator p = res.begin();for (; p != res.end(); p++){int m = n;int temp = n / (*p).first;int counts = temp * (*p).first;m -= counts;int price = 0;price = temp * (*p).second;if (m > 0)price += (*p).second;if (price < min)min = price;}printf("%lld", min);return 0;
}
P1089 津津的储蓄计划
直接模拟即可
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;int main()
{int total = 0;int save = 0;for (int i = 0; i < 12; i++){int surplus = 300;int cost;scanf("%d", &cost);surplus -= cost;total += surplus;if (total >= 100){int nums = total / 100;save += nums * 100;total -= nums * 100;}if (total < 0){printf("-%d", i + 1);return 0;}}printf("%d", total + int(save * 1.2));return 0;
}
P1085 不高兴的津津
直接模拟即可
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;int main()
{int res = 0;int max = 0;for (int i = 0; i < 7; i++){int a, b;scanf("%d %d", &a, &b);int temp = a + b-8;if (temp > max){max = temp;res = i + 1;}}printf("%d", res);return 0;
}
P1980 级数求和
直接模拟即可
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;int main()
{double k;scanf("%lf", &k);double res = 1;double n = 1;while (res <= k){n++;res += 1 / n;}printf("%d", int(n));return 0;
}
P1980 计数问题
关键点在于对0的判断
考虑比较笨的方法，记录下第一个不是0的位置，单独考虑
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;int counts(int n,int flag)
{int res = 0;int count = 1000000;int firstplace = 1;int count_0 = 0;for (int i = 0; i <=6; i++){int temp = n / count;if (temp == flag)res++;if (temp > 0){if (7 - i > firstplace)firstplace = 7 - i;}else{if (firstplace != 1)count_0++;}n -= temp * count;count = count / 10;}if (flag != 0)return res;elsereturn count_0;}
int main()
{int n, flag;scanf("%d %d", &n, &flag);int res = 0;for (int i = 1; i <= n; i++){res += counts(i, flag);}printf("%d", res);return 0;
}
其实直接从数来考虑就可以了。。
还是做复杂了
P1014 Cantor表
规律比较难归纳，考虑一个个模拟
通过奇偶不同进行归纳
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;int main()
{int n;scanf("%d", &n);int a = 1;int b = 1;for (int i = 1; i != n; i++){if (b == 1&&(a%2==0)){a++;}else if (a == 1&&(b%2==1)){b++;}else{//考虑是增是减if ((a + b) % 2 == 1){a++;b--;}else{a--;b++;}}}printf("%d/%d", a, b);return 0;
}
P1307 数字反转
最主要是解决前导0和负号的问题
显然使用字符串来解决应该比用整数来解决合理
注意特殊情况0
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
int main()
{char str[100];scanf("%s", str);if (str[0] == '0'){printf("0");return 0;}bool flag = 0;if (str[0] == '-')flag = 1;//记录下负号reverse(str,str+strlen(str));//反转//输出注意前导0即可if (flag)printf("-");int i = 0;while (str[i] == '0')i++;while (str[i] != '-' && str[i] != 0){printf("%c", str[i]);i++;}return 0;
}
P1046 陶陶摘苹果
模拟即可
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
int main()
{int a[10];int n;for (int i = 0; i < 10; i++)scanf("%d", &a[i]);scanf("%d", &n);int res = 0;for (int i = 0; i < 10; i++){if (a[i] <= n + 30)res++;}printf("%d", res);return 0;
}
P1047 校门外的树
主要考虑边界重合的情况
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
int a[10001];
int main()
{int l, m;scanf("%d %d", &l, &m);memset(a, -1, sizeof(int) * (l+1));for (int i = 0; i < m; i++){int min, max;scanf("%d %d", &min, &max);memset(a + min, 0, sizeof(int) * (max - min+1));}int res = 0;for (int i = 0; i <= l; i++)if (a[i] == -1)res++;printf("%d", res);return 0;
}
P1427 小鱼的数字游戏
逆置即可
这里要注意中间差个1 （a，a+n） 从a开始要n+1
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll a[101];
int main()
{int i = 0;while (1){scanf("%lld", &a[i]);if (a[i] == 0)break;i++;}reverse(a, a + i);for (int j = 0; j < i; j++)printf("%lld ", a[j]);return 0;
}
P2141 珠心算测验
注意题意，只是看集合内的数是否能表示为其他两个数之和
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
bool a[20001];
ll b[101];
int main()
{int n;scanf("%d", &n);memset(a, 0, sizeof(a));for (int i = 0; i < n; i++){scanf("%lld", &b[i]);a[b[i]] = 1;}sort(b, b + n);int res = 0;for (int i = 0; i < n; i++){for (int j = i + 1; j < n; j++){if (a[b[i] + b[j]] == 1){res++;a[b[i] + b[j]] = 0;}}}printf("%d", res);return 0;
}
P5594 模拟赛
使用bool开的数组可真大！
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
bool a[1001][1001];
int main()
{int n, m, k;scanf("%d %d %d", &n, &m, &k);for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){int d;scanf("%d", &d);a[d-1][j] = 1;}}for (int i = 0; i < k; i++){int res = 0;for (int j = 0; j < m; j++)if (a[i][j] == 1)res++;printf("%d ", res);}return 0;
}
P5015 标题统计
单纯的输入问题
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
char str[10000];
int main()
{cin.getline(str, 10000);int res = 0;for (int i = 0; i < strlen(str); i++){if (str[i] != ' ' && str[i] != '\n')res++;}printf("%d", res);return 0;
}
P1055 ISBN号码
直接模拟即可
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
char str[20];
int main()
{scanf("%s", str);int a[10];for (int i = 0, j = 0; str[i] != 0; i++){if (str[i] != '-'){a[j] = str[i]-48;j++;}}int res = 0;for (int i = 0; i < 9; i++)res += a[i] * (i + 1);res %= 11;char ch;if (res == 10)ch = 'X';elsech = res + '0';if (str[12] == ch)printf("Right");else{for (int i = 0; i < 9; i++){printf("%d", (a[i]));if (i == 0 || i == 3 || i == 8)printf("-");}printf("%c", ch);}return 0;
}
P1308 统计单词数
transform(::toupper)
transform(a.begin(), a.end(), a.begin(), ::toupper);
其中a是string类
strstr
strstr是在一个字符串里面给定一个字符串，寻找有没有这个字符串，若有，返回首次出现的指针否则返回NULL（空指针）
用strstr来判断字符是否存在，注意前后界考虑即可
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;int main()
{char txt[1000001],word[11];cin.getline(word, 11);cin.getline(txt, 1000001);int counts=0, first_place=0;transform(txt, txt + strlen(txt), txt, ::toupper);transform(word, word + strlen(word), word, ::toupper);char* p = txt;char* q;int len = strlen(word);for (; q = strstr(p,word);){if (q != NULL&& (q == txt||(*(q - 1) == ' '))&& ((*(q + len) == 0) || (*(q + len) == ' '))){if (counts == 0){first_place = q - txt;}counts++;}p = q + len;//关键！}if (counts == 0)printf("-1");elseprintf("%d %d", counts, first_place);return 0;
}
P2010 回文日期
要注意填充0 比如1月是01
其实总体来说由于只有8位，那么可以由年份来直接确定是否合法即可
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
struct res {int year;int mon;int day;
};
bool judge_leap(int year)
{return (year % 400 == 0) || (year % 4 == 0 && year % 100 != 0) ? 1 : 0;
}
bool day_valid(res day)
{int month_day[] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };month_day[2] += judge_leap(day.year);if (day.mon < 1 || day.mon>12 || day.day<1 || day.day>month_day[day.mon])return 0;elsereturn 1;
}
bool year_size(res day1, res day2)
{if (day1.year < day2.year)return 1;else if (day1.year == day2.year){if (day1.mon < day2.mon)return 1;else if (day1.mon == day2.mon){if (day1.day <= day2.day)return 1;elsereturn 0;}elsereturn 0;}elsereturn 0;
}
int main()
{res sta;res end;char temp[9];char str[5];cin >> temp;memcpy(str, temp, sizeof(char) * 4);str[4] = 0;sta.year = atoi(str);memcpy(str, temp + 4, sizeof(char) * 2);str[2] = 0;sta.mon = atoi(str);memcpy(str, temp + 6, sizeof(char) * 2);str[2] = 0;sta.day = atoi(str);cin >> temp;memcpy(str, temp, sizeof(char) * 4);str[4] = 0;end.year = atoi(str);memcpy(str, temp + 4, sizeof(char) * 2);str[2] = 0;end.mon = atoi(str);memcpy(str, temp + 6, sizeof(char) * 2);str[2] = 0;end.day = atoi(str);int counts = 0;while (sta.year <= end.year){//按每年来计算该年的回文日期char mon[3];char day[3];mon[0] = sta.year % 10+'0';mon[1] = sta.year%100 / 10 + '0';mon[2] = 0;day[0] = sta.year %1000/ 100 + '0';day[1] = sta.year / 1000 + '0';day[2] = 0;res temp;temp.year = sta.year;temp.mon = atoi(mon);temp.day = atoi(day);if (day_valid(temp) && year_size(temp, end))counts++;sta.year++;}printf("%d", counts);return 0;
}
%别人直接算日期的做法确实太清晰了
P1012 拼数
sort默认是升序 less
这里直接根据需求来比较即可
自定义cmp函数！！ 巧妙
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
bool cmp(string s1, string s2)
{return s1 + s2 > s2 + s1;
}
int main()
{int n;cin >> n;string res[21];for (int i = 0; i < n; i++)cin >> res[i];sort(res, res+n,cmp);string str;for (int i = 0; i < n; i++)str += res[i];cout << str;return 0;
}
P5587 打字练习
注意 inf是指无穷大 一般是除数为0
要注意两个串的长度可能不一样
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
string out[10001];
string in[10001];
int main()
{int i = 0;while (1){getline(cin,out[i]);if (out[i] == "EOF")break;char res[100001];if (out[i].find('<') != -1){char temp[100001];strcpy(temp, (out[i]).c_str());//开始往后给int pos = 0;int k;for ( k = 0; temp[k] != 0; k++){if (temp[k] == '<')//退格{if (pos != 0)pos--;}else{res[pos] = temp[k];pos++;}}res[pos] = 0;out[i] = res;}i++;}int j = 0;int counts = 0;while (1){getline(cin, in[j]);if (in[j] == "EOF")break;//中间存在转换char res[100001];if (in[j].find('<')!=-1){char temp[100001];strcpy(temp, (in[j]).c_str());//开始往后给int pos = 0;for (int k = 0; temp[k] != 0; k++){if (temp[k] == '<')//退格{if (pos != 0)pos--;}else{res[pos] = temp[k];pos++;}}res[pos] = 0;}elsestrcpy(res, (in[j]).c_str());char aim[100001];strcpy(aim, out[j].c_str());int len1 = out[j].length();int len2 = strlen(res);len1 = len1 <= len2 ? len1 : len2;for (int k = 0; k < len1; k++){if (aim[k] == res[k])counts++;}j++;}int T;cin >> T;cout << floor(double(counts)*60 / T+0.5);return 0;
}
P1028 数的计算
反向推理
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int counts = 1;
int a[1001];
int main()
{int n;scanf("%d", &n);for (int i = 1; i <= n; i++){for (int j = 1; j <= i / 2; j++)a[i] += a[j];a[i]++;}cout << a[n];return 0;
}
P1464 Function
直接先递推把数据记录下来
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int a[21][21][21];
void solve()
{for (int i = 0; i <= 20; i++){for (int j = 0; j <= 20; j++){a[0][i][j] = 1;a[i][0][j] = 1;a[i][j][0] = 1;}}for (int i = 1; i <=20; i++){for (int j = 1; j <= 20; j++){for (int k = 1; k <= 20; k++){if (i < j && j < k)a[i][j][k] = a[i][j][k - 1] + a[i][j - 1][k - 1] - a[i][j - 1][k];elsea[i][j][k] = a[i-1][j][k] + a[i-1][j - 1][k]+a[i-1][j][k-1] - a[i-1][j - 1][k-1];}}}}
int main()
{solve();while (1){ll aa, b, c;scanf("%lld %lld %lld", &aa, &b, &c);if (aa == -1 && b == -1 && c == -1)break;int res;if (aa <= 0 || b <= 0 || c <= 0)res = 1;else if (aa > 20 || b > 20 || c > 20)res = a[20][20][20];elseres = a[aa][b][c];printf("w(%lld, %lld, %lld) = %d\n", aa, b, c, res);}return 0;
}
%题解之后发现
原来记录下来的方法就是在原来递归语句前加一句等于
eg: rpt[a][b][c]=w(20,20,20)
P5534 等差数列
直接算
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;int main()
{ll a1, a2, d,n;scanf("%lld %lld %lld", &a1, &a2, &n);d = a2 - a1;ll res = n * a1 +((n) * (n - 1) * d) / 2;printf("%lld", res);return 0;
}
P1192 台阶问题
标准dp但使用递推规律会更快
注意答案要取模
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int a[100001];
int n, k;
void solve()
{a[n] = 1;a[n - 1] = 1;for (int i = 2; i <= n; i++){for (int j = 1; j <= i&&j<=k; j++)a[n - i] =(a[n-i]+ a[n - i + j])%100003;}
}
int main()
{memset(a, 0, sizeof(a));scanf("%d %d", &n, &k);solve();printf("%d", a[0]);return 0;
}
更多推荐
ACM入门（一）
发布评论