第二场题解

1006

思路:

某位由1变为0，相当于在原数上减去了这一位，找回即可。

我用C++提交时似乎总会超时，很困扰。

代码:

#include<iostream>
using namespace std;
typedef unsigned long long ull;
const int N = 3000005;
int T, i;
ull A, B, C, f[N];
inline ull read()
{
int n, i, x;
ull ret = 0;
cin >> n;
for (i = 1; i <= n; i++)
{
cin >> x;;
if (x)ret += f[i];
}
return ret;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
for (f[1] = 1, f[2] = 2, i = 3; i < N; i++)f[i] = f[i - 1] + f[i - 2];
cin >> T;
while (T--)
{
A = read();
B = read();
C = read();
A *= B;
for (i = 1; C + f[i] != A; i++);

cout << i << ‘\n‘;
}

return 0;
}

1010

DFS搜索，注意跳过为0的情况。

通过代码:

#include<iostream>
#include<vector>
using namespace std;
//一种类型只能穿一个
typedef long long ll;
vector<int> ith_num, nex;
vector<vector<vector<int> > > v;//第i种装备的第j件的第k种属性
int n, type;
ll res;

void DFS(int x, int a, int b, int c, int d)
{
if (x > type)
{
if ((ll)a * b * c * d > res) res = (ll)a * b * c * d;
return;
}
if (!ith_num[x])
{//剪枝？
DFS(nex[x], a, b, c, d);
return;
}
for (int i = 1; i <= ith_num[x]; ++i) DFS(x + 1, a + v[x][i][1], b + v[x][i][2], c + v[x][i][3], d + v[x][i][4]);
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
res = 0;
int T, x;
cin >> T;
while (T--)
{
cin >> n >> type;
v.resize(type + 1);
for (int i = 1; i <= type; ++i)
{
v[i].resize(n + 1);
for (int j = 1; j <= n; ++j)
{
v[i][j].resize(4 + 1);
}
}
ith_num.resize(type + 1);
nex.resize(type + 1);
while (n--)
{
cin >> x;
ith_num[x]++;
for (int k = 1; k <= 4; ++k)
{
cin >> v[x][ith_num[x]][k];
}
}
for (int i = type; i > 0; --i)
{//跳过数量为0的类型
nex[i] = x;
if (ith_num[i]) x = i;
}
DFS(1, 100, 100, 100, 100);//从第1种装备开始，初始伤害皆为100
cout << res;
}
return 0;
}

第二场题解

原文：https://www.cnblogs.com/masteryee/p/13388775.html