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
完全背包
多重背包