一、前綴和的應(yīng)用
求完前綴和后 可以根據(jù)前綴和數(shù)組求出字段和
如求L~R的字段和
前綴和數(shù)組為s
子段和為s[R]-s[L-1]
二、判斷回文數(shù)算法
bool pdh(int n) {
int m = n;
int num=0;
//將數(shù)字倒著計(jì)算出來
while (m) {
num = num * 10 + m % 10;
m /= 10;
}
//判斷結(jié)果與原數(shù)字是否相等
if (num == n)
return true;
else return false;
}
三、判斷位數(shù)的方法
int weishu(int j) { //計(jì)算一個(gè)數(shù)的長(zhǎng)度
int b = j, count = 0;
while (b > 0) {
b /= 10;
count++;
}
return count;
}
三指攒、stringstream
#include <iostream>
#include <sstream>
using namespace std;
int main(void)
{
stringstream ss;
int sum = 0;
//string s1 = "123";
int num = 123;
string s2 = "456";
ss << num << s2 << endl;
string text = ss.str();
cout << text;
//傳入字符串 合成一個(gè)字符串
return 0;
}
#include <iostream>
#include <sstream>
using namespace std;
int main(void)
{
stringstream ss;
int sum = 0;
string s1 = "12 34 56";
string s2 = "456";
//ss << s1 << s2 << endl;
//string text = ss.str();
//cout << text;
int num;
ss << s1;
while (ss >> num) {
sum += num;
}
//字符串傳入流 按空格解析字符串
//輸出sum=102
cout << sum << endl;
return 0;
}
#include <iostream>
#include <sstream>
using namespace std;
int main(void)
{
stringstream ss;
int sum = 0;
//string s1 = "123";
int num = 123;
string s2 = "456";
ss << num ;
ss << 456;
string text;
ss >> text;
cout << text<<endl;
stringstream ss1;
string s3 = "12 34 56";
string s4 = " 456";
int num1;
ss1 << s3<<s4;
while (ss1 >> num1) {
sum += num1;
}
cout << sum << endl;
//傳入字符串 合成一個(gè)字符串
return 0;
}
四、一種巧妙的構(gòu)造回文的方法
列如1234->12344321
int date=1234;
int x=1234;
for(int i=0;i<4;i++){
date=date*10+x%10;
x/=10;
}
常用判斷日期是否合法的方法
例題 回文日期
int monday[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
//判斷閏年
bool isyear(int year) {
if (year % 400 == 0 || year % 100 != 0 && year % 4 == 0)
return true;
else return false;
}
bool judge(int year,int mon,int day) {
//判斷日期是否合法
if (day == 0)
return false;
if (mon != 2 &&day > monday[mon])
return false;
if (mon < 1 || mon>12)
return false;
if (mon == 2) {
if (isyear(year)) {
if (day > monday[2] + 1)
return false;
}
else if (day > monday[2])
return false;
}
return true;
}
五僻焚、scanf格式化輸入
如輸出日期2020/03/04
int year,mon,day;
scanf("%d/%d/%d",&year,&mon,&day);
printf("%d %d %d",year,mon,day);
輸出 2020 3 4
scanf 可以根據(jù)題目要求的任意格式進(jìn)行輸入
例題 Acwing1231 航班時(shí)間
#include<bits/stdc++.h>
using namespace std;
int main()
{
int h1,m1,s1,h2,m2,s2,day1,day2;
注意：就算后面沒有輸入day1也沒有關(guān)系 day1為0
scanf("%d:%d:%d %d:%d:%d (+%d)",&h1,&m1,&s1,&h2,&m2,&s2,&day1);
cout<<h1<<' '<<m1<<' '<<s1<<' '<<h2<<' '<<m2<<' '<<s2<<' '<<day1<<endl;
return 0;
}
六允悦、printf補(bǔ)0
int a=4;
不足兩位就補(bǔ)0
printf("%02d",a); 輸出04
不足三為就補(bǔ)0
printf("%03d",a);輸出004
七、printf補(bǔ)空格
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a = 5,b=6;
不足5位左補(bǔ)空格
printf("%5d%d\n", a, b);輸出 56
不足5位右補(bǔ)空格
printf("%-5d%d\n", a,b);輸出5 6
return 0;
}
八虑啤、getline
在使用getline的時(shí)候隙弛，無論前面使用過scanf 還是cin
getline都會(huì)讀入他們后面輸入的回車
因此要先寫一句getline 吃掉回車
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
string s;
getline(cin, s);
getline(cin, s);
cout << s << endl;
return 0;
}
九、思維強(qiáng)化 二分
當(dāng)具有單調(diào)性的問題狞山，一定要考慮到使用二分算法全闷。
多數(shù)為最大求最小，和最小求最大問題萍启；
如总珠，在一個(gè)線段上，每一個(gè)點(diǎn)有一個(gè)數(shù)字
每次選擇一段區(qū)間勘纯，減去一個(gè)數(shù)局服。求第一次出現(xiàn)小于等于0的次數(shù)
當(dāng)?shù)谝淮纬霈F(xiàn)了一個(gè)0后，以后再操作驳遵，每次都會(huì)存在小于等于0的數(shù)
所以這個(gè)問題具有單調(diào)性淫奔，需要用二分查找
十、容器的重載運(yùn)算符問題
當(dāng)pair重載了<想按照second排序時(shí)超埋，由于pair初始化時(shí)已經(jīng)重載過運(yùn)算符，所以此時(shí)重載無效佳鳖。此時(shí)要自己寫排序結(jié)構(gòu)函數(shù)cmp霍殴，加入到第三個(gè)參數(shù)上。
#include<bits/stdc++.h>
using namespace std;
//bool operator<(pair<int, int> a, pair<int, int> b) {
// return a.second < b.second;
//
//}
bool cmp(pair<int, int> a, pair<int, int> b) {
return a.second < b.second;
}
int main()
{
pair<int, int> num[10];
for (int i = 0; i < 4; i++) {
int a, b;
cin >> a >> b;
num[i] = make_pair(a, b);
}
sort(num, num + 4,cmp);
for (int i = 0; i < 4; i++) {
cout << num[i].first << ' ' << num[i].second << endl;
}
return 0;
}
vecctor排序需要些begin() end()
重載運(yùn)算符也是沒有效果 需要自己寫比較函數(shù)
#include<bits/stdc++.h>
using namespace std;
//bool operator<(vector<int> a,vector<int> b) {
// return a < b;
//}
bool cmp(int a, int b) {
return a > b;
}
int main()
{
vector<int> v;
for (int i = 0; i < 4; i++) {
int num;
cin >> num;
v.push_back(num);
}
sort(v.begin(), v.end(),cmp);
//reverse(v.begin(), v.end());
for (int i = 0; i < 4; i++) {
cout << v[i] << ' ';
}
return 0;
}
十一系吩、快速乘
根據(jù)二進(jìn)制的原理 把乘法變?yōu)榧臃?/p>
#include<bits/stdc++.h>
using namespace std;
const int mod = 99901;
long long ksc(int x, int y, int p) {
long long res = 0;
while (y) {
if (y & 1)
res = (res + x) % p;
x = (x << 1) % p;
y = y >> 1;
}
return res;
}
int main()
{
int a, b;
cin >> a >> b;
long long ans = ksc(a, b, mod);
cout << ans << endl;
return 0;
}
