P1282 & P1131 & P1090 & P1307 & P1095

P1282

*描述: *

一共有n个人（以1–n编号）向佳佳要照片，而佳佳只能把照片给其中的k个人。佳佳按照与他们的关系好坏的程度给每个人赋予了一个初始权值W[i]。然后将初始权值从大到小进行排序，每人就有了一个序号D[i]（取值同样是1–n）。按照这个序号对10取模的值将这些人分为10类。也就是说定义每个人的类别序号C[i]的值为(D[i]-1) mod 10 +1，显然类别序号的取值为1–10。第i类的人将会额外得到E[i]的权值。你需要做的就是求出加上额外权值以后，最终的权值最大的k个人，并输出他们的编号。在排序中，如果两人的W[i]相同，编号小的优先。

n<=50 000，k<=2000，给出的所有正整数都不超过32767。

输入:

第一行输出用空格隔开的两个整数，分别是n和k。

第二行给出了10个正整数，分别是E[1]到E[10]。

第三行给出了n个正整数，第i个数表示编号为i的人的权值W[i]。

输出:

只需输出一行用空格隔开的k个整数，分别表示最终的W[i]从高到低的人的编号。

实例：

输入：
10 10
1 2 3 4 5 6 7 8 9 10
2 4 6 8 10 12 14 16 18 20

输出：
10 9 8 7 6 5 4 3 2 1
  • 这题其实很水，关键是知道结构体数组的排序怎么写，然后判断一下就OK了

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#define MAX 50005
using namespace std;
int n, k;
int E[MAX];
typedef struct Person{
    int num;
    int W;
    int D;
    int C;
}P;
P people[MAX];
bool cmp1(const P &a, const P &b){
    if (a.W != b.W)
        return a.W > b.W;
    else
        return a.num < b.num;
}

int main(int argc, const char * argv[]) {
    cin >> n >> k;
    for (int i=1; i<=10; i++)
        cin >> E[i];
    for (int i=1; i<=n; i++){
        cin >> people[i].W;
        people[i].num = i;
    }
    sort(people+1, people+n+1, cmp1);
    for (int i=1; i<=n; i++){
        people[i].C = (i-1) % 10 +1;
        people[i].W += E[people[i].C];
    }
    sort(people+1, people+n+1, cmp1);
    for (int i=1; i<=k; i++){
        if (i<=k-1)
            cout<<people[i].num<<" ";
        else
            cout<<people[i].num<<endl;
    }
    return 0;
}

P1131

*描述: *

输入二个正整数x0,y0(2≤x0≤100000，2≤y0≤1000000)，求出满足下列条件的P、Q的个数。

条件:1.P、Q是正整数
2.要求P、Q以xO为最大公约数，以yO为最小公倍数。

试求，满足条件的所有可能的两个正整数的个数。

输入:

两个正整数

输出:

满足条件的所有可能的两个正整数的个数

实例：

输入：
3 60

输出：
4
  • 这题关键是需要利用LMD和GCD之间的关系，LMD=(ai*aj)/GCD，使用LMD除以GCD之后，寻找互质的ai和aj即可；
  • 但是这题非常的水，我只用了改变步长的方式就可以直接完成

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#define MAX 50005
using namespace std;
int x, y;

int Max_Com_Divisor(int x, int y){
    while (x * y){
        if (x > y)//将较大数模较小数的结果（余数）赋给较大的值，直到两个数相等
            x %= y;
        else if(x < y)
            y %= x;
    }
    return x > y ? x : y;
}
int main(int argc, const char * argv[]) {
    cin >> x >> y;
    int res = 0;
    for (int i=x; i<=y; i+=x){
        for (int j=i+x; j<=y; j+=x) {
            int max_com_div = Max_Com_Divisor(i,j);
            int min_com_mult = (i * j)/max_com_div;
            if (max_com_div==x && min_com_mult==y)
                res++;
        }
    }
    cout<<2*res<<endl;
    return 0;
}

P1282

*描述: *

有n个正整数排成一行。你的目的是要从中取出一个或连续的若干个数，使它们的和能够被k整除。

