这次ACM的题感觉思考得太慢了,脑子好久不动,思考能力也下降了

来总结一下做第一题的思路吧

先贴题目

Problem A: zbj的糖果

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 101  Solved: 12
[Submit][Status][Web Board]

Description

现在zbj跟n个小朋友在玩一个游戏。首先,这n个小朋友的编号分别为1,2,3…n,每个小朋友手里都有不同数量的糖果,每个小朋友手里的糖果数量刚好等于他们的编号。

现在他们按顺序围着一张桌子坐下,即 x 的两边分别坐的是x – 1 和 x + 1,n 和 1 相邻。

现在zbj可以从编号为1的小朋友开始,把他们手里的糖果拿走,当然为了游戏乐趣,对于每一轮游戏,zbj决定规定一个数字 k ,表示他每隔 k 个小朋友,就会拿走当前小朋友手里的糖果,当某次又要拿走编号为 1 的小朋友手里的糖果时,他就会停止这轮游戏。

比如有6个小朋友,规定k为4,即n=6,k=4,zbj拿糖果的顺序为:1→5→3→1 

现在zbj想知道,按照这样的游戏规则,最多能拿到手的糖果总数有几种不同的情况?

Input

输入只包含一个正整数n(2<=n<=10^9)表示有n个小朋友。

Output

zbj最后能拿到手里的糖果总数的数量集合,按升序输出,两个数字中间用空格隔开,末尾没有空格。

Sample Input

6

Sample Output

1 5 9 21

HINT

对于样例的解释。有以下6种情况

题目理解:找一下规律就知道,先将所有最小因子求出来,然后列出所有可能的取法

解题代码:

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int coun=0;
ll s[10000];
ll f(int i,int n){
    ll sum=0,t;
    t=n/i;
    sum=t+i*(t-1)*t/2;
    return sum;
}

void g(int pr[],int j,int n,ll s[],ll sum){
   for(int i=0;i<j;i++){
        sum*=pr[i];
        if(sum>=n) {break;}
        if(n%sum!=0) {sum/=pr[i];continue;}
        s[coun++]=f(sum,n);
        g(&pr[i],j-i,n,s,sum);
        sum/=pr[i];
   }
}

int main(){
    int pr[10000];
    int i,j=0,t,n;
    cin>>n;
    t=n;
    for(i=2;i<=t;i++){
        if(t%i==0) {
            while(t%i==0&&t) t/=i;
            pr[j++]=i;
        }
    }
  /*  for(i=0;i<j;i++){
        cout<<pr[i]<<" ";
    }*/
    g(pr,j,n,s,1);
    s[coun++]=f(1,n);
    s[coun++]=1;
    sort(s,s+coun);
    cout<<s[0];
    for(i=1;i<coun;i++){
        cout<<" "<<s[i];
    }
    cout<<endl;
    return 0;
}

有些细节的地方自己以后再来理解一下

测量int数组的正整数个数

一次想用strlen得到int数组内元素个数,发现不行,又查了半天也没找到有类似的对int能计算实际储存个数的函数,就把一些能间接达到效果的奇怪的方法写出来了

#include <bits/stdc++.h>

using namespace std;

int strlen(int a[],int len){
    int coun=0,t;
    t=len;
    while(t--){
        if(a[t]==-1) coun++;
        else break;
    }
    return len-coun;
}
int main(){
    int a[10],len;
    memset(a,-1,sizeof(a)); //数组初始化-1
    a[0]=1;
    a[1]=2;
    a[2]=3;
    a[3]=4;
    cout<<strlen(a,10)<<endl;   //10为数组最大空间
    return 0;
}

这个程序只有效于从0开始的地址连续的自然数

注意在初始化数组为-1后,sizeof(a)会有问题,不能再使用sizeof