```cpp
#include<iostream>
#include<cstdio>
using namespace std;
int n,ans1,ans2[10001][11],sum,a[11];
void trys(int t,int m)//t代表当前的尝试的调料。m代表当前美味程度
{
    if (t>10) 
    {
        if (m==n) //如果美味程度与猪猪的要求相等 
        {
            ans1++;//统计方案总数 
            for (int i=1;i<=10;i++)
            ans2[ans1][i]=a[i];//存入答案的数组 
        }
        return ;
    }
    for (int i=1;i<=3;i++)
    {
        if (m+i>n) break;//如果超过了要求，那么后面的就可以直接忽略 
        a[t]=i;//储存答案 
        trys(t+1,m+i);//查看下一种调料 
        a[t]=0;//状态恢复 
    }
}
int main()
{
    cin>>n;
    trys(1,0);//从第一种调料开始尝试，美味程度为0 
    cout<<ans1<<endl;
    for (int i=1;i<=ans1;i++)
    {
        for (int j=1;j<=10;j++)
            cout<<ans2[i][j]<<" ";
        cout<<endl;
    }//输出结果 
    return 0;
} 



// 

#include<iostream>
using namespace std;
int s,t,n;
int a[11];
int b[10000][11];//一个二维数组，先出方案总数很难做呀
int c=1;
int num;
void ss(int k);
void pp();
int main() {
	cin>>n;
	ss(1);
	cout<<num<<endl;
	for(int i=1; i<c; i++) {
		for(int j=1; j<=10; j++) {
			cout<<b[i][j]<<" ";
		}
		cout<<endl;
	}
}
void ss(int k) {
	for(int i=1; i<=3; i++)//每个只能加1,或2或3 {
		s+=i;
		a[k]=i;
		if(k==10) {
			if(s==n)pp();
		} else ss(k+1);
		s-=i;//回溯
	}
}
void pp() {
	num++;
	for(int i=1; i<=10; i++)
		b[c][i]=a[i];//存数组
	c++;
}




// STL

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int b3[10]={0,1,2,3,4,5,6,7,8,9};//打表
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	int co=0;
	do{
		int a1=100*b3[1]+10*b3[2]+b3[3];//第一个数
		int b1=100*b3[4]+10*b3[5]+b3[6];//第二个数
		int c1=100*b3[7]+10*b3[8]+b3[9];//第三个数
		if((a1*b==b1&&a1*c==c1)||(a1==a&&b1==b&&c1==c)){//判断
			co++;
			printf("%d %d %d\n",a1,b1,c1);//输出
		}
	}
	while(next_permutation(b3+1,b3+10));
	if(co==0){
		printf("No!!!");
	}
	return 0;
}
```

P2089回溯

```cpp
#include <iostream>
#include <vector>
using namespace std;



void bucketSort(vector<int>& arr) {
    const int maxVal = 1000; // 假设候选人编号不超过 1000
    vector<int> buckets(maxVal + 1, 0);

    for (int i = 0; i < arr.size(); i++) {
        buckets[arr[i]]++;
    }

    for (int i = 1; i <= maxVal; i++) {
        for (int j = 0; j < buckets[i]; j++) {
            cout << i << ' ';
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> votes(m);

    for (int i = 0; i < m; i++) {
        cin >> votes[i];
    }

    bucketSort(votes); // 调用桶排序函数

    return 0;
}

```


```cpp
#include<bits/stdc++.h>
using namespace std;
int a,n,m,b[1000];
int main()
{
	cin>>n>>m;
	for(int i=0;i<m;i++)cin>>a,++b[a]; //记录票出现的次数
	for(int i=0;i<1000;i++)while(b[i]--)cout<<i<<" "; //根据票出现的次数输出
	return 0;
}
```

P1271

P1481




```cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct TrieNode {
    TrieNode* children[26];
    int depth;

    TrieNode() {
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
        depth = 0;
    }
};

int findLongestWordChain(vector<string>& words) {
    sort(words.begin(), words.end());
    TrieNode* root = new TrieNode();
    int maxLength = 0;

    for (const string& word : words) {
        TrieNode* cur = root;
        int length = 0;

        for (char c : word) {
            int index = c - 'a';
            if (cur->children[index] == nullptr) {
                cur->children[index] = new TrieNode();
            }
            cur = cur->children[index];
            length = max(length, cur->depth);
        }

        cur->depth = length + 1;
        maxLength = max(maxLength, cur->depth);
    }

    return maxLength;
}

int main() {
    int n;
    cin >> n;

    vector<string> words;
    for (int i = 0; i < n; i++) {
        string word;
        cin >> word;
        words.push_back(word);
    }

    int result = findLongestWordChain(words);
    cout << result << endl;

    return 0;
}

```

解法二  dp

```cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int findLongestWordChain(vector<string> words) {
    int n = words.size();
    vector<int> dp(n, 1);

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (words[i].find(words[j]) == 0) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    int maxChainLength = 0;
    for (int i = 0; i < n; i++) {
        maxChainLength = max(maxChainLength, dp[i]);
    }

    return maxChainLength;
}

int main() {
    int n;
    cin >> n;
    vector<string> words(n);

    for (int i = 0; i < n; i++) {
        cin >> words[i];
    }

    sort(words.begin(), words.end()); // Sort the words lexicographically

    int result = findLongestWordChain(words);
    cout << result << endl;

    return 0;
}

```

trie树

B3616




```cpp
#include <iostream>

class Queue {
private:
    int* data;
    int front;
    int rear;
    int capacity;
    int size;

public:
    Queue(int cap) {
        data = new int[cap];
        capacity = cap;
        front = rear = -1;
        size = 0;
    }

    ~Queue() {
        delete[] data;
    }

    void push(int x) {
        if (size == capacity) {
            std::cout << "ERR_CANNOT_PUSH" << std::endl;
        } else {
            rear = (rear + 1) % capacity;
            data[rear] = x;
            if (size == 0) {
                front = rear;
            }
            size++;
        }
    }

    void pop() {
        if (size == 0) {
            std::cout << "ERR_CANNOT_POP" << std::endl;
        } else {
            front = (front + 1) % capacity;
            size--;
        }
    }

    void query() {
        if (size == 0) {
            std::cout << "ERR_CANNOT_QUERY" << std::endl;
        } else {
            std::cout << data[front] << std::endl;
        }
    }

    int getSize() {
        return size;
    }
};

int main() {
    int n;
    std::cin >> n;

    Queue q(100); // 假设队列最大容量为100

    for (int i = 0; i < n; i++) {
        int op;
        std::cin >> op;
        if (op == 1) {
            int x;
            std::cin >> x;
            q.push(x);
        } else if (op == 2) {
            q.pop();
        } else if (op == 3) {
            q.query();
        } else if (op == 4) {
            std::cout << q.getSize() << std::endl;
        }
    }

    return 0;
}

```

队列

看到要计算最短时间就知道要排序

[并查集模板](https://www.luogu.com.cn/training/3065#problems)


```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Road {
    int from, to, repairTime;
};

vector<int> parent;

int find(int x) {
    if (parent[x] == x) {
        return x;
    }
    return parent[x] = find(parent[x]);
}

bool unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootX] = rootY;
        return true; // 返回 true 表示成功合并
    }
    return false; // 返回 false 表示已经在同一集合中
}

int main() {
    int N, M;
    cin >> N >> M;

    vector<Road> roads(M);

    for (int i = 0; i < N; ++i) {
        parent.push_back(i); // 初始化每个村庄独立成集合
    }

    for (int i = 0; i < M; ++i) {
        cin >> roads[i].from >> roads[i].to >> roads[i].repairTime;
        roads[i].from--;
        roads[i].to--;
    }

    sort(roads.begin(), roads.end(), [](const Road &a, const Road &b) {
        return a.repairTime < b.repairTime;
    });

    int components = N;
    int earliestTime = -1;

    for (int i = 0; i < M; ++i) {
        if (unite(roads[i].from, roads[i].to)) {
            components--;
            earliestTime = roads[i].repairTime;
            if (components == 1) {
                break; // 所有村庄已连通
            }
        }
    }

    if (components == 1) {
        cout << earliestTime << endl;
    } else {
        cout << -1 << endl;
    }

    return 0;
}


```