例如，有6个正整数，它们依次为1、2、6、3、7、4。若k=3，则你可以取出1、2、6，或者2、6、3、7，也可以仅仅取出一个6或者3使你所取的数之和能被3整除。当然，满足要求的取法不止以上这4种。事实上，一共有7种取法满足要求。

给定n和k，以及这n个数。你的任务就是确定，从这n个数中取出其中一个数或者若干连续的数使它们的和能被k整除有多少方法。

由于取法可能很多，因此你只需要输出它mod 1234567的值即可。

输入:

第一行有两个正整数，分别代表n和k。输入数据保证有n<=500 000，k<=100 000。

以下n行每行一个正整数。这些正整数保证都不大于10 000。

输出:

一个正整数。它应该是你的答案mod 1234567的结果。

实例：

输入：
6 3
1
2
6
3
7
4

输出：
7
  • 这题我开始觉得很难，因为毕竟不能直接用n^2来做。但是经过bzb大神指点，发现其实很简单；
  • 算法课上李清勇说过，枚举，你要么改变枚举的对象，要么改变枚举的过程；
  • 那这一题就是改变枚举的对象，因为最后都是模k，所以如果结果都模k的话，就在0->k-1之间，就会比较容易搞定了；
  • 具体的思路就是，假设Sn=a1+…+an，那么如果中间有一段满足要求的话，必然要求Si和Sj之差为k的倍数。因此，如果直接将每一个Si都模k之后，直接寻找有多少组一样的即可，比如多少组为0……多少组为k-1，利用数组统计即可，毕竟都可以直接进行计算Cij什么的对吧。

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#define MAX 500005
using namespace std;
long long n;
long long k;
long long int res[MAX];
long long int a[MAX];
int ticket[MAX];
int main(int argc, const char * argv[]) {
    cin >> n >> k;
    for (int i=0; i<n; i++)
        cin >> a[i];
    res[0] = a[0];
    for (int i=1; i<n; i++)
        res[i] = res[i-1] + a[i];
    for (int i=0; i<n; i++){
        res[i] = res[i] % k;
        ticket[res[i]]++;
    }
    long sum = ticket[0] % 1234567;
    for (int i=0; i<k; ++i){
        sum += ticket[i] * (ticket[i] - 1) / 2;
        sum = sum % 1234567;
    }
    cout<<sum<<endl;
    
    return 0;
}

P1307

*描述: *

一天他不务正业出去耍，看见街上的地板是由很多小的正方形组成，顿时心里突发奇想想要总结一下到底有多少正方形。。。。

于是乎，他狠下心数了数，终于翻山越岭知道了正方形的总边长为N，你的目的是找出在可以组成的每个至少边为1的正方形的个数。(因为黑皮太笨了，无法找到)。。

输入:

自然数(0<=n<=32767)

输出:

一个数，即正方形的总数

实例：

输入：
2

输出：
5
  • 这题水到不像话，直接1^2+…+n^2即可（为什么我做的都是水题，废话，因为我菜啊）

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#define MAX 500005
using namespace std;
int n;
long long int sum;
int main(int argc, const char * argv[]) {
    cin >> n;
    for (int i=1; i<=n; i++){
        sum += i * i;
    }
    cout<<sum<<endl;
    return 0;
}

P1095

*描述: *

n个人排成一圈。从某个人开始，按顺时针方向依次编号。从编号为1的人开始顺时针“一二一”报数，报到2的人退出圈子。这样不断循环下去，圈子里的人将不断减少。由于人的个数是有限的，因此最终会剩下一个人。试问最后剩下的人最开始的编号。

输入:

一个正整数n，表示人的个数。输入数据保证数字n不超过100位。

输出:

一个正整数。它表示经过“一二一”报数后最后剩下的人的编号。

实例：

输入：
9

输出：
3

  • 这题就相当的有意思了，如果直接读的话肯定不行的，因为n有高达100位，所以你需要使用高精度运算，你得自己去写，就非常非常麻烦；

  • 但是！！如果你愿意计算的话，你会发现结果非常的优美11313513579….；

  • 看出规律了吗？

    1

    13

    135

    1357

    ……

  • 是不是惊呆了！我也是。

  • 接下来，两行代码就搞定！

