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

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;
}

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

#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; }

分类： ACM题解

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