这几次比赛题解
因为考虑到再看，所以将所有题目都做成了pdf格式
梦熊十三连测
T1
这道题其实什么也不用想，就按照题目给的意思来打代码就行，这就有40分可以拿。懒人做法
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
ll x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0') {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int N=2e5+10;
ll a[N];
ll ans;
ll n,q,l,r;
ll trunc(ll v,ll s,ll t){
return (v-s)/t;
}
int main(){
freopen("arithmetic.in","r",stdin);
freopen("arithmetic.out","w",stdout);
n=read(),q=read(),l=read(),r=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1;i<=q;i++){
ll op=read();
ll x=read(),s=read(),t=read();
if(op==1){
for(int j=s;j<=t;j++){
if(a[i]>=x) a[i]=t*(a[i]+s);
}
}
if(op==2){
for(int j=s;j<=t;j++){
if(a[i]<=x){
a[i]=trunc(a[i],s,t);
}
}
}
}
for(int i=1;i<=n;i++){
// cout<<l<<" "<<a[i]<<" "<<r<<endl;
if(a[i]>=l&&a[i]<=r) ans++;
}
printf("%lld",ans);
return 0;
}
然后就是要注意
“
/
”
“ / ”
“/” 这个除是直接就向零取整了,没必要刻意实现函数,反而偷鸡不成蚀把米
然后就是想正解：
发现对于任意
x
≤
y
x \le y
x≤y,在操作后还满足
x
′
≤
y
′
x' \le y'
x′≤y′
考虑将序升序列排序后二分最小和最大下标，并注意一些细节
时间复杂度反正不会超时
正解代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef __int128 i128;
int n, q, qry[200010][4], a[200010], L, R;
i128 foo(int x) {
i128 ans = x;
for (int i = 1; i <= q; i++) {
if (qry[i][0] == 1 && ans >= qry[i][1])
ans = (ans + qry[i][2]) * qry[i][3];
if (qry[i][0] == 2 && ans <= qry[i][1])
ans = (ans - qry[i][2]) / qry[i][3];
}
return ans;
}
signed main() {
freopen("arithmetic.in", "r", stdin);
freopen("arithmetic.out", "w", stdout);
cin >> n >> q >> L >> R;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);
for (int i = 1; i <= q; i++) cin >> qry[i][0] >> qry[i][1] >> qry[i][2] >> qry[i][3];
int l = 1, r = n, ans = n + 1;
while (l <= r) {
int mid = (l + r) >> 1;
i128 x = foo(a[mid]);
if (L <= x) {
ans = mid;
r = mid - 1;
} else
l = mid + 1;
}
int sws = 0;
l = 1, r = n;
while (l <= r) {
int mid = (l + r) >> 1;
i128 x = foo(a[mid]);
if (x <= R) {
sws = mid;
l = mid + 1;
} else
r = mid - 1;
}
if (ans > sws)
puts("0");
else
printf("%lld\n", sws - ans + 1);
return 0;
}
基础算法，考场上如果会正解了，还可能会因为精度挂分， i n t 128 int128 int128挂的话应该是大部分，这是挂分也不要难过，这个差距不大
T2
这道题考试直接跳过去写
T
3
T3
T3了,所以没有部分分思路，直接说正解
1.考虑计算每个中位数
p
i
p_{i}
pi 的贡献
2. 对于
p
j
>
p
i
p_{j}>p_{i}
pj>pi 令
a
j
=
1
a_{j}=1
aj=1 , 对于
p
j
<
p
i
p_{j}<p_{i}
pj<pi 令
a
j
=
−
1
a_{j}=-1
aj=−1 , 问题变为有多个区间
[
l
,
r
]
[l, r]
[l,r]满足：
l
≤
i
≤
r
l \leq i \leq r
l≤i≤r, 且
∑
j
=
l
r
a
j
=
0
\sum_{j=l}^{r} a_{j}=0
∑j=lraj=0
3. 从
i
i
i 往左扫描并累计和
s
j
=
∑
k
=
j
i
a
k
s_{j}=\sum_{k=j}^{i} a_{k}
sj=∑k=jiak , 使用一个数组标记每种
s
j
s_{j}
sj 的取值个数
4. 类似从
i
i
i 往右扫描并累计和
t
j
=
∑
k
=
i
j
a
k
t_{j}=\sum_{k=i}^{j} a_{k}
tj=∑k=ijak , 并询问取值为
−
t
j
-t_{j}
−tj 的
s
s
s 数量
时间复杂度
O
(
n
2
)
O\left(n^{2}\right)
O(n2)
这道题出题人给的时间还是很富裕的，所以不会被卡常数
#include <bits/stdc++.h>
using namespace std;
int n, p[10005];
long long tmp[20010];
int main() {
freopen("book.in", "r", stdin);
freopen("book.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) cin >> p[i];
long long ans = 0;
for (int i = 1; i <= n; i++) {
long long sws = 0;
for (int j = 0; j <= 20004; j++) tmp[j] = 0;
int plc = 0;
for (int j = 1; j <= n; j++)
if (p[j] == i)
plc = j;
int sum = 10002;
for (int j = plc; j >= 1; j--) {
if (p[j] < i)
sum--;
if (p[j] > i)
sum++;
tmp[sum] += j;
}
sum = 10002;
for (int j = plc; j <= n; j++) {
if (p[j] < i)
sum--;
if (p[j] > i)
sum++;
sws += tmp[20004 - sum] * j;
}
ans += sws * i;
}
cout << ans;
return 0;
}
T3
看到这道题要想到一个式子 联通块数
=
=
= 剩余的点数
−
-
− 剩余的边数
然后用
s
e
t
set
set维护每个点的边就行了。贡献啥的就是图论，下面是解决方法:
贡献被拆成四个部分
：
：
：点
×
\times
× 点 - 边
×
\times
× 点 - 点
×
\times
× 边
+
+
+ 边
×
\times
× 边
这里以边
×
\times
× 边 为例, 对于树
T
T
T 的边
(
u
,
v
)
(u, v)
(u,v) 假设它被保留
（概率
1
/
4
）
1.
（概率 1 / 4 ） 1.
（概率1/4）1.则树
U
U
U 中
u
,
v
u, v
u,v 必定被删除
2.计算树
U
U
U 中有多少边
(
x
,
y
)
(x, y)
(x,y) 不以
u
或
v
u 或 v
u或v 为端点
3.每条边
(
x
,
y
)
(x, y)
(x,y) 都有
1
/
4
1 / 4
1/4 概率被保留
用
s
e
t
set
set 维护每个点的边, 时间复杂度
O
(
n
log
n
)
O(n \log n)
O(nlogn)
这道题在场上A了
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const int mod = 998244353;
const int MAXN = 200011;
set<ll> a[MAXN], b[MAXN];
ll fac[MAXN], inv[MAXN];
ll n;
ll read() {
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
ll max(ll a, ll b) { return a > b ? a : b; }
ll min(ll a, ll b) { return a < b ? a : b; }
void umax(ll &a, ll t) {
if (t > a)
a = t;
}
void umin(ll &a, ll t) {
if (t < a)
a = t;
}
ll Qpow(ll a, ll p = mod - 2) {
if (p < 0)
return 0;
ll res = 1;
while (p) {
if (p & 1)
res = res * a % mod;
a = a * a % mod;
p >>= 1;
}
return res;
}
void add(ll &x, ll y) { x = (x + y) % mod; }
ll C(ll n, ll m) { return n < m ? 0 : fac[n] * inv[m] % mod * inv[n - m] % mod; }
int main() {
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
n = read();
if (n == 1)
return puts("0"), 0;
fac[0] = 1;
inv[0] = 1;
for (ll i = 1; i <= n; i++) {
fac[i] = fac[i - 1] * i % mod;
inv[i] = Qpow(fac[i]);
}
for (ll i = 1; i < n; i++) {
ll u = read(), v = read();
a[u].insert(v), a[v].insert(u);
}
for (ll i = 1; i < n; i++) {
ll u = read(), v = read();
b[u].insert(v), b[v].insert(u);
}
ll ans = 0;
for (ll i = 1; i <= n; i++) {
add(ans, C(n, i) * i % mod * (n - i));
add(ans, 2 * (mod - (C(n - 2, i) * i % mod * (n - 1) % mod)));
}
ll ctrb = (n < 4 ? 0 : Qpow(2, n - 4));
for (ll u = 1; u <= n; u++) {
for (auto v : a[u]) {
if (u > v)
continue;
add(ans, ctrb * (n - 1 - b[u].size() - b[v].size() + b[u].count(v)) % mod);
}
}
for (ll i = 1; i <= n; i++) {
ans = ans * inv[2] % mod;
}
printf("%lld\n", ans);
return 0;
}
这个题其实还能用并查集，由于作者直接写的正解，所以并查集靠自己思考
T4
这道题当时没想上来，然后思考片刻，改题时看了题解
于是就可以猜假结论，这也是一种得分技巧
使用一棵（类似于哈夫曼树的）二叉树来编码。每个非叶子结点的两条子边权值分别为
1
1
1 和
2
2
2 。每个叶子节点对应了一个字符, 其代价即为根到该叶子节点的路径长度。
最优解中出现频次越大的字符深度越小，考虑由浅入深构造整棵二叉树
设
f
[
i
]
[
a
]
[
b
]
[
l
]
f[i][a][b][l]
f[i][a][b][l] 表示构造二叉树深度为
i
i
i , 其中深度为
i
−
1
i-1
i−1 的节点有
a
a
a 个, 深度为
i
i
i 的节点有
b
b
b 个, 深度不超过
i
−
2
i-2
i−2 的叶子有
l
l
l 个。我们可以枚举深度
i
−
1
i-1
i−1 保留
k
k
k 个节点作为叶子, 将剩下的节点扩展。由此可以得到一个
O
(
n
5
)
O\left(n^{5}\right)
O(n5) 复杂度的做法
转移时不需要记录深度 (将贡献拆分到每一层), 可以减少一维做到
O
(
n
4
)
O\left(n^{4}\right)
O(n4)
进一步将枚举
k
k
k 的过程省略, 将其拆分为两种转移：扩展一个节点, 或者将深度加一。最后时间复杂度
O
(
n
3
)
O\left(n^{3}\right)
O(n3)
这个题还是挺需要思维的
#include <bits/stdc++.h>
#define ALL(x) begin(x), end(x)
#define All(x, l, r) &x[l], &x[r] + 1
using namespace std;
void file() {
freopen("telegram.in", "r", stdin);
freopen("telegram.out", "w", stdout);
}
using ll = long long;
const int kL = 405, inf = (1 << 30) - 3;
int n;
array<int, kL> a, pre;
array<array<array<array<int, kL>, kL>, 40>, 2> f;
void chkmn(int& x, int y) { (x > y) && (x = y); }
int main() {
file();
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(All(a, 1, n));
for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
for (auto& A : f)
for (auto& B : A)
for (auto& k : B) k.fill(inf);
f[1][1][0][1] = -a[1];
for (int i = 1; i <= n; i++) {
int cr = (i & 1), nx = !(i & 1);
for (int j = 1; j < 38; j++)
for (int k = 0; k <= i; k++) fill(All(f[nx][j][k], 0, i), inf);
for (int j = 1; j < 38; j++)
for (int k = 0; k <= i; k++) {
for (int p = k; p + k <= i; p++) chkmn(f[cr][j + 1][p - k][k], f[cr][j][k][p]);
for (int p = 0; p + k <= i; p++) chkmn(f[nx][j][k][p + 1], f[cr][j][k][p] - j * a[i + 1]);
}
}
ll ans = inf, sum = accumulate(All(a, 1, n), 0ll);
for (int i = 1; i < 38; i++) ans = min(ans, sum * i + f[n & 1][i][0][1]);
cout << ans << "\n";
return 0;
}
然后可以试试打暴力，毕竟考场上不一定想出来正解：
暴力拿了30分
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int lowbit(int x) { return x & (-x); }
int n, a[100010], dp[100010], s[100010], sum[100010];
signed main() {
freopen("telegram.in", "r", stdin);
freopen("telegram.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) s[1 << (i - 1)] = i;
sum[0] = 0;
for (int msk = 1; msk < (1 << n); msk++) sum[msk] = sum[msk ^ lowbit(msk)] + a[s[lowbit(msk)]];
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= n; i++) dp[1 << (i - 1)] = 0;
for (int msk = 1; msk < (1 << n); msk++) {
for (int c = (msk - 1) & msk; c; c = (c - 1) & msk) {
dp[msk] = min(dp[msk], dp[c] + dp[msk ^ c] + sum[c] + 2 * sum[msk ^ c]);
}
}
cout << dp[(1 << n) - 1];
return 0;
}
十三联测就结束了，然后NOIP考这个分数是不行的，所以还要加油
梦熊CSP-S模拟赛
打暴力寄掉了，悲剧啊
T1
P11217 【MX-S4-T1】「yyOI R2」youyou 的垃圾桶
考后又看了这个题，发现思路对了一半想用线段树维护区间加，后来想用树状数组维护区间加
先放一个写挂掉的代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
ll x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int N=2e5+10;
ll a[N],tree[N];
ll lowbit(ll x){
return x&(-x);
}
int n,q,w;
void add(ll x,ll k){
while(x<=n){
tree[x]+=k;
x+=lowbit(x);
}
}
ll ser(ll x){
ll ans=0;
while(x>0){
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
ll sum[N],all;
int main(){
ll W;
n=read(),q=read(),W=read();
for(ll i=1;i<=n;i++){
a[i]=read();
add(i,a[i]-a[i-1]);
sum[i]=a[i]+sum[i-1];
all+=a[i];
}
while(q--){
w=W;
ll ans=0;
ll res=1;
ll l=read(),r=read(),d=read();
add(l,d),add(r+1,-d);
// cout<<ser(1);
all+=(r-l+1)*d;
while(res*all<w){
w-=res*all;
res*=2;
ans+=n;
}
// cout<<w<<endl;
// cout<<all*res<<endl;
// cout<<ans<<endl;
// cout<<res<<endl;
// cout<<"jk";
// for(int i=1;i<=n;i++){
// cout<<ser(i)<<endl;
// }
for(ll i=1;;i++){
ll op=ser(i);
// cout<<op<<"jk";
if(w>op*res){
ans++;
w-=op*res;
}else break;
// cout<<w<<endl;
}
printf("%lld\n",ans);
}
return 0;
}
然后想正解
首先每场战斗前的强化就相当于区间加操作。
我们先对整个区间进行整体操作，计算
y
o
u
y
o
u
youyou
youyou 被所有垃圾桶攻击一遍后剩余血量，并用
k
k
k 记录当前垃圾桶攻击力翻了多少倍。
当
y
o
u
y
o
u
youyou
youyou 的血量不足以支撑被全部垃圾桶攻击时，直接在线段树上二分，查找最多还能被攻击几次。
所以这道题还是很简单的，想到正解了，没写出来，可能受点在家的原因吧
正解的代码：
#include<bits/stdc++.h>
#include<cstdio>
#define LL long long
#define N 222222
#define pushup(now) sum[now]=sum[now<<1]+sum[now<<1|1]
inline LL read(){
LL x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
using namespace std;
LL n,q,W;
LL sum[N<<2],add[N<<2];
void build(LL l,LL r,LL now){
if(l==r){
sum[now]=read();
return ;
}
LL mid=l+r>>1;
build(l,mid,now<<1);build(mid+1,r,now<<1|1);
pushup(now);
return ;
}
void Add(LL l,LL r,LL now,LL v){
sum[now]+=(r-l+1)*v;
add[now]+=v;
return ;
}
void pushdown(LL l,LL r,LL now){
if(!add[now])return ;
LL mid=l+r>>1;
Add(l,mid,now<<1,add[now]);
Add(mid+1,r,now<<1|1,add[now]);
add[now]=0;
return ;
}
void modify(LL l,LL r,LL now,LL x,LL y,LL v){
if(l>=x&&r<=y)return Add(l,r,now,v);
LL mid=l+r>>1;
pushdown(l,r,now);
if(x<=mid)modify(l,mid,now<<1,x,y,v);
if(y>mid)modify(mid+1,r,now<<1|1,x,y,v);
pushup(now);
return ;
}
int main(){
// freopen("wxyt4.in","r",stdin);
// freopen("wxyt.out","w",stdout);
n=read();q=read();W=read();
build(1,n,1);
while(q--){
LL l=read(),r=read(),d=read(),w=W,ans=0,now=1,k=1;
modify(1,n,1,l,r,d);
while(w>sum[1]*k){
w-=sum[1]*k;
ans+=n;
k<<=1;
}
//以下为线段树二分
l=1,r=n;
while(l!=r){
LL mid=l+r>>1;
pushdown(l,r,now);//注意在此处下传懒标记
if(sum[now<<1]*k<w)ans+=mid-l+1,w-=sum[now<<1]*k,l=mid+1,now=now<<1|1;
else r=mid,now<<=1;
}
printf("%lld\n",ans);
}
return 0;
}
T2
P11218 【MX-S4-T2】「yyOI R2」youyou 不喜欢夏天
这道题感觉像是DP，同学说是诈骗题
首先考虑简单DP
O
(
n
m
)
O(nm)
O(nm)
设
f
i
,
j
,
c
f_{i,j,c}
fi,j,c表示前i列反转了j次:
c
=
0
c=0
c=0只选上面的
c
=
1
c=1
c=1只选下面的
c
=
2
c=2
c=2两格都选
但这个暴力没有优化空间，和正解无关
考虑正解，好像可以舍去m这一个维度，不妨大胆试试
如果舍去m后那么 yy 必然就有确定的最优方案。继续分讨。
当两格同色，翻转与否无影响，故不翻转；
当两格异色：
当同时选两格，翻转与否无影响，故不翻转；
当选黑一格，尽可能多翻转此类，假设共有
x
x
x 次这样的选择，贡献
−
2
m
i
n
x
,
m
；
−2min{x,m}；
−2minx,m；
当选白一格，不做处理即最优。
注意到
−
2
m
i
n
x
,
m
−2min{x,m}
−2minx,m 是单峰的，故最大值取在两侧，即
x
x
x 尽可能少一侧和尽可能多一侧，所以贪心地取这两侧进行
D
P
DP
DP 就完了。
对于少一侧，注意每遇到一列异色的贡献 − 1 −1 −1，因为默认 y y yy yy 会翻转。而多一侧则恰恰相反贡献 1 1 1，但注意统计答案要减去 2 m 2m 2m。
因为转移方程比较冗长，这里就不用公式列出，读者可自行移至代码处查看，故解释代码中一部分细节。
代码先分讨上述第一类情况，再分讨第二类情况。在第一类情况中代码将异色列一起处理了而第二类分开处理，因为第二类中需要明确选择的是黑格还是白格，二者贡献不一致（即先假设了 yy 一个都不翻的自然情况）。这个 DP 类似最大子段和，故每次 f f f 的值掉下 0 0 0 之后就应该重新开始，这里为了方便编写，代码将 max 操作中的 0 0 0 平衡了贡献，这样可以把贡献直接提出来，读者为方便理解，可将后面加上贡献的改回 m a x max max 操作中。
#include<bits/stdc++.h>
using namespace std;
inline void read(int &x) {
char c=getchar();
x=0;
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10-48+c,c=getchar();
}
int t,n,m,f[2000005][3],ans;
bool a[2000005][2];
int main() {
read(t);
read(t);
while(t--) {
read(n);
read(m);
ans=0;
char c=getchar();
while(!isdigit(c)) c=getchar();
for(int i=1; i<=n; i++) a[i][0]=c-48,c=getchar();
while(!isdigit(c)) c=getchar();
for(int i=1; i<=n; i++) a[i][1]=c-48,c=getchar();
for(int i=1; i<=n; i++) {
if(a[i][0]^a[i][1])
f[i][0]=max({1,f[i-1][0],f[i-1][2]})-1,
f[i][1]=max({1,f[i-1][1],f[i-1][2]})-1,
f[i][2]=max({0,f[i-1][0],f[i-1][1],f[i-1][2]});
else if(a[i][0])
f[i][0]=max({-1,f[i-1][0],f[i-1][2]})+1,
f[i][1]=max({-1,f[i-1][1],f[i-1][2]})+1,
f[i][2]=max({-2,f[i-1][0],f[i-1][1],f[i-1][2]})+2;
else
f[i][0]=max({1,f[i-1][0],f[i-1][2]})-1,
f[i][1]=max({1,f[i-1][1],f[i-1][2]})-1,
f[i][2]=max({2,f[i-1][0],f[i-1][1],f[i-1][2]})-2;
ans=max({ans,f[i][0],f[i][1],f[i][2]});
}
memset(f,0,sizeof f);
for(int i=1; i<=n; i++) {
if(a[i][0]^a[i][1])
if(a[i][0])
f[i][0]=max({-1,f[i-1][0],f[i-1][2]})+1,
f[i][1]=max({1,f[i-1][1],f[i-1][2]})-1,
f[i][2]=max({0,f[i-1][0],f[i-1][1],f[i-1][2]});
else
f[i][0]=max({1,f[i-1][0],f[i-1][2]})-1,
f[i][1]=max({-1,f[i-1][1],f[i-1][2]})+1,
f[i][2]=max({0,f[i-1][0],f[i-1][1],f[i-1][2]});
else if(a[i][0])
f[i][0]=max({-1,f[i-1][0],f[i-1][2]})+1,
f[i][1]=max({-1,f[i-1][1],f[i-1][2]})+1,
f[i][2]=max({-2,f[i-1][0],f[i-1][1],f[i-1][2]})+2;
else
f[i][0]=max({1,f[i-1][0],f[i-1][2]})-1,
f[i][1]=max({1,f[i-1][1],f[i-1][2]})-1,
f[i][2]=max({2,f[i-1][0],f[i-1][1],f[i-1][2]})-2;
ans=max({ans,f[i][0]-2*m,f[i][1]-2*m,f[i][2]-2*m});
}
printf("%d\n",ans);
}
return 0;
}
这道题就做完了
T3
P11219 【MX-S4-T3】「yyOI R2」youyou 的序列 II
结论：当且仅当 A 能操作一个区间使得所有剩下的点被覆盖时才能胜利。
这道题有点难度，算上调的时间，这道题花了几乎一个上午
先提出一个结论（以下讨论均局限于询问的区间 (x, y) 中）：令第二个人可以操作的区间集合为 S ，
即:
S
=
{
(
l
,
r
)
∣
r
−
l
+
1
≤
c
2
,
∑
i
=
l
r
a
i
>
w
2
}
S=\left\{(l, r) \mid r-l+1 \leq c_{2}, \sum_{i=l}^{r} a_{i}>w_{2}\right\}
S={(l,r)∣r−l+1≤c2,∑i=lrai>w2}
如果存在一个区间
(
L
,
R
)
(L, R)
(L,R) 满足:
- 第一个人可以操作 ( L , R ) (L, R) (L,R) ，即 R − L + 1 ≤ c 1 R-L+1 \leq c_{1} R−L+1≤c1, ∑ i = l r ≤ w 1 \sum_{i=l}^{r} \leq w_{1} ∑i=lr≤w1
-
(
L
,
R
)
(L, R)
(L,R) 包含
S
S
S 中所有的区间，即
L
≤
min
(
l
,
r
)
∈
S
l
,
R
≥
min
(
l
,
r
)
∈
S
r
。
L \leq \min _{(l, r) \in S} l, R \geq \min _{(l, r) \in S} r_{\text {。 }}
L≤min(l,r)∈Sl,R≥min(l,r)∈Sr。
并且如果忽略第二个人的存在，这个区间可以全部变成红色，即 max i = x y a i ≤ w 1 \max _{i=x}^{y} a_{i} \leq w_{1} maxi=xyai≤w1 。如果以上两个条件均满足，那么第一个人会赢。否则第二个人会赢。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 3e5 + 5;
int n, q, c1, c2;
ll w1, w2;
ll a[maxn], tr[maxn];
void upd(int id, ll k){
for(int i = id; i <= n; i += i & -i) tr[i] += k;
}
ll que(int id){
ll s = 0;
for(int i = id; i > 0; i -= i & -i) s += tr[i];
return s;
}
namespace seg{
#define l(x) (x << 1)
#define r(x) (x << 1 | 1)
ll max1[maxn << 2], tag[maxn << 2];
void up(int x){
max1[x] = max(max1[l(x)], max1[r(x)]);
}
void down(int x){
max1[l(x)] += tag[x], tag[l(x)] += tag[x];
max1[r(x)] += tag[x], tag[r(x)] += tag[x];
tag[x] = 0;
}
void update(int x, int l, int r, int ql, int qr, ll k){
if(ql <= l && r <= qr){
max1[x] += k, tag[x] += k;
return;
}
down(x);
int mid = l + r >> 1;
if(ql <= mid) update(l(x), l, mid, ql, qr, k);
if(qr > mid) update(r(x), mid + 1, r, ql, qr, k);
up(x);
}
int query1(int x, int l, int r, int ql, int qr, ll k){
if(ql <= l && r <= qr){
if(max1[x] <= k) return 0;
if(l == r){
if(max1[x] > k) return l;
else return 0;
}
down(x);
int mid = l + r >> 1;
if(max1[l(x)] > k) return query1(l(x), l, mid, ql, qr, k);
else return query1(r(x), mid + 1, r, ql, qr, k);
}
down(x);
int mid = l + r >> 1, res = 0;
if(ql <= mid) res = query1(l(x), l, mid, ql, qr, k);
if(res) return res;
if(qr > mid) res = query1(r(x), mid + 1, r, ql, qr, k);
return res;
}
int query2(int x, int l, int r, int ql, int qr, ll k){
if(ql <= l && r <= qr){
if(max1[x] <= k) return 0;
if(l == r){
if(max1[x] > k) return l;
else return 0;
}
down(x);
int mid = l + r >> 1;
if(max1[r(x)] > k) return query2(r(x), mid + 1, r, ql, qr, k);
else return query2(l(x), l, mid, ql, qr, k);
}
down(x);
int mid = l + r >> 1, res = 0;
if(qr > mid) res = query2(r(x), mid + 1, r, ql, qr, k);
if(res) return res;
if(ql <= mid) res = query2(l(x), l, mid, ql, qr, k);
return res;
}}
namespace seg2{
#define l(x) (x << 1)
#define r(x) (x << 1 | 1)
ll max1[maxn << 2];
void up(int x){
max1[x] = max(max1[l(x)], max1[r(x)]);
}
void build(int x, int l, int r){
if(l == r){
max1[x] = a[l];
return;
}
int mid = l + r >> 1;
build(l(x), l, mid), build(r(x), mid + 1, r);
up(x);
}
void update(int x, int l, int r, int id, ll k){
if(l == r){
max1[x] += k;
return;
}
int mid = l + r >> 1;
if(id <= mid) update(l(x), l, mid, id, k);
else update(r(x), mid + 1, r, id, k);
up(x);
}
ll query(int x, int l, int r, int ql, int qr){
if(ql <= l && r <= qr) return max1[x];
int mid = l + r >> 1;
ll res = 0;
if(ql <= mid) res = max(res, query(l(x), l, mid, ql, qr));
if(qr > mid) res = max(res, query(r(x), mid + 1, r, ql, qr));
return res;
}}
int main(){
scanf("%d %d %d %d %lld %lld", &n, &q, &c1, &c2, &w1, &w2);
for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
for(int i = 1; i <= n; i ++){
upd(i, a[i]);
seg::update(1, 1, n, max(1, i - c2 + 1), i, a[i]);
}
seg2::build(1, 1, n);
while(q --){
int op;
scanf("%d", &op);
if(op == 1){
int x;
ll y;
scanf("%d %lld", &x, &y);
upd(x, y);
seg::update(1, 1, n, max(1, x - c2 + 1), x, y);
seg2::update(1, 1, n, x, y);
a[x] += y;
}else{
int l, r;
scanf("%d %d", &l, &r);
if(seg2::query(1, 1, n, l, r) > w1){
printf("tetris\n");
continue;
}
int L = 0, R = 0;
if(r - l + 1 <= c2){
if(que(r) - que(l - 1) > w2) L = l, R = r;
}else{
L = seg::query1(1, 1, n, l, r - c2 + 1, w2);
R = seg::query2(1, 1, n, l, r - c2 + 1, w2) + c2
}
if(!L || !R){
printf("cont\n");
continue;
}
if(que(R) - que(L - 1) <= w1 && R - L + 1 <= c1) printf("cont\n");
else printf("tetris\n");
}
}
return 0;
}
T4
改不动了
贴一个题目吧
信友队
T1
不难注意到无论是哪一种收益，每次操作后数的奇偶性都会变化。
考察异或的性质：
x⊕1=x−1(x is odd)，x+1 (x is even)
所以我们可以知道，异或放在奇数个事件时等价于 +1，放在偶数个事件时等价于 −1。
于是我们得出了每个事件坦白的收益，按照收益排序后输出即可。
时间复杂度 O(TN)。
T2
T3
这道题只写了暴力
非常暴力
#include<bits/stdc++.h>
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int N=510;
int a[N];
deque<int> q;
const int MOD=1e9+7;
int main(){
freopen("potential.in","r",stdin);
freopen("potential.out","w",stdout);
int n=read(),m=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
int ans=0;
do{
for(int i=1;i<=m;i++){
q.push_back(0);
}
for(int i=1;i<=n;i++){
if(q.front()<a[i]){
q.pop_front();
q.push_back(a[i]);
}
}
while(q.size()){
ans+=q.front();
ans%=MOD;
q.pop_front();
}
}while(next_permutation(a+1,a+1+n));
printf("%d",ans);
return 0;
}
T4
不会