P7287 「EZEC-5」魔法
Creative.
考虑到有两个量。发现乘法操作最多只会应用
#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;
#define int long long
int rd() {
int f = 1, val = 0; char ch = getchar();
while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
return f * val;
}
void file() {
freopen("in.in", "r", stdin);
//freopen("out.out", "w+", stdout);
}
const int N = 1e5 + 5;
int a[N], b[N], f[N], n, aa, bb, s;
int judge(int x, int d) {
for(int i = 1; i <= n; i++) b[i] = a[i];
for(int i = 1; i <= n; i++) b[i] += x, b[i] *= (1LL << d);
// for(int i = 1; i <= n; i++) cout << b[i] << " ";
// cout << endl;
ms(f);
for(int i = 1; i <= n; i++) f[i] = max(b[i], f[i - 1] + b[i]);
// for(int i = 1; i <= n; i++) cout << f[i] << " ";
// cout << endl;
return *max_element(f + 1, f + n + 1) >= s;
}
void solve() {
n = rd(), aa = rd(), bb = rd(), s = rd();
for(int i = 1; i <= n; i++) {
a[i] = rd();
}
int finalAns = 0x7f7f7f7f7f7f7f7f;
for(int i = 0; i <= 31; i++) {
int l = 0, r = 0x7f7f7f7f, ans = 0;
while(l <= r) {
int mid = (l + r) >> 1;
if(judge(mid, i)) ans = mid, r = mid - 1;
else l = mid + 1;
}
finalAns = min(finalAns, aa * ans + bb * i);
}
cout << finalAns << endl;
}
signed main() {
#ifdef LOCAL
file();
#endif
int T = 1;
while(T--) solve();
return 0;
}P6612 [POI2012]LIC-Bidding
博弈论 DP。
注意到
同时我们注意到
设
瞎转移即可。
值得注意的是 交互题一个测试点可能会多次调用。。。能预处理就预处理。
#include <bits/stdc++.h>
using namespace std;
#define d(x) cerr << #x << " => " << x << endl
int f[30010][17][12], s = 0;
int p2[20] = {1}, p3[15] = {1};
extern "C" int _opt(int n, int x, int y) {
for(int i = 1; i <= 19; i++) p2[i] = p2[i - 1] * 2;
for(int i = 1; i <= 14; i++) p3[i] = p3[i - 1] * 3;
if(s == 0) {
for(int i = 3e4; ~i; --i) {
for(int a = 15; ~a; --a) {
for(int b = 10; ~b; --b) {
if(i + p2[a] * p3[b] >= n) f[i][a][b] = 0;
else {
if(!f[i][a + 1][b]) f[i][a][b] = 2;
if(!f[i][a][b + 1]) f[i][a][b] = 3;
if(!f[i + p2[a] * p3[b]][0][0]) f[i][a][b] = 1;
}
}
}
}
s = 1;
}
int t2 = 0, t3 = 0;
while(x % 2 == 0) ++t2, x /= 2;
while(x % 3 == 0) ++t3, x /= 3;
return f[y][t2][t3];
}P1280 尼克的任务
屑dp。
#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;
int rd() {
int f = 1, val = 0; char ch = getchar();
while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
return f * val;
}
void file() {
freopen("in.in", "r", stdin);
//freopen("out.out", "w+", stdout);
}
const int N = 1e4 + 6;
struct Tasks {
int p, t;
bool operator<(const Tasks& a) const {
return p < a.p;
}
} tasks[N];
int f[N];
signed main() {
#ifdef LOCAL
file();
#endif
int n = rd(), k = rd();
for(int i = 1; i <= k; i++) {
tasks[i].p = rd(), tasks[i].t = rd();
}
sort(tasks + 1, tasks + k + 1);
for(int i = n; i; i--) {
if(tasks[k].p != i) {
f[i] = f[i + 1] + 1;
continue;
}
while(tasks[k].p == i) {
f[i] = max(f[i], f[i + tasks[k].t]);
--k;
}
}
cout << f[1] << endl;
return 0;
}P1463 [POI2002][HAOI2007]反素数
枚举质因子爆搜。剪枝：较大的质因子出现次数一定不会更大。
#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
#define int long long
using namespace std;
int rd() {
int f = 1, val = 0; char ch = getchar();
while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
return f * val;
}
void file() {
freopen("in.in", "r", stdin);
//freopen("out.out", "w+", stdout);
}
const int Primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int n, ans, ans_num;
void solve(int u, int lst, int num, int dn) {
if(u > n) return ;
if(num > 9) return ;
if(dn > ans) ans = dn, ans_num = u;
else if(dn == ans && u < ans_num) ans_num = u;
int ulayer = 1;
for(int i = 1; i <= lst; i++) {
ulayer *= Primes[num];
if(u * ulayer > n) break;
solve(u * ulayer, i, num + 1, dn * (i + 1));
}
}
signed main() {
#ifdef LOCAL
file();
#endif
n = rd();
solve(1, 9999, 0, 1);
cout << ans_num << endl;
return 0;
}P3846 [TJOI2007] 可爱的质数/【模板】BSGS
BSGS。据说方法是根号分治，好高级的名字。
#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
#define int long long
using namespace std;
int rd() {
int f = 1, val = 0; char ch = getchar();
while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
return f * val;
}
void file() {
freopen("in.in", "r", stdin);
//freopen("out.out", "w+", stdout);
}
int p, b, n;
unordered_map<int, int> maps;
signed main() {
#ifdef LOCAL
file();
#endif
p = rd(), b = rd(), n = rd() % p;
int sz = sqrt(p) + 1;
int ulayer = n;
for(int i = 0; i < sz; i++) {
maps[ulayer] = i;
ulayer = ulayer * b % p;
}
int bsz = 1;
for(int i = 1; i <= sz; i++) bsz = bsz * b % p;
int v = 1;
for(int i = 1; i <= sz; i++) {
v = v * bsz % p;
if(maps.count(v)) {
cout << i * sz - maps[v] << endl;
return 0;
}
}
puts("no solution");
return 0;
}
此处评论已关闭