2016/10/20-白红宇

2016/10/20

阅读量：6096 次

发布时间：2019-06-20

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

hdu5908

划分子序列为等长子串，这些子串要求两两匹配，匹配的含义是各个数字出现的次数一样。10w规模。

显然剪枝的方法就是利用子长度为总长的约数。匹配其实所有都和第一个子序列去匹配就好了。先++统计第一个，其余的

遇到一次--，全部是0就匹配成功。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
              9 #include
              
               10 #include
               
                11 #include
                
                 12 #include
                 
                  13 using namespace std;14 #define ll long long15 #define LL long long16 #define inf 0x3f3f3f3f17 #define llinf 0x3f3f3f3f3f3f3f3f18 #define FOR(i,a,b) for(int i=a;i<=b;i++)19 #define FORD(i,a,b) for(int i=b;i>=a;i--)20 #define fp freopen("/Volumes/未命名2/Downloads/acm/in.txt","r",stdin)21 #define ptarr(a,x,y) for(int _=x;_<=y;_++) if(_!=y) cout<
                  
                   <<" ";else cout<
                   
                    <
                    
                     >n;42 FOR(i,1,n) cin>>a[i];43 }44 void solve(){45 vector
                     
                      ans;46 FOR(len,1,n)47 {48 if(n%len!=0) continue;49 else50 {51 int l=1,r=len,flg=1;52 for(l=1,r=len;r<=n;l+=len,r+=len)53 {54 FOR(k,1,len) cnt[a[k]]++;55 FOR(k,l,r) if(cnt[a[k]]) cnt[a[k]]--;56 FOR(k,1,len) if(cnt[a[k]]!=0) cnt[a[k]]=0,flg=0;57 58 }59 if(flg) ans.push_back(len);60 FOR(k,1,len) cnt[a[k]]=0;61 }62 }63 int sz=ans.size();64 FOR(k,0,sz-1)65 {66 if(k!=sz-1) printf("%d ",ans[k]);67 else printf("%d\n",ans[k]);68 }69 }70 int main()71 {72 cin>>T;73 while(T--)74 {75 read();76 solve();77 }78 return 0;79 }

View Code

hdu5909

树里面选取非空一个子树使得所有的点权异或和作为树的值。求出各种树的值下的方案数％(1e9+10)

规模:值不超过m(m<1024)，点数目不超过1000.

题解:方案选择类的问题常用的一个化简的思路就是有序化方法。虽然树的选择有很多种。但是只要钦定了一个根，使得总树称为有根树，那么任何一种方案都可以转化为偏序的树形dp的问题。接下来就考虑dp方程是i表示根,j表示总异或和,d[i][j]=d[i][j]+(s2^s1==j)sum(d[i][s1]*d[x][s2]),这里需要解释下为什么想到,这个问题的本质是选取若干子树以及它们的值使得异或和为j,但是这样显然不能做,但是依然考虑有序化的话其实子树可以按照偏序选择，用背包dp兜住。但是这个方程规模过大，注意到这是一个卷积，所以用fwt加速。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    using namespace std;#define FORD(i,k,n) for(int i=n;i>=k;i--)#define FOR(i,k,n) for(int i=k;i<=n;i++)#define CLR(a,b) memset(a,b,sizeof(a));#define INF 0x3f3f3f3f#define LLINF 0x3f3f3f3f3f3f3f3f#define ll long long#define LL long long#define ull unsigned long long#define i64 long long#define u32 unsigned int#define u64 unsigned long long#define ptb(b,a){int tmp=a;string s;do{s+=tmp%2+'0';tmp/=2;}while(tmp);reverse(s.begin(),s.end());cout<<"bin "<<<"="<<
                       
                        >1; struct edge{ int u,v;};vector
                        
                         e[maxn];void read(){ scanf("%d%d",&n,&m); FOR(i,1,n) { scanf("%d",&a[i]); e[i].clear(); } FOR(i,1,n-1) { int u,v; scanf("%d%d",&u,&v); edge tmp; tmp.v=v; e[u].push_back(tmp); tmp.v=u; e[v].push_back(tmp); }}void FWT(int *a,int n) { for(int d=1; d

View Code

hdu5902 gcd is funny

给定一个序列，每次选取三个，划掉一个，另外两个用它们的gcd代替，经过n－2轮之后显然只剩下两个相同的数字。问最后剩下的数值可能是哪些？

规模：序列规模1000，数值大小1000

题解：经过初步的感觉应该是若干个数的gcd。但是因为最初会删除一个，所以应该是任意n-1个数字的gcd。有的时候奇怪的操作不是为了设置限制，而是不得不这么做。这里为什么要两个用gcd替代两次呢，因为如果只替代一次就不能用经典的gcd容斥进行求解。经典的n－1轮gcd容斥的做法就和floyd很像，而且n－1轮的gcd是允许重复选择一个数字的。

bug:1.没有在gcd容斥里面加flg得到tle

　　 2.加了flg却忘记了只有产生新的时候才flg＝1，if条件忘记写

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    using namespace std;#define FORD(i,k,n) for(int i=n;i>=k;i--)#define FOR(i,k,n) for(int i=k;i<=n;i++)#define CLR(a,b) memset(a,b,sizeof(a));#define INF 0x3f3f3f3f#define LLINF 0x3f3f3f3f3f3f3f3f#define ll long long#define LL long long#define ull unsigned long long#define i64 long long#define u32 unsigned int#define u64 unsigned long long#define ptb(b,a){int tmp=a;string s;do{s+=tmp%2+'0';tmp/=2;}while(tmp);reverse(s.begin(),s.end());cout<<"bin "<<<"="<<
                       
                        >n; FOR(i,1,n) { cin>>a[i]; }}void preprocess(){}void solve(){ CLR(g,0); int cnt=n-3; FOR(i,1,n) { FOR(j,i+1,n){ g[gcd(a[i],a[j])]=1; } } int flg=1; while(cnt--&&flg) { flg=0; FOR(i,1,1000) { if(g[i]==0) continue; FOR(j,1,n) { if(!g[gcd(i,a[j])]){ g[gcd(i,a[j])]=1; flg=1; } } } } int ans[2000],len=0; FOR(i,1,1000) { if(g[i]==1) ans[len++]=i; } FOR(i,0,len-1) { printf("%d%c",ans[i],i==len-1?'\n':' '); }}int main(){ cin>>T; while(T--) { read(); solve(); } return 0;}

View Code

hdu5903 wa

hdu5904 LCIS

给定两个10w数值100w序列要求选取子序列数值连续，那么问最长公共上升数值连续子序列是多少？

题解:如果分别求出两个序列的下标偏序的dp然后组合显然会超时，那可以从key的偏序考虑改成value的偏序，按照数值进行dp，那么d[a[i]]=(d[a[i]-1]+1)/1，分别求出两个序列，然后按照值取max(ans,min(f,g))就可以了。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    using namespace std;#define FORD(i,k,n) for(int i=n;i>=k;i--)#define FOR(i,k,n) for(int i=k;i<=n;i++)#define CLR(a,b) memset(a,b,sizeof(a));#define INF 0x3f3f3f3f#define LLINF 0x3f3f3f3f3f3f3f3f#define ll long long#define LL long long#define ull unsigned long long#define i64 long long#define u32 unsigned int#define u64 unsigned long long#define ptb(b,a){int tmp=a;string s;do{s+=tmp%2+'0';tmp/=2;}while(tmp);reverse(s.begin(),s.end());cout<<"bin "<<<"="<<

View Code

转载于:https://www.cnblogs.com/diang/p/5980532.html

你可能感兴趣的文章