$Acwing\ University$

4347

zzz_90

Misaka_9982
zhihaoFu

MIisaka

zdkk

Nan97
hunzia

Pipipapi
Fantasyli
kaaaaa

Thu_yc
acWing_lbwnb

3小时前

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 12;

int f[N][10];

void init(){
for(int i = 0; i <= 9; i ++)
if(i != 4)
f[1][i] = 1;
for(int i = 2; i < N; i ++)
for(int j = 0; j <= 9; j ++){
if(j == 4) continue;
for(int k = 0; k <= 9; k ++){
if(k == 4 || j == 6 && k == 2) continue;
f[i][j] += f[i - 1][k];
}
}
}

int dp(int n){
vector<int> nums;
if(!n) return 1;

while(n) nums.push_back(n % 10), n /= 10;

int res = 0;
int last = 0;
for(int i = nums.size() - 1; i >= 0; i --){
int x= nums[i];
for(int j = 0; j < x; j ++){
if(j == 4 || last == 6 && j == 2) continue;
res += f[i + 1][j];
}
if(x == 4 || last == 6 && x == 2) break;
last = x;
if(!i) res ++;
}

return res;
}
int main(){
init();
int l, r;
while(cin >> l >> r, l || r)
cout << dp(r) - dp(l - 1) << endl;

return 0;
}


4小时前

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 11, M = 110;

int P;
// i位数 最高位为j   mod n 为k 的数的个数
int f[N][10][M];

int mod(int x, int y)
{
return (x % y + y) % y;
}

void init()
{
memset(f, 0, sizeof f);

for (int i = 0; i <= 9; i ++ ) f[1][i][i % P] ++ ;

for (int i = 2; i < N; i ++ )
for (int j = 0; j <= 9; j ++ )
for (int k = 0; k < P; k ++ )
for (int x = 0; x <= 9; x ++ )
f[i][j][k] += f[i - 1][x][mod(k - j, P)];
}

int dp(int n)
{
if (!n) return 1;

vector<int> nums;
while (n) nums.push_back(n % 10), n /= 10;

int res = 0;
int last = 0;
for (int i = nums.size() - 1; i >= 0; i -- )
{
int x = nums[i];
for (int j = 0; j < x; j ++ )
res += f[i + 1][j][mod(-last, P)];

last += x;

if (!i && last % P == 0) res ++ ;
}

return res;
}

int main()
{
int l, r;
while (cin >> l >> r >> P)
{
init();

cout << dp(r) - dp(l - 1) << endl;
}

return 0;
}



6小时前
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 11;

int f[N][10];

void init()
{
for (int i = 0; i <= 9; i ++ ) f[1][i] = 1;

for (int i = 2; i < N; i ++ )
for (int j = 0; j <= 9; j ++ )
for (int k = 0; k <= 9; k ++ )
if (abs(j - k) >= 2)
f[i][j] += f[i - 1][k];
}

int dp(int n)
{
if (!n) return 0;

vector<int> nums;
while (n) nums.push_back(n % 10), n /= 10;

int res = 0;
int last = -2;
for (int i = nums.size() - 1; i >= 0; i -- )
{
int x = nums[i];
//暂不处理第一位是0的情况
for (int j = i == nums.size() - 1; j < x; j ++ )
if (abs(j - last) >= 2)
res += f[i + 1][j];

if (abs(x - last) >= 2) last = x;
else break;

if (!i) res ++ ;
}

// 在这里特殊处理有前导零的数, 即第一位是0的情况
for (int i = 1; i < nums.size(); i ++ )
for (int j = 1; j <= 9; j ++ )
res += f[i][j];

return res;
}

int main()
{
/*因为本题中特殊规定了，windy数不能包含前导零。如果把位数较低的数看成是包含前导零，那么首位就不能是1了，但windy数的首位可以是1。*/
init();

int l, r;
cin >> l >> r;
cout << dp(r) - dp(l - 1) << endl;

return 0;
}


7小时前

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;

const int N = 15;

int f[N][N];

void init(){
for(int i = 0; i <= 9; i ++) f[1][i] = 1;

for(int i = 2; i <= N; i ++)
for(int j = 0; j <= 9; j ++)
for(int k = j; k <= 9; k ++)
f[i][j] += f[i - 1][k];
}

int dp(int n){
vector<int> nums;
if(!n) return 1;
while(n) nums.push_back(n % 10), n /= 10;

int res = 0;
//记录右分支 即上一个数
int last = 0;
for(int i = nums.size() - 1; i >= 0; i --){
int x = nums[i];
//左分支架
for(int j = last; j < x; j ++)
res += f[i + 1][j];

//该右分支大于上一个数, 提前break
if(x < last) break;
last = x;

//若走到了最后一个数没被break, 则加上
if(!i) res ++;
}

return res;
}

