CSP-J入门组
简单排序：
图书馆中每本书都有一个图书编码，可以用于快速检索图书，这个图书编码是一个正整数。每位借书的读者手中有一个需求码，这个需求码也是一个正整数。如果一本书的图书编码恰好以读者的需求码结尾，那么这本书就是这位读者所需要的。小 D 刚刚当上图书馆的管理员，她知道图书馆里所有书的图书编码，她请你帮她写一个程序，对于每一位读者，求出他所需要的书中图书编码最小的那本书，如果没有他需要的书，请输出-1。
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b){
return (*(int *)a - *(int *)b);
}
int mod(int x){
int i, sum=1;
for(i=1; i<=x; i++)
{
sum*=10;
}
return sum;
}
int main()
{
int n, q, len[1002];
scanf("%d%d", &n, &q);
int i, j, num[1002], q1[1002];
for(i=1; i<=n; i++)
scanf("%d", &num[i]);
for(i=1; i<=q; i++)
scanf("%d%d", &len[i], &q1[i]);
qsort(num, n+1, sizeof(int), cmp);
for(i=1; i<=q; i++)
{
for(j=1; j<=n; j++)
{
if(num[j]%mod(len[i])==q1[i])
{
printf("%d\n", num[j]);
break;
}
else if(j==n)
printf("-1\n");
}
}
return 0;
} 字符串
给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见样例2）。
#include<iostream>
using namespace std;
int main()
{
int n,a,b=0;
cin>>n;
while(n!=0)
{
a=n%10;
n=n/10;
b=b*10+a;
}
cout<<b<<endl;
return 0;
} 二分：二分法是指对于区间[a，b]上连续不断且f（a）·f（b）<0的函数y=f（x），通过不断地把函数f（x）的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法。
有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值 ≥ 1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。
提示：记方程f(x) = 0，若存在2个数x1和x2，且x1 < x2，f(x1)*f(x2) < 0，则在(x1，x2)之间一定有一个根。
#include<bits/stdc++.h>
using namespace std;
double a,b,c,d,l,r,mid;
double s(double s)
{
return a*pow(s,3)+b*pow(s,2)+c*pow(s,1)+d;
}
int main()
{
cin>>a>>b>>c>>d;
for(int i=-100;i<=100;i++)
{
l=i,r=i+1;
if(s(l)==0) cout<<fixed<<setprecision(2)<<l<<" ";
else if(s(l)*s(r)<0)
{
while(r-l>=1e-5)
{
mid=(r+l)/2;
if(s(r)*s(mid)<0) l=mid;
else r=mid;
}
cout<<fixed<<setprecision(2)<<l<<" ";
}
}
return 0;
} 高精度：高精度运算，是指参与运算的数(加数，减数，因子……）范围大大超出了标准数据类型（整型，实型）能表示的范围的运算。
给出一个整数 n（n<1030) 和 k 个变换规则（k<=15）。
规则：
一位数可变换成另一个一位数：规则的右部不能为零。
例如：n=234。有规则（k＝2）：
2－> 5
3－> 6
上面的整数 234 经过变换后可能产生出的整数为（包括原数）:
234
534
264
564
共 4 种不同的产生数
问题：
给出一个整数 n 和 k 个规则。
求出：
经过任意次的变换（0次或多次），能产生出多少个不同整数。仅要求输出个数。
#include<iostream>
using namespace std;
string s;
int n,f[10][10],a[100010],c[100010];
void work()
{
cin>>s>>n;
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
f[x][y]=1;
}
for(int k=0;k<=9;k++)
for(int i=0;i<=9;i++)
for(int j=0;j<=9;j++)
if(i!=j&&i!=k&&j!=k&&f[i][k]&&f[k][j]) f[i][j]=1;
for(int i=0;i<=9;i++)
for(int j=0;j<=9;j++)
if(f[i][j]) a[i]++;
int d=1;
c[1]=1;
for(int j=0;j<s.size();j++)
{
int x=0;
int e=s[j]-'0';
e=a[e]+1;
for(int i=1;i<=d;i++)
{
c[i]=c[i]*e+x;
x=c[i]/10;
c[i]%=10;
}
if(x>0) c[++d]=x;
}
for(int i=d;i>=1;i--)
cout<<c[i];
cout<<"\n";
}
int main()
{
work();
return 0;
} 排列组合数学：
妞妞参加了Nowcoder Girl女生编程挑战赛, 但是很遗憾, 她没能得到她最喜欢的黑天鹅水晶项链。
于是妞妞决定自己来制作一条美丽的项链。一条美丽的项链需要满足以下条件:
1、需要使用n种特定的水晶宝珠
2、第i种水晶宝珠的数量不能少于li颗, 也不能多于ri颗
3、一条美丽的项链由m颗宝珠组成
妞妞意识到满足条件的项链种数可能会很多, 所以希望你来帮助她计算一共有多少种制作美丽的项链的方案。
#include <cstdio>
// #include <algorithm>
// using namespace std;
#define max(a, b) ((a) > (b) ? (a) : (b))
#define ll long long
const int M = 1e5 + 10;
int arr[M];
ll dp[25][105];
bool vis[25][105];
struct number{
int l, r;
}req[25];
ll DP(int n, int w) {
if (w < 0) return 0;
if (n == 0 && (w > req[0].r || w < req[0].l)) return 0;
if (n == 0) return 1;
if (vis[n][w]) return dp[n][w];
vis[n][w] = true;
ll &ret = dp[n][w];
for (int i = req[n].l; i <= req[n].r; ++i) {
ret += DP(n - 1, w - i);
}
return ret;
}
int main() {
int n, m;
scanf("%d %d\n", &n, &m);
for (int i = 0; i < n; ++i) {
int l, r;
scanf("%d %d", &l, &r);
req[i] = {.l = l, .r = r};
}
printf("%lld", DP(n - 1, m));
return 0;
} 递归排序：
哈希：散列函数（又称散列算法、哈希函数）能够从某一类数据中提取出一个有限长度的数字指纹作为数据的代表，这个”指纹“被称为散列值(哈希值）。散列函数产生的结果通常会比原数据小，从而实现数据的压缩；同时通过散列函数的计算过程是不可逆的，即无法根据散列值反推出原始数据，所以散列函数被广泛用于需要生成数据摘要或实现数据加密的应用场景中。[1]对于散列函数的选择，通常需要结合散列结果的冲突率、散列函数计算的代价来综合考虑。
基本递推
动态规划
贪心：贪婪算法是一种算法范例，它遵循在每个阶段做出局部最优选择[1] 的启发式求解方法，目的是寻找到一个全局最优解。在许多问题中，贪婪策略通常不会产生最优解，但是贪婪启发式可能会在合理的时间内产生近似全局最优解的局部最优解。
树形结构
枚举和暴力：在数学和计算机科学理论中，一个集的枚举是列出某些有穷序列集的所有成员的程序，或者是一种特定类型对象的计数。
暴力：利用枚举所有的情况，或者其它大量运算又不用技巧的方式，来求解问题的方法。广义的暴力法在解决问题，特别是数学和计算机编程问题方面应用广泛，有着巨大的作用。它的缺点是效率低下，优点是编码复杂度低，几乎不用思考，不容易出错。狭义的暴力法：这是一种简单的串匹配算法，用来判断一个短串t是不是一个长串s的子串。
01背包
区间dp
完全背包
多重背包