A 憧憬
分析
直接暴力 O(n2) 做
代码实现
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T& x)
{
x = 0; int f = 1; char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0', ch = getchar();}
x *= f;
}
template <typename T>
void print(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}
template <typename T>
void print(T x, char ch)
{
print(x), putchar(ch);
}
typedef double db;
typedef long long ll;
const int M = (int)1e5;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
int n;
vector<pair<int, int>> v;
bool pall(int a, int b, int c)
{
pair<int, int> ad = make_pair(v[a].first + v[b].first, v[a].second + v[b].second);
return ad.first * v[c].second == ad.second * v[c].first;
}
void work()
{
read(n);
v.push_back(make_pair(-1, -1));
for(int i = 1, a, b, c, d; i <= n + 1; ++i)
{
read(a), read(b), read(c), read(d);
v.push_back(make_pair(c - a, d - b));
}
for(int i = 1; i <= n; ++i)
{
for(int j = i + 1; j <= n; ++j)
{
if(pall(i, j, n + 1))
{
printf("YES\n");
return;
}
}
}
printf("NO\n");
}
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T; read(T);
// for(int ca = 1; ca <= T; ++ca)
// {
// work();
// }
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
B 欢欣
分析
语法题QAQ
代码实现
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T& x)
{
x = 0; int f = 1; char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0', ch = getchar();}
x *= f;
}
template <typename T>
void print(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}
template <typename T>
void print(T x, char ch)
{
print(x), putchar(ch);
}
typedef double db;
typedef long long ll;
const int M = (int)1e5;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
void work()
{
string s; cin >> s;
cout << s.find("QAQ") + 1 << "\n";
}
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T; read(T);
// for(int ca = 1; ca <= T; ++ca)
// {
// work();
// }
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
D 绝望
分析
因为一个非 1 数 x 乘以另一个非 1 的数字 y 之后，乘积 xy 一定不是质数.
所以势能线段树即可.
代码实现
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T& x)
{
x = 0; int f = 1; char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0', ch = getchar();}
x *= f;
}
template <typename T>
void print(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}
template <typename T>
void print(T x, char ch)
{
print(x), putchar(ch);
}
typedef double db;
typedef long long ll;
const int M = (int)2e5;
const int N = (int)5e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
bool is_prime[N + 5];
int prime[N + 5], cnt;
int v[N + 5];
void init()
{
memset(is_prime, 1, sizeof(is_prime));
is_prime[0] = is_prime[1] = 0;
for(int i = 2; i <= N; ++i)
{
if(is_prime[i])
{
prime[++cnt] = i;
v[i] = i;
}
for(int j = 1; j <= cnt && i * prime[j] <= N; ++j)
{
is_prime[i * prime[j]] = 0;
v[i * prime[j]] = prime[j];
if(i % prime[j] == 0)
{
break;
}
}
}
}
struct segT
{
int one[M * 4 + 5];
int s[M * 4 + 5], val[M * 4 + 5];
inline int lc(int k) {return k<<1;}
inline int rc(int k) {return k<<1|1;}
inline void push_up(int k) {s[k] = s[lc(k)] + s[rc(k)], one[k] = one[lc(k)]|one[rc(k)];}
void build(int k, int l, int r)
{
if(l == r)
{
read(val[k]);
one[k] = (val[k] == 1);
s[k] = is_prime[val[k]];
return;
}
int mid = (l + r) >> 1;
build(lc(k), l, mid);
build(rc(k), mid + 1, r);
push_up(k);
}
void update(int k, int l, int r, int a, int b, int c)
{
if(one[k] == 0 && s[k] == 0) return;
if(l == r)
{
if(l == 1) return;
if(one[k] == 1 && c == 1 && is_prime[l])
{
one[k] = 0, s[k] = 1;
}
else
one[k] = s[k] = 0;
//printf("k=%d l=%d r=%d a=%d b=%d c=%d s=%d\n", k, l, r, a, b, c, s[k]);
return;
}
int mid = (l + r) >> 1;
if(a <= mid) update(lc(k), l, mid, a, b, c);
if(mid < b) update(rc(k), mid + 1, r, a, b, c);
push_up(k);
//printf("k=%d l=%d r=%d s=%d\n", k, l, r, s[k]);
}
int query(int k, int l, int r, int a, int b)
{
if(l >= a && r <= b) return s[k];
int mid = (l + r) >> 1, s = 0;
if(a <= mid) s += query(lc(k), l, mid, a, b);
if(mid < b) s += query(rc(k), mid + 1, r, a, b);
return s;
}
} tr;
void work()
{
init();
int n, m; read(n), read(m);
tr.build(1, 1, n);
for(int i = 1, op, l, r, x; i <= m; ++i)
{
read(op);
if(op == 1)
{
read(l), read(r), read(x);
if(x) tr.update(1, 1, n, l, r, x);
print(tr.query(1, 1, n, l, r), '\n');
}
else if(op == 2)
{
read(l), read(r);
print(tr.query(1, 1, n, l, r), '\n');
}
}
}
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T; read(T);
// for(int ca = 1; ca <= T; ++ca)
// {
// work();
// }
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
E 迷惘
分析
就模拟呗
代码实现
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T& x)
{
x = 0; int f = 1; char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0', ch = getchar();}
x *= f;
}
template <typename T>
void print(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}
template <typename T>
void print(T x, char ch)
{
print(x), putchar(ch);
}
typedef double db;
typedef long long ll;
const int M = (int)1e5;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
int n;
int cal(int x)
{
if(x == 0) return 0;
vector<int> v;
while(x)
{
v.push_back(x & 1);
x >>= 1;
}
int p = 0; while(v[p] == 0) ++p; int s = 0;
for(int i = p; i < (int)v.size(); ++i) s = s * 2 + v[i];
return s;
}
void work()
{
read(n);
ll s = 0;
for(int i = 1, a; i <= n; ++i)
{
read(a);
s += cal(a);
}
print(s, '\n');
}
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T; read(T);
// for(int ca = 1; ca <= T; ++ca)
// {
// work();
// }
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
G 冷静
分析
预处理3e6内所有数的最小质因子，离线所有询问，树状数组维护答案.
代码实现
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T& x)
{
x = 0; int f = 1; char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0', ch = getchar();}
x *= f;
}
template <typename T>
void print(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}
template <typename T>
void print(T x, char ch)
{
print(x), putchar(ch);
}
typedef double db;
typedef long long ll;
const int M = (int)3e6;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
bool is_prime[M + 5];
int prime[M + 5], cnt;
int v[M + 5];
void init()
{
memset(is_prime, 1, sizeof(is_prime));
is_prime[0] = is_prime[1] = 0;
for(int i = 2; i <= M; ++i)
{
if(is_prime[i])
{
prime[++cnt] = i;
v[i] = i;
}
for(int j = 1; j <= cnt && i * prime[j] <= M; ++j)
{
is_prime[i * prime[j]] = 0;
v[i * prime[j]] = prime[j];
if(i % prime[j] == 0)
{
break;
}
}
}
}
struct TA
{
int n; ll tree[M + 5];
void init(int _n) {n = _n; for(int i = 0; i <= n; ++i) tree[i] = 0;}
inline int lowbit(int n) {return n&-n;}
void add(int a, ll b) {for(int i = a; i <= n; i += lowbit(i)) tree[i] += b;}
ll ask(int r) {ll s = 0; for(int i = r; i; i -= lowbit(i)) s += tree[i]; return s;}
ll ask(int l, int r) {return ask(r) - ask(l - 1);}
} tr;
struct node
{
int n, k, id;
bool operator<(const node& b) const
{
return n < b.n;
}
} s[M + 5];
int ans[M + 5];
void work()
{
init();
int q; read(q);
for(int i = 1; i <= q; ++i)
{
read(s[i].n), read(s[i].k), s[i].id = i;
}
sort(s + 1, s + q + 1);
tr.init(M);
for(int i = 1, p = 1; i <= q; ++i)
{
while(p + 1 <= s[i].n) tr.add(v[++p], 1);
ans[s[i].id] = tr.ask(M) - tr.ask(s[i].k - 1);
}
for(int i = 1; i <= q; ++i) print(ans[i], '\n');
}
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T; read(T);
// for(int ca = 1; ca <= T; ++ca)
// {
// work();
// }
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
H 终别
分析
因为魔法只能使用一次，所以枚举魔法的释放位置，这样原序列就被分成了一个前缀和一个后缀，O(n) 预处理出前缀和后缀的花费即可.
代码实现
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T& x)
{
x = 0; int f = 1; char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0', ch = getchar();}
x *= f;
}
template <typename T>
void print(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}
template <typename T>
void print(T x, char ch)
{
print(x), putchar(ch);
}
typedef double db;
typedef long long ll;
const int M = (int)1e6;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
int n, a[M + 5], b[M + 5];
ll pre[M + 5], suf[M + 5];
void work()
{
read(n); for(int i = 1; i <= n; ++i) read(a[i]);
memcpy(b, a, sizeof(a));
pre[0] = 0;
for(int i = 1; i <= n; ++i)
{
if(b[i] >= 0) pre[i] = pre[i - 1] + b[i], b[i + 2] -= b[i], b[i + 1] -= b[i], b[i] -= b[i];
else pre[i] = pre[i - 1];
}
memcpy(b, a, sizeof(a));
suf[n + 1] = 0;
for(int i = n; i >= 1; --i)
{
if(b[i] >= 0) suf[i] = suf[i + 1] + b[i], b[i - 2] -= b[i], b[i - 1] -= b[i], b[i] -= b[i];
else suf[i] = suf[i + 1];
}
ll mi = (ll)1e18;
for(int i = 2; i <= n; ++i)
{
mi = min(mi, pre[i - 2] + suf[i + 1]);
}
print(mi, '\n');
}
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T; read(T);
// for(int ca = 1; ca <= T; ++ca)
// {
// work();
// }
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
京公网安备 11010502036488号