几道数学题目

poj 1026 http://poj.org/problem?id=1026

题意：给你（乱序）数字，数字表示下面输入的字符串变幻的位置。比如说事例给的

10（n）

4 5 3 7 2 8 1 6 10 9

1（k） Hello Bob

1 代表对字符串中每一个字符进行变幻的次数。

变幻的方式就是

1 2 3 4 5 6 7 8 9 10（十个数排完序后）

H e l l o B o b

4 5 3 7 2 8 1 6 10 9

这样经过 1 次变幻后，H到第四个位置（也就是字符串下标为 3 的位置）e变幻到第 5 个位置，依次类推。当然，如果 k 不等于 1,例如 k = 4, H 的变幻路径为 4 -> 7 -> 1 -> 4

e的变幻路径为 2 -> 5 -> 2 -> 5 -> 2依次类推

思路：其实模拟就行了，但是要加一些优化，否则会超时的。从上面可以看出，因为答案只是让求出每个字符的最终位置，可以求出所给的n个数的每一个的循环次数，这样用k取余循环次数，可以减少很多不必要的操作

注意题目输出字符串时要求必须是 n 的长度，样例给的那个输出后面没有多余的空格，真是坑死人了。还有就是每个block后还要再输出一个空行，但是用puts输出就会PE，用printf输出就AC了，上网查了一下区别，只是说puts只是用来输出字符串的，其他的也没查出什么区别

#include <iostream>
#include <math.h>
#include <cstdio>
#include <algorithm>
#include <string.h>
#define N 210
#define _clr(a,val) (memset(a,val,sizeof(a)))

using namespace std;

int tkey[N],key[N];
int tind[N];  //用来保存每个数的循环次数
int tem[N],v[N];// v[i]标记是否已经被计算过，因为在一个循环内的数的循环数是相等的，tem[i]用来记录一个循环内的编号
char str[N],sbr[N];
int cnt;
void get_next(int n)
{
    int i,sum,j;
    int cnt;
    _clr(v,0);
    for(i = 0; i < n; i++)
    {
        if(!v[i])
        {
            for(j = 0; j < n; j++)
            tem[j] = 0;
            v[i] = 1;
            j = i;
            sum = 1;
            cnt = 0;
            while(tkey[i] != key[j])  // 求循环数
            {
                sum++;
                tem[cnt++] = j;
                v[j] = 1;
                j = key[j] - 1;
            }
            v[j] = 1;
            tem[cnt++] = j;
            for(j = 0; j < cnt; j++)
            tind[tem[j]] = sum;
        }
    }
}
void chang(int n,int k)
{
    _clr(sbr,0);
    int i,j,len;
    int temp;
    len = strlen(str);
    if(len < n)
    for(i = len; i < n; i++)
    str[i] = ' ';
    str[i] = '\0';
    for(i = 0; i < n; i++)
    {
        if(k == 1) temp = 1;
        else temp = k % tind[i];
        j = i;
        while(temp > 0)
        {
            if(tkey[i] == key[j]) temp--;   //循环数为 1 时做的处理
            while(tkey[i] != key[j])   // 查找最终的位置
            {
                temp --;
                j = key[j] - 1;
                if(!temp) break;
            }
        }
        sbr[j] = str[i];
    }
    cout<<sbr<<endl;
}
int main()
{
    int n,i,k;
    //freopen("data.txt","r",stdin);
    while(scanf("%d",&n),n)
    {
        for(i = 0; i < n; i++)
        {
            scanf("%d",&key[i]);
            tkey[i] = key[i];
        }
        sort(tkey,tkey + n);
        get_next(n);
        while(scanf("%d",&k),k)
        {
            getchar();
            gets(str);
            chang(n,k);
        }
        //puts("\n");  // 用puts结果总是PE，用printf就AC了
        printf("\n");
    }
    return 0;
}

poj 3270 http://poj.org/problem?id=3270

题意：给出一个含有n 个数的序列，n个数中任意两个可以调换位置，使得目标序列为递增序列，调换位置付出的代价是两个数的和，怎样才能使得总代价最小，输出最小代价值

