hiho_offer收割18_题解报告_差第四题-白红宇

hiho_offer收割18_题解报告_差第四题

阅读量：4947 次

发布时间：2019-06-11

本文共 3873 字，大约阅读时间需要 12 分钟。

I.求逆元

欧几里得方法

II.模拟

细心+耐心

*本人感悟：

自己的错误在于：

对于这道模拟题没有耐心静下来一字一字看题，一行一行调错，一步一步调试，我要引以为戒。

III.dp

f[i][j][k]=max(f[i-1][j][k],min(f[i-1][t][k-1])+value[i][k])

t=0,1,…,801

i为第i个曲子(长度为3)

j为至今已进行j次的和弦改变(j<=c(c为允许和弦改变的最多次数))

k为第k种和弦的方法

value[i][k]为用对第i个曲子用第k个和弦的不和谐值

本人想到的进一步优化(本题不用)：

1.求出全程不能变音的最小值

2.对于某个变音方法，如果其值已经大于最小值，则该方法不能继续进行下去

具体操作：

把对应第1~i个曲子可以实现的和弦存放到数组，生成第1~i+1个曲子可以实现的和弦

时间复杂度：

i<=1000

j<=20

k<=802

对于每个i,k，求出一次min(f[i-1][t][k-1])即可

O(nk*802)

1000*20*802=16040000

可在一秒内解决

*另：注意数组维数的范围

如发现错误，可在各个位置设置“输出一个数”，看哪里不正常，那么就是哪里出错了

*测试数据：

如n=1000，k=20

其它全为0

判断是否数组开的正确

IV.

实际上，没多少斤两就不要想第四题了，看看题目和测试数据就知道是不想让你用简单方法拿点分了

反正不会做

下面是想法：

不同的分图没有边相连，不互相影响，可分开考虑

以k个点为标准点，分别考虑这k个点是否发生故障，除去？？？不行，2^k 太大了

有第i个点和有第j点，

当某边在/不在时

当某点在/不在时

当n很大时

当m很大时

极限数据：

100000个点，编号为前400的点，每个点之间都有一个边相连；剩下的点都仅与编号为1的点相连

1 #include 
     
       2 #include 
      
        3  4 long s,t; 5  6 void gcd(long x,long y) 7 { 8     if (y==0) 9     {10         s=1;11         t=0;12         return;13     }14     long r,q;15     r=x/y;16     gcd(y,x%y);17     q=s;18     s=t;19     t=q-r*t;20 }21 22 int main()23 {24     long a,b,p;25     scanf("%ld%ld%ld",&a,&b,&p);26     b=b%p;27     gcd(p,b);28     t=t%p+p;29     printf("%ld\n",a*t%p);30     return 0;31 }

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5   6 struct node  7 {  8     long f[4];  9     long a[3]; 10 }pai[10]; 11  12 long n; 13  14 bool judge() 15 { 16     long j,k,g; 17     //1 18     for (j=0;j<4;j++) 19     { 20         g=0; 21         for (k=0;k
         
          0) 29             break; 30     if (j!=n) 31     { 32         for (j=0;j
          
           0) 34 break; 35 if (j!=n) 36 { 37 for (j=0;j
           
            0) 39 break; 40 if (j==n) 41 return true; 42 } 43 } 44 //3 45 for (j=0;j
            
             0) 47 break; 48 if (j!=n) 49 { 50 for (j=0;j
             
              0) 52 break; 53 if (j!=n) 54 { 55 for (j=0;j
              
               0) 57 break; 58 if (j==n) 59 return true; 60 } 61 } 62 //4 63 for (j=0;j
               
                0) 65 break; 66 if (j!=n) 67 { 68 for (j=0;j
                
                 0) 70 break; 71 if (j!=n) 72 return true; 73 } 74 return false; 75 } 76 77 int main() 78 { 79 long c,g,t,i,j,k,sum[10],tot[10],num; 80 char s[50]; 81 scanf("%ld%ld",&n,&c); 82 for (i=0;i

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define maxf 10000000 5 //max=400*3000=1200000 6  7 long music[3001],value[1001][802],f[1001][21][802],ch[1001]; 8  9 long min(long a,long b)10 {11     if (a>b)12         return b;13     else14         return a;15 }16 17 int main()18 {19     long n,g,i,j,k,l,m,pr;20     scanf("%ld%ld",&n,&g);21     for (i=1;i<=3*n;i++)22         scanf("%ld",&music[i]);23     for (i=0;i<=400;i++)24     {25         j=i-200;26         l=0;27         m=0;28         for (k=1;k<=n;k++)29         {30             m++;31             value[m][i]=0;32             l++;33             value[m][i]+=abs(j-music[l]);34             l++;35             value[m][i]+=abs(j+4-music[l]);36             l++;37             value[m][i]+=abs(j+7-music[l]);38         }39     }40 41     for (i=401;i<=801;i++)42     {43         j=i-601;44         l=0;45         m=0;46         for (k=1;k<=n;k++)47         {48             m++;49             value[m][i]=0;50             l++;51             value[m][i]+=abs(j-music[l]);52             l++;53             value[m][i]+=abs(j+3-music[l]);54             l++;55             value[m][i]+=abs(j+7-music[l]);56         }57     }58 59     for (i=1;i<=n;i++)60         for (j=1;j<=g;j++)61             for (k=0;k<802;k++)62                 f[i][j][k]=maxf;63 64     for (k=0;k<802;k++)65         f[0][0][k]=0;66     for (i=1;i<=n;i++)67         for (k=0;k<802;k++)68             f[i][0][k]=f[i-1][0][k]+value[i][k];69 70     pr=maxf;71     //272     for (i=2;i<=n;i++)73     {74         //0