int main(){
init();
int l, r;
while(cin >> l >> r) cout << dp(r) - dp(l - 1) << endl;
return 0;
}


### 对枚举第i个数的情况

#### 2.x == 1

• 第i位放0，那么后面的数位上可以放k-last个1，res += f[i][k-last];
• 第i位放1，那么后面数位上的情况不能用组合数计算，因为要保证答案中的数字比原数字要小

#### 3.x > 1

• 第i位放0，那么后面的数位上可以放k-last个1，res += f[i][k-last];
• 第i位放1，那么后面的数位上可以放k-last-1个1，res += f[i][k-last-1];
• 此时计算完了该位取0，1的情况后，需要break，因为每一位不能取除0和1以外的数
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

using namespace std;

const int N = 35;

int K, B;
int f[N][N];

//预处理组合数
void init(){
for(int i = 0; i < N; i ++)
for(int j = 0; j <= i; j ++)
if(!j) f[i][j] = 1;
else f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
}

int dp(int n){
if(!n) return 0;

vector<int> nums;
//转换为B进制
while(n) nums.push_back(n % B), n /= B;

int res = 0;
int last = 0;
for(int i = nums.size() - 1; i >= 0; i --){
int x = nums[i];
//如果x不为0
if(x){
//先加上该位取0的情况，后面i位随便选k-last个1
res += f[i][K - last];
if(x > 1){
//加上该位取1的情况, 后面i位随便选k-last-1个1
if(K - last - 1 >= 0) res += f[i][K - last - 1];
//该位不能取其他数了, 不用继续枚举了, break
break;
}
else{
//该位必须为1, 后面不能随便选, last ++
last ++;
if(last > K) break;
}
}
//最右边的分支
if(!i && last == K) res ++;
}

return res;
}
int main(){
init();

int l, r;
cin >> l >> r >> K >> B;

cout << dp(r) - dp(l - 1) << endl;

return 0;
}


• 该节点由父节点处放置的守卫看护
• 该节点由子节点处放置的守护看护
• 该节点由在该节点放置的守卫看护

### 状态表示

$f[i,0]$：在点 i 不摆放警卫，且被父结点看到的所有摆放方案的最小花费

$f[i,1]$：在点 i 不摆放警卫，且被子结点看到的所有摆放方案的最小花费

$f[i,2]$：在点 i 摆放警卫的所有方案的最小花费

### 状态转移

$f[i,0]=∑min(f[j,1],f[j,2])$
$f[i,2]=∑min(f[j,0],f[j,1],f[j,2])$
$f[i,1]=min(f[k,2]+∑_{j≠k}min(f[j,1],f[j,2]))$

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1510;

int n;
int h[N], w[N], e[N], ne[N], idx;
int f[N][3];
bool st[N];

{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
f[u][2] = w[u];

int sum = 0;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
dfs(j);
f[u][0] += min(f[j][1], f[j][2]);
f[u][2] += min(min(f[j][0], f[j][1]), f[j][2]);
sum += min(f[j][1], f[j][2]);
}

f[u][1] = 1e9;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
f[u][1] = min(f[u][1], f[u][0] -  min(f[j][1], f[j][2]) + f[j][2]);
//f[u][1] = min(f[u][1], sum - min(f[j][1], f[j][2]) + f[j][2]);
}
}

int main()
{
cin >> n;

memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ )
{
int id, cost, cnt;
cin >> id >> cost >> cnt;
w[id] = cost;
while (cnt -- )
{
int ver;
cin >> ver;
st[ver] = true;
}
}

int root = 1;
while (st[root]) root ++ ;

dfs(root);

cout << min(f[root][1], f[root][2]) << endl;

return 0;
}


### 思路

• 没有上司的舞会：每条边上最多选择一个点，求最大权值

• 战略游戏：每条边上最少选择一条点，求最小权值

### 状态表示

• f[u][0]：所有以u为根的子树中选择，并且不选u这个点的方案
• f[u][1]：所有以u为根的子树中选择，并且选u这个点的方案
• 属性：Min

### 状态计算

($s_i$代表$u$的子节点们)

• $f[u][0] = \sum f[s_i, 1]$
• $f[u][1] = \sum min(f[s_i, 0], f[s_i, 1])$
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1510;

int e[N], ne[N], h[N], idx;
int f[N][2];
bool st[N];
int n;

