在 link1 与 link2 两份代码中,后者 RE,前者通过。
而这两份的代码的仅有的差异就是遍历 vector 的方式。在前者我使用 for(int j=0; j<(int)arr[x].size(); j++) {
遍历,后者用 for(int v:arr[x]) {
遍历,产生了不同的结果。请问这是什么导致的?
link1:
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N=8200;
vector<int> arr[N];
int now[N],vis[N];
int main() {
int n; scanf("%d",&n);
vis[0]=1;
for(int i=0; i<8192; i++) now[i]=8191,arr[i].push_back(0);
for(int i=1; i<=n; i++) {
int x; scanf("%d",&x);
for(int j=0; j<(int)arr[x].size(); j++) {
int v=arr[x][j],w=v^x; vis[w]=1;
while(now[w]>x) arr[--now[w]].push_back(w);
}
arr[x].clear();
}
int cnt=0;
for(int i=0; i<8192; i++) cnt+=vis[i];
printf("%d\n",cnt);
for(int i=0; i<8192; i++) if(vis[i]) printf("%d ",i);
printf("\n");
return 0;
}
link2:
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N=8200;
vector<int> arr[N];
int now[N],vis[N];
int main() {
int n; scanf("%d",&n);
vis[0]=1;
for(int i=0; i<8192; i++) now[i]=8191,arr[i].push_back(0);
for(int i=1; i<=n; i++) {
int x; scanf("%d",&x);
for(int v:arr[x]) {
int w=v^x; vis[w]=1;
while(now[w]>x) arr[--now[w]].push_back(w);
}
arr[x].clear();
}
int cnt=0;
for(int i=0; i<8192; i++) cnt+=vis[i];
printf("%d\n",cnt);
for(int i=0; i<8192; i++) if(vis[i]) printf("%d ",i);
printf("\n");
return 0;
}