TYUT

1619

qujunyi
weak_like_old_time
1900-

rainchen
whlbest
zx_explorer
ylqhe001

TheGiao
2079512280
icebreaker
0x5A48
cxposition
NBxiang
PDX

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

using namespace std;

const int N = 35;

int f[N][10];
/*

*/
void init()
{
for (int i = 0; i <= 9; i ++ )
if (i != 4)
f[1][i] = 1;

for (int i = 1; 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)
{
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 ++ )
{
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;
}



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

using namespace std;

const int N = 15, M = 110;

int l, r, P;
int f[N][10][M];//填了i位数字, 最高位是j, 所有位数和mod(sum, P)的余数为k!!

int mod(int x, int y)
{
return (x % y + y) % y; //c++中mod会得到负数!!
}

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 u)
{
if (!u) return 1;

int res = 0;
int last = 0;
vector<int> nums;
while (u) nums.push_back(u % 10), u /= 10;

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;//这里统计的是每位数之和的mod, 所以last记录的是前面的所有位数的和!!!

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

return res;
}

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

return 0;
}


#include <iostream>
#include <vector>

using namespace std;

const int N = 11;

int f[N][N];
/*

*/
void init()
{
for (int i = 0; i <= 9; i ++ ) f[i][1] = 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[j][i] += f[k][i - 1];
}

int dp(int u)
{
if (u == 0) return 0;

vector<int> nums;
int last = -2;
int res = 0;

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

for (int i = nums.size() - 1; i >= 0; i -- )
{
int x = nums[i];

//用有前导0的去算没有前导0的!!!
for (int j = i == nums.size() - 1; j < x; j ++ )
{
if (abs(j - last) >= 2)
res += f[j][i + 1];
}

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

if (!i) res ++;
}

//用有前导0的去算没有前导0的!!!
for (int j = 1; j <= nums.size() - 1; j ++ )
for (int k = 1; k <= 9; k ++ )
res += f[k][j];

return res;
}

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

return 0;
}


#include <iostream>
#include <vector>

using namespace std;

const int N = 15;

int f[N][N];//以i开头的, 有j位数字的非递减数个数!!

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

//这样一个个数可以由长度由小到大推出来!! 很快呀!!
for (int i = 2; i <= N; i ++ )
for (int j = 0; j <= 9; j ++ )
for (int k = j; k <= 9; k ++ )
f[j][i] += f[k][i - 1];
}

//这里求的是0 - u的个数!!!
int dp(int u)
{
if (!u) return 1;//如果是0的话确实0本身就满足要求, 如果不特判的话下面的vector中就没有数字!! 返回结果就是0!!!

vector<int> nums;
int res = 0;
int last = 0;

while (u) nums.push_back(u % 10), u /= 10;//倒除法!

for (int i = nums.size() - 1; i >= 0; i -- )
{
//选last~num[i] - 1
for (int j = last; j <= nums[i] - 1; j ++ )
res += f[j][i + 1];//开头比这个数开头小的情况一定满足条件 !!

//可以的话选num[i]!!  相当于子问题划分了!!这里思维魔鬼了!!认真想!!!
if (nums[i] >= last)
last = nums[i];
else break;

//如果没有break, 证明这个数本身满足要求!!然后加一下完事了!!
if (!i) res ++;
}

return res;
}

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


#include <iostream>
#include <vector>

using namespace std;

const int N = 35;

int l, r, 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];
}

//这里求的是0 - u中的满足1为K, 其它全为0的  数的个数
//这里是在转化进制之后做的计算!!!
int dp(int u)
{
if (!u) return 0;
vector<int> nums;
while (u) nums.push_back(u % B), u /= B;//倒除法求N进制数, 别还给老师了!

int res = 0, last = 0;
for (int i = nums.size() - 1; i >= 0; i -- )
{
int x = nums[i];
if (x)//如果>1的话证明可以有左边
{
res += f[i][K - last];//这一位取0时候的个数
if (x > 1)
{
//这一位取一时的个数
if (K - last - 1 >= 0) res += f[i][K - last - 1];
break;//右边没有, 因为右边是填x的情况, 但是题目只要0/1所以直接不计算这个子树了!!
}
else
{
last ++;
if (last > K) break;//一定是">K"再去break, 因为下面还要去特判下最后情况!!
}
}
//如果填到最后一个位置&&这个位置以及之前已经填了K个1, 证明合法的!!!
if (!i && K == last) res ++;//特判下最右下的是不是合法的!!
}
return res;
}

int main()
{
cin >> l >> r >> K >> B;
init();

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

return 0;
}


#include <iostream>
#include <cstring>

using namespace std;

const int N = 1510;

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

这样能够很好的将所以情况搞出来!!!
*/
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

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

f[u][1] = 0x3f3f3f3f;
for (int i = h[u]; ~i; i = ne[i])
{
int son = e[i];
//递推方程自己认真思考下!!!
f[u][1] = min(f[u][1], f[son][2] + f[u][0] - min(f[son][1], f[son][2]));
}
}

int main()
{
cin >> n;

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

while (cnt -- )
{
cin >> x;
st[x] = true;
}
}

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

dfs(root);

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

return 0;
}


#include <iostream>
#include <cstring>

using namespace std;

const int N = 1510;

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

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

