考试过程：先读题，然后觉得开题顺序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