代码：

n = int(input())
print(int(bin(n).replace('1','0',1), 2)<<1|1)

补充：

关于约瑟夫环问题，我认真的看了一下，觉得非常优美，我决定记录一下

问题描述

>约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。
>例如只有三个人，把他们叫做A、B、C，他们围成一圈，从A开始报数，假设报2的人被杀掉。
>
>​    首先A开始报数，他报1。侥幸逃过一劫。
>​    然后轮到B报数，他报2。非常惨，他被杀了
>​    C接着从1开始报数
>​    接着轮到A报数，他报2。也被杀死了。
>​    最终胜利者是C

解决方案

普通方案

​ 刚学数据结构的时候，我们可能用链表的方法去模拟这个过程，N个人看作是N个链表节点，节点1指向节点2，节点2指向节点3，……，节点N-1指向节点N，节点N指向节点1，这样就形成了一个环。然后从节点1开始1、2、3……往下报数，每报到M，就把那个节点从环上删除。下一个节点接着从1开始报数。最终链表仅剩一个节点。它就是最终的胜利者。

图片名称

递推

约瑟夫环是一个经典的数学问题，我们不难发现这样的依次报数，似乎有规律可循。为了方便导出递推式，我们重新定义一下题目。
问题： N个人编号为1，2，……，N，依次报数，每报到M时，杀掉那个人，求最后胜利者的编号。

这边我们先把结论抛出了。之后带领大家一步一步的理解这个公式是什么来的。
递推公式：

​ F(N,M)=(F(N−1,M)+M)%N

  • F(N,M)表示，N个人报数，每报到M时杀掉那个人，最终胜利者的编号
  • F(N−1,M)表示，N-1个人报数，每报到M时杀掉那个人，最终胜利者的编号

解释一下

问题1：假设我们已经知道11个人时，胜利者的下标位置为6。那下一轮10个人时，胜利者的下标位置为多少？
答：其实吧，第一轮删掉编号为3的人后，之后的人都往前面移动了3位，胜利这也往前移动了3位，所以他的下标位置由6变成3。

问题2：假设我们已经知道10个人时，胜利者的下标位置为3。那下一轮11个人时，胜利者的下标位置为多少？
答：这可以看错是上一个问题的逆过程，大家都往后移动3位，所以f(11,3)=f(10,3)+3
f(11,3)=f(10,3)+3。不过有可能数组会越界，所以最后模上当前人数的个数，f(11,3)=（f(10,3)+3）%11
f(11,3)=（f(10,3)+3）%11

问题3：现在改为人数改为N，报到M时，把那个人杀掉，那么数组是怎么移动的？
答：每杀掉一个人，下一个人成为头，相当于把数组向前移动M位。若已知N-1个人时，胜利者的下标位置位f(N−1,M)
f(N−1,M)，则N个人的时候，就是往后移动M为，(因为有可能数组越界，超过的部分会被接到头上，所以还要模N)，既f(N,M)=(f(N−1,M)+M)%n
f(N,M)=(f(N−1,M)+M)%n

注：理解这个递推式的核心在于关注胜利者的下标位置是怎么变的。每杀掉一个人，其实就是把这个数组向前移动了M位。然后逆过来，就可以得到这个递推式。

是不是有点明白了？

再上一张图，就更明白了：

忽略绿色的一行，黄色的表示要被杀的，每一行表示现在存在的人的编号

如果将上面表格的每一行看成数组，这个公式描述的是：幸存者在这一轮的下标位置

  • F(1,3)：只有1个人了，那个人就是获胜者，他的下标位置是0F(2,3)=(F(1,3)+3)%2=3%2=1
  • F(2,3)=(F(1,3)+3)%2=3%2=1：在有2个人的时候，胜利者的下标位置为1
  • F(3,3)=(F(2,3)+3)%3=4%3=1：在有3个人的时候，胜利者的下标位置为1
  • F(4,3)=(F(3,3)+3)%4=4%4=0：在有4个人的时候，胜利者的下标位置为0
    ……
  • F(11,3)=6
  • F(11,3)=6

怎么样，是不是很清晰了？