CSP2020-S题解
QAQ
A
"按照题意模拟"
做法1
我们把时间轴砍成三段,第一段为公元前,第二段为公元后到1502年10月4日
第三段为之后的日子
前面两端可以通过取模每次跳四年这样子,然后暴力跳剩下的
第三段可以跳到1601年,然后每四百年一跳,然后暴力搞剩下的
做法2
我们暴力预处理1502/10/4之前的年份对应的儒略历,然后剩下的我们按照第三段的暴力跳即可.....
特别好写,省略很多
B
最简单的一道题
首先,已有的饲料我们是已经知道的
然后那些未有的饲料我们只需要考虑他们是不是会是某一位必要的
如果某一位是必要的,但是我们没有这个饲料,这一位就不能放1
否则都可以放1,为种方案
最后减去剩下的动物数即可
,实现精细可以
C
dp题.....
显然的,我们每个数可以写成,然后会发现一次加法操作受到操作序列后面所有函数的乘法操作影响
也就是说我们要计算每个加法操作受到影响的次数
不妨来把这个dag建出来,那么会发现一个函数x对于操作y的计算次数就是x到y的路径条数
所以我们可以拓扑序dp,表示i这个点的计算次数是什么
再处理一个mul函数,表示调用这个点,不考虑加法操作,他的总乘法操作影响是什么
然后对于我们一个三函数,倒序访问他经过的每一个点
于是这个东西就是可以用一个后缀积优化
但是这样你会发现我们没有处理好按照一定顺序访问这件事情,也就是说我们是按照拓扑序访问的时候这个是对的!
解决方式也很简单,更改一下初始的f_i为操作序列后面的函数的mul后缀积即可
D
其实比C简单
第一步,你要发现我们如果一条蛇吃掉之后不会成为最小的,那么一定吃
因为下一条蛇如果吃,吃不到他,而且会成为比他更小的
但是你会发现这样一个case:
6 1
这样的情况下我是可以吃的.....
6 6 1
这样的情况下我是不能吃的,否则我就会被第一条蛇套路
所以要推广一下
6 6 6 1
第三条蛇想吃,但是要看第二条蛇能不能吃
于是第一条蛇告诉第二条蛇我必然吃
第二条蛇不敢吃,所以第三条蛇可以吃了
所以一般的,如果进入这个状态下剩下偶数条蛇输出n-1,否则输出n
但是这样是不对的,问题在于我们每个权值还是可能起作用
所以扩展一下,设一次吃掉后成为全局最小的为冒险
那么从第一次冒险开始,大家都必须继续冒险....知道有一个蛇可以安全的吃掉最小的时候
两次冒险经过偶数输出n-1,否则输出n
这个结论就显然正确了,因为推导一下就能发现我们吃或不吃结局是什么了....
再看看多测,告诉我们
但是每次改完之后都是单调不降的....
所以说我们可以类似于一个蚯蚓的思路,每次一条蛇从没吃的序列吃一口后,把它插入一个队列尾,然后那个队列由于排序的奇怪单调性是一定单调递增的....
所以只需要队头和原数组指针比较即可
//考虑排序之后双队列即可
//我们可以考虑如果吃掉之后不是最小的就吃一口
//最小的判断，看队尾和整个序列的尾
//最大的我们拿队首和整个序列的首
//偶数是n-1
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define mkp(x,y) (make_pair(x,y))
using namespace std;
const int MAXN=1e6+7;
int T,n,a[MAXN],m,hd,tl,kt,ans;
pii que[MAXN],b[MAXN];
namespace fastIO {
#define BUF_SIZE (1<<20)
static char buf[BUF_SIZE],*p1=buf,*pend=buf;
inline char nc() {
if(p1==pend) {
pend=buf+fread(buf,1,BUF_SIZE,stdin);
p1=buf;
}
return *p1++;
}
inline int read() {
char s=nc();
int x=0;
for(; !isdigit(s); s=nc());
for(; isdigit(s); s=nc())x=(x<<1)+(x<<3)+s-'0';
return x;
}
}
using namespace fastIO;
//如果相同，队列里面的大
//没有处理kt>i的？？
int cnt=0;
inline void solve() {
for(int i=1; i<=n; ++i)b[i].fi=a[i],b[i].se=i;
hd=1,tl=0,kt=1;
cnt=0;
for(int i=n; i>=1; --i) {
if(tl-hd+1+i-kt+1==2) {
if(cnt)printf("%d\n",cnt&1?ans:ans-1);
else puts("1");
return ;
}
// printf("%d?hd : %d tl : %d kt : %d !cnt!:%d\n",i,hd,tl,kt,cnt);
// 选择队列里面的
if(hd<=tl && que[hd]>b[i]) {
if(hd<tl && que[tl]<b[kt]) {//最小值判据
// puts("caser : 1");
pii g=b[kt];
if(hd<tl)
g=min(que[tl-1],b[kt]);
pii tmp=mkp(que[hd].fi-que[tl].fi,que[hd].se);
if(tmp<g) {
if(cnt) {
++cnt;
} else {
ans=tl-hd+1+i-kt+1;
cnt=1;
}
} else if(cnt) {
printf("%d\n",cnt&1?ans:ans-1);
return;
}
++hd;
que[tl]=tmp;
//现有最小的被吃掉了，然后换成这个
} else {//说明kt是开头呢
// puts("caser : 2");
pii g=b[kt+1];
if(hd<=tl)
g=min(que[tl],b[kt+1]);
pii tmp=mkp(que[hd].fi-b[kt].fi,que[hd].se);
if(tmp<g) {
if(cnt) {
++cnt;
} else {
ans=tl-hd+1+i-kt+1;
cnt=1;
}
} else if(cnt) {
printf("%d\n",cnt&1?ans:ans-1);
return;
}
++hd;
que[++tl]=tmp;
++kt;
}
++i;
} else {//选择序列哒
if(hd<=tl && que[tl]<b[kt]) {
// puts("caser : 3");
pii g=b[kt];
if(hd<tl)
g=min(que[tl-1],g);
pii tmp=mkp(b[i].fi-que[tl].fi,b[i].se);
if(tmp<g) {
if(cnt) {
++cnt;
} else {
ans=tl-hd+1+i-kt+1;
cnt=1;
}
} else if(cnt) {
printf("%d\n",cnt&1?ans:ans-1);
return;
}
que[tl]=tmp;
} else {
// puts("caser : 4");
pii g=b[kt+1];
if(hd<=tl)
g=min(que[tl],b[kt+1]);
pii tmp=mkp(b[i].fi-b[kt].fi,b[i].se);
if(tmp<g) {
if(cnt) {
++cnt;
} else {
ans=tl-hd+1+i-kt+1;
cnt=1;
}
} else if(cnt) {
printf("%d\n",cnt&1?ans:ans-1);
return;
}
que[++tl]=tmp;
++kt;
}
}
}
return ;
}
//kt>i
//这种情况相当于我们所有蛇都在队列里面操作。。。。
//要单独特判吧?
/*
1
8
1 1 1 1 1 8 8 8
*/
inline void init() {
memset(que,0,sizeof(que));
memset(b,0,sizeof(b));
}
int main() {
// freopen("snakes.in","r",stdin);
// freopen("snakes.out","w",stdout);
T=read();
n=read();
for(int i=1; i<=n; ++i)a[i]=read();
solve();//直接调用solve
while(T-->1) {
init();
m=read();
for(int i=1,x,y; i<=m; ++i) {
x=read();
y=read();
a[x]=y;
}
solve();
}
return 0;
}
/*
1
15
0 1 2 2 2 2 3 3 4 5 5 6 7 8 8
*/