A. Equivalent Prefixes
很水的单调队列
首先说是处理最低位置一样 那么肯定队首存的下标一样
其次 1 ~ p 位置区间内每部分最小对应下标一样 那样的话 队列每次进入一个元素就可以想到
如果每部分最小下标对应一样 那样队列队尾弹出数量应该是一致的 只需要保证 队列大小一致就完成了
第一个可以去掉 因为弹出一致了
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn = 1e5 + 5;
deque<int> s1;
deque<int> s2;
int a[maxn], b[maxn];
int n;
int main(){
while(scanf("%d", &n) != -1){
int f = 0;
while(!s1.empty()) s1.pop_back();
while(!s2.empty()) s2.pop_back();
for(int i = 1; i <= n; i ++) scanf("%d", a + i);
for(int i = 1; i <= n; i ++) scanf("%d", b + i);
for(int i = 1; i <= n; i ++) {
while(!s1.empty() && a[s1.back()] > a[i]) s1.pop_back();
s1.push_back(i);
while(!s2.empty() && b[s2.back()] > b[i]) s2.pop_back();
s2.push_back(i);
if(s1.size() != s2.size()){
cout << i - 1 << endl;
f = 1;
break;
}
//if(s1.front() != s2.front()){
// cout << i - 1 << endl;
// f = 1;
// break;
//} 这个可以去掉 因为 弹出都一致了
}
if(!f) cout << n << endl;
}
return 0;
}
B. Integration
数学专业就是不一样啊 啥是复变啊 那个是啥定理啊 他给我张纸 我看的一脸懵逼啊 orz
总而言之 1 / [（b * b + x * x）* (c * c + x* x) ]
就是 1 / [ (b * b - c * c ) * (c * c + x * x) ] + 1 / [ (c * c - b * b) * (x * x + b * b)] ;
#include<iostream>
#include<cstdio>
#include <queue>
#define int long long
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 5;
const int mod = 1e9 + 7;
int n;
int a[maxn], b[maxn];
ll pow_mod(ll a, ll b) {
ll ans = 1; a %= mod;
while (b) {
if (b & 1) {
ans = ans * a % mod;
b--;
}
b >>= 1;
a = a * a % mod;
}
return ans;
}
signed main(){
while(cin >> n) {
for(int i = 1; i <= n; i ++) cin >> a[i], b[i] = a[i] * a[i] % mod;
int ans = 0;
for(int i = 1; i <= n; i ++) {
int tmp = 2 * a[i] % mod;
int tp = a[i] * a[i] % mod;
for(int j = 1; j <= n; j ++) {
if(j == i) continue;
tmp = (tmp * (b[j] - tp)) % mod;
}
ans = (ans + pow_mod(tmp, mod - 2)) % mod;
}
cout << (ans+mod)%mod << endl;
}
return 0;
}
E. ABBA
贪心的认为 前n个A都是AB的A 后面的都是 BA的 A 补充的 同理B也是
dp[i][j] 代表方案数 i 是 A数量 j 是 B 数量
那么 我们考虑 i_A - nAB_A 数量 应该是 mBA_A 的数量
当出现 i_A - nAB_A < mBA_A 时肯定是A不够 我们选择在之前随便一个位置加上 BA的A 这里就会是 += dp[i][j]的方案数量
B 同理
#include<iostream>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
const int maxn = 2e3 + 5;
int dp[maxn][maxn];
int n, m;
signed main(){
while(cin >> n >> m) {
for(int i = 0; i <= n + m; i ++) {
for(int j = 0; j <= m + n; j ++) {
dp[i][j] = 0;
}
}
dp[0][0] = 1;
for(int i = 0; i <= n + m; i ++) {
for(int j = 0; j <= n + m; j ++) {
if( i - n < j) {
dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % mod;
}
if( j - m < i) {
dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % mod;
}
}
}
cout << dp[n + m][n + m] << endl;
}
return 0;
}
F. Random Point in Triangle
这题 不用想 肯定猜 1 到 18 的系数 和面积的关系
然后 有一个比较扯的方法
就是三角形 每个边取4等分点 平行相连 我们用这个方法算期望 猜系数
估了下 在 10 到15 之间 试一试 就wa 1发过了…orz
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e3+10;
ll dp[maxn][maxn];
int main(){
ll a,b,c,d,e,f,g,S;
while(cin>>a>>b>>c>>d>>e>>f){
S=11*abs((c-a)*(f-b)-(d-b)*(e-a));
cout<<S<<endl;
}
return 0;
}
H. XOR
线性基 处理出64 x 64 表达这些数据的 矩阵
子集大小处理成 我们选取数据的组合方案和
先求出 这n数据 的 线性基 当然他的线性基不唯一
我们先求出一个 那么 这个线性基 和外部的组合方案 就是pow(2, N_R + 1) * (n - r)
其次 我们考虑 多个线性基的情况 他们的方案数 同样也是pow(2, N_R + 1) 组合
为了 避免 我们重复对 剩下的 N_R 进行重复计算 我们只需要 预先处理出N_R基 然后 每次从R基拿一个 暴力搞一遍 看看 这个 vec[i] 是不是可以替代掉 就加上这一次的方案
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
int n;
bool vis[maxn];
vector<ll> vec;
ll R[70], N_R[70], tmp[70];
ll a[maxn];
ll q_mod(ll a, ll b) {
ll res = 1;
while(b) {
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
bool ins(ll x, ll base[]){
for(int i = 63; i >= 0; i--){
if(x & (1ll << i)) {
if(base[i]) x ^= base[i];
else{
base[i] = x;
return 1;
}
}
}
return 0;
}
int main(){
while(scanf("%d",&n) != EOF) {
int r = 0;
vec.clear();
for(int i = 0; i <= 63; i ++) R[i] = 0;
for(int i = 1; i <= n; i ++){
scanf("%lld", &a[i]);
vis[i] = 0;
if(ins(a[i], R)) vis[i] = 1, r++, vec.push_back(a[i]);
}
if(r == n) {
puts("0");
continue;
}else{
ll ans = q_mod(2, n - r - 1) * (n - r) % mod;
for(int j = 0; j <= 63; j ++) N_R[j] = 0;
for(int i = 1; i <= n; i ++) {
if(vis[i]) continue;
ins(a[i], N_R);
}
for(int i = 0; i < vec.size(); i ++ ) {
int cnt = 0;
for(int j = 0; j <= 63; j ++) tmp[j] = 0;
for(int j = 0; j <vec.size(); j ++ ) {
if(i == j) continue;
ins(vec[j], tmp);
}
for(int j = 0; j <= 63; j ++)
if(N_R[j]) ins(N_R[j], tmp);
if(!ins(vec[i], tmp)) ans = (ans + q_mod(2, n - r - 1) ) % mod ;
}
printf("%lld\n", ans);
}
}
return 0;
}
I. Points Division
A, B 两个位置 有不同权重
不存在a∈A和b∈B，使得xa>=xb且ya<=yb;
也就是 对于所有 A 都在 B 左边上方
dp[i] = max dp[1~i] + b[i];
用线段树处理的是 离散化后 Y轴 每个点对之后位置的贡献度
每次放入一个点 它对之后的点的影响 如果对于 之后某些点低于它 会贡献a[i] 所以我们向y点之前 更新a[i] 的值
如果对于 之后某些点高于它 会贡献b[i] 所以我们向y点之后 更新b[i] 的值
我们每放 一个点到线上 查询 这个点之前可以影响它 的 A 集合 可以贡献最大的值 加上当前这个点的B[i] 是否会变的更大 进行更新
这里不在需要dp数组 因为线段树最后维护就是我们的最大值了
ps 我们很关键的是要补 0 如果 B集合什么都没有的话
我们没有把A的值更新进去 第一个点 1 - 1 会丢掉
补个0X3F点 防止 y + 1 越界
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int n;
struct node {
int x, y, a, b;
bool operator < (const node &a) const {
return x < a.x || (x == a.x && y > a.y);
}
} a[maxn];
int ly[maxn];
ll ma[maxn << 2], lazy[maxn << 2];
void push_up(int rt) {
ma[rt] = max(ma[rt << 1], ma[rt << 1 | 1]);
}
void push_down(int rt) {
ma[rt << 1 | 1] += lazy[rt] ;
ma[rt << 1] += lazy[rt];
lazy[rt << 1 | 1] += lazy[rt];
lazy[rt << 1] += lazy[rt];
lazy[rt] = 0;
}
void build(int l, int r, int rt){
ma[rt] = lazy[rt] = 0;
if(l == r) return ;
int mid = l + r >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
}
void update1(int L, int l, int r, int rt, ll c) {
if(l == r) {
ma[rt] = max(c, ma[rt]);
return ;
}
if(lazy[rt]) push_down(rt);
int mid = l + r >> 1;
if(L <= mid) update1(L, l, mid, rt << 1, c);
else update1(L, mid + 1, r, rt << 1 | 1, c);
push_up(rt);
}
void update2(int L, int R, int l, int r, int rt, ll c) {
if(L <= l && R >= r) {
ma[rt] += c;
lazy[rt] += c;
return ;
}
if(lazy[rt]) push_down(rt);
int mid = l + r >> 1;
if(L <= mid) update2(L, R, l, mid, rt << 1, c);
if(R > mid) update2(L, R, mid + 1, r, rt << 1 | 1, c);
push_up(rt);
}
ll query(int L, int R, int l, int r, int rt) {
if(L <= l && R >= r) return ma[rt];
if(lazy[rt]) push_down(rt);
int mid = l + r >> 1;
ll res = 0;
if(L <= mid) res = max(query(L, R, l, mid, rt << 1), res);
if(R > mid) res = max(query(L, R, mid + 1, r, rt << 1 | 1), res);
return res;
}
signed main() {
while(scanf("%lld", &n) != EOF){
for(int i = 1; i <= n; i ++)
scanf("%lld %lld %lld %lld", &a[i].x, &a[i].y, &a[i].a, &a[i].b), ly[i] = a[i].y;
ly[n + 1] = 0, ly[n + 2] = 0x3f3f3f3f;
sort(ly + 1, ly + 2 + n);
int cnt = unique(ly + 1, ly + 3 + n) - ly - 1;
for(int i = 1; i <= n; i ++ )
a[i].y = lower_bound(ly + 1, ly + 1 + cnt, a[i].y) - ly;
sort(a + 1, a + 1 + n);
build(1, cnt, 1);
for(int i = 1; i <= n; i ++) {
ll tmp = query(1, a[i].y, 1, cnt, 1);
update1(a[i].y, 1, cnt, 1, tmp + a[i].b);
update2(1, a[i].y - 1, 1, cnt, 1, a[i].a);
update2(a[i].y + 1, cnt, 1, cnt, 1, a[i].b);
}
printf("%lld\n", ma[1]);
}
return 0;
}
J. Fraction Comparision
python 嚎啊
while True:
try:
x,y,a,b=map(int,input().split())
if x * b > y * a:
print(">")
elif x * b < y * a:
print("<")
else:
print("=")
except:
break
c 版本
官方题解 菜啊当时
京公网安备 11010502036488号