A：异或症
题意：给定一个排列，选任意i, j，使得 pi = pi ^ j，最后求前缀异或数组，求这个数组的最大和
思路：发现可以把所有数变成出现过的二进制位的和
void solve(){
ll n;
cin >> n;
map<ll, ll> mp;
for(int i = 1; i <= n; i ++){
ll x;
cin >> x;
for(int i = 0; i <= 40; i ++){
if(x >> i & 1){
mp[1ll << i] = 1;
}
}
}
ll ans = 0;
for(auto [x, y] : mp) ans += x;
ans *= n;
cout << ans << '\n';
}
B：拾取糖果
题意：直角坐标平面上有 n 个糖果，糖果都处于整数点上，求任意一条通过原点的直线最多可以经过几个糖果
思路：对坐标除以 gcd 即可，注意特判一下在坐标轴上和原点的糖果即可
void solve(){
ll n;
cin >> n;
map<PLL, ll> mp;
ll ze = 0;
for(int i = 1; i <= n; i ++){
ll x, y;
cin >> x >> y;
if(x == 0 && y == 0){
ze ++;
continue;
}
else if(x == 0){
mp[{0, 1}] ++;
continue;
}
else if(y == 0){
mp[{1, 0}] ++;
continue;
}
ll gd = __gcd(x, y);
x /= gd;
y /= gd;
mp[{x, y}] ++;
}
ll ans = 0;
for(auto [x, y] : mp) ans = max(ans, y + ze);
cout << ans << '\n';
}
C：图腾
题意：长度为 n 的数轴上有 m 个图腾，每个点的能量为左边最近的图腾的能量 * 右边最近的图腾的能量，q 次操作，插入图腾或者求区间内点的能量值的和
思路：线段树维护即可，倒过来看作每次删除图腾，预处理每个点的左边的图腾和右边的图腾，每次删除图腾就修改 pre + 1 ~ i - 1，i ~ i，i + 1 ~ nxt - 1，这三个区间即可，线段树维护一下区间和
struct Node{
ll sum, siz;
ll add;
};
struct segtree{
ll n;
vector<Node> a;
segtree(ll _n) : n(_n * 4 + 10), a(n + 1) {}
void pushup(ll u){
a[u].sum = a[u * 2].sum + a[u * 2 + 1].sum;
}
void eval(Node & t, ll add){
t.sum = t.sum + add * t.siz;
t.add = t.add + add;
}
void pushdown(ll u){
eval(a[u * 2], a[u].add);
eval(a[u * 2 + 1], a[u].add);
a[u].add = 0;
}
void build(ll u, ll l, ll r, vector<ll> & arr){
if(l == r){
a[u] = {arr[l], 1, 0};
return;
}
ll mid = l + r >> 1ll;
a[u] = {0, r - l + 1, 0};
build(u * 2, l, mid, arr);
build(u * 2 + 1, mid + 1, r, arr);
pushup(u);
}
void modify(ll u, ll l, ll r, ll l1, ll r1, ll add){
if(l1 <= l && r <= r1) eval(a[u], add);
else{
pushdown(u);
ll mid = l + r >> 1ll;
if(l1 <= mid) modify(u * 2, l, mid, l1, r1, add);
if(r1 > mid) modify(u * 2 + 1, mid + 1, r, l1, r1, add);
pushup(u);
}
}
ll query(ll u, ll l, ll r, ll l1, ll r1){
if(l1 <= l && r <= r1) return a[u].sum;
else{
pushdown(u);
ll mid = l + r >> 1ll;
ll res = 0;
if(l1 <= mid) res += query(u * 2, l, mid, l1, r1);
if(r1 > mid) res += query(u * 2 + 1, mid + 1, r, l1, r1);
return res;
}
}
};
ll n, m, q;
struct node{
ll op, l, r;
};
void solve(){
cin >> n >> m >> q;
vector<ll> p(n + 1);
vector<ll> x(m + 1), v(m + 1);
for(int i = 1; i <= m; i ++) cin >> x[i];
for(int i = 1; i <= m; i ++){
cin >> v[i];
p[x[i]] = v[i];
}
vector<node> now(q + 1);
for(int i = 1; i <= q; i ++){
ll op, l, r;
cin >> op >> l >> r;
now[i] = {op, l, r};
if(op == 1){
p[l] = r;
}
}
vector<ll> ans;
vector<ll> pre(n + 1), nxt(n + 1);
vector<ll> he(n + 1);
for(int i = 1, j = 0; i <= n; i ++){
if(j != 0) pre[i] = j;
if(p[i] != 0) j = i;
}
for(int i = n, j = 0; i >= 1; i --){
if(j != 0) nxt[i] = j;
if(p[i] == 0 && pre[i] && nxt[i]) he[i] = p[pre[i]] * p[nxt[i]];
if(p[i] != 0) j = i;
}
segtree seg(n);//初始化线段树大小
seg.build(1, 1, n, he);//建树，s是vector数组
for(int i = q; i >= 1; i --){
auto [op, l, r] = now[i];
if(op == 1){
ll pp = pre[l], qq = nxt[l];
ll p1 = p[pp] * p[qq];
seg.modify(1, 1, n, pp + 1, l - 1, p1 - seg.query(1, 1, n, l - 1, l - 1));
seg.modify(1, 1, n, l + 1, qq - 1, p1 - seg.query(1, 1, n, l + 1, l + 1));
seg.modify(1, 1, n, l, l, p1);
nxt[pp] = qq;
pre[qq] = pp;
}
else{
ll res = seg.query(1, 1, n, l, r);
ans.push_back(res);
}
}
for(int i = ans.size() - 1; i >= 0; i --) cout << ans[i] << '\n';
}
D：能源
题意：n 个庇护所，每个庇护所需要 ai 的能源，有 m 个能提供 bi 能源的电池，求满足所有庇护所需求的同时最小的电池能源之和
思路：排序双指针即可
void solve(){
ll n, m;
cin >> n >> m;
vector<ll> a(n + 1), b(m + 1);
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= m; i ++) cin >> b[i];
sort(a.begin() + 1, a.end());
sort(b.begin() + 1, b.end());
ll ans = 0;
int i = 1, j = 1;
for(i = 1, j = 1; i <= n && j <= m; i ++){
while(j <= m && a[j] < a[i]) j ++;
ans += a[j];
j ++;
}
cout << ans << '\n';
}
E：又双叒叕分糖果
题意：两个糖果包分别有一些重量的糖果，丢掉每个糖果包一半数量的糖果，然后再从两个糖果剩余的糖果中选取糖果组成新的糖果包，新的糖果包中不能有相同重量的糖果，求新的糖果包最多能有几种不同重量的糖果
思路：先分别统计两个糖果包的糖果种类，种类相同的数量全部丢掉，如果丢掉了重复的还不够就从糖果种类中丢掉，求每个糖果包中能选几种糖果，同时记录一下两个糖果包都有的糖果，优先选掉各自独有的糖果种类，然后才从共有的糖果中选取
void solve(){
ll n;
cin >> n;
ll x, y;
cin >> x >> y;
ll sum1 = 0, sum2 = 0;
map<ll, ll> a, b, c1;
for(int i = 1; i <= x; i ++){
ll w, num;
cin >> w >> num;
sum1 += num - 1;
a[w] ++;
}
for(int i = 1; i <= y; i ++){
ll w, num;
cin >> w >> num;
sum2 += num - 1;
b[w] ++;
if(a.count(w)) c1[w] ++;
}
ll ans = 0;
ll cha1 = 0, cha2 = 0;
if(sum1 < n / 2) cha1 = n / 2 - sum1;
if(sum2 < n / 2) cha2 = n / 2 - sum2;
x -= cha1, y -= cha2;
for(auto [c, d] : a){
if(x <= 0) break;
if(!c1.count(c)){
x --;
ans ++;
}
}
for(auto [c, d] : b){
if(y <= 0) break;
if(!c1.count(c)){
y --;
ans ++;
}
}
ll yu = x + y;
ll get = min(yu, (ll)(c1.size()));
ans += get;
cout << ans << '\n';
}
J：再聚端午，祝全体老师、同学、志愿者们，端午安康！
题意：四个点，A-B-C-D-A，求总路程
思路：一个求距离函数，调用即可
double dist(double x1, double y1, double x2, double y2){
double ans = 0;
ans = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
ans = sqrt(ans);
return ans;
}
void solve(){
vector<double> x(5), y(5);
for(int i = 1; i <= 4; i ++){
cin >> x[i] >> y[i];
}
double ans = 0;
ans += dist(x[1], y[1], x[2], y[2]);
ans += dist(x[2], y[2], x[3], y[3]);
ans += dist(x[3], y[3], x[4], y[4]);
ans += dist(x[4], y[4], x[1], y[1]);
cout << fixed << setprecision(15) << ans;
}
K：枝江一梦
题意：给定二维平面，初始在 X 正半轴有 n 点都在 y=0 处。有 m 次操作，每次操作会使得在 x=b 点提高 a×c 然后扩散其周围，但是 c 递减，直到 c=0。问最后正半轴 [1,n] 的 y 轴坐标
思路：先记录一下每个点到左边的最远能到的地方，分别在当前点和左边界标一下，然后分别维护加的数量add_n，减的数量del_n，当前需要加的值add，当前需要减的值del，每次就把后两项分别加上对应的前两项，当到达的点是开始点，也就是初始操作的地方，再维护往后加的数量add_nf，往后减的数量add_nf，当前往后加的值add_f，往后减的值del_f，每次把后两项减去对应的前两项，同时小根堆维护一下每个操作失效的时间即可
void solve(){
ll n, m;
cin >> n >> m;
vector<TLL> v[n + 10];
for(int i = 1; i <= m; i ++){
ll a, b, c;
cin >> a >> b >> c;
ll l = b - c + 1, r = b + c - 1;
l = max(1ll, l), r = min(n, r);
v[l].push_back({a * c, b, 1});
v[b].push_back({a * c, b, 2});
}
ll add = 0, del = 0;
ll add_n = 0, del_n = 0;
ll add_f = 0, del_f = 0;
ll add_nf = 0, del_nf = 0;
priority_queue<PLL, vector<PLL>, greater<PLL>> q;
for(int i = 1; i <= n; i ++){
for(auto [x, y, z] : v[i]){
ll x1 = abs(x);
if(z == 1){
if(x < 0){
del_n ++;
del += x1 - (y - i);
}
else{
add_n ++;
add += x1 - (y - i);
}
}
else{
q.push({i + x1, x});
if(x < 0){
del_n --;
del -= x1;
del_nf ++;
del_f += x1;
}
else{
add_n --;
add -= x1;
add_nf ++;
add_f += x1;
}
}
}
ll res = 0;
res = add - del + add_f - del_f;
add += add_n;
del += del_n;
while(q.size() && q.top().first <= i){
if(q.top().second < 0) del_nf --;
else add_nf --;
q.pop();
}
add_f -= add_nf;
del_f -= del_nf;
cout << res << ' ';
}
}
Pending......
标签：第二十届,int,ll,ACM,add,ans,程序设计,糖果,void From： https://www.cnblogs.com/RosmontisL/p/18239773