刘汝佳 黑书 248页有关于这道题目的详细解答

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#define _clr(a,val) (memset(a,val,sizeof(a)))
#define N 10005
#define inf 100001

using namespace std;

int  cow[N],v[N],tcow[N];
int ind[inf];
int main()
{
    int n,i,j,k;
    int sum,minn,ans;
    int tem;
    //freopen("data.txt","r",stdin);
    while(scanf("%d",&n) != EOF)
    {
        //minn = inf;
        /*for(i = 0; i < n; i++)
        {
            v[i] = 0;
            ind[i] = 0;
        }*/
        for(i = 0; i < n; i++)
        {
            scanf("%d",&cow[i]);
            //if(cow[i] < minn) minn = cow[i];
            tcow[i] = cow[i];
            v[i] = ind[i] = 0;
        }
        sort(tcow, tcow + n);
        minn = tcow[0];
        for(i = 0; i < n; i++)
        {
            ind[tcow[i]] = i;
        }
        ans = 0;
        for(i = 0; i < n; i++)
        {
            if(!v[i])
            {
                sum = 0;
                tem = tcow[i];
                j = i, k = 1;
                v[j] = 1;
                while(tcow[i] != cow[j])
                {
                    sum += cow[j];
                    j = ind[cow[j]];
                    v[j] = 1;
                    k++;
                }
                if(k > 1)
                {
                    ans += min(sum + (k - 1) * tem,sum + (k - 1) * minn + 2 * (tem + minn));
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

poj 2409 http://poj.org/problem?id=2409

题意：给你 c 种颜色，s 个弹珠，问可以串出几种不同的手镯。

如果做了poj 的 1286,再来做这道题目，就会觉得很简单了，因为只需改一下输入和计算时用的参数就可以了。 这两道题目是polya定理,置换群的应用中最裸的题目，关键就是如何找每个置换群的循环节数，我也是看的别人的解题报告，知道的如何找循环节数。给出两个参考链接，结合这看，应该是可以能够理解，http://www.cnblogs.com/yongze103/archive/2010/10/05/1842936.html   http://blog.sina.com.cn/s/blog_64d591e80100h8be.html。不过如果想知道那个公式怎么来的，有兴趣的可以去看 组合数学 第四版，或是  符文杰：《Pólya原理及其应用》

#include <iostream>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <algorithm>

using namespace std;

int gcd(int a,int b)
{
    if(!b) return a;
    else return gcd(b,a % b);
}
int main()
{
    int n,i,m;
    long long sum;
    //freopen("data.txt","r",stdin);
    while(cin>>m>>n,n + m)
    {
        sum = 0;
        if(!n)
        {
            cout<<"0\n";continue;
        }
        for(i = 1; i <= n; i++)
        {
            sum +=  (pow(1.0 * m,gcd(n,i)));
        }
        if(n % 2 == 0)
        {
            sum +=  ((pow(1.0 * m, n / 2 ) * (n / 2)));
            sum +=   ((pow(1.0 * m, (n + 2) / 2) * (n / 2)));
        }
        else sum +=  ((pow(1.0 * m, (n + 2) / 2) * n));
        sum = sum / (2 * n);
        printf("%lld\n",sum);
    }
    return 0;
}

poj 1286  http://poj.org/problem?id=1286

#include <iostream>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <algorithm>

using namespace std;

int gcd(int a,int b)
{
    if(!b) return a;
    else return gcd(b,a % b);
}
int main()
{
    int n,i;
    long long sum;
    //freopen("data.txt","r",stdin);
    while(cin>>n,n != -1)
    {
        sum = 0;
        if(!n)
        {
            cout<<"0\n";continue;
        }
        for(i = 1; i <= n; i++)
        {
            sum +=  (pow(3.0,gcd(n,i)));
        }
        if(n % 2 == 0)
        {
            sum +=  ((pow(3.0, n / 2 ) * (n / 2)));
            sum +=   ((pow(3.0, (n + 2) / 2) * (n / 2)));
        }
        else sum +=  ((pow(3.0, (n + 2) / 2) * n));
        sum = sum / (2 * n);
        printf("%lld\n",sum);
    }
    return 0;
}