比赛时看完了 4 5 6 题，第四题感觉是线段树，想等会儿让HG 写，5 题没看懂，是后来LM给我讲的，所以一开始一直在研究 6，等LM 跟HG的题都过了，6 的样例还是没出来，然后跟LM一起想，还是没思路，决定去看别的题了，最后HG说可能是置换群的题目，他说他正好刚刷过去，说让他想吧，比完赛一看确实是有关置换的，但我们还是没做出来，5 后来到是猜到了一点的意思，但是看了题解后我才知道自己是多么的无知，竟然想着用打表的方式过，比赛还是充分体现了自己没学到的很多，学到了不会用的也很多，多做多练思路是很有必有的

下面都是比赛时过题较多的，做过的无视就可以了

题目：

题意：给出一些点坐标，表示这个点上有物体价值为val，需要的时间为 tim，问在给定的时间内可以获得的最大价值，有一个限制，如果在一条线上的获取宝贝必须按顺序来

思路：把给的点先进行排序，然后统计出斜率相同的，然后再重新处理价值和时间，在进行二维背包

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #define N 21010 #define inf 10000000011 #define _clr(a,val) (memset(a,val,sizeof(a)))12 13 using namespace std;14 15 struct node16 {17 int x;18 int y;19 int val;20 int tim;21 int dis;22 }point[N];23 int val[N][N],tim[N][N];24 bool vis[N];25 int back[N][N];26 int dp[N * N]; 27 bool cmp(node a,node b)28 {29 return a.dis < b.dis;30 }31 bool dist(node a,node b)32 {33 if(a.x * b.y == a.y * b.x) return true;34 else return false;35 }36 int main()37 {38 int i,j,k;39 int n,t;40 int cs = 0;41 //freopen("data.txt","r",stdin);42 while(scanf("%d%d",&n,&t) != EOF)43 {44 for(i = 0; i < n; i++)45 {46 scanf("%d%d%d%d",&point[i].x,&point[i].y,&point[i].tim,&point[i].val);47 point[i].dis = point[i].x * point[i].x + point[i].y * point[i].y; // 排序时的参数48 }49 sort(point,point + n,cmp);50 _clr(vis,0);51 _clr(back,0);52 int num = 0;53 for(i = 0; i < n; i++)54 {55 if(!vis[i])56 {57 num++; 58 for(j = i; j < n; j++)59 {60 if(!vis[j])61 {62 if(dist(point[i],point[j]) == true) // 统计斜率相同的点63 {64 vis[j] = true;65 back[num][0]++; // 保存个数66 back[num][back[num][0]] = j; // 保存第几个点67 }68 }69 }70 }71 }72 for(i = 1; i <= num; i++)73 {74 val[i][0] = 0;75 tim[i][0] = 0;76 for(j = 1; j <= back[i][0]; j++)77 {78 val[i][j] = val[i][j - 1] + point[back[i][j]].val; // 重新计算价值和时间79 tim[i][j] = tim[i][j - 1] + point[back[i][j]].tim;80 }81 }82 _clr(dp,0);83 for(i = 1; i <= num; i++)84 {85 for(j = t; j >= 0; j--)86 {87 for(k = 0; k <= back[i][0]; k++)88 {89 if(j >= tim[i][k])90 {91 dp[j] = max(dp[j],(dp[j - tim[i][k]] + val[i][k])); // 背包92 }93 }94 }95 }96 printf("Case %d: %d\n",++cs,dp[t]);97 }98 return 0;99 }
             
            
           
          
         
        
       
      

题目：

题意：给一个n 让你求 第n个非平方数，并求出 从 1 到 n 的

 这个值，也就是 开方不大于 i 的正整数

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5  6 using namespace std; 7  8 typedef long long ll; 9 ll capow(ll x)10 {11     return x * x;12 }13 int main()14 {15     ll i,j;16     int t;17     ll n;18     //int n;19     //freopen("data.txt","r",stdin);20     scanf("%d",&t);21     while(t--)22     {23         cin>>n;24         i = 1;25         ll sum = 0;26         while(1)27         {28             if(n < capow(i + 1) - capow(i) - 1)29             break;30             else31             {32                 sum += (capow(i + 1) - capow(i)) * i;  // 根据给的公式，i 到 i + 1之间的数，除了 （i + 1) 开方 等于 (i + 1) 其他的都等于 i33                 n -= capow(i + 1) - capow(i) - 1;   //  (i + 1) 平方 到 i 平方之间的数全部为非平方数，这样不断的去降 n 34                 i++;35             }36         }37         int temp = i;38         if(n == 0)   39         {40             i = capow(i) - 1;41             cout<
          <<" "<
           
            <
            
              i) // 处理剩余的没有加的数54 {55 tem = tem - capow(temp) + 1;56 sum += temp * tem;57 }58 cout<
             <<" "<
              
               <
              
            
           
         
        
       
      

题目：

这个本来就是看标程才懂的，所以还是贴别人的讲解吧     循环节的长度为各独立置换环长度的最小公倍数。问题即求相加和为N的正整数的最小公倍数的可能数。由于1不影响最小公倍数，问题转化为相加小于等于N的若干正整数的最小公倍数的可能数。 如果这些正整数包含大于一个质因子，只会使得正整数的和更大。 因而问题再次转化为相加小于等于N的若干质数的最小公倍数的可能数。  N<1000,于是可递推得，标程用记忆化搜索实现的。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #define _clr(a,val) (memset(a,val,sizeof(a))) 6  7 using namespace std; 8  9 typedef long long ll;10 ll dp[210][1200];11 ll prim[210], num;12 int vis[1010];13 void is_prim(int n)14 {15     int i,j,k;16     for(i = 2; i <= n; i++)17     {18         if(vis[i] == 0)19         {20             prim[num ++] = i;21         }22         for(j = 0, k = i * prim[j]; j <= num && k <= n; j++,k = i * prim[j])23         {24             vis[k] = 1;25             if(i % prim[j] == 0) break;26         }27     }28 }29 ll cal(int x,int n)30 {31     if(x == num) return 1;32     if(dp[x][n] != -1) return dp[x][n];33     dp[x][n] = cal(x + 1,n);34     ll ans = prim[x];35     while(ans <= n)36     {37         dp[x][n] += cal(x + 1,n - ans);38         ans *= prim[x];39     }40     return dp[x][n];41 }42 int main()43 {44     int n;45     while(scanf("%d",&n) != EOF)46     {47         _clr(vis,0);48         num = 0;49         is_prim(n);50         _clr(dp,-1);51         cout<
          
           <
          
         
        
       
      

题目：

思路：题解上是这样解释的本题为Lucas定理推导题，我们分析一下 C(n,m)%2,那么由lucas定理，我们可以写成二进制的形式观察，比如 n=1001101，m是从000000到1001101的枚举，我们知道在该定理中   C(0,1)=0,因此如果n=1001101的0对应位置的m二进制位为1那么C(n,m) % 2==0,因此m对应n为0的  位置只能填0，而1的位置填0，

1都是1（C(1,0)=C(1,1)=1)，不影响结果为奇数，并且保证不会出n的范围，因此所有的情况即是n中1位置对应m位置0，1的枚举，那么结果很明显就是：2^(n中1的个数)

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5  6 using namespace std; 7  8 typedef long long ll; 9 int main()10 {11     int i,j;12     ll sum;13     int n;14     while(scanf("%d",&n) != EOF)15     //while(cin>>n)16     {17         int num = 0;18         while(n)19         {20             if(n % 2) num ++;21             n /= 2;22         }23         sum = pow(2,num);24         printf("%I64d\n",sum);25         //cout<
          
           <