20210902模拟赛解题报告
- 评价
- T1
- T2
- T3
评价
这次的题目好像没有什么好喷的，还是挺不错的。
那这次我们喷什么？喷键盘！
一场模拟赛我换了三个键盘，其中两个是好似板砖，另一个的空格就像在玩跷跷板。
为什么有按键那么硬的键盘！！！！/fn/fn
中间还有一次因为换键盘，电脑要重启，然后代码没了，呜呜呜。
题目本身还行，因为评测机太慢被卡掉 40 分，申诉之后调大了时限跑过去了。
后来发现洛谷评测机能 1s 1e9！又能多拿 40 分！
这是非常棒的。
T1 是找规律题，因为细节特判被卡了一个点，这是不好的。（还好不是多组数据）
T2 写了一个枚举右端点加二分套线段树的 \(O(n\log^2 n)\) 做法，期望 \(80\)，被卡 \(40\)，后来要回来了。
T3 只会一个 \(O(n^3)\) 加一个部分分特判做法，期望 \(30\)，洛谷评测机跑的快，能拿到 \(70\)。
期望得分：\(100+80+30=210pts\)
实际得分：\(90+40+30=160pts\)
放大时限后得分：\(90+80+30=200pts\)
洛谷评测：\(90+80+70=240pts\)
补题通道：
| T1 | T2 | T3 |
|---|---|---|
| \(\text{U177562 lock}\) | \(\text{U177563 sequence}\) | \(\text{U177564 fight}\) |
没有题解，没仔细研究std，所以只讲考场做法，不是正解！！。
代码只有 T1 是自己写的（我感觉我写的比 std好看），其他的是 std。
代码为啥使用了 Tab 字符啊，八空格有点恶心。
T1
找规律。
对于 \(L\)，不管它是奇数还是偶数，都能通过倒两次水使它们的总和达到 \(L+2\)。
- 偶数：先往一个杯里倒 \(\frac{L}{2}+0.5\) 滴水，再向另一个杯里倒 \(\frac{L}{2}+1.5\) 滴水。
- 奇数：先往一个杯里倒 \(\left\lfloor \frac{L}{2} \right\rfloor +1\) 滴水，再向另一个杯中到 \(\left\lfloor \frac{L}{2} \right\rfloor +2\) 滴水。
然后两个杯子来回倒就可以，不难发现一次向一个杯子倒两滴是最快的，直到两杯水之和达到 \(R\) 或者 \(R-1\)。
所以答案为 \(2+\left\lfloor \frac{R-L-2}{2} \right\rfloor\)。
当 \(R \le L+2\) 和 \(R \le 2\) 时的所有情况需要单独考虑。
#include
#include
#include
#include
#include
#include
#include
#define LL long long
using namespace std;
const int MAXN = 1e5 + 10;
const int INF = 1e9 + 7;
const int mod = 1e9 + 7;
LL L, R;
LL read() {
LL s = 0, f = 0; char ch = getchar();
while(!isdigit(ch)) f = (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 3) + (s << 1) + ch - '0', ch = getchar();
return f ? -s : s;
}
int main() {
// freopen("lock.in","r",stdin);
// freopen("lock.out","w",stdout);
L = read(), R = read();
if(R == 1) { puts("0"); return 0; }
if(R <= L + 2) {
if(R <= 2) puts("1");
else puts("2");
} else {
cout << 2 + (R - L - 2) / 2 << "\n";
}
return 0;
}
T2
std 貌似是个双指针。
固定右端点，二分左端点，然后用线段树求出把那一段区间赋为 \(0\) 最赚，对合法区间取长度最大值，时间复杂度 \(O(n \log^2 n)\)。
#include
#define ll long long
#define pb push_back
#define mk make_pair
#define rint register int
using namespace std;
inline ll read(){ll w=1,s=0;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}return w*s;}
ll Sum[2000010];
ll tmp[2000010];
ll Max[2000010],pos[2000100];
int A[2000010];
ll n,p,d;
int main()
{
// freopen("sequence.in","r",stdin);
// freopen("sequence.out","w",stdout);
n=read(),p=read(),d=read();
for(rint i=1;i<=n;++i)
{
A[i]=read();Sum[i]=Sum[i-1]+A[i];
}
for(rint i=1;i<=d-1;++i) tmp[i]=Sum[i];
for(rint i=d;i<=n;++i)
{
tmp[i]=Sum[i]-Sum[i-d];
}
// if(n<=d)
// {
// cout<Max[tail]) tail--;
Max[++tail]=tmp[rp];
pos[tail]=rp;
}
}
else
{ ll tt=-1e18;
if(head<=tail) tt=max(tt,Max[head]);
tt=max(tt,tmp[rp+1]);
if(Sum[rp+1]-Sum[l-1]-tt<=p)
{
rp++;
while(head<=tail&&tmp[rp]>Max[tail]) tail--;
Max[++tail]=tmp[rp];
pos[tail]=rp;
}
else break;
}
}
ans=max(ans,rp-l+1);
}cout< T3
std 写了个线段树？？？？
\(k=0\) 的情况答案显然为 \(0\)。
考虑维护一个 \(f_{a,b}\) 表示 \(a,b\)两个点同时被多少线段覆盖。
枚举所有三元组 \((a,b,c)\)，显然合法情况只有两种，利用 \(f\) 数组判断是否合法即可。
时间复杂度 \(O(n^3)\)。
洛谷评测跑的快把 \(n=1000\) 的部分卡过去了。
#include
#define ll long long
#define pb push_back
#define mk make_pair
#define rint register int
//#define int ll
using namespace std;
inline int read(){int w=1,s=0;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}return w*s;}
typedef pair pa;
vector vec[200010];
int n,m;ll A[500010];
ll tot=0,q[500010];
ll Sum[500010],tag[500010],du[500100];
inline void pushdown(int now,int l,int r)
{
if(tag[now])
{ int mid=(l+r)>>1;
tag[now<<1]^=1;
tag[now<<1|1]^=1;
Sum[now<<1]=(mid-l+1)-Sum[now<<1];
Sum[now<<1|1]=(r-mid)-Sum[now<<1|1];
tag[now]=0;
}
}
inline void Modify(int now,int l,int r,int x,int y)
{
// cout<>1;
if(x<=mid) Modify(now<<1,l,mid,x,y);
if(y>mid) Modify(now<<1|1,mid+1,r,x,y);
Sum[now]=Sum[now<<1]+Sum[now<<1|1];
}
inline ll Query(int now,int l,int r,int x,int y)
{ if(x>y) return 0;
if(x<=l&&r<=y)
{
return Sum[now];
}pushdown(now,l,r);
int mid=(l+r)>>1;
ll res=0;
if(x<=mid) res=Query(now<<1,l,mid,x,y);
if(y>mid) res+=Query(now<<1|1,mid+1,r,x,y);
Sum[now]=Sum[now<<1]+Sum[now<<1|1];
return res;
}
inline void Solve()
{
for(rint i=1;i<=n;++i)
{
if(i!=1)
{
Modify(1,1,n,i-1,i-1);
}
int sz=vec[i].size();
for(rint j=0;j=y) continue;
vec[x].pb(mk(x,y));
vec[y+1].pb(mk(x,y));
}
Solve();
return 0;
}