Taka 想要买个饮料。通常这需要 元。但是他如果同时买个杯子，就只需要 元。杯子有 种，第 种的价格为 。求他最少要花多少钱可以买到饮料。
#include <bits/stdc++.h>
using namespace std;
int n, p, q;
int d[105];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> p >> q;
for (int i = 1; i <= n; i++)
cin >> d[i];
int ans = p;
for (int i = 1; i <= n; i++)
ans = min(ans, d[i] + q);
cout << ans << "\n";
return 0;
}
AtCoder 商店有 件商品。第 件商品的价格为 。第 件商品有 种功能，对应的功能编号（）分别为 。
Taka 想知道是否存在同时满足下面所有条件的 ：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100;
const int MAXM = 100;
int n, m;
int p[MAXN + 5], c[MAXN + 5], f[MAXN + 5][MAXM + 5];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> p[i] >> c[i];
for (int j = 1; j <= c[i]; j++)
{
int x;
cin >> x;
f[i][x] = 1;
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i == j || p[i] < p[j])
continue;
bool flag1 = true; // 所有 i 有的 j 都有
bool flag2 = false; // 存在 i 没有的 j 有
for (int k = 1; k <= m; k++)
{
if (f[i][k] == 1 && f[j][k] == 0)
flag1 = false;
if (f[i][k] == 0 && f[j][k] == 1)
flag2 = true;
}
if (p[i] >= p[j] &&
flag1 == true &&
(p[i] > p[j] || flag2))
{
cout << "Yes\n";
return 0;
}
}
}
cout << "No\n";
return 0;
}
给定 个字符串 。求不同的字符串有多少个？
在本题中，如果字符串 与 字符串 相同，或者与字符串 翻转后的字符串相同。我们就说 与 是相同的。
字典树轻松完成。
当然也可以把字符串丢进 set<string>，然后查一下当前字符串的正反序是否存在。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
const int MAXNODE = 200000;
int n, ans;
string s[MAXN + 5];
struct Trie
{
int tot, root;
int son[MAXNODE + 5][26];
int tag[MAXNODE + 5];
// 清空节点
void clearNode(int nId)
{
for (int i = 0; i < 26; i++)
son[nId][i] = 0;
tag[nId] = 0;
}
// 字典树中插入字符串
void ins(const string &s)
{
int now = root;
for (int i = 0; i < s.size(); i++)
{
int j = s[i] - 'a';
if (!son[now][j])
{
son[now][j] = ++tot;
clearNode(tot);
}
now = son[now][j];
}
tag[now]++;
}
bool check(const string &s)
{
int now = root;
for (int i = 0; i < s.size(); i++)
{
int j = s[i] - 'a';
if (!son[now][j])
return false;
now = son[now][j];
}
return tag[now];
}
bool check1(const string &s)
{
int now = root;
for (int i = s.size() - 1; i >= 0; i--)
{
int j = s[i] - 'a';
if (!son[now][j])
return false;
now = son[now][j];
}
return tag[now];
}
} trie;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
trie.tot = trie.root = 1;
ans = 0;
for (int i = 1; i <= n; i++)
{
cin >> s[i];
if (trie.check(s[i]) || trie.check1(s[i]))
continue;
ans++;
trie.ins(s[i]);
}
cout << ans << "\n";
return 0;
}
有 个运动员，编号为 。有 组不相容的关系，第 组的关系为 。不相容指的是不能把 两位运动员放在同一个小组。
现在需要把这 位运动员恰好分成 组，问有多少种分法。
数据范围非常小，直接爆搜然后加一点小剪枝即可。
需要注意的是因为组与组之间是不区分的，所以在爆搜时需要注意小细节。
一个解决方法是：在给当前运动员分配组的时候，放入已有成员的组什么都不用管，但如果单独成一组，那么与前面的运动员中间不留空组。比如给前四位运动员分组可以 12 | 3 | 4 而不能 123 | | 4，后者在下一个 5 来的时候，如果 5 放入了空组，就会有重复的情况了。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 10;
int n, t, m, ans;
int ai, bi;
vector<int> e[MAXN + 5]; // i与哪些人有冲突
bool f[MAXN + 5][MAXN + 5]; // i 与 j 是否冲突
int cnt[MAXN + 5]; // i 与几个人有冲突
int cntT; // 一共用了几组
int hav[MAXN + 5][MAXN + 5]; // 第 i 组有 hav[i][0] 个人，分别为 hav[i][1] ~ hav[i][hav[i][0]]
// 当前考虑第now个人
void dfs(int now)
{
if (now > n)
{
if (cntT == t)
ans++;
return;
}
for (int i = 1; i <= t; i++)
{
// 可以直接放进第 i 组
if (cnt[now] == 0 || e[now].front() > now || hav[i][0] == 0)
{
hav[i][0]++;
hav[i][hav[i][0]] = now;
if (hav[i][0] == 1)
cntT++;
if (cntT + (n - now) >= t)
dfs(now + 1);
hav[i][0]--;
if (hav[i][0] == 0)
cntT--;
}
else
{
// 需要检查之前是否有冲突
bool flag = true;
for (int j = 1; j <= hav[i][0]; j++)
{
if (f[now][hav[i][j]])
{
flag = false;
break;
}
}
if (flag)
{
hav[i][0]++;
hav[i][hav[i][0]] = now;
if (hav[i][0] == 1)
cntT++;
if (cntT + (n - now) >= t)
dfs(now + 1);
hav[i][0]--;
if (hav[i][0] == 0)
cntT--;
}
}
// 避免重复计算
if (hav[i][0] == 0)
break;
}
}
signed main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
cin >> n >> t >> m;
for (int i = 1; i <= m; i++)
{
cin >> ai >> bi;
f[ai][bi] = f[bi][ai] = true;
e[ai].push_back(bi);
e[bi].push_back(ai);
cnt[ai]++;
cnt[bi]++;
}
for (int i = 1; i <= n; i++)
sort(e[i].begin(), e[i].end());
ans = 0;
cntT = 0;
dfs(1);
cout << ans << "\n";
return 0;
}
用字符串形式给定一个数的二进制表示：， 为 或 。
求：
表示与非逻辑，满足下面的规则：
数据范围：
简单 DP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1000000;
int n, sum;
string s;
int f[MAXN + 5][2]; // 以i结尾的后缀有几个结果为0，几个与非结果为1
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
cin >> s;
f[0][0] = (s[0] == '0');
f[0][1] = (s[0] == '1');
sum = f[0][1];
for (int i = 1; i < s.size(); i++)
{
if (s[i] == '0')
{
f[i][0] = 1 + 0;
f[i][1] = 0 + f[i - 1][0] + f[i - 1][1];
}
else
{
f[i][0] = 0 + f[i - 1][1];
f[i][1] = 1 + f[i - 1][0];
}
sum += f[i][1];
}
cout << sum << "\n";
return 0;
}
/*
0 0 = 1
0 1 = 1
1 0 = 1
1 1 = 0
*/