为啥这一套题目背景感到很熟悉。

T1  嚎叫响彻在贪婪的厂房

考试一个小时没调出来，自闭了..........

正解很好想，最后实在打不出来了只好暴力骗分了。。。

联想到以前做的题：（涉及质因数分解）

对于此题需要注意

1.等差数列中不能有相同的数,所以可以用set判断

2.同时对于等差数列我们可以用gcd判断，

设当前数为a[i]，定义变量gcdd，那么就将其与a[i-1]的差的绝对值与gcdd取gcd

因为当前的两个数的gcd不见得是序列真正的gcd，但他只会比真正的gcd要大，所以我们通过此可以缩小gcdd的范围，

然后注意删除是清空

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
            
           
          
         
        
       
      

 

T2 主仆见证了 Hobo 的离别考试读错题还能水到40分？？？？用了bitset的错解不再说了，从网上大佬那学了.....

然后是正(bao)解(li)

首先这题的记忆不是具体的数值，所以不能用bitset暴力求并集交集，因为这样并集根本不存在

于是我们连边，对于交集，我们将k个点向新点连边表示控制

并集反之，然后我暴力水过了，大佬勿看.........

1 #include
      
        2 #define MAXN 500000 3 #define int long long 4 using namespace std; 5 int head[MAXN],tot; 6 struct node{
    int to,n;}e[MAXN*2]; 7 void add(int u,int v){e[++tot].to=v;e[tot].n=head[u];head[u]=tot;} 8 int n,m;int id;int orz; 9 bool ok=0;10 bool vis[MAXN];int ss[MAXN];11 void clear()12 {13      for(int i=1;i<=ss[0];++i)vis[ss[i]]=0;14      ss[0]=0;15 }16 void DFS(int x,int y)17 {18      vis[x]=1;ss[++ss[0]]=x;19      if(x==y){ok=1;return ;}20      for(int i=head[x];i;i=e[i].n)21      {22          int to=e[i].to;23          if(vis[to])continue;24          vis[to]=1;25          DFS(to,y);26          if(ok==1)return ;27      }28 }29 signed main()30 {31      scanf("%lld%lld",&n,&m);32      id=n;33      for(int i=1;i<=m;++i)34      {35          scanf("%lld",&orz);36          if(orz==1)37          {38              ok=0;int x,y;39              scanf("%lld%lld",&x,&y);40              DFS(y,x);41              cout<
       
        <
       
      

 

T3 征途堆积出友情的永恒

这是个DP优化的好题，不知道为啥大家这么快就改过来了........

对于线性的DP方程很好推啊，f[i]表示从那下车的费用

f[i]=min(f[j]+max(b[j],sum[i]-sum[j]),f[i])(j>=i-k)

对于该方程我们考虑优化，因为f[j]-sum[j],f[j]+b[j]是一定的，所以我们考虑用堆维护

但是一个堆显然无法存储两个值，于是我们开两个堆

sum1记录f[j]+b[j],sum2记录f[j]-sum[j];

然后因为我们需要的是max(sum[i]-sum[j],b[j])，那么我们不能直接将两个值放进去

那么我们考虑在两个堆中放进不同的j值，保证两个堆的j不会重复，

这样当我们取出两个堆的值时他们一定是当前j的情况下max(sum[i]-sum[j],b[j])

但是由于sum[i]是变化的那么堆里的值也会变化

我们发现sum1里维护的值是不变的，那么例如

在i==2时取出sum1的堆顶此时的堆顶是j，我们发现f[j]+b[j]>f[j]+sum[i]-sum[j],证明对于j的位置，我是选f[j]+b[j]的情况我们当然可以选

但是i==3取出j，我们发现f[j]+b[j]<f[j]+sum[i]-sum[j],这时证明我们不能再用b的值了，因为f[j]+sum[i]-sum[j]大

所以在以后的过程中sum[i]只会越来越大，所以我们把sum1中j弹去加入sum2中

细节：

1.注意j<i-k的情况要处理两遍

2.关于堆内无值的情况要随时特判

if(sum1.size())min1_id=sum1.top().second;        if(sum2.size())min2_id=sum2.top().second;        while(!sum1.empty()&&f[min1_id]-sum[min1_id]+sum[i]>f[min1_id]+b[min1_id])        {           sum1.pop();                     sum2.push(make_pair(-(f[min1_id]-sum[min1_id]),min1_id));             min1_id=0;           if(sum1.size())min1_id=sum1.top().second;        }

 

这里一开始没有特判是否为空死了很久........

1 #include
      
        2 #define int long long 3 #define MAXN 1010000 4 using namespace std; 5 priority_queue
       
        
          >sum1; 6 priority_queue
         
          
            >sum2; 7 int n,k; 8 int f[MAXN]; 9 int a[MAXN],b[MAXN],sum[MAXN];10 int min1_id=0,min2_id=0;11 void clear(int i)12 {13       while(sum1.size()&&sum1.top().second
           
            f[min1_id]+b[min1_id])64 {65 sum1.pop(); 66 sum2.push(make_pair(-(f[min1_id]-sum[min1_id]),min1_id)); 67 min1_id=0;68 if(sum1.size())min1_id=sum1.top().second;69 }70 clear(i); 71 if(sum1.size())min1_id=sum1.top().second;72 if(sum2.size())min2_id=sum2.top().second; 73 if(!sum1.size())74 {75 f[i]=f[min2_id]-sum[min2_id]+sum[i];76 }77 else if(!sum2.size())78 {79 f[i]=f[min1_id]+b[min1_id];80 }81 else82 {83 f[i]=min(f[min1_id]+b[min1_id],f[min2_id]-sum[min2_id]+sum[i]);84 }85 sum1.push(make_pair(-(f[i]+b[i]),i));86 }87 printf("%lld\n",f[n]);88 }
           
          
         
        
       
      

 调不过只好打对拍啦啦啦........

随机数据生成

1 #include
      
        2 using namespace std; 3 int random(int m) 4 { 5     return (long long)rand()*rand()%m; 6 } 7 int main() 8 { 9     freopen("text.in","w",stdout);10     srand((unsigned)time(0));11     int n=1000;12     int m=random(n)+1;13     printf("%d %d\n",n,m);14     for(int i=1;i<=n;++i)15     {16         printf("%d ",random(100)+1);17     }18     cout<
      

以及对拍

1 #include
      
        2 using namespace std; 3 int main() 4 {  5     int c=0; 6     while(true) 7     { 8          system("./pai"); 9          system("./ac");10          system("./wa");11          if(system("diff -b -B ac.out wa.out"))12          {13             puts("WA");14             return 0;15          }16          cout<<++c<<" ";17          puts("AC");18     }19     return 0;20 }21 /*22 g++ pai.cpp -o pai 23 ./pai24 g++ ac.cpp -o ac25 ./ac26 g++ wa.cpp -o wa27 ./wa28 g++ ran.cpp -o ran29 ./ran30 */