1007 正整数分组 1010 只包含因子2 3 5的数 1014 X^2 Mod P 1024 矩阵中不重复的元素 1031 骨牌覆盖

1007 正整数分组

将一堆正整数分为2组，要求2组的和相差最小。

例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。

Input

第1行：一个数N，N为正整数的数量。

第2 - N+1行，N个正整数。

(N <= 100, 所有正整数的和 <= 10000)

Output

输出这个最小差

Input示例

Output示例

1
这题不就是小李打怪兽吗，不知道谁模仿谁，呵呵，刚还是我编的题里的，dp，证明一下（要证明什么自己考虑）。

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 #include<cmath>

 #include<cstring>

 using namespace std;

 int n,sum;

 bool boo[];

 int main()

 {

     scanf("%d",&n);

     boo[]=true,sum=;

     int x;

     for (int i=;i<=n;i++)

     {

         scanf("%d",&x);

         for (int j=;j>=x;j--)

             if (boo[j-x]) boo[j]=true;

         sum+=x;

     }

     int i=sum/,j=sum-i;

     while (!boo[i]||!boo[j]) i--,j++;

     printf("%d\n",j-i);

 }

1010 只包含因子2 3 5的数

K的因子中只包含2 3 5。满足条件的前10个数是：2,3,4,5,6,8,9,10,12,15。

所有这样的K组成了一个序列S，现在给出一个数n，求S中 >= 给定数的最小的数。

例如：n = 13，S中 >= 13的最小的数是15，所以输出15。

Input

第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000)

第2 - T + 1行：每行1个数N(1 <= N <= 10^18)

Output

共T行，每行1个数，输出>= n的最小的只包含因子2 3 5的数。

Input示例

Output示例

2

8

15

36

80
枚举处理出在范围内的所有满足条件的数+排序，然后二分找答案就可以了。

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 #include<cmath>

 #include<cstring>

 using namespace std;

 typedef long long LL;

 const LL INF=1e18+;

 int n,cnt=;

 LL a[];

 void init()

 {

     for (LL i=;i<=INF;i*=)

         for (LL j=;j*i<=INF;j*=)

             for (LL k=;k*i*j<=INF;k*=)

                 a[++cnt]=i*j*k;

     sort(a+,a+cnt+);

 }

 int main()

 {

     init();

     scanf("%d",&n);

     LL x;

     for (int i=;i<=n;i++)

     {

         scanf("%lld",&x);

         printf("%lld\n",*lower_bound(a+,a+cnt+,x));

     }

 }

　　　　　　　　　　　　　　　　　　1014 X^2 Mod P

X*X mod P = A，其中P为质数。给出P和A，求<=P的所有X。

Input

两个数P A，中间用空格隔开。(1 <= A < P <= 1000000, P为质数)

Output

输出符合条件的X，且0 <= X <= P，如果有多个，按照升序排列，中间用空格隔开。

如果没有符合条件的X，输出：No Solution

Input示例

13 3

Output示例

4 9

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 #include<cmath>

 #include<cstring>

 using namespace std;

 int top=,p,a;

 int ans[]={};

 int main()

 {

     scanf("%d%d",&p,&a);

     for (int i=;i<=p;i++)

     {

         long long x;

         x=(long long)i*i;

         if (x%p==a) ans[++top]=i;

     }

     if (top==) printf("No Solution\n");

     else

     {

         for (int i=;i<top;i++)

             printf("%d ",ans[i]);

         printf("%d\n",ans[top]);

     }

 }

1024 矩阵中不重复的元素

一个m*n的矩阵。

该矩阵的第一列是a^b,(a+1)^b,.....(a + n - 1)^b

第二列是a^(b+1),(a+1)^(b+1),.....(a + n - 1)^(b+1)

.......

第m列是a^(b + m - 1),(a+1)^(b + m - 1),.....(a + n - 1)^(b + m - 1)

(a^b表示a的b次方）

下面是一个4*4的矩阵：

2^2=4, 2^3=8, 2^4=16, 2^5=32

3^2=9, 3^3=27, 3^4=81, 3^5=243

4^2=16, 4^3=64, 4^4=256, 4^5=1024

5^2=25, 5^3=125, 5^4=625, 5^5=3125

问这个矩阵里有多少不重复的数（比如4^3 = 8^2，这样的话就有重复了)

2^2=4, 2^3=8, 2^4=16, 2^5=32

3^2=9, 3^3=27, 3^4=81, 3^5=243

4^2=16, 4^3=64, 4^4=256, 4^5=1024

m = 4, n = 3, a = 2, b = 2。其中2^4与4^2是重复的元素。

Input

输入数据包括4个数：m,n,a,b。中间用空格分隔。m，n为矩阵的长和宽（2 <= m,n <= 100)。a，b为矩阵的第1个元素，a^b（2 <= a , b <= 100）。

Output

输出不重复元素的数量。

Input示例

4 3 2 2

Output示例

11
一个hash的事情。

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<iostream>

 #include<cstring>

 #include<map>

 using namespace std;

 typedef long long LL;

 const LL mod=;

 int m,n,a,b,ans;

 map<int,bool>p;

 int main()

 {

     scanf("%d%d%d%d",&m,&n,&a,&b);

     ans=m*n;

     for (int i=;i<=n;i++)

     {

         LL x=,jed=(a+i-);

         for (int j=;j<b;j++)

             x=x*jed%mod;

         for (int j=;j<=m;j++)

         {

             x=x*jed%mod;

             if (p[x]) ans--;

             else p[x]=true;

         }

     }

     printf("%d\n",ans);

 }

1031 骨牌覆盖

在2*N的一个长方形方格中，用一个1*2的骨牌排满方格。

问有多少种不同的排列方法。

例如：2 * 3的方格，共有3种不同的排法。（由于方案的数量巨大，只输出 Mod 10^9 + 7 的结果）

Input

输入N(N <= 1000)

Output

输出数量 Mod 10^9 + 7

Input示例

Output示例

比铺砖块要水吧，转移的东西都少，一般的状态压缩。

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<iostream>

 #include<cstring>

 using namespace std;

 const int mod=1e9+;

 int n,m,cnt=;

 int f[][]={};

 struct Node

 {

     int x,y;

 }next[];

 void dfs(int num,int sta,int old)

 {

     if (num>m) return;

     if (num==m)

     {

         next[++cnt].x=old;

         next[cnt].y=sta;

         return;

     }

     dfs(num+,(sta<<)+,old<<);

     dfs(num+,sta<<,old<<);

     dfs(num+,sta<<,(old<<)+);

 }

 int main()

 {

     scanf("%d",&n);

     m=;

     dfs(,,);

     f[][]=;

     for (int i=;i<=n;i++)

         for (int j=;j<=cnt;j++)

         {

             int x=next[j].x,y=next[j].y;

             f[i][y]=(f[i][y]+f[i-][x])%mod;

         }

     printf("%d\n",f[n][]);

 }

巴特西

1007 正整数分组 1010 只包含因子2 3 5的数 1014 X^2 Mod P 1024 矩阵中不重复的元素 1031 骨牌覆盖

最新文章

热门文章