题目描述

题意是给你一个k,n.找到一组序列长度为k的数列,使得a1+a2+.....ak=n;
且这些序列的最小公倍数小于等于n/2;
easy是k=3,hard k可能很大

样例

3
3 3
8 3
14 3

1 1 1
4 2 2
2 6 6

分析

a.如果这个数%2!=0,可以输出1,(n-1)/2,(n-1)/2
b.如果这个数%2==0 (1) 如果%4==0 可以输出n/2,n/4,n/4
(2) 如果%4!=0 是余数是2 可以输出2,(n-2)/2,(n-2)/2

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        if(n%2) printf("%d %d %d\n",1,n-1>>1,n-1>>1);
        else
        {
            if(n%4) printf("%d %d %d\n",2,n-2>>1,n-2>>1);
            else printf("%d %d %d\n",n/2,n/4,n/4);
        }
    }
}

当k很大时

样例

2
6 4
9 5

1 2 2 1 
1 3 3 1 1 

分析

可以把这个n-1*(k-3),这样减完之后的k就是上一题的3

C++代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        n=n-(k-3);
        if(n%2) printf("%d %d %d",1,n-1>>1,n-1>>1);
        else
        {
            if(n%4) printf("%d %d %d",2,n-2>>1,n-2>>1);
            else printf("%d %d %d",n/2,n/4,n/4);
        }
        while(k-3)  printf(" 1"),k--;//输出多余的1
        puts("");

    }
}

题目描述

题意是给一个n,m,再给一个序列长度为n的数列,要求对数列进行分组操作:
组内的相邻两个元素i和i+1的和可以被m整除,(组内只有一个数可以视为被m整除)
求最小组数

样例

4
6 4
2 2 8 6 9 4
10 8
1 1 1 5 2 4 4 8 6 7
1 1
666
2 2
2 4

3
6
1
1

分析

a.所有mod m=0的元素放一堆
b.所有mod m=1 和 mod m=m-1的交叉放
c.所有mod m=2 和 mod m=m-2的交叉放
.....以此类推

代码

/*


    1 1 1 5 2 4 4 8 6 7
    4 4--8--1 7 1--2 6--1--5


*/
#include<bits/stdc++.h>
using namespace std;
#define rd(x)   scanf("%d",&x)
const int N =1e5+10;
int n,m;
int flag[N],cnt;
int main()
{
    int t;
    rd(t);
    while(t--)
    {
        memset(flag,0,sizeof flag);
        cnt=0;
        rd(n),rd(m);
        for(int i=1;i<=n;i++)
        {
            int x;
            rd(x);
            flag[x%m]++;
        }
        if(flag[0]) cnt++;//模结果为0是一组
        for(int i=1;i<=m/2;i++)
        {
          if(abs(flag[i]-flag[m-i])<=1)
            {
                if(!flag[i]&&!flag[m-i])   continue;//有可能没有flag[i],flag[m-i];
                cnt++;//交叉放于一组,且刚好放完
                flag[i]=flag[m-i]=0;//清零
            }
            else
            {
                cnt++;//交叉放于一组且不会放完有多余
                int t=flag[i]-flag[m-i];
                if(t<-1)
                {
                    flag[m-i]-=flag[i]+1;//flag[m-i]比flag[i]大至少1
                    //可以在交叉放的时候m-i放开头结尾,这样就可以多减1
                    flag[i]=0;
                }
                if(t>1)
                {
                    flag[i]-=flag[m-i]+1;
                    flag[m-i]=0;
                }
            }
        }
        for(int i=1;i<=m;i++)   cnt+=flag[i];
        cout<<cnt<<endl;
    }

}