总结
这次 ( t ARC) 因为 (A,B) 一直 ( t Wa) 心态直接起飞，根本就无心做题了。
可能 (2000+) 就是我所背负的包袱，我总是为了涨分去打比赛，所以签到题做不出自然心态就炸了。但比赛的真正目的在于参与啊，如果你一直把附加的东西看得那么重，会失去它本身的乐趣了。
如果 ( t noip) 我也做不出来签到题会怎样？也就失去了一次机会罢了，根本就没有老师们说得那么严重，我只想说不要因为结果而丧失了过程中的乐趣。
据说情绪不稳定是有抑郁倾向，那我打比赛时一直大吼大叫是怎么回事，还是要多打球啊
还有打比赛时不要跳签到题，心态会有很大影响
要不下次我先开后面的题，如果做不出来就不交了
(A)：去掉多余的限制，如果操作偶数次等价于不操作可以转异或。
(B)：找不变量，球模 (3) 余数永远不变，根据必要条件构造即可。
补记：后两题有时间再补 (...)
C.Max Dot
题目描述
解法
设 (sum[i]) 表示后 (i) 个元素的和，如果不考虑 (m) 的限制那么我们肯定选取 (frac{sum[i]}{i}) 的后缀无脑增大即可。
考虑 (m) 的限制，这时候我们贪心增大后缀可能导致某些元素大于 (m)，怎么办呢？设最优后缀是 (p)，那么我们知道的信息只有后缀 (p) 的 (x) 值等于 (m) 了，也就是我们可以确定一段后缀的取值，那么自然就得到了子问题。
暴力递归子问题时间复杂度 (O(n^2))，可以用凸包提前确定子问题，时间复杂度 (O(n))
#include <cstdio>
const int M = 5005;
#define int long long
#define db double
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,k;db b[M],c[M],s,ans;
signed main()
{
n=read();m=read();s=read();
for(int i=1;i<=n;i++)
{
int x=read();
b[++k]=x;c[k]=1;
while(k>1 && b[k]*c[k-1]<=b[k-1]*c[k])
{
b[k-1]+=b[k];
c[k-1]+=c[k];
k--;
}
}
for(int i=k;i>=1;i--)
{
if(m*c[i]<=s)
{
ans+=b[i]*m;
s-=m*c[i];
}
else
{
ans+=b[i]*(s/c[i]);
break;
}
}
printf("%.8f
",ans);
}
D.Neq Neq
题目描述
解法
这道题我明明会做啊，怎么比赛时就是没搞出来啊(...)
设 (dp[i]) 表示前 (i) 个元素可能形成的集合个数，显然我们只需要枚举一段后缀 ([j,i])，使得 ((j,i)) 全部都被删除，然后可以递归到子问题了。
先找一些必要条件，比如有两个相邻相等的元素存在于 ([j,i]) 中那么根本删不动。然后考虑 (len=2,3) 可以特殊处理。考虑 (1,2,1,2) 这种情况，也就是种类 (=2) 的情况也是删不动的。
那么种类 (=3) 删得动吗？我们找到一对三个互不相同的相邻元素 ((a,b,c))，若删去 (b) 之后任然满足种类 (=3) 则删去，否则一定是 (...x,y,x,a,y,x,y...) 这种形式，以 (a) 为端点暴力删即可。
那么搞两个指针分别维护元素种类和相邻不等的条件，简单前缀和就可以做到 (O(n))
#include <cstdio>
const int M = 200005;
const int MOD = 998244353;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,a[M],b[M],dp[M],sum[M];
signed main()
{
n=read();dp[0]=1;
int j=0,k=1,cnt=0;
for(int i=1;i<=n;i++)
{
a[i]=read();
dp[i]=dp[i-1];//do nothing
if(a[i]==a[i-1]) j=i-1;
if(i>2 && a[i]!=a[i-1] && a[i-1]!=a[i-2])
dp[i]=(dp[i]+dp[i-2])%MOD;
//
if(b[a[i]]==0) cnt++;
b[a[i]]++;
while(k<i-2 && cnt>=3)
{
b[a[k]]--;
if(b[a[k]]==0) cnt--;
k++;
}
//
if(j<k) dp[i]+=sum[k-1]-sum[j];
dp[i]=(dp[i]%MOD+MOD)%MOD;
sum[i]=(sum[i-1]+dp[i])%MOD;
}
printf("%d
",dp[n]);
}