e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u){
f[u][0] = 0, f[u][1] = 1;

for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
dfs(j);
f[u][0] += f[j][1];
f[u][1] += min(f[j][0], f[j][1]);
}

}

int main(){
while(scanf("%d", &n) == 1){
memset(h, -1, sizeof h);
memset(st, 0, sizeof st);
idx = 0;

int cnt, id;
for(int i = 0; i < n; i ++){
scanf("%d:(%d)", &id, &cnt);
while(cnt --){
int ver;
scanf("%d", &ver);
st[ver] = true;
}
}
int root = 0;
while(st[root]) root ++;
dfs(root);
printf("%d\n", min(f[root][0], f[root][1]));
}

return 0;
}


### 状态表示

• f[u][j]:表示所有以u为树根的子树中选，选j条边的最大价

### 状态计算

f[u][j] = max(f[u][j], f[u][j - 1 - k] + f[son][k]+ w[i])

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, M = N * 2;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int f[N][N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u, int father)
{
for (int i = h[u]; ~i; i = ne[i])
{
if (e[i] == father) continue;
dfs(e[i], u);
for (int j = m; j; j -- )
for (int k = 0; k + 1 <= j; k ++ )
f[u][j] = max(f[u][j], f[u][j - k - 1] + f[e[i]][k] + w[i]);
}
}

int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
}

dfs(1, -1);

printf("%d\n", f[1][m]);

return 0;
}



### 步骤

• 把每个数的约数之和用筛法筛出来,复杂度是$O(nlogn)$, 试除法是$O(n \sqrt{n})$
• 若某个数的约数之和小于本身, 则可以连一条边
• 再次和第一题树的最长路径一样, res = max(res, d1 + d2)
#include<iostream>
#include<cstring>

using namespace std;

const int N = 100010;

int h[N], e[N], ne[N], idx;
int n;
int sum[N];
int res;

e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int dfs(int u){
int d1 = 0, d2 = 0;
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
int d = dfs(j) + 1;
if(d > d1) d2 = d1, d1 = d;
else if(d > d2) d2 = d;
}

res = max(res, d1 + d2);

return d1;
}

int main(){
memset(h, -1, sizeof h);

cin >> n;

for(int i = 1; i <= n; i ++)
for(int j = 2; j <= n / i; j ++){
sum[i * j] += i;
}

for(int i = 2; i <= n; i ++)
if(sum[i] < i)
dfs(1);

cout << res << endl;
}


### 思路

1. 当前点向下求最长 与上题一样
2. 当前点向上求最长：
分为两种： 向上的向上
$\quad$ $\quad$$\quad$ $\quad$ 向上的向下： 此处又有两种情况：(1)它的向下最长过当前点 (2)它的向下最长不过当前点

#### 下面放三张图理解向上求最长

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010, M = N * 2, INF = 0x3f3f3f3f;

int n;
int h[N], e[M], w[M], ne[M], idx;
//该点向下走的最大值，该点向下走的次大值
//该点向下走的最大值所经过的儿子结点, 该点向上走的最大值
int d1[N], d2[N], p1[N], up[N];
//是否是叶子结点
bool is_leaf[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

//通过儿子结点更新父亲
//和上题一样, 求该点向下走的最大值和次大值
int dfs_d(int u, int father)
{
d1[u] = d2[u] = -INF;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (j == father) continue;
int d = dfs_d(j, u) + w[i];
if (d >= d1[u])
{
d2[u] = d1[u], d1[u] = d;
p1[u] = j;
}
else if (d > d2[u]) d2[u] = d;
}

if (d1[u] == -INF)
{
d1[u] = d2[u] = 0;
is_leaf[u] = true;
}

return d1[u];
}

//注意dfs顺序：通过父节点更新儿子
//求该点向上走的最大值, 分两种情况 1.p1[u] == j 2.p1[u] != j 代码中取max一步操作即可
void dfs_u(int u, int father)
{
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (j == father) continue;

if (p1[u] == j) up[j] = max(up[u], d2[u]) + w[i];
else up[j] = max(up[u], d1[u]) + w[i];

dfs_u(j, u);
}
}

int main()
{
cin >> n;
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i ++ )
{
int a, b, c;
cin >> a >> b >> c;
}

dfs_d(1, -1);
dfs_u(1, -1);

int res = d1[1];
for (int i = 2; i <= n; i ++ )
if (is_leaf[i]) res = min(res, up[i]);
else res = min(res, max(d1[i], up[i]));

printf("%d\n", res);

return 0;
}