A
签到题，模拟。
B
可知
于是输入三个 ull 类型的数，然后先找到 3 的倍数将其除以 3，最后乘起来输出即可。
C
首先只有 $n$ 为 $2$ 时才有可能无法使杠杆平衡，特判一下。（因为这个罚了一发）。
此外，这个物品显然只能加在最左边和最右边，因为要求为最小质量，杠杆原理。
可以想到，求出以每个点为支点时，所需要添加的物品的质量，其中最小值即为答案。
于是考虑如何求出每个点为支点时所需要添加的物品的质量。
令左力矩和为 $L$ ，右力矩和为 $R$ ，前缀和为 $S$ 。
先令支点为第一个点， $L=0$ ， $R$ 可以 $O(n)$ 地求出来。
支点每次后移时，假设由 $i$ 移至了 $i+1$ ，则 $L$ 应加上 $S_i$ ， $R$ 应减去 $S_n-S_i$ 。过程中取添加物品的质量的最小值即可。
时间复杂度 $O(n)$ 。
E
模拟题。
本题让我知道了 queue<int> q[1000010]; 会直接 MLE 。罚了 6 发。
后来发现不需要开队列，直接对每个窗口记录其最后一个人即可，因为按照时间顺序排队的话后进队的一定在后面。
同时开一个优先队列，离开时间最早的在前，然后按照时间顺序处理到目前的人时，将在时间的人全部出队，再将目前的人加进去。
如此模拟即可。
以上四题是赛时前 2 小时做出来的，后 3 小时一题没做出来 QAQ .
G
考试一直在调范围，妄图卡过去，暴交 41 发 23333 。
当时没有想到子集枚举。
首先，对于学分为 $i$ 时能够获得的最大的知识 ，假设其为 $dp[i]$ 。
这个很显然可以 $O(N\sum a_i)$ 求出来。
然后假设 $maxn[i]$ 表示学分为 $i$ 及其子集时能够获得的最大的知识。显然有
这个可以用子集枚举 $O(3^{\log k})$ 求出来。
于是假设全集是 $S$ ，那么只需要 $O(\sum a_i)$ 求出 $maxn[i]+maxn[S\oplus i]$ 的最大值即可，其中 $i$ 与 $S\oplus i$ 均要大于 $K$ 且合法。
如此即可解决本题。
#include<bits/stdc++.h>
#define N 200010
using namespace std;
int n,k,a[N],b[N],dp[N],maxn[N],m=0,ans=-1;
void work() {
memset(maxn,-1,sizeof(maxn));
memset(dp,-1,sizeof(dp));
scanf("%d%d",&n,&k);
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++) m+=a[i];
dp[0]=0;
for(int i=1;i<=n;i++) {
for(int j=m;j>=a[i];j--) {
if(dp[j-a[i]]==-1) continue;
dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
}
}
for(int i=0;i<=m;i++) {
for(int j=i;j>0;j=(j-1)&i) {
if(j<k) continue;
maxn[i]=max(maxn[i],dp[j]);
}
}
int S=1;
while(S<=m) S<<=1;
S--;
for(int i=k;i<=m;i++) {
if((S^i)<k||maxn[i]==-1||maxn[S^i]==-1) continue;
ans=max(ans,maxn[S^i]+maxn[i]);
}
printf("%d\n",ans);
}
int main() {
work();
return 0;
}F
看了 MSC 群里 luoyue 的思路。
首先一个序列的代价是与其奇数与偶数的数量有关的。
假设一个序列奇数数量为 $A$ ，偶数数量为 $B$ ，则其代价为
若 $A<B$ 则为
若 $A>B$
若 $A-B$ 为奇数则为
若 $A-B$ 为偶数则为
考虑从左往右一个一个把数加入序列。
假设 $A-B$ 为 $delta$ 。
因为一个一个把数加入序列， $delta$ 的值要么加一要么减一。
根据上面的代价，可知对于相邻的 $delta$ 对应的代价，其是有一定的规律的。
如果要加入的这个数为奇数，那么考虑未加入前的 $delta$ ：
- 如果 $delta>0$
- 如果 $delta$ 为奇数，则新加入数后序列的代价减原先序列代价值为 $-1$ 。
- 如果 $delta$ 为偶数，则新加入数后序列的代价减原先序列待j价值为 $2$ 。
- 如果 $delta<0$
- 如果 $delta$ 为奇数，则新加入数后序列的代价减原先序列代价值为 $-1$ 。
- 如果 $delta$ 为偶数，则新加入数后序列的代价减原先序列代价值为 $0$ 。
/*
odd-even -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6
3 3 2 2 1 1 0 2 1 3 2 4 3
*/于是可考虑维护正负奇偶 $delta$ 的个数，每次加数相当于把所有的 $delta$ 左移或右移，但是这样一个一个操作显然不行。所以可考虑将 $0$ 左移右移。
然后这样扫一遍，边累加贡献边移动 $0$ 维护序列即可。
时间复杂度 $O(n)$ 。
#include<bits/stdc++.h>
#define ll long long
#define N 100010
using namespace std;
int n,a[N],cnt[N<<1];
int base=N-10,delta=0;
ll ans=0;
void work() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
ll Opos=0,Epos=0,Oneg=0,Eneg=0,res=0;
for(int i=1;i<=n;i++) {
if(a[i]&1) {
delta++;
cnt[base-delta+1]++;
res+=-Opos+2*Epos-Oneg+0*Eneg+2*cnt[base-delta+1];
swap(Opos,Epos);
Opos+=cnt[base-delta+1];
swap(Oneg,Eneg);
Eneg-=cnt[base-delta];
}
else {
delta--;
cnt[base-delta-1]++;
res+=-2*Opos+Epos+0*Oneg+Eneg+cnt[base-delta-1];
swap(Opos,Epos);
Epos-=cnt[base-delta];
swap(Oneg,Eneg);
Oneg+=cnt[base-delta-1];
}
ans+=res;
}
printf("%lld\n",ans);
}
int main() {
work();
return 0;
}
