NOI-Online 2 test0425
surprise mtf
T1 涂色游戏
题意
你有 (10^{20}) 个格子，它们从 (0) 开始编号，初始时所有格子都还未染色，现在你按如下规则对它们染色：
- 编号是 (p_1)倍数的格子（包括 (0) 号格子，下同）染成红色。
- 编号是 (p_2) 倍数的格子染成蓝色。
- 编号既是 (p_1) 倍数又是 (p_2) 倍数的格子，你可以选择染成红色或者蓝色。
其中 (p_1) 和 (p_2) 是给定的整数，若格子编号是 (p_1) 或 (p_2) 的倍数则它必须要被染色。在忽略掉所有未染色格子后，你不希望存在 (k) 个连续的格子颜色相同，因为你认为这种染色方案是无聊的。现在给定 (p_1,p_2,k)，你想知道是否有一种染色方案不是无聊的。
得分情况
期望得分：100
实际得分：0-20（luogu民间估计）
改题得分：100
考试想法
真的心态崩了……公式推错了就很棒棒……没啥好讲的，样例跟……一样水。
正解
不妨设 (p_1<p_2)，且 (p_1,p_2) 互质。
则会发现：最坏情况，也就是从 (kp_2+1) 到 ((k+1)p_2-1)这个连续串内塞 (p_1) 所对应的颜色。
这样就有 (dfrac{p_2-2}{p_1}+1) 个连续块，将其与 (k) 比较即可。
因为可能不互质，所以可以两边除 (gcd(p_1,p_2)) 即可。
T2 子序列问题
题意
给定一个长度为 (n) 的正整数序列 (A_1,A_2,cdots,A_n)。定义一个函数 (f(l,r)) 表示：序列中下标在 ([l,r])范围内的子区间中，不同的整数个数。换句话说，(f(l,r)) 就是集合 ${A_l,A_{l+1},cdots,A_r} $的大小，这里的集合是不可重集，即集合中的元素互不相等。
现在，请你求出(sum_{l=1}^nsum_{r=l}^n (f(l,r))^2)。由于答案可能很大，请输出答案对 (10^9 +7) 取模的结果。
得分情况
期望得分：100
实际得分：70-100（luogu民间估计）
改题得分：100（直接开O2没有改动）
考试想法
正解……可能我太弱了，没算好复杂度，以为线段树可以过……
而且可能也不是线段树的问题，我用的map，用离散化将快的飞起。
我们从前往后递推当前位置 (i) 加入了新数 (a_i)。
对于每次加入了(a_i) 我们需要计算
(tmp_i=sum_{l=1}^i (f(l,i))^2),然后就可以直接 (ans=ans+tmp) 了。
怎样快速的计算(tmp)呢。
不妨设 (b_j) 为 (f(j,i)) 。
那么每次枚举到的新的 (b_i) 为 (1) 。
对于(b_j(jin[1,i-1])) ，设s为最后一次出现 (a_i) 的位置（离散化和map皆可）。
这个可以用 线段树 树状数组维护。
此时我们需要计算的 (tmp_i= sum_{j=1}^ib_j^2)。
此时我们已经有了(tmp_{i-1}) ，那么我们的问题变为了怎样快速的转换 (tmp_i)。
此时，(b_j,jin[s+1,i-1]) 已经变为了(b_j+1)，此时给 (tmp) 的贡献是多少呢？
我们易知这个小学算式
每个 (b_j,jin[s+1,i-1]) 给 (tmp) 贡献了 (2b_i+1) 。
我们可以直接用线段树 树状数组计算出(sss=sum_{j=s+1}^{i-1} 2b_j+1) 。
那么 (tmp_i=tmp_{i-1}+sss+b_i^2) ，这里前面讲到了 (b_i=1) 。
然后就可以愉快的 (ans=ans+tmp_i)了。
这里附上一下线段树的假代码，开 O2 在Luogu 上可过……但是我肯定凉凉了……
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define Int signed
const int maxn=1e6+10;
const int mod=1e9+7;
map<int,int>ma;
int n;
struct sgt_tree{
int a[maxn<<2],f[maxn<<2];
inline void push_up(int x){
a[x]=a[x<<1]+a[x<<1|1];
return;
}
inline void push_down(int x,int l,int r){
if(f[x]){
int mid=(l+r)>>1;
f[x<<1]+=f[x];
f[x<<1|1]+=f[x];
a[x<<1]+=(mid-l+1)*f[x];
a[x<<1|1]+=(r-mid)*f[x];
f[x]=0;
}
return;
}
int sum(int x,int l,int r,int L,int R){
if(L>R)
return 0;
int s=0;
if(L<=l && r<=R)
s+=a[x];
else{
push_down(x,l,r);
int mid=(l+r)>>1;
if(L<=mid)
s+=sum(x<<1,l,mid,L,R);
if(mid<R)
s+=sum(x<<1|1,mid+1,r,L,R);
}
return s;
}
void add(int x,int l,int r,int L,int R){
int mid=(l+r)>>1;
if(L<=l && r<=R){
a[x]+=r-l+1;
f[x]++;
}
else{
push_down(x,l,r);
if(L<=mid)
add(x<<1,l,mid,L,R);
if(mid<R)
add(x<<1|1,mid+1,r,L,R);
push_up(x);
}
return;
}
}sgt;
inline int read(){
int x=0,c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
return x;
}
int ans,tmp;
Int main(){
#ifdef ZTZ_CPP
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
#endif
int x;
scanf("%lld",&n);
for(register int i=1;i<=n;i++){
x=read();
int s=ma[x];
ma[x]=i;
//tmp=(tmp+i-1-s+sgt.sum(1,1,n,s+1,i-1)*2+1)%mod;
tmp=(tmp+i-s+sgt.sum(1,1,n,s+1,i-1)*2%mod)%mod;
sgt.add(1,1,n,s+1,i);
ans=(ans+tmp)%mod;
}
printf("%lld
",ans);
return 0;
}
正解
用树状数组……
T3 游戏
题意
小 A 和小 B 正在玩一个游戏：有一棵包含 (n=2m) 个点的有根树（点从 (1sim n)编号），它的根是 (1) 号点，初始时两人各拥有 (m) 个点。游戏的每个回合两人都需要选出一个自己拥有且之前未被选过的点，若对手的点在自己的点的子树内，则该回合自己获胜；若自己的点在对方的点的子树内，该回合自己失败；其他情况视为平局。游戏共进行 (m) 回合。
作为旁观者的你只想知道，在他们随机选点的情况下，第一次非平局回合出现时的回合数的期望值。
为了计算这个期望，你决定对于 (k=0,1,2,cdots,n)计算出第一次非平局回合出现在第 (k) 个回合的情况数。两种情况不同当且仅当存在一个小 A 拥有的点 (x)，小 B 在 (x) 被小 A 选择的那个回合所选择的点不同。
由于情况总数可能很大，你只需要输出答案对 (998244353) 取模后的结果。
(n le 5000)
得分情况
实际得分：没写
改题得分：
正解
大概？是个玄学数学公式+树上DP吧
树上DP可能想的到，不过真的不知道从何下手就没动了……还是太菜了……
考试总结
可能还是考试的时候没有多想
第一题看到旁边人推出来了于是也急了
发现自己的公式可以过样例就直接交了一手也没验证……
然后T2想当然的以为map跑得快……
一开始想过要改成离散化的
但是由于懒了还是没去改……然后得分就这么看脸了…………
T3可能也就没啥心情想做了
没看出暴力怎么打于是就放弃了……
下次考试还是要分配好时间
简单的题目多验证几下
然后还要多考虑优化代码，鬼晓得评测机会出什么玄学事故……