日期差值
题目
有两个日期，求两个日期之间的天数，如果两个日期是连续的我们规定他们之间的天数为两天
思路
先上日期三板斧
int保存日期，然后从后往前摩，逐次取出来年月日，然后先加年，再加月，再加日
代码
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 10010;
const int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int is_leap_year(int year) {
if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0))
return 1;
return 0;
}
int days_of_month(int year, int month) {
return months[month] + is_leap_year(year);
}
int date1, date2;
int main() {
while (cin >> date1 >> date2) {
int y1, d1, m1, d2, m2, y2;
d1 = date1 % 100;
date1 /= 100;
m1 = date1 % 12;
date1 /= 100;
y1 = date1;
d2 = date2 % 100;
date2 /= 100;
m2 = date2 % 12;
date2 /= 100;
y2 = date2;
int cha = 0;
for (int i = y1; i < y2; i++) {
cha += 365 + is_leap_year(i);
}
for (int i = m1; i < m2; i++) {
cha += months[i];
}
cha += d2 - d1;
cout << cha + 1 << endl;
}
return 0;
}
字母统计
题目
输入一行字符串，计算其中A-Z大写字母出现的次数
思路
char[1000] s;
int n = strlen(s);
for(int i = 0; i < n;i ++)…
定义map:
map<char,int> m;
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
char s[1000];
while (~scanf("%s", s)) {
map<char, int> m;
int n = strlen(s);
for (int i = 0; i < n; i++) {
if (s[i] >= 'A' && s[i] <= 'Z') {
m[s[i]]++;
}
}
for (int i = 'A'; i <= 'Z'; i++) {
printf("%c:%d\n", i, m[i]);
}
}
return 0;
}
后缀子串排序
题目
对于一个字符串，将其后缀子串进行排序，例如grain 其子串有： grain rain ain in n 然后对各子串按字典顺序排序，即： ain,grain,in,n,rain
思路
逐个把后缀压入vector，注意不要压入空字符串！！
代码
#include <bits/stdc++.h>
using namespace std;
bool cmp(string a, string b) {
return a < b;
}
int main() {
string s;
while (cin >> s) {
vector<string> vec;
int n = s.size();
for (int i = 1; i <= n; i++) {
vec.push_back(s.substr(n - i));
}
sort(vec.begin(), vec.end(), cmp);
int m = vec.size();
for (int j = 0; j < m; j++) {
cout << vec[j] << endl;
}
}
return 0;
}
筛质数：
从2到n遍历，如果当前数是质数，就把它的所有倍数都置为合数
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int st[N], primes[N], cnt;
void get_primes(int n) {
for (int i = 2; i <= n; i++) {
if (!st[i]) { //如果i是质数
primes[cnt++] = i;
for (int j = 2 * i; j <= n; j += i)
st[j] = true;
}
}
}
int main() {
int n;
cin >> n;
get_primes(n);
cout << cnt << endl;
for (int i = 0; i < cnt; i++) {
cout << primes[i] << endl;
}
return 0;
}
快速幂
把k分解成二进制的形式，从后往前逐位的乘$a^{2^i}$
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int st[N], primes[N], cnt;
// a ^ k % p
int qmi(int a, int k, int p) {
int res = 1;
while (k) {
if (k & 1)
res = (long long)res * a % p;
k >>= 1;
a = (long long)a * a % p;
}
return res;
}
int main() {
int n;
cin >> n;
while (n--) {
int a, k, p;
cin >> a >> k >> p;
cout << qmi(a, k, p) << endl;
}
return 0;
}
整除问题
题目
给定n，a求最大的k，使n！可以被a^k整除但不能被a^(k+1)整除。
思路
把n!和a^k都分解成多项式的乘积的形式，然后看每个质因子的指数的倍数关系，最小的倍数就是k
代码
#include<bits/stdc++.h>
using namespace std;
//得到数n的质因子及其个数
void getPrime(vector<int>& factors, int n){
for(int i=2; i*i<=n; i++){
while(n % i == 0){
factors[i]++;
n /= i;
if(n <= 1)
return;
}
}
if(n > 1)
factors[n]++;
}
int main(){
int n, a;
while(cin >> n >> a){
vector<int> factor_a(1000), factor_n(1000);
getPrime(factor_a, a);
//计算阶乘的每一个数的质因子及其个数；并进行个数的累加
for(int i=2; i<=n; i++)
getPrime(factor_n, i);
int k = 1000;
//看2~n包含多少个对应的质因子
for(int i=2; i<=a; i++)
if(factor_a[i])
k = min(k, factor_n[i]/factor_a[i]);
cout << k << endl;
}
}
高精度
import java.util.Scanner;
import java.math.BigInteger;
public class Main{
public static void main(String[] args){
Scanner sr = new Scanner(System.in);
while(sr.hasNext()){
BigInteger a, b;
a = sr.nextBigInteger();
b = sr.nextBigInteger();
System.out.println(a.add(b));
System.out.println(a.substract(b));
System.out.println(a.multiply(b));
System.out.println(a.divided(b));
}
}
}
运算表达式*
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int num[N]; // 数组模拟栈
int a, b;
char op[N];
void calc() {
int y = num[a--];
int x = num[a--];
char ope = op[b--];
int res;
if (ope == '+')
res = x + y;
else if (ope == '-')
res = x - y;
else if (ope == '*')
res = x * y;
else
res = x / y;
num[++a] = res;
}
int main() {
unordered_map<char, int> pr = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
string str;
cin >> str;
for (int i = 0; str[i]; i++) {
char c = str[i];
if (c == '(')
op[++b] = c; // 读入`(`
else if (c == ')') { // 读入`)`
while (op[b] ^ '(')
calc();
b--;
} else if (isdigit(c)) { // 读入数字
int j = i, res = 0;
while (str[j] && isdigit(str[j]))
res = res * 10 + str[j++] - '0';
num[++a] = res;
i = j - 1;
} else { // 读入运算符
while (b and pr[c] <= pr[op[b]])//把栈中所有优先级大于等于当前运算符的都计算完
calc();
op[++b] = c;
}
}
while (b)
calc(); // 读入结束，处理结果。
cout << num[a]; // 输出结果。
return 0;
}
求连通分量的个数
dfs1
#include <bits/stdc++.h>
using namespace std;
vector<int>g[1010];
bool vis[1010];
void dfs(int x){
vis[x]=true;
for(int y:g[x]){
if(!vis[y]){
dfs(y);
}
}
}
int main(){
unordered_set<int>st;
int x,y;
while(cin>>x>>y){
st.insert(x);
st.insert(y);
g[x].push_back(y);
g[y].push_back(x);
}
int ans=0;
for(int x:st){
if(!vis[x]){
ans++;
dfs(x);
}
}
cout<<ans;
return 0;
}
dfs2
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx, st[N];
int cnt = 0;
void dfs(int x) {
st[x] = false;
for (int i = h[x]; i != -1; i = ne[i]) {
int j = e[i];
if (st[j]) {
dfs(j);
}
}
}
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int main() {
memset(h, -1, sizeof h);
int a, b;
int mx = 0;
while (cin >> a >> b) {
mx = max(max(a, b), mx);
add(a, b);
add(b, a);
st[a] = true;
st[b] = true;
}
for (int i = 1; i <= mx; i++) {
if (st[i]) {
dfs(i);
cnt++;
}
}
cout << cnt;
return 0;
}
并查集
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int p[N];
int find(int x) {
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
int main() {
int a, b;
for (int i = 0; i < N; i++) {
p[i] = i;
}
set<int> s;
while (cin >> a >> b) {
s.insert(a);
s.insert(b);
if (find(a) != find(b)) {
p[a] = find(b);
}
}
int res = 0;
for (auto x : s) {
if (p[x] == x)
res++;
}
cout << res << endl;
return 0;
}
n!后面0的个数
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
while (cin >> n) {
int res = 0;
while (n) {
n /= 5;
res += n;
}
cout << res << endl;
}
return 0;
}
最长上升子序列
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int res = 0;
int i = 0, j = 1;
while (j < n) {
while (a[j] > a[j - 1])
j++;
res = max(res, j - i);
i = j;
j++;
}
cout << res << endl;
return 0;
}
最小面积子矩阵
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m, k;
int a[N][N], s[N][N];
int main() {
cin >> n >> m >> k;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> s[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == 0 && j == 0)
continue;
else if (i == 0)
s[i][j] += s[i][j - 1];
else if (j == 0)
s[i][j] += s[i - 1][j];
else
s[i][j] = s[i][j] - s[i - 1][j - 1] + s[i][j - 1] + s[i - 1][j];
}
}
int res = 10000;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int ii = 0; ii <= i; ii++) {
for (int jj = 0; jj <= j; jj++) {
if (s[i][j] - s[i][jj] - s[ii][j] + s[ii][jj] >= k) {
res = min(res, (i - ii) * (j - jj));
}
}
}
}
}
cout << res << endl;
return 0;
}
取中值
#include <bits/stdc++.h>
using namespace std;
const int N = 1000100;
int n, m;
int p[N], q[N];
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> p[i];
}
for (int i = 0; i < m; i++) {
cin >> q[i];
}
int a, b, c, d;
cin >> a >> b >> c >> d;
sort(p + a - 1, p + b);
sort(q + c - 1, q + d);
vector<int> f;
for (int i = a - 1; i < b; i++) {
f.push_back(p[i]);
}
for (int i = c - 1; i < d; i++) {
f.push_back(q[i]);
}
sort(f.begin(), f.end());
cout << f[f.size() / 2] << endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
while(getline(cin,s)){
int index = s.find(' ');
int sum = 0;
bool flag = true;
while(index!=-1 && index<s.size()){
string tmp = s.substr(0,index);
int t = 0;
for(int i=tmp.size()-1,c=1;i>=0;--i,c*=10){
if(tmp[i]>'9'||tmp[i]<'0'){
flag = false;
break;
}
t+=(tmp[i]-'0')*c;
}
if(!flag){
break;
}
sum+=t;
s = s.substr(index+1);
index = s.find(' ');
}
if(s.size()!=0){
for (int i = s.size() - 1, c = 1; i >= 0;--i,c*=10){
if(s[i]>'9'||s[i]<'0'){
flag = false;
break;
}
sum += (s[i] - '0') * c;
}
}
if(!flag){
cout<<"ERROR"<<endl;
}else{
int a = sum/2;
int b = sum-a;
cout<<b<<" "<<a<<endl;
}
}
return 0;
}
最长公共子序列
#include <bits/stdc++.h>
using namespace std;
int main() {
string s1, s2;
while (cin >> s1 >> s2) {
s1 = " " + s1;
s2 = " " + s2;
int n = s1.size(), m = s2.size();
vector<vector<int>> dp(n, vector<int>(m));
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (s1[i] == s2[j]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
cout << dp[n - 1][m - 1] << endl;
}
return 0;
}
Day of week
#include <bits/stdc++.h>
using namespace std;
int n;
int xq[5000][20][50];
int isLeap(int y){
if(y%4==0&&y%100!=0||y%400==0)return 1;
else return 0;
}
int m2d[5][20]={{0,31,28,31,30,31,30,31,31,30,31,30,31},{0,31,29,31,30,31,30,31,31,30,31,30,31}};
int y2d[5]={365,366};
string dayName[10]={"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
string monthName[20]={"","January","February","March","April","May","June","July","August","September","October","November","December"};
int main(){
int d,m,y;
string mn;
int cnt=0;
for(int y=1;y<=2100;++y){
int l=isLeap(y);
for(int m=1;m<=12;++m){
for(int d=1;d<=m2d[l][m];++d){
cnt++;
xq[y][m][d]=cnt%7;
}
}
}
unordered_map<string,int>mn2m;
for(int i=1;i<=12;++i){
mn2m[monthName[i]]=i;
}
while(cin>>d>>mn>>y){
m=mn2m[mn];
cout<<dayName[xq[y][m][d]]<<'\n';
}
return 0;
}
最长公共子串
垃圾用例，为啥用b的子串在a里find就只能过50%
用a的子串在b里find就能ac
#include <bits/stdc++.h>
using namespace std;
int main() {
string a, b;
while (cin >> a >> b) {
string res;
bool hit = false;
int n = a.size(), m = b.size();
for (int i = n; i >= 1; i--) {
for (int j = 0; j + i <= n; j++) {
bool flag = true;
string tmp = a.substr(j, i);
for (int k = 0; k < tmp.size(); k++) {
if (isdigit(tmp[k]))
flag = false;
}
if (flag && b.find(tmp) != b.npos) {
hit = true;
res = tmp;
break;
}
}
if (hit)
break;
}
cout << res << endl;
}
return 0;
}
玛雅人的密码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
int n;
int bfs(string s){
queue<string> q;
map<string,int> dist;
q.push(s);
dist[s] = 0;
while(q.size()){
string str = q.front();
q.pop();
for(int i = 0; i <n;i ++){
if(str.substr(i,4) == "2012"){
return dist[str];
}
}
for(int i = 1; i < n; i ++){
string r = str;
swap(r[i],r[i - 1]);
if(!dist.count(r)){
q.push(r);
dist[r] = dist[str] + 1;
}
}
}
return -1;
}
int main(){
cin >>n;
string s;
cin >> s;
cout << bfs(s);
return 0;
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1149440709@qq.com