void dfs(int u)
{
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 (cin >> n)
{
memset(st, 0 , sizeof st);
memset(f, 0, sizeof f);
memset(h, -1, sizeof h);
idx = 0;//注意这个恢复原装很容易漏下的!!!记住了!!!
string str;
int root = 1;
for (int i = 0; i < n; i ++ )
{
cin >> str;
int l = str.find('('), r = str.find(')');
int mao = str.find(':');

int a = stoi(str.substr(0, mao));
int count = stoi(str.substr(l + 1, r - l - 1));

for (int j = 0; j < count; j ++ )
{
int x;
cin >> x;
st[x] = true;
}
}

for (int i = 0; i < n; i ++ )
if (!st[i])
{
root = i;
break;
}

dfs(root);
cout << min(f[root][0], f[root][1]) << endl;
}
return 0;
}


#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

int n, m;
int h[N], e[N], ne[N], idx;
int v[N], w[N];
int f[N][N];
/*

*/
void dfs(int u)
{
for (int i = h[u]; ~i; i = ne[i])//一共有几个子节点就有几个组!!
{
dfs(e[i]);//将子节点的数据计算出来!!
for (int j = m - v[u]; j >= 0; j -- )//枚举这个组中怎么选比较好!!!
for (int k = 1; k <= j; k ++ )//这里的DP不包含根节点的值!!
f[u][j] = max(f[u][j], f[e[i]][k] + f[u][j - k]);//这里省略了一维, 省略了从前i个子树中选择!!所以体积从大到小枚举!!!
}

//把根节点加上!!
for (int i = m; i >= v[u]; i -- ) f[u][i] = f[u][i - v[u]] + w[u];
for (int i = 0; i < v[u]; i ++ ) f[u][i] = 0;//放不下根节点就是0!!
}

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

int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);

int root;
for (int i = 1; i <= n; i ++ )
{
int c;
cin >> v[i] >> w[i] >> c;
if (c == -1)
{
root = i;
continue;
}
}

dfs(root);

cout << f[root][m] << endl;

return 0;
}


#include <iostream>
#include <cmath>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 18, M = 1 << N;
const double eps = 1e-8;

int T;
int n, m;
PDD q[N];//存每个点
int f[M];//每个状态用的抛物线最少个数
int p[N][N];//两个点的抛物线可以穿过哪些点

int cmp(double x, double y)//浮点数判断大小
{
if (fabs(x - y) < eps) return 0;
else if (x < y) return -1;
return 1;
}
/*

状压是小更大!
*/

int main()
{
int T;
cin >> T;
while (T -- )
{
cin >> n >> m;
for (int i = 0; i < n; i ++ ) cin >> q[i].x >> q[i].y;

memset(p, 0, sizeof p);//多组测试数据, 注意了!
for (int i = 0; i < n; i ++ )
{
p[i][i] = 1 << i;//题中保证没有重复的点, 所以两点同为本身只能穿过自己!!!
for (int j = 0; j < n; j ++ )
{
double x1 = q[i].x, y1 = q[i].y;
double x2 = q[j].x, y2 = q[j].y;
if (!cmp(x1, x2)) continue;//不符合抛物线要求, 穿过个数为0
double a = (y1 / x1 - y2 / x2) / (x1 - x2);
double b = y1 / x1 - a * x1;

if (cmp(a, 0) >= 0) continue;//>=0就不能作为抛物线!!
int state = 0;
//预处理所以穿过的抛物线
for (int k = 0; k < n; k ++ )
{
double x = q[k].x, y = q[k].y;
if (!cmp(a * x * x + b * x, y)) state += 1 << k;
}
p[i][j] = state;//穿过的点编号用状态压缩成一个数
}
}

memset(f, 0x3f, sizeof f);
f[0] = 0;//没有穿过一个点, 所以需要的抛物线为0
for (int i = 0; i + 1 < 1 << n; i ++ )//向后更新, 所以从0开始
{
int x = 0;
for (int j = 0; j < n; j ++ )
if ((i >> j & 1) == 0)//挑一个没有被穿过的抛物线给它穿过
{
x = j;
break;//因为一个点最后一定属于一个抛物线, 先后没关系!
}

//可以被转移的状态跟新计算一下!!
for (int j = 0; j < n; j ++ )
f[i | p[x][j]] = min(f[i | p[x][j]], f[i] + 1);
}

cout << f[(1 << n) - 1] << endl;
}

return 0;
}


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

using namespace std;

typedef long long LL;

const int N = 55, M = 35, INF = 1e9;

int n;
int w[N];
LL f[N][N][M];

{
static LL c[M];
memset(c, 0, sizeof c);
for (int i = 0, t = 0; i < M; i ++ )
{
t += a[i] + b[i];
c[i] = t % 10;
t /= 10;
}
memcpy(a, c, sizeof c);
}

void mul(LL a[], LL b)
{
static LL c[M];
memset(c, 0, sizeof c);
LL t = 0;
for (int i = 0; i < M; i ++ )
{
t += a[i] * b;
c[i] = t % 10;
t /= 10;
}
memcpy(a, c, sizeof c);
}

int cmp(LL a[], LL b[])
{
for (int i = M - 1; i >= 0; i -- )
if (a[i] > b[i]) return 1;
else if (a[i] < b[i]) return -1;
return 0;
}

void print(LL a[])
{
int k = M - 1;
while (k && !a[k]) k -- ;
while (k >= 0) cout << a[k -- ];
cout << endl;
}

int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> w[i];

LL temp[M];
for (int len = 3; len <= n; len ++ )
for (int l = 1; l + len - 1 <= n; l ++ )
{
int r = l + len - 1;
f[l][r][M - 1] = 1;
for (int k = l + 1; k < r; k ++ )
{
memset(temp, 0, sizeof temp);
temp[0] = w[l];
mul(temp, w[k]);
mul(temp, w[r]);