题解题解题解题解
P1064 [NOIP2006 提高组] 金明的预算方案 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
感觉这道题挺不错的，附带条件的背包问题，总的有两种可能：
一：买主件（有四种）：
1.买主件
2.买主件+附件1
3.买主件+附件2
4.买主件+附件1+附件2
二：不买主件（没有情况可以考虑的，不买主件也就是也不买附件）
ll zw[N], zv[N], fw[N][3], fv[N][3], dp[N];
void solve()
{ll n, m;cin >> n >> m;for (int i = 1; i <= m; i++){ll v, p, q;cin >> v >> p >> q;if (!q)//主件{zw[i] = v;zv[i] = v * p;}else//附件{fw[q][0]++;fw[q][fw[q][0]] = v;fv[q][fw[q][0]] = v * p;}}for (int i = 1; i <= m; i++){for (int j = n; j >= zw[i]; j--){//情况1dp[j] = max(dp[j], dp[j - zw[i]] + zv[i]);//情况2if (j >= zw[i]+fw[i][1]){dp[j] = max(dp[j], dp[j - zw[i] - fw[i][1]] + zv[i] + fv[i][1]);}//情况3if (j >= zw[i] + fw[i][2]){dp[j] = max(dp[j], dp[j - zw[i] - fw[i][2]] + zv[i] + fv[i][2]);}//情况4if (j >= zw[i] + fw[i][1] + fw[i][2]){dp[j] = max(dp[j], dp[j - zw[i] - fw[i][1] - fw[i][2]] + zv[i] + fv[i][1] + fv[i][2]);}}}cout << dp[n] << endl;return;
}P1156 垃圾陷阱 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
很奇怪，不知道为什么sort函数突然用不了，一直报错
这也是一道dp题，从d~0进行遍历，用一个数组这样子记录f[高度]=生命，将垃圾根据掉落时间从小到大进行排序，若当前高度的生命大于当前垃圾掉落的时间且高度+当前生命不小于所需要跳过的高度就可以直接输出（因为我们是从小到大根据掉落时间进行遍历的，越早满足条件自然越符合题目要求），否则就按照正常dp来，f[j]=max(f[j],f[j+lj[i].h])
代码（sort报错）：
struct node
{int t;int f;int h;
}lj[1010];
ll f[1010];
bool cmp(node a, node b)
{return a.t < b.t;
}
void solve()
{int d, g;cin >> d >> g;for (int i = 1; i <= g; i++){cin >> lj[i].t >> lj[i].f >> lj[i].h;}sort(lj + 1, lj + 1 + g, cmp);f[0] = 10;for (int i = 1; i <= g; i++){for (int j = d; j >= 0; j--){if (f[j] >= lj[i].t){if (j + lj[i].h >= d){cout << lj[i].t;return;}}f[j] = max(f[j], f[j + lj[i].h]);f[j] += lj[i].f;}}cout << f[0] << endl;return;
}P3405 [USACO16DEC] Cities and States S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
使用数组记录即可，把字符串的前两位拿出来进行哈希（防止字符串过大）
ll ch[1010][1010];
void solve()
{ll n;cin >> n;ll ans = 0;while (n--){string a, b;cin >> a >> b;ll x = (a[0] - 'A') * 26 + (a[1] - 'A');ll y = (b[0] - 'A') * 26 + (b[1] - 'A');if (x != y){ch[x][y]++;ans += ch[y][x];}}cout << ans << endl;return;
}P5250 【深基17.例5】木材仓库 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
学习set的好题
先定义set和set的迭代器:set<int>a set<int>::iterator it
学会了一些set的基本操作：
it.find(a.begin(),a.end(),查找的元素),若集合中不存在该元素则会返回a.end()
a.insert(插入元素的值) a.empty()判断集合是否为空 a.erase(要删除元素的下标)
itup = upper_bound(a.begin(), a.end(), x);查找第一个大于x的元素的位置
itup = lowpper_bound(a.begin(), a.end(), x);查找第一个大于等于x的元素的位置
AC代码：
set<int>a;
set<int>::iterator it, itup;
void solve()
{int n;cin >> n;for (int i = 0; i < n; i++){int x, y;cin >> x >> y;it = find(a.begin(), a.end(), y);if (x == 1){if (it == a.end()){a.insert(y);}else{cout << "Already Exist\n";}}else if (x == 2){if (a.empty()){cout << "Empty\n";}else if (it != a.end()){cout << y << endl;a.erase(it);}else{itup = upper_bound(a.begin(), a.end(), y);if (itup == a.end())//找到最后还没找到{itup--;cout << *itup << endl;a.erase(itup);}else if (itup == a.begin())//找到了但是是第一位{cout << *itup << endl;a.erase(itup);}else{it = itup--;if (y - (*it) > (*itup) - y){cout << *it << endl;a.erase(it);}else{cout << *itup << endl;a.erase(itup);}}}}}return;
}P2024 [NOI2001] 食物链 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这道题考查的是并查集，采取三倍并查集的思想，x代表当前动物，x+n代表其猎物,x+2*n代表其天敌，从下面两种情况来考虑：
为1时：若x或y>n则为假话，若x和y不为同类则为假话
为2时：若x的猎物是本身则为假话，若x的天敌是y或x的同类是y则为假话
AC代码：
int fa[N];
int find(int x)
{if (fa[x] == x)return x;fa[x] = find(fa[x]);return fa[x];
}
void combine(int x, int y)
{int a = find(fa[x]);int b = find(fa[y]);if (a != b){fa[a] = b;}
}
void solve()
{ll n, k;cin >> n >> k;ll ans = 0;for (int i = 1; i <= 3 * n; i++){fa[i] = i;}for (int i = 1; i <= k; i++){int z, x, y;cin >> z >> x >> y;if (x > n || y > n){ans++;continue;}if (z == 1){if (find(x + n) == find(y) || find(x + 2 * n) == find(y)){ans++;continue;}//x和y是同类说明它们的猎物和天敌都会相同combine(x, y);combine(x + n, y + n);combine(x + 2 * n, y + 2 * n);}else{if (x == y){ans++;continue;}if (find(x) == find(y) || find(x + 2 * n) == find(y))//若x的天敌是y或x的同类是y则为假话{ans++;continue;}combine(x + n, y);combine(x + 2 * n, y + n);combine(x, y + 2 * n);}}cout << ans << "\n";return;
}