C

a+b = sa xor b = x的方案数(a,b有序)

DP
我们考虑a,b的每一位(二进制)
d[i][j][k][l] 表示第i位,a为j,b为k,l表示是否进位
转移很明显,我们可以根据s和x的第i位来确定a和b

复杂度$O(log(n))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

LL s,x;
LL d[40][2][2][2];

LL solve()
{
memset(d,0,sizeof d);
LL dec = 0;
if(s == x) dec = -2;
int i = 0;
while(s || x)
{
int ts = s&1,tx = x&1;
if(!i)
{
if(tx && ts)
{
d[i][1][0][0] = 1;
d[i][0][1][0] = 1;
}
if(!tx && !ts)
{
d[i][1][1][1] = 1;
d[i][0][0][0] = 1;
}
}
else
{
if(tx && ts)
{
d[i][0][1][0] += d[i-1][0][1][0];
d[i][0][1][0] += d[i-1][1][0][0];
d[i][0][1][0] += d[i-1][0][0][0];

d[i][1][0][0] += d[i-1][0][1][0];
d[i][1][0][0] += d[i-1][1][0][0];
d[i][1][0][0] += d[i-1][0][0][0];
}

if(tx && !ts)
{
d[i][0][1][1] += d[i-1][0][1][1];
d[i][0][1][1] += d[i-1][1][0][1];
d[i][0][1][1] += d[i-1][1][1][1];

d[i][1][0][1] += d[i-1][0][1][1];
d[i][1][0][1] += d[i-1][1][0][1];
d[i][1][0][1] += d[i-1][1][1][1];
}

if(!tx && ts)
{
d[i][0][0][0] += d[i-1][0][1][1];
d[i][0][0][0] += d[i-1][1][0][1];
d[i][0][0][0] += d[i-1][1][1][1];

d[i][1][1][1] += d[i-1][0][1][1];
d[i][1][1][1] += d[i-1][1][0][1];
d[i][1][1][1] += d[i-1][1][1][1];
}

if(!tx && !ts)
{
d[i][0][0][0] += d[i-1][0][1][0];
d[i][0][0][0] += d[i-1][1][0][0];
d[i][0][0][0] += d[i-1][0][0][0];

d[i][1][1][1] += d[i-1][0][1][0];
d[i][1][1][1] += d[i-1][1][0][0];
d[i][1][1][1] += d[i-1][0][0][0];
}

}
s>>=1;
x>>=1;
++i;
}
--i;
return d[i][0][0][0] + d[i][0][1][0] + d[i][1][0][0] + dec;
}

int main()
{
//freopen("test.txt","r",stdin);
scanf("%lld %lld",&s,&x);
printf("%lld\n",solve());
return 0;
}

D

一个工厂,休整一段时间,每天产量休整前为b,休整后为a,有q组询问/更新:

  • 1 d a : 第d天订单需求增加a
  • 2 p : 求从第p天开始休息k天,可以满足订单的最大产量

树状数组
根据a,b分别维护可完成订单的前缀和(若当天订单要求超过产量则只增加到当天产量)

复杂度$O(nlog(n))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 2e5 + 10;

int n,k,a,b,q;
LL cur[maxn];
LL bit[2][maxn];

inline int lowbit(int x)
{
return x&-x;
}

void add(int id,int x,LL p)
{
for(int i=x;i<=n;i+=lowbit(i))
{
bit[id][i] += p;
}
}

LL query(int id,int x)
{
LL res = 0;
for(int i=x;i>0;i-=lowbit(i))
{
res += bit[id][i];
}
return res;
}


int main()
{
//freopen("test.txt","r",stdin);
scanf("%d %d %d %d %d",&n,&k,&a,&b,&q);
memset(bit,0,sizeof bit);
memset(cur,0,sizeof cur);
for(int i=0;i<q;++i)
{
int op;
scanf("%d",&op);
if(op==1)
{
int dd,aa;
scanf("%d %d",&dd,&aa);
if(a > cur[dd]) add(0,dd,min((LL)aa,a-cur[dd]));
if(b > cur[dd]) add(1,dd,min((LL)aa,b-cur[dd]));
cur[dd] += aa;
}
else
{
int p;
scanf("%d",&p);
printf("%lld\n",query(1,p-1)+query(0,n)-query(0,p+k-1));
}
}
return 0;
}

E

一条长度为d的路上,有m个加油站,每个加油站有不同油价,油箱容量为n,每走1公里消耗1L油,求走完这条路的最小开销

贪心+单调栈

对于当前点,我们将油加到恰好可以到达下一个油价小于等于它的加油站。
若没有比它小的加油站,则加满。

下一个油价小于等于它的加油站用单调栈即可求。

复杂度$O(m)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 2e5 + 10;
int d,n,m,nxt[maxn];

struct P{
int x,p;
bool operator<(const P& rhs) const{
return x < rhs.x;
}
} p[maxn];

stack<pair<int,int> > st;
#define mp make_pair

void init()
{
nxt[m] = -1;
st.push(mp(0,m));
for(int i=m-1;i>=0;--i)
{
while(!st.empty() && p[i].p < st.top().first) st.pop();
if(st.empty()) nxt[i] = -1;
else nxt[i] = st.top().second;
st.push(mp(p[i].p,i));
}
}

LL solve()
{
LL res = 0,cur = n-p[0].x;
if(p[0].x > n) return -1;
int i = 0;
while(i<m)
{
if(p[i+1].x - p[i].x > n) return -1;
if(nxt[i]==-1 || p[nxt[i]].x - p[i].x > n)
{
res += (LL)p[i].p*(n-cur);
cur = n- (p[i+1].x - p[i].x);
++i;
}
else
{
res += (LL)p[i].p*max(0LL,(p[nxt[i]].x - p[i].x - cur));
cur += max(0LL,(p[nxt[i]].x - p[i].x - cur)) - (p[nxt[i]].x - p[i].x);
i = nxt[i];
}
}
return res;
}

int main()
{
// freopen("test.txt","r",stdin);
scanf("%d %d %d",&d,&n,&m);
for(int i=0;i<m;++i) scanf("%d %d",&p[i].x,&p[i].p);
sort(p,p+m);
p[m].x = d;
p[m].p = 0;
init();
printf("%lld\n",solve());
return 0;
}