题目链接 题目大意: 给出正整数n,求整数1到整数n之中,有多少整数是由单一的字符组成,比如说1 , 77, 777, 44 和 999999 就是符合要求的整数。 整数1到18中,只有 1, 2, 3, 4, 5, 6, 7, 8, 9 和 11符合要求。
输入: 第一行整数𝑡,表示有t个样例 (1≤𝑡≤1e4) 每个样例一行,𝑛 (1≤𝑛≤1e9)
输出: 每个样例一行,输出1到n之间有多少个数字符合要求。
input 6 18 1 9 100500 33 1000000000
output 10 1 9 45 12 81
题目解析: 纯暴力枚举,则是从1、2、3开始算,把每个数字拆解成字符串数组,然后判断数字是否相同的; 但是由于n=1e9,数据量较大,容易在字符串转化的过程中超时。
换一种思路,只枚举符合要求的部分,比如说先考虑1位数、再考虑2位数、然后是3位数,知道数字比n大。
char a[N];
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
cin >> a;
int n = strlen(a);
int ans = (n - 1) * 9 + (a[0] - '0');
int ok = 1;
for (int i = 1; i < n; ++i) {
if (a[i] < a[0]) {
ok = 0;
break;
}
else if (a[i] > a[0]) {
ok = 1;
break;
}
}
if (!ok) {
--ans;
}
cout << ans << endl;
}
return 0;
}
题目链接 题目大意: 给出n个整数 𝑎1,𝑎2,…,𝑎𝑛; 每次可以选择一个偶数c,将数组中所有等于c的数字除以2; 比如说数组[6,8,12,6,3,12] 选择数字6,将6除以2之后得到[3,8,12,3,3,12] 问现在最少需要操作多少次,才能将所有的数字转化成奇数;
输入: 第一行整数𝑡,表示有t个样例 (1≤𝑡≤1e4) 每个样例有2行: 第一行整数𝑛 (1≤𝑛≤2⋅1e5) 第二行𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e9)
输出: 每个样例一行,输出最小的操作次数。
input 4 6 40 6 40 3 20 1 1 1024 4 2 4 8 16 3 3 1 7 output 4 10 4 0
题目解析: 每次可以选择一个数字x,将数组所有的x=x/2;
通过贪心的思想可以知道,每次会选择最大的数字开始贪心; 并且数字出现个数的多少没有影响,那么可以采用这样的策略: 1、把数组中的数字排序,从大到小开始遍历; 2、每次拿出最大的数字,如果是奇数则直接通过;如果是偶数,则需要++ans,进入第3步; 3、判断原来数组里面是否有这个数字;如果有对应数字,则直接通过;如果没有出现过x/2,则把x/2放回数组; 循环处理,直到结束。
int a[N];
map<int, int> h;
vector<int> s;
priority_queue<int> q;
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
h.clear();
while (!s.empty()) {
s.pop_back();
}
for (int i = 0; i < n; ++i) {
int k;
scanf("%d", &k);
++h[k];
}
for (map<int, int>::iterator iter = h.begin(); iter != h.end(); ++iter) {
q.push(iter->first);
}
int ans = 0;
while (!q.empty()) {
int top = q.top();
q.pop();
if (top % 2 == 0) {
if (!h[top/2]) {
q.push(top / 2);
}
++ans;
}
}
cout << ans << endl;
}
return 0;
}
题目链接 题目大意: 给出一个字符串s,现在不希望字符串里面出现one和two这两个单词,比如说"oneee", "ontwow", "twone" and "oneonetwo"都是不好的字符串。 现在可以从字符串中选择若干个位置,去掉这些位置上的字符。 问最少去掉多少个字符。
输入: 第一行𝑡,表示t个样例 (1≤𝑡≤1e4) 每个样例一行,字符串s,长度不超过 1.5⋅1e5
输出: 每个样例2行 第一行,整数k表示需要去掉k个位置 第二行,k个整数,表示k个需要去掉字符的位置。
input 4 onetwone testme oneoneone twotwo
output 2 6 3 0
3 4 1 7 2 1 4
题目解析: 对于某个字符结尾,可能有normal、o、on、t、tw这几种情况,分别表示为状态0、1、2、3、4; 那么dp[i][j]表示,第i个字符,以状态j结尾时,需要去掉的最少字符数量;
对于第i个字符,都可以有dp[i][j] = dp[i-1][j] + 1; 同时,根据字符内容,有特定的转移方案,这部分转移方程较多,可以直接思考代码。
思考🤔: 这个题目也可以使用贪心的做法,假如只有one这个单词,那么直接去掉n是最优解:因为去掉头尾会有oone和onee的bad case存在,去掉n会直接破坏one这个单词; 但是由于有两个字符存在,会导致出现twone的情况导致去掉n仍然存在two的情况;针对这种特殊情况,是需要去掉中间的o; 这种贪心的做法相对动态规划比较容易实现。
string a;
int dp[N][5];
pair<int, int> last[N][5];
void compare(int i, int j, int x, int y) {
if (dp[i][j] > dp[x][y]) {
dp[i][j] = dp[x][y];
last[i][j] = make_pair(x, y);
}
}
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
cin >> a;
int n = (int)a.length();
for (int j = 0; j < 5; ++j) {
dp[0][j] = n;
last[0][j] = make_pair(0, 0);
}
if (a[0] == 'o') {
dp[0][1] = 0;
}
else if (a[0] == 't') {
dp[0][3] = 0;
}
else {
dp[0][0] = 0;
}
for (int i = 1; i < n; ++i) {
// 不取a[i]
for (int j = 0; j < 5; ++j) {
dp[i][j] = dp[i - 1][j] + 1;
last[i][j] = make_pair(i - 1, j);
}
// 取a[i], normal、o、on、t、tw这几种情况,分别表示为状态0、1、2、3、4;
if (a[i] == 'o') {
compare(i, 1, i-1, 0);
compare(i, 1, i-1, 1);
compare(i, 1, i-1, 2);
compare(i, 1, i-1, 3);
}
else if (a[i] == 'n') {
compare(i, 2, i - 1, 1);
compare(i, 0, i-1, 0);
compare(i, 0, i-1, 2);
compare(i, 0, i-1, 3);
compare(i, 0, i-1, 4);
}
else if (a[i] == 't') {
compare(i, 3, i-1, 0);
compare(i, 3, i-1, 1);
compare(i, 3, i-1, 2);
compare(i, 3, i-1, 3);
compare(i, 3, i-1, 4);
}
else if (a[i] == 'w') {
compare(i, 4, i-1, 3);
compare(i, 0, i-1, 0);
compare(i, 0, i-1, 1);
compare(i, 0, i-1, 2);
compare(i, 0, i-1, 4);
}
else if (a[i] == 'e') {
compare(i, 0, i-1, 0);
compare(i, 0, i-1, 1);
compare(i, 0, i-1, 3);
compare(i, 0, i-1, 4);
}
else {
compare(i, 0, i-1, 0);
compare(i, 0, i-1, 1);
compare(i, 0, i-1, 2);
compare(i, 0, i-1, 3);
compare(i, 0, i-1, 4);
}
}
long index = min_element(dp[n - 1], dp[n - 1] + 5) - dp[n - 1];
cout << dp[n-1][index] << endl;
long x = n - 1, y = index;
while (x != 0 || y != 0) {
pair<int, int> fp = last[x][y];
if (dp[fp.first][fp.second] < dp[x][y]) {
printf("%d ", x + 1);
}
x = fp.first, y = fp.second;
}
puts("");
}
return 0;
}
题目链接 题目大意: 一个整数是2的x次幂,或者是x的阶乘,那么这个数字是powerful的; 现在给出一个整数n,希望由若干个powerful的整数相加来得到n,要求: 1、没有相同的powerful整数; 2、powerful整数尽可能少;
输入: 第一行样例数𝑡 (1≤𝑡≤100). 接下来每个样例一行𝑛 (1≤𝑛≤1e12).
输出: 能相加得到n的最少powerful整数的数量,如果没有答案则输出-1;
Examples input 4 7 11 240 17179869184 output 2 3 4 1
题目解析: 首先把powerful的整数枚举取出来: 2的x次幂:1、2、4、8、16、32、64、128等; x的阶乘:1、2、6、24、120等; 这两部分数字可以通过hash去重,得到1、2、4、8、16、24、32、64、120、128等; 题目的要求就是从这些数字中选出最少的数字,来组成整数n; n个物品的选择来形成特定大小,这个是典型的动态规划问题,但是如果用背包的解法,会由于状态数过多而超时;
仔细分析题目,2的x次幂这部分数字,其实已经可以足够组成任意数字; 那么题目就变成了,要在阶乘中选择多少个数字来组成n,剩下的部分可以有2的x次幂来组成(并且这部分的最优解就是数字的二进制位数); 阶乘递增比较快,在15!的时候就超过了题目要求,再减去最开始的阶乘1和2,最终可以不超过2^13=8000左右种结果; 枚举这些结果,结合剩下数字的二进制长度,来得到最优解;
class Solution {
static const int N = 10010;
string str;
vector<lld> num;
lld count(lld n) {
lld ret = 0;
while (n) {
ret += n % 2;
n /= 2;
}
return ret;
}
public:
void solve() {
int t;
cin >> t;
lld tmp = 2;
for (int i = 3; i < 15; ++i) {
tmp *= i;
num.push_back(tmp);
}
while (t--) {
lld n;
cin >> n;
lld ans = n;
for (int i = 0; i < (1 << num.size()); ++i) {
lld sum = 0;
lld index = 0;
int tmp = i;
while (tmp) {
if (tmp % 2) {
sum += num[index];
}
tmp /= 2;
++index;
}
if (sum <= n) {
ans = min(ans, count(i) + count(n - sum));
}
}
cout << ans << endl;
}
}
}
ac;
题目链接 题目大意: 给出一个有n个节点的树,现在可以把1、2、3·····n的整数赋值到每一个节点上; 一个节点可以被称为good节点,如果它满足:相邻点的数字之和等于自己节点的数字; 现在需要给每个节点赋值,要求整棵树有尽可能多的good节点,如果有多种方案则输出数字和最小的方案;
输入: 第一行𝑛 (2≤𝑛≤2e5) 接下来有n-1行,每行两个整数 𝑢 and 𝑣 表示相邻的节点(1≤𝑢,𝑣≤𝑛)
输出: 先输出最多的good节点数和总的数字和; 接下来n个数字, 𝑤1,𝑤2,…,𝑤𝑛分别表示n个节点的数字 (1≤𝑤𝑖≤1e9)
Examples input 2 1 2 output 2 2 1 1 input 9 3 4 7 6 2 1 8 3 5 6 1 8 8 6 9 6 output 6 11 1 1 1 1 1 1 1 3 1
题目解析: 由题目的要求,首先要求是尽可能多的good节点,那么叶子节点肯定都会标位1; 其次叶子的相邻节点也一定是1(为了满足good节点的要求),如果有节点和两个叶子相邻节点连接,那么这个节点也有机会成为good节点,如下: 五个连乘一条直线节点:1-1-2-1-1
由此我们知道,每个节点有两种状态isGood=1和0,信息有maxNode子树最大节点数,minWeight子树最小数字和; 而且我们按照题目可以得到两个状态转移的条件,对于节点u: 1、假如u是good节点,那么和u相邻的节点一定不是good节点; 2、假如u不是good节点,那么和u相邻的节点可以是good节点,也可以不是good节点;
由于上面的条件2,我们知道这个题目无法使用贪心的思想,因为贪心需要决策路径是唯一的,但是由于非good节点节点是可以相邻的,导致出现了分支; 针对这个情况,我们可以用动态规划来解决。 首先设定好状态,pair<int, int> dp[n][2]:n个节点,每个节点有2个状态,每个节点需要关注两个信息; dp[i][0]表示第i个节点不为good的子树最优解,dp[i][1]为第i个节点为good的子树最优解,first是good数,second是子树和; 再由上面的状态转移条件,可以得到转移方程。
接着从节点1开始dfs,对于每一个节点u和字节点v,计算得到dp[u][0]和dp[u][1]; 同时需要记录动态规划的决策过程,因为最终答案还要回溯决策,从而得到结果。
思考🤔: 这个题目的输出略微麻烦,但是记录清楚决策分支,再用dfs回溯还是可以解决的。
class Solution {
static const int N = 200010;
vector<int> g[N];
int vis[N];
vector<int> last[N];
int ans[N];
pair<int, int> dp[N][2]; // dp[i][0]表示第i个节点不为good的子树最优解,dp[i][1]为第i个节点为good的子树最优解,first是good数,second是子树和
void add_pair(pair<int, int> &x, pair<int, int> &y) {
x.first += y.first;
x.second += y.second;
}
bool cmp_pair(pair<int, int> &x, pair<int, int> &y) {
return x.first > y.first || (x.first == y.first && x.second < y.second);
}
void dfs(int u) {
vis[u] = 1;
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];
if (!vis[v]) {
dfs(v);
}
}
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];
if (cmp_pair(dp[v][0], dp[v][1])) {
add_pair(dp[u][0], dp[v][0]);
last[u].push_back(0);
}
else {
add_pair(dp[u][0], dp[v][1]);
last[u].push_back(1);
}
add_pair(dp[u][1], dp[v][0]);
}
dp[u][1].first += 1; // 自己作为good节点
dp[u][1].second += g[u].size(); // good节点代价,自重
dp[u][0].second += 1; // 自重
// cout << u << " " << dp[u][0].first << " " << dp[u][0].second << " " << dp[u][1].first << " " << dp[u][1].second << endl;
}
void dfs_ans(int u, bool isGood) {
vis[u] = 1;
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];
if (!vis[v]) {
dfs_ans(v, isGood ? 0 : last[u][i]);
}
}
if (isGood) {
ans[u] = g[u].size();
}
else {
ans[u] = 1;
}
}
public:
void solve() {
int n;
cin >> n;
for (int i = 1; i < n; ++i) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
if (n == 2) {
cout << "2 2\n1 1" << endl;
}
else {
dfs(1);
memset(vis, 0, sizeof(vis));
if (cmp_pair(dp[1][0], dp[1][1])) {
cout << dp[1][0].first << " " << dp[1][0].second << endl;
dfs_ans(1, 0);
}
else {
cout << dp[1][1].first << " " << dp[1][1].second << endl;
dfs_ans(1, 1);
}
for (int i = 1; i <= n; ++i) {
cout << ans[i] << " ";
}
cout << endl;
}
}
}
ac;
这次题目都比较有意思,题目4和题目5有点难度,尤其是题目5的输出。题目5的结果输出不难想出办法,就是挺麻烦,不够优雅。