昨天考试考得有点迷？？？

一看内存限制，T1 64MB T2 16MB 当场懵比.........

T1 set

考场打的背包问题和随机化，其实能randA掉，但不小心数组开小了？？？？（长记性！！！！！）

正解的话因为每个前缀只需mod%n，所以有n+1个数，其中一定有重复的

所以就可以O(n)扫了

其实正解不难就是没有细想

1 #include
      
        2 #define MAXN 1100 3 using namespace std; 4 int read(){ 5     int x=0;char c=getchar(); 6     while(c<'0'||c>'9')c=getchar(); 7     while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();} 8     return x; 9 }10 int n;11 int a[MAXN*MAXN];12 struct node{
    int id,w;}e[1000001];13 int ans[MAXN];14 int pre[MAXN][1001];15 bool biao[2][MAXN];16 void work(){17      for(int i=1;i<=n;++i){18          e[i].id=i;e[i].w=a[i];19      }20      for(int i=1;i<=20000;++i){21          if(clock()>990000){22             printf("-1\n");23             return ;24          }25          random_shuffle(e+1,e+n+1);26          int ok=0;int me=0;27          for(int j=1;j<=n;++j){28              me=(me+(e[j].w%n))%n;29              if(me==0){30                 ok=j;break;31              }32          }33          if(ok==0)continue;34          printf("%d\n",ok);35          for(int j=1;j<=ok;++j)printf("%d ",e[j].id);36          return ;37      }38 }39 signed main(){40     n=read();41     for(int i=1;i<=n;++i){42         a[i]=read();a[i]%=n;43     }44     if(n>1000){45         work();46         return 0;47     }48     int now=1;int last=0;49     biao[last][0]=1;50     for(int i=1;i<=n;++i){51         for(int j=0;j
       
        =1;--i){68         if(pre[i][now]!=0)ans[++ans[0]]=pre[i][now];69         now=(now-a[pre[i][now]]%n+n)%n;        70     }71     if(ans[0]==0){printf("-1\n");return 0;}72     printf("%d\n",ans[0]);73     for(int i=1;i<=ans[0];++i){74         printf("%d ",ans[i]);75     }76     cout<
       
      

1 #include
      
        2 #define MAXN 1100000 3 #define int long long 4 using namespace std; 5 int vis[MAXN];int n,a[MAXN]; 6 signed main(){ 7      scanf("%lld",&n); 8      vis[0]=0; 9      for(int i=1;i<=n;++i){10          scanf("%lld",&a[i]);11      }int sum=0;12      for(int i=1;i<=n;++i){13          sum=(a[i]+sum)%n;14          if(vis[sum]!=0){15             printf("%lld\n",i-vis[sum]);16             for(int j=vis[sum]+1;j<=i;++j){17                 printf("%lld ",j);18             }19             return 0;20          }21          vis[sum]=i;22      }23 }
      

 

T2 read

考场时看出了答案其实就是2*maxn_sum-N-1，至于证明，除非最后时只剩一种类型的书了，不然肯定能接着放

那么我们就可以直接判断了

考场没算清内存其实1e6的数据是可以开数组的

对于正解，定义一个id，cnt

我们对于每个新出现的数，当cnt=0时id=当前数，不然id=当前数cnt++;否则cnt--;

可以发现如果存在解的话，id一定为最大出现次数的值，但是因为可能中间存在非最大值之间互相抵消的情况

所以还要再扫一边，判断当前值出现次数

1 #include
      
        2 #define MAXN 1100 3 #define int long long 4 using namespace std; 5 int M,N,K; 6 int co[MAXN],x[MAXN],y[MAXN],z[MAXN];int a[MAXN]; 7 int maxn_sum=0;int maxn;int S; 8 signed main(){       9       scanf("%lld%lld",&M,&K);10       S=(1<
       
        0){printf("%lld\n",2*cnt-N-1);}43       else printf("0\n");44       /*scanf("%lld",&N);45       int cnt=0;int id=0;46       for(int i=1;i<=N;++i){scanf("%lld",&a[i]);}47       for(int i=1;i<=N;++i){48           long long last=a[i];     49           if(cnt==0){cnt=1;id=last;}50           else if(id==last){cnt++;}51           else if(id!=last){cnt--;}         printf("i=%lld\n",i);  52       }53       if(cnt-1>0)printf("%lld\n",cnt-1);54       else printf("%lld\n",cnt);55       */56 }57 /*58 2259 1 3 3 3 3 2 2 2 2 1 1 1 1 1 1 1 1 1  1 1 1 1 60 */
       
      

 

T3 race

咕了.............

不咕。

一道trie树好题，想了两节课，（在语文课上想题效率很高QAQ）

首先对于x^2的转化：

   既然是排名，我们可以考虑成x^2，是每个大于他的数的集合相乘，即（x1+x2+x3+x4.....）*（x1+x2.......）

（其中每个xi都为1），那么结果可以看成任意一个点对的贡献为一，答案就是点对的个数

既然结果是求异或和，我们联想到trie树（这样说有些牵强.......）

无论如何我们先建棵trie树

那么从1-n的每个i，我们统计这个节点时单独考虑每一位的贡献，我们枚举一个j,一个k

j(k)上的数表示在M-1位到j+1位的数与a[i]的这些位的数相等，那么如果使j，k同时大于a[i]，我们只需

确定好异或的第j，k位上的数，其他数随意，这样这两位上的数对他的贡献就是两个位的指针上的size*(1<<M-2)

当j==k时乘的变成（1<<M-1），因为只需确定一位

 

1 #include
      
        2 #define int long long 3 #define MAXN 210000 4 using namespace std; 5 int fa[MAXN][31]; 6 struct node{ 7      int ch[2]; 8      int size; 9 }t[MAXN*20];int n,M;10 const int mod=1e9+7;11 int tot=1;int a[MAXN];12 void insert(int x){13      int p=1;t[p].size++;fa[x][M]=1;14      for(int i=M-1;i>=0;--i){15          int me=(a[x]>>i)&1;16          if(t[p].ch[me]==0)t[p].ch[me]=++tot;17          p=t[p].ch[me];18          t[p].size++;19          fa[x][i]=p;20      }21 }22 int ans[MAXN];23 void work(int x){24      for(int i=0;i<=M-1;++i){25          int me1=0,find1=0;int me2=0,find2=0;26          for(int j=0;j
       
        >i)&1;me2=(a[x]>>j)&1;28              me1^=1;me2^=1;29              find1=fa[x][i+1];find2=fa[x][j+1];30              ans[x]=(ans[x]+2*t[t[find1].ch[me1]].size*t[t[find2].ch[me2]].size%mod*(1ll<<(M-2ll)))%mod;31          }32          me1=(a[x]>>i)&1;me1^=1;33          find1=fa[x][i+1];34          ans[x]=(ans[x]+t[t[find1].ch[me1]].size*t[t[find1].ch[me1]].size%mod*(1<<(M-1)))%mod;35      }36 }37 int sum=0;38 signed main(){39      scanf("%lld%lld",&n,&M);40      for(int i=1;i<=n;++i){41          scanf("%lld",&a[i]);42      }43      for(int i=1;i<=n;++i){insert(i);}44      for(int i=1;i<=n;++i){work(i);}45      for(int i=1;i<=n;++i){46          sum^=ans[i];47      }48      printf("%lld\n",sum);49 }
       
      

 

 

 

******************************

思路积累：

x^2的转化，

trie树的应用，

比较大小只需考虑每一位的贡献