考试过程：先读题，然后觉得开题顺序1 4 2 3。
首先是T1，要是不考虑重复这题很简单，但是考虑重复就比较复杂了，我打完，对拍完差不多用了两个小时，然后就是忘了算内存，结果内存爆了，\(100pts ->30pts\),气炸我了。
然后是T4，我将题意化简为一个式子，\(\sum_{i=l}^{r}max(a_{i-k} -> a_i)\),但是我想了半天不会化简。
然后是T2，T3，我没什么思路，就打了个暴力。
期望得分：\(100+30+30+30=190\)
实际得分：\(30+0+30+30=90\)
考试总结：1.打完题后一定要算内存！！！尤其是花了一些时间想出的正解，不然时间就白费了。
2.打完题后可以想一些时间和空间的优化。
T1 F
思路：因为要让所有数异或出来的值相等，很容易想到求出交集，那么这道题的解题步骤分为两步：
1.求出所有数异或的交集
2.判断里面的数字是否合法
我们先从简单的问题入手，假设里面不存在相同的数字，那么只需要\(n^2\)扫一遍统计答案即可。
现在考虑如果有重复出现的数字，造成的影响。主要有三个方面：
1.类似于 \(A: 1,1,3\),\(B: 6,4,7\),那么\(1 xor 4=5,3xor7=5\),但是只有一个\(4\),也就是出现了一对多的情况
2.类似于\(A:1,2\),\(B: 2,2\) ,其中\(1xor2\)和\(2xor2\)都出现了两遍，但是却不是交集。
3..类似于\(A:1,1\),\(B: 2,2\),A数列和B数列出现了相同的数字，且可能合法的情况
首先解决问题1：我们对于一个\(i\)，利用一个\(set\)记录用当前\(A_i\)可以组成的值，如果出现过了就直接\(continue\)
那么其实解决了问题1，剩下两个问题就都解决了，证明是显然的。
最后注意，一定要算好内存！！！！
代码如下：
AC_code
#include<bits/stdc++.h>
#define re register int
#define ii inline int
#define iv inline void
using namespace std;
const int N=2010;
struct node
{
int val,sum;
}cun[N*N];
unordered_map<int,int> mp;
priority_queue<int,vector<int>,greater<int> > Q;
int n,cnt,ans,timi;
int a[N],b[N],hs[N*N];
unordered_set<int> S;
ii read()
{
int x=0;char ch=getchar();bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
int main()
{
freopen("f.in","r",stdin),freopen("f.out","w",stdout);
n=read();
for(re i=1;i<=n;i++) a[i]=read();
for(re i=1;i<=n;i++) b[i]=read();
int tmp,p;
for(re i=1;i<=n;i++)
{
S.clear();
for(re j=1;j<=n;j++)
{
tmp=a[i]^b[j];
if(S.find(tmp)==S.end())
{
S.insert(tmp);
if(mp.find(tmp)==mp.end())
{
mp[tmp]=++timi;
cun[timi].val=tmp;
cun[timi].sum++;
hs[timi]=i;
}
else
{
int p=mp[tmp];
if(hs[p]!=i)
{
hs[p]=i;
cun[p].sum++;
}
}
}
else continue;
}
}
for(re i=1;i<=timi;i++) if(cun[i].sum>=n) Q.push(cun[i].val);
if(!Q.size()) printf("0\n");
else
{
printf("%d\n",(int)Q.size());
while(!Q.empty())
{
printf("%d\n",Q.top());
Q.pop();
}
}
return 0;
}
T2 S
思路：看到数据范围，猜测应该是\(n^3\)的DP
我们设\(f_{i,j,k,0/1/2}\),表示当前选了\(i\)个\(R\),\(j\)个\(G\),\(k\)个\(Y\),结尾为\(R/G/Y\)的最小步数。
\(g_{0/1/2,k}\)表示原序列第\(k\)个\(R/G/Y\)的位置
那么转移就是\(f_{i+1,j,k,0}=min(f_{i+1,j,k,0,min(f_{i,j,k,1},f_{i,j,k,2})+abs(g_{0,i+1}-(i+j+k+1)})\)
最后记得将\(ans/2\)
代码如下：
AC_code
#include<bits/stdc++.h>
#define re register int
#define ii inline int
#define iv inline void
using namespace std;
const int N=210;
int n,ans;
char s[N*2];
int f[N][N][N][3],g[3][N*2];
ii read()
{
int x=0;char ch=getchar();bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
int main()
{
freopen("s.in","r",stdin),freopen("s.out","w",stdout);
n=read();
scanf("%s",s+1);
for(re i=1;i<=n;i++)
{
if(s[i]=='R') g[0][++g[0][0]]=i;
else if(s[i]=='G') g[1][++g[1][0]]=i;
else if(s[i]=='Y') g[2][++g[2][0]]=i;
}
if(g[0][0]>n/2 or g[1][0]>n/2 or g[2][0]>n/2) {printf("-1\n");return 0;}
memset(f,0x3f,sizeof(f));
for(re i=0;i<3;i++) f[0][0][0][i]=0;
for(re len=0;len<=n;len++)
{
for(re i=0;i<=min(len,g[0][0]);i++)
{
for(re j=0;j<=g[1][0] and i+j<=len;j++)
{
if(len-i-j>g[2][0] ) continue;
if(i+1<=g[0][0]) f[i+1][j][len-i-j][0]=min(f[i+1][j][len-i-j][0],min(f[i][j][len-i-j][1],f[i][j][len-i-j][2])+abs(len+1-g[0][i+1]));
if(j+1<=g[1][0]) f[i][j+1][len-i-j][1]=min(f[i][j+1][len-i-j][1],min(f[i][j][len-i-j][0],f[i][j][len-i-j][2])+abs(len+1-g[1][j+1]));
if(len-i-j+1<=g[2][0]) f[i][j][len-i-j+1][2]=min(f[i][j][len-i-j+1][2],min(f[i][j][len-i-j][0],f[i][j][len-i-j][1])+abs(len+1-g[2][len-i-j+1]));
}
}
}
for(re i=0;i<3;i++) ans=min(f[g[0][0]][g[1][0]][g[2][0]][0],min(f[g[0][0]][g[1][0]][g[2][0]][1],f[g[0][0]][g[1][0]][g[2][0]][2]))>>1;
printf("%d\n",ans);
return 0;
}
T3 Y
咕咕咕
T4 O
思路：这里有一个结论，对于随机数据，一个单调栈里的元素个数为\(log2(n)\)个。
那么对于这道题，我们对于每个点维护一个单调递减的单调栈，栈里维护两个信息，一个是权值，另一个是时间。
这样我们在开一个\(vector\)数组记录每个时刻要在线段树更新的值，然后计算答案即可。
代码如下：
AC_code
#include<bits/stdc++.h>
#define ll long long
#define re register int
#define ii inline int
#define iv inline void
#define f() cout<<"fuck"<<endl
#define head heeead
#define next neet
using namespace std;
const int N=2e5+10;
struct CUN
{
int id,t,l,r;
}cun[N];
struct node
{
int val,timi;
friend bool operator < (node x,node y){return x.timi<y.timi;}
};
int cnt,sta[N];
vector<pair<int,int> >v[N];
int n,q;
int a[N];
long long ans[N];
ii read()
{
int x=0;char ch=getchar();bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
inline bool com(CUN x,CUN y) {return x.t<y.t;}
struct Segment_Tree
{
#define lc (rt<<1)
#define rc (rt<<1|1)
#define mid ((l+r)>>1)
ll sum[N<<2];
//iv pp(int rt) {sum[rt]=sum[lc]+sum[rc];}
iv build(int rt,int l,int r)
{
if(l==r)
{
sum[rt]=a[l];
return;
}
build(lc,l,mid),build(rc,mid+1,r);
sum[rt]=sum[lc]+sum[rc];
}
iv change(int rt,int l,int r,int p,int z)
{
if(l==r)
{
sum[rt]=z;
return;
}
if(mid>=p) change(lc,l,mid,p,z);
else change(rc,mid+1,r,p,z);
sum[rt]=sum[lc]+sum[rc];
}
ll query(int rt,int l,int r,int L,int R)
{
if(L<=l and r<=R) return sum[rt];
if(mid>=R) return query(lc,l,mid,L,R);
if(mid<L) return query(rc,mid+1,r,L,R);
return query(lc,l,mid,L,R)+query(rc,mid+1,r,L,R);
}
#undef lc
#undef rc
#undef mid
}T;
signed main()
{
freopen("o.in","r",stdin),freopen("o.out","w",stdout);
n=read(),q=read();
for (re i=1;i<=n;++i)
{
a[i] = read ();
while (cnt && a[i] >= a[sta[cnt]]) cnt -- ;
for (re j=1;j <= cnt; ++ j) v[i - sta[j]].push_back (make_pair(i,a[sta[j]]));
sta[++cnt] = i;
}
T.build (1,1,n);
for(re i=1;i<=q;i++) cun[i]=(CUN){i,read(),read(),read()};
sort(cun+1,cun+q+1,com);
int now=1;
for(re i=0;i<=n;i++)
{
for(re j=0;j<v[i].size();j++) T.change(1,1,n,v[i][j].first,v[i][j].second);
while(cun[now].t==i) {ans[cun[now].id]=T.query(1,1,n,cun[now].l,cun[now].r);++now;}
}
for(re i=1;i<=q;i++) printf("%lld\n",ans[i]);
return 0;
}