这样大概就是板子问题了

考场的树状数组+二分的60分暴力？？？

 

1 #include
      
        2 #define int long long 3 #define MAXN 11000001 4 int c[MAXN]; 5 int lowbit(int x){
    return x&(-x);}int n; 6 void add(int x,int k) 7 { 8      for(int i=x;i<=n;i+=lowbit(i)) 9      {10          c[i]+=k;11      }12 }13 int query(int x)14 {15      int ans=0;16      for(int i=x;i>=1;i-=lowbit(i))ans+=c[i];17      return ans;18 }19 int second_divied(int l,int r,int x,int last_rs)20 {21 22     while(l+1
       
        >1;25          if(query(mid)-last_rs
        
         =cir)52           {53               pos=second_divied(pos+1,n,cir,last_rs);54               add(pos,-1); 55               pos=find(pos);       56           }57           else if(now_rs-last_rs
        
       
      

 

 

 

对于约瑟夫问题

我们可以知道最后的人一定是升到最后的，他在新的队伍里的编号是零(因为只有一个人，从零开始编号)

然后我们从后往前递推，考虑最后胜利者在上一层的编号直到最后编号

我们假设当前层为4，编号为3

那么在上一层时因为干掉了一个人，那么就从干掉的人的后一个开始编号

所以上一层是在位置6

这样我们得到f[i]表示在第i次操作后胜利者所处的编号

然后就简单了

 

#include
     
      #define MAXN 10000001using namespace std;int T;int n;int ans=0;signed main(){    scanf("%d",&T);    while(T--)    {         scanf("%d",&n);         ans=0;         for(int i=n-1;i>=1;--i)         {             ans=(ans+i)%(n-i+1);         }         printf("%d\n",ans+1);    }}