【ccf线上赛普及组 2020】

A.文具订购order

思路：首先，要花光所有的q，发现除了n=1，2，5以外都能被花光。

观察条件得知我们要尽可能的配套，尽可能多的14元。

找完所有的14之后在将剩余的尽可能分为3，4，这样总数就更多满足条件。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 long long read(){
 7     long long ans = 0, f = 1;
 8     char ch = getchar();
 9     while(ch < '0' || ch > '9')
10         f *= (ch == '-') ? -1 : 1, ch = getchar();
11     do ans = ((ans << 1) + (ans << 3) + (ch ^ 48)), ch = getchar();
12     while(ch >= '0' && ch <= '9');
13     return ans * f;
14 }
15 
16 int main(){
17     int n = read(), a = 0, b = 0, c = 0;
18     a = b = c = n / 14, n %= 14;
19     if(n == 1 || n == 2 || n == 5){
20         if(!a){
21             printf("-1");
22             return 0;
23         }
24         n += 14, a--, b--, c--;
25     }
26     int a2 = -a-1, b2 = -b-1, c2 = -c-1;
27     for(int i=0; i<=n; i+=7)
28         for(int j=0; i+j<=n; j+=4)
29             for(int k=0; i+j+k<=n; k+=3)
30                 if(i + j + k == n && i/7+j/4+k/3 > a2+b2+c2)
31                     a2 = i / 7, b2 = j / 4, c2 = k / 3;
32     printf("%d %d %d", a+a2, b+b2, c+c2);
33     return 0;
34 }

B.跑步running

五边形数和五边形定理的模版题（phdhd dalao说不需要了解五边形定理证明，只要会用）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 typedef long long ll;
 6 
 7 ll read(){
 8     ll ans = 0, f = 1;
 9     char ch = getchar();
10     while(ch < '0' || ch > '9')
11         f *= (ch == '-') ? -1 : 1, ch = getchar();
12     do ans = ((ans << 1) + (ans << 3) + (ch ^ 48)), ch = getchar();
13     while(ch >= '0' && ch <= '9');
14     return ans * f;
15 }
16 
17 const int N = 100005;
18 ll f[N],dp[N],cnt=0;
19 
20 int main(){
21     int n = read(), mod = read();
22     for(int i=1; f[cnt] <= n; i++){
23         f[++cnt] = i * (3 * i - 1) / 2;
24         f[++cnt] = i * (3 * i + 1) / 2;
25     }
26     dp[0] = 1;
27     for(int i=1; i<=n; i++){
28         for(int j=1; j<=cnt && f[j]<=i; j++)
29             dp[i] = (dp[i] + mod + dp[i-f[j]] * (((j - 1) % 4 <= 1) ? 1 : -1)) % mod;
30     }
31     printf("%d", dp[n]);
32     return 0;
33 }

另一种好像二维dp可以勉强卡过

 1 #include<bits/stdc++.h>
 2 #define ll long long 
 3 using namespace std; 
 4 
 5 ll d[100001],f[1001][100001];
 6 
 7 int main()
 8 {
 9     int n,p;
10     scanf("%d%d",&n,&p);
11     int m=sqrt(n)+1;
12     d[0]=f[0][0]=1;
13     for(int i=1;i<m;i++)
14     {
15         for(int j=i;j<=n;j++)
16         {
17             d[j]=(d[j]+d[j-i])%p;
18         }
19     }
20     for(int i=1;i<m;i++)
21     {
22         for(int j=i;j<=n;j++)
23         {
24             f[i][j]=f[i][j-i];
25             if(j>=m) f[i][j]=(f[i][j]+f[i-1][j-m])%p;
26         }
27     }
28     ll ans=0,p=0;
29     for(int i=0;i<=n;i++)
30     {
31         for(int j=0;j<m;j++)
32         {
33             p=(p+f[j][n-i])%p;
34         }
35         ans+=p*d[i];
36         ans%=p;
37         p=0;
38     }
39     printf("%d",ans);
40     return 0;
41 }

c......