正在更新中~
202212
202209
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f3f3f3f3f;
int n, m;
int a[N], b[N], c[N];
int sum;
void solve()
{
cin >> n >> m;
c[0] = 1;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
c[i] = c[i - 1] * a[i];
}
for (int i = 1; i <= n; i++)
{
int x = m % c[i];
b[i] = (x - sum) / c[i - 1];
sum += c[i - 1] * b[i];
}
for (int i = 1; i <= n; i++)
cout << b[i] << ' ';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// int T;
// cin >> T;
// while (T--)
solve();
return 0;
}
搜索 + 剪枝
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f3f3f3f3f;
int n, m, x;
int a[N], s[N];
int res = INF;
void dfs(int u, int sum)
{
if (sum >= x)
res = min(res, sum);
if (u >= n)
return;
if (sum + a[n] > res)
return;
if (sum + s[n] - s[u] < x)
return;
for (int i = u + 1; i <= n; i++)
if (sum + a[i] <= res)
dfs(i, sum + a[i]);
return;
}
bool cmp(int a, int b)
{
return a > b;
}
void solve()
{
cin >> n >> x;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
s[i] = s[i - 1] + a[i];
}
sort(a + 1, a + 1 + n, cmp);
dfs(0, 0);
cout << res;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// int T;
// cin >> T;
// while (T--)
solve();
return 0;
}
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1010, M = 2e5 + 10, INF = 0x3f3f3f3f3f3f3f3f;
int n;
set<int> day[N];
struct node
{
int d, u, r;
};
vector<node> opt[N];
set<int> ans[N];
void solve()
{
cin >> n;
for (int i = 0; i < n; i++)
{
int r, m;
cin >> r >> m;
while (r--)
{
int p;
cin >> p;
for (int j = i; j <= i + 6; j++)
day[j].insert(p);
}
while (m--)
{
int d, u, r;
cin >> d >> u >> r;
if (d < i - 6 || d < 0)
continue;
opt[i].push_back({d, u, r});
}
}
for (int i = 0; i < n; i++)
for (auto t : opt[i])
{
int d = t.d, u = t.u, r = t.r;
for (int j = d; j <= d + 6; j++)
{
if (!day[j].count(r))
break;
if (j >= i)
ans[j].insert(u);
}
}
for (int i = 0; i < n; i++)
{
cout << i << ' ';
for (auto it = ans[i].begin(); it != ans[i].end(); it ++)
cout << *it << ' ';
cout << endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// int T;
// cin >> T;
// while (T--)
solve();
return 0;
}