A：牛牛的DRB迷宫I
思路：设dp[i][j]为起点在(i,j)时的方案数
那么dp转移式就显然可以得到：
if(s[i][j] == 'R'){
dp[i][j] = dp[i][j + 1];
}
if(s[i][j] == 'D'){
dp[i][j] = dp[i + 1][j];
}
if(s[i][j] == 'B'){
dp[i][j] = dp[i][j + 1] + dp[i + 1][j];
}考虑到此dp转移式是由后面状态更新，所以用递归写比较简单
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
int n, m;
ll dp[55][55];
char s[55][55];
ll dfs(int i, int j){
if(i <= 0 || i > n || j <= 0 || j > m) return 0;
if(dp[i][j]) return dp[i][j];
if(s[i][j] == 'R'){
dp[i][j] = dfs(i, j + 1) % mod;
}
if(s[i][j] == 'D'){
dp[i][j] = dfs(i + 1, j) % mod;
}
if(s[i][j] == 'B'){
dp[i][j] = (dfs(i, j + 1) + dfs(i + 1, j))% mod;
}
return dp[i][j];
}
void print(){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
printf("%c", s[i][j]);
}
putchar('\n');
}
}
int main(){
while(scanf("%d%d", &n, &m) != EOF){
memset(dp, 0, sizeof(dp));
dp[n][m] = 1;
for(int i = 1; i <= n; i++){
scanf("%s", s[i] + 1);
}
//print();
printf("%lld\n", dfs(1, 1));
}
return 0;
}
B：牛牛的DRB迷宫II
感受：这个题目真得需要多观察，不然感觉不好想
思路：
例子
BDXX
RBDX
XRBD
XXRB
XXXX
这是5 * 4的矩形，'X'代表未知字母，'B','D','R'为题目所给
观察第一行到第四行，起点为（1，1）----目前考虑的路径不经过'X'
到第一行的B（1，1）,方案数为1
到第二行的B（2，2）,方案数为2
到第三行的B（3，3）,方案数为4
到第四行的B（4，4）,方案数为8
...
显然按照这种构造方法，到第i行的B（i，i）,方案数为;
有没有发现，这与二进制非常相符，那我们怎么构造3，5，...呢？
例如我想构造11
11 = 8 + 2 + 1
BDXX
RBDX
XRBD
XXRB
XXXF
'F'表示终点，那么我们可以知道所有到达F（不经过X）的路径一共8条，那我们就要思考怎样构造+2
BDXX
RBDX
XBBD
XDRB
XRXF
我们把(3,2)由'R'改成'B',(4,2)由'X'改成'D',(5,2)由'X'改成'R';
有没有发现新增一系列路径，可以到达(5,2)点，其方案数为2
那我们就可以把（5，3）改成'R'，从而贡献F点，使得方案数变为8 + 2
有没有发现，其实第5行就是加法器（或者认为是二进制）
11 = 1011
整体思路已经说得很清楚了，剩下地大家可以自己思考，毕竟自己思考才能提升自己的能力
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const ll mod = 1e9 + 7;
char s[50][50];
vector<int>pos;
ll k;
int n;
void solve(ll k){
pos.clear();
int cnt = 1;
while(k){
if(k % 2){
pos.push_back(cnt);
}
cnt++;
k /= 2;
}
}
void print(){
int Size = pos.size();
printf("digit = %d\n", Size);
for(int i = 0; i < Size; i++){
printf("%d\n", pos[i]);
}
}
void print1(){
printf("%d %d\n", n, n);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
printf("%c", s[i][j]);
}
putchar('\n');
}
}
int main(){
while(scanf("%lld", &k) != EOF){
k %= mod;
if(k == 0){
printf("2 3\n");
printf("DDD\n");
printf("DDD\n");
continue;
}
solve(k);
int Size = pos.size();
n = pos[Size - 1];
for(int i = 1; i <= n; i++){
s[i][i] = 'B';
if(i != n){
s[i + 1][i] = 'R';
s[i][i + 1] = 'D';
}
s[n + 1][i] = 'B';
}
for(int j = 1; j <= n; j++){
for(int i = j + 2; i <= n; i++){
s[i][j] = 'D';
}
}
for(int j = n; j >= 1; j--){
for(int i = j - 2; i >= 1; i--){
s[i][j] = 'R';
}
}
for(int i = 0; i < Size - 1; i++){
int tmp = pos[i];
s[tmp + 1][tmp] = 'B';
}
printf("%d %d\n", n + 1, n);
for(int i = 1; i <= n + 1; i++){
for(int j = 1; j <= n; j++){
printf("%c", s[i][j]);
}
putchar('\n');
}
}
return 0;
}
C：牛牛的数组越位
思路：就是暴力模拟题，没什么难度。注意数组越界范围
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1005;
ll n, m, p, ma;
int ok;
ll a[maxn][maxn];
void check(ll x, ll y, ll val){
if(x < 0 || x >= n || y < 0 || y >= m) ok = 1;
ll dis = m * x + y;
if(dis < 0 || dis > ma){
ok = 2;
return ;
}
ll res = dis % m;
ll tp = dis / m;
a[tp][res] = val;
}
int main(){
int t;
scanf("%d", &t);
while(t--){
memset(a, 0, sizeof(a));
scanf("%lld%lld%lld", &n, &m, &p);
ma = m * n - 1;
ok = 0;///ok = 1 B = 2 RE
ll x, y, val;
while(p--){
scanf("%lld%lld%lld", &x, &y, &val);
if(ok != 2 )check(x, y, val);
}
if(ok == 2){
printf("Runtime error\n");
}
else{
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
printf("%lld%c", a[i][j], j == m - 1 ? '\n' : ' ');
}
}
if(ok == 1){
printf("Undefined Behaviour\n");
}
else{
printf("Accepted\n");
}
}
}
return 0;
}
D：牛牛与二叉树的数组存储
感受：这场两道暴力模拟题，见到就很难受。
思路：就直接按照题目给出的定义模拟即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
struct Node{
int fa;
int lson, rson;
Node(){
fa = -1;
lson = rson = -1;
}
}ans[maxn];
int a[maxn];
int main(){
int n, Size = 0, root = -1;
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
if(a[i] != -1 && root == -1) root = a[i];
Size = max(Size, a[i]);
}
printf("The size of the tree is %d\n", Size);
printf("Node %d is the root node of the tree\n", root);
for(int i = 1; i <= n; i++){
if(a[i] != -1){
int tp = i;
int fa, lson, rson;
fa = lson = rson = -1;
if(tp * 2 <= n) lson = a[tp * 2];
if(tp * 2 + 1 <= n) rson = a[tp * 2 + 1];
if(tp / 2 > 0) fa = a[tp / 2];
ans[a[i]].fa = fa;
ans[a[i]].lson = lson;
ans[a[i]].rson = rson;
}
}
for(int i = 1; i <= Size; i++){
printf("The father of node %d is %d, the left child is %d, and the right child is %d\n", i, ans[i].fa, ans[i].lson, ans[i].rson);
}
return 0;
}
E：牛牛的随机数
感受：代码量多一点，利用贡献量计算在本题集中极为常见
思路：多观察
例子[1,1] [3,5]
000
001
010
011---3
100
101---5
我们用1 ^ 3 + 1 ^ 4 + 1 ^ 5。
考虑每一位（bit）对答案的恭喜，从右向左观察第一位（1（3） 0（4） 1（5）），1的第一位也是1，那么只有4对答案有贡献。这就让我们得出一个思路，我们只要能快速统计一个区间的数在某一位上有多少个1，多少个0，就可以求出该二进制位对答案的贡献。
#include <bits/stdc++.h>
#define ls o << 1
#define rs o << 1 | 1
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 5;
struct Node{
ll num1;
ll num0;
Node(){
num1 = num0 = 0;
}
};
ll l1, r1, l2, r2;
ll quick_mod(ll a, ll b, ll mod){
ll sum = 1;
while(b){
if(b & 1) sum = sum * a % mod;
a = a * a % mod;
b /= 2;
}
return sum;
}
Node solve(ll x, ll y, ll bit){
Node ans;
ll len = (ll)1 << (bit + 1);///[1, len]
ll t1, t2;
t1 = x / len + 1; t2 = y / len + 1;
x %= len; y %= len;
ll num = (t2 - t1 - 1) < 0 ? 0 : t2 - t1 - 1; num %= mod;
ll dif = len / 2;///[0, dif - 1] 0 [dif, len - 1] 1
if(t1 == t2){
if(x < dif && y < dif){
ans.num0 = y - x + 1;
}
else if(x >= dif && y >= dif){
ans.num1 = y - x + 1;
}
else{
ans.num0 = dif - x;
ans.num1 = y - dif + 1;
}
ans.num0 %= mod;
ans.num1 %= mod;
return ans;
}
ans.num0 = ans.num1 = (len / 2) % mod * num % mod;
//printf("num0 = %lld num1 = %lld\n", ans.num0, ans.num1);
ll num0 = 0, num1 = 0;
if(x >= dif){
num1 = len - x;
num1 %= mod;
}
else{
num0 = dif - x; num0 %= mod;
num1 = dif; num1 %= mod;
}
//printf("add: num0 = %lld num1 = %lld\n", num0, num1);
if(y >= dif){
num1 = num1 + y - dif + 1; num1 %= mod;
num0 = num0 + dif; num0 %= mod;
}
else{
num0 = num0 + y + 1; num0 %= mod;
}
ans.num0 = (ans.num0 + num0) % mod;
ans.num1 = (ans.num1 + num1) % mod;
return ans;
}
void print(Node c, ll i){
printf("***************************\n");
printf("i = %lld\n", i);
printf("num0 = %lld num1 = %lld\n", c.num0, c.num1);
printf("**************************\n");
}
int main(){
int t;
scanf("%d", &t);
while(t--){
scanf("%lld%lld%lld%lld", &l1, &r1, &l2, &r2);
ll ans = 0; ll tmp = quick_mod(((r1 - l1 + 1) % mod * ((r2 - l2 + 1) % mod)) % mod, mod - 2, mod);
//Node tt = solve(8, 12, 0);
//print(tt, 0);
for(ll i = 0; i < 62; i++){
Node a = solve(l1, r1, i);
Node b = solve(l2, r2, i);
//print(a, i);
//print(b, i);
ll cnt = (((a.num1 % mod) * (b.num0 % mod) % mod) + ((a.num0 % mod) * (b.num1 % mod) % mod)) % mod;
ll val = (((ll)1 << i) % mod) % mod;
ans = ans + val * cnt % mod;
ans %= mod;
}
ans = ans * tmp % mod;
printf("%lld\n", ans);
}
return 0;
}
F：牛牛的Link Power I
感受：同样可以用贡献来算
思路：看下面例子分析
1000100101，记a = 10001对答案贡献，也就是4（5- 1），b = 1001对答案的贡献，也就是3（8 - 5）c = 101对答案的贡献，也就是2（10-8）
每两个1之间设一个变量贡献值
考虑所有答案选取1的方式，发现太杂，但是我们可以发现每一次选择不同1，它都是累加a 或 b 或 c。
那我们求答案，就是考虑a被累加多少次，b被累加多少次, c被累加多少次。
比如我们要算b被累加多少次？
b = 1**10011
左边可以取index = 1 或者 index = 5 的 1
右边可以取index = 8 或者 index = 10 的 1
那么b被累加2 * 2 次
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 5;
int n;
char s[maxn];
int main(){
while(scanf("%d", &n) != EOF){
scanf("%s", s + 1);
ll ans = 0;
int num = 0, num_1 = 0;
for(int i = 1; i <= n; i++){
if(s[i] == '1') num++;
}
int pos = -1;
for(int i = 1; i <= n; i++){
if(s[i] == '1'){
if(num_1){
ans = ans + (ll)1 * (i - pos) * (num - num_1) % mod * num_1 % mod;
ans %= mod;
}
num_1++;
pos = i;
}
}
printf("%lld\n", ans);
}
return 0;
}G：牛牛的Link Power II
感受：mod太可怕，已经在这方面犯了不少由于负数%mod导致一直wa的错误
思路：考虑把1改成0对当前答案ans有什么影响，显然这个1会让ans - (1与剩下的1构成的dis和)，把0改成1同理。
那我们就要思考怎样快速算某一个1与剩下的1构成dis和（记作res）？
举例子
1 0 1 1 0 1 1 0 1
我们要把第4个1改成0
res = (4 - 1) + (4 - 3) + (6 - 4) + (7 - 4) + (9 - 4)
= 4 * 2 - (1 + 3) + (6 + 7 + 9) - 4 * 3
有没有观察出规律：1 + 3 其实就是把1的下标累加得到的和（也就是区间和） 4 * 2中的2就是区间1的个数
那我们就可以用线段树维护区间1的下标和以及1的个数，从而得到更新答案的目的
#include <bits/stdc++.h>
#define ls o << 1
#define rs o << 1 | 1
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 5;
struct Node{
ll num_one;
ll sum;
}node[maxn << 2];
ll n, m;
char s[maxn];
void up(ll o){
node[o].num_one = node[ls].num_one + node[rs].num_one;
node[o].sum = (node[ls].sum + node[rs].sum) % mod;
}
void build(ll o, ll l, ll r){
if(l == r){
if(s[l] == '1'){
node[o].num_one = 1;
node[o].sum = l;
}
else{
node[o].num_one = 0;
node[o].sum = 0;
}
return ;
}
ll mid = (l + r) / 2;
build(ls, l, mid);
build(rs, mid + 1, r);
up(o);
}
void update(ll o, ll l, ll r, ll x, ll opt){
if(l == r){
if(opt == 1){
node[o].num_one = 1;
node[o].sum = x;
}
else{
node[o].num_one = 0;
node[o].sum = 0;
}
return ;
}
ll mid = (l + r) / 2;
if(mid >= x) update(ls, l, mid, x, opt);
else update(rs, mid + 1, r, x, opt);
up(o);
}
ll query1(ll o, ll l, ll r, ll x, ll y){
if(l >= x && y >= r){
return node[o].sum;
}
ll ans = 0;
ll mid = (l + r) / 2;
if(mid >= x){
ans += query1(ls, l, mid, x, y);
ans %= mod;
}
if(y > mid){
ans += query1(rs, mid + 1, r, x, y);
ans %= mod;
}
return ans;
}
ll query2(ll o, ll l, ll r, ll x, ll y){
if(l >= x && y >= r){
return node[o].num_one;
}
ll ans = 0;
ll mid = (l + r) / 2;
if(mid >= x){
ans += query2(ls, l, mid, x, y);
ans %= mod;
}
if(y > mid){
ans += query2(rs, mid + 1, r, x, y);
ans %= mod;
}
return ans;
}
void print(ll ans){
printf("ans = %lld\n", ans);
}
int main(){
while(scanf("%lld", &n) != EOF){
scanf("%s", s + 1);
scanf("%lld", &m);
ll ans = 0;
ll num = 0, num_1 = 0;
for(ll i = 1; i <= n; i++){
if(s[i] == '1') num++;
}
ll pos = -1;
for(ll i = 1; i <= n; i++){
if(s[i] == '1'){
if(num_1){
ans = ans + (ll)1 * (i - pos) * (num - num_1) % mod * num_1 % mod;
ans %= mod;
}
num_1++;
pos = i;
}
}
build(1, 1, n);
ll q, r_num;
printf("%lld\n", ans);
while(m--){
scanf("%lld%lld", &q, &pos);
num_1 = query2(1, 1, n, 1, pos);
if(q == 2) num_1--;
r_num = num - num_1;
if(q == 2) r_num--;
ll val = (num_1 * pos - query1(1, 1, n, 1, pos)) + (query1(1, 1, n, pos, n) - r_num * pos);
while(val < 0) val += mod;
val %= mod;
if(q == 1){
ans = (ans + val) % mod;
num++;
}
else{
ans = ans - val;
while(ans < 0) ans += mod;
ans = ans % mod;
num--;
}
update(1, 1, n, pos, q);
printf("%lld\n", ans);
}
}
return 0;
}
H：牛牛的k合因子数
感受：比赛时，看了好久，最后才想起可以直接暴力打表
思路：对于1 - n我们需要把所有数是几合因子数统计出来
例子
考虑K合因子的定义，指一个数的所有因子中，是合数的因子共有k个
很显然知道所有因子个数为（2 + 1） * （1 + 1） * （2 + 1）
那么容斥一下，减去非合数（2 + 1 + 2 + 1），也就是质数的种数 + 1(1是这个数)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 5;
ll flag[maxn];
ll n;
int m;
ll Get(ll n){
ll ans = 1;
ll num_1 = 0;
for(ll i = 2; i * i <= n; i++){
if(n % i == 0){
num_1++;
ll num = 1;
while(n % i == 0){
num++;
n /= i;
}
ans *= num;
}
}
if(n > 1) ans *= 2, num_1++;
return ans - (num_1 + 1);
}
int main(){
while(scanf("%lld%d", &n, &m) != EOF){
memset(flag, 0, sizeof(flag));
for(ll i = 1; i <= n; i++){
ll tmp = Get(i);
flag[tmp]++;
}
int k;
for(int i = 1; i <= m; i++){
scanf("%d", &k);
printf("%lld\n", flag[k]);
}
}
return 0;
}
I：牛牛的汉诺塔
思路：找规律
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
ll dp[65][10];///dp[i][1] = dp[i][4] dp[i][6] = dp[i][3]
int main(){
int n;
scanf("%d", &n);
dp[1][2] = 1;
dp[2][1] = dp[3][1] = 1; dp[2][2] = 1; dp[2][4] = 1;
dp[4][1] = dp[5][1] = 4; dp[3][2] = 3; dp[3][3] = 1; dp[3][4] = 1; dp[3][6] = 1;
for(int i = 6; i <= n + 1; i++){
if(i % 2 == 0){
dp[i][1] = 5 * dp[i - 2][1] - 4 * dp[i - 4][1] - 1;
}
else{
dp[i][1] = dp[i - 1][1];
}
}
for(int i = 3; i <= n + 1; i++){
if(i % 2){
dp[i][6] = 4 * dp[i - 2][6] + i / 2;
}
else{
dp[i][6] = dp[i - 1][6];
}
}
int i = n;
if(n % 2 == 0){
printf("A->B:%lld\n", dp[i][1]);
printf("A->C:%lld\n", dp[i][1] - dp[i][6]);
printf("B->A:%lld\n", dp[i][6]);
printf("B->C:%lld\n", dp[i][1]);
printf("C->A:%lld\n", dp[i][6] * 2);
printf("C->B:%lld\n", dp[i][6]);
printf("SUM:%lld\n", dp[i][1] + dp[i][1] - dp[i][6] + dp[i][6] + dp[i][1] + dp[i][6] * 2 + dp[i][6]);
}
else{
printf("A->B:%lld\n", dp[i][1]);
printf("A->C:%lld\n", dp[i + 1][1]- dp[i + 1][6]);
printf("B->A:%lld\n", dp[i][6]);
printf("B->C:%lld\n", dp[i][1]);
printf("C->A:%lld\n", dp[i][6] - dp[i][1]);
printf("C->B:%lld\n", dp[i][6]);
printf("SUM:%lld\n", dp[i][1] + dp[i + 1][1]- dp[i + 1][6] + dp[i][6] + dp[i][1] + dp[i][6] - dp[i][1] + dp[i][6]);
}
return 0;
}
J：牛牛的宝可梦Go
思路：设dp[i]表示前i个时刻取走第i时刻物品的最大值
显然dp转移式为dp[i] = max(dp[0], dp[1], dp[2], ...,dp[i - 1]) + val(第i时刻)
但是这样更新答案，复杂度是炸了，所以我们需要思考怎样优化
考虑到dp[i] = max(dp[i], dp[j] + val)更行前提是（i - j >= dis[i.pos][j.pos]）；
（i.pos表示i时刻所在位置，j.pos表示j时刻所在位置）---注意这个假设的前提，dp[i]表示前i个时刻取走第i时刻物品的最大值
dis[i.pos][j.pos] < n
所以dp[i] = max(dp[i - 1], dp[i - 2], dp[i - 3], ..., dp[i - n + 1], max(dp[0], dp[1], ..., dp[i - n]))
注意这里所有max里面的dp式，要保证满足i - j >= dis[i.pos][j.pos]
所以max(dp[0], dp[1], ..., dp[i - n])可以用数组维护，把复杂度降至1e7级别
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const ll mod = 1e9 + 7;
const ll inf = 1e18;
struct P{
ll t;
int p;
ll val;
}in[maxn];
ll ans[maxn];
ll dis[205][205];
ll dp[maxn];
int n, m;
bool cmp(P a, P b){
return a.t < b.t;
}
void floyd(){
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
}
int main(){
//while(scanf("%d%d", &n, &m) != EOF){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(i != j)
dis[i][j] = inf;
else
dis[i][j] = 0;
}
}
int u, v, k;
for(int i = 1;i <= m; i++){
scanf("%d%d", &u, &v);
dis[u][v] = 1;
dis[v][u] = 1;
}
floyd();
scanf("%d", &k);
for(int i = 1; i <= k; i++){
scanf("%lld%d%lld", &in[i].t, &in[i].p, &in[i].val);
}
sort(in + 1, in + k + 1, cmp);
for(int i = 1; i <= k; i++) dp[i] = -inf, ans[i] = 0;
dp[0] = 0; ans[0] = 0;
in[0].p = 1; in[0].t = 0;
for(int i = 1; i <= k; i++){
for(int j = i - 1; j >= 0; j--){
ll res = in[i].t - in[j].t;
if(res >= n){
dp[i] = max(dp[i], ans[j] + in[i].val);
break;
}
int u = in[i].p, v = in[j].p;
if(dis[u][v] <= res){
dp[i] = max(dp[i], dp[j] + in[i].val);
}
}
ans[i] = max(dp[i], ans[i - 1]);
}
ll ko = 0;
for(int i = 1; i <= k; i++) ko = max(ko, dp[i]);
printf("%lld\n", ko);
//}
return 0;
}
京公网安备 11010502036488号