原题大战D1

吐槽:

1. T1 \(O(N^2)\; N \leq 26\) N大时还要写高精, 可以增加难度

2. T2 不给范围

3. T3 居然没有完全卡掉 不对应该赞美出题人

4. T4 PJ考个四边形不等式?? orz 出题人 %%%

这里是点名被卡的直接高精选手.

并没有感觉很卡啊, 写了就过了啊

因为平常高精求余是这么写的

pair
    
      divide(string a, string b){    for(int i=0;i
    

但是我的高精是这样的:

string mod(string x, string y){    string ans ;     for(int i=0;i

这种写法的优点在于:

1. 码量小(高精除了除码量都不大)

2. 常数小, 具体来说, 采用第一种写法执行了10次乘法(高精乘单精)以求出除得的值(但其实用二分只用至多4次, 而且不断加也可以), 而这里执行的是减法, 不需要取余,所以常数较小. 并且该算法较玄学, 卡不满? 并且开上O2, O3后, STL常数极小

3. 能AC本题

gcd主要代码如下:

string gcd(string x, string y){    if(y == 1) return 1; // 加速    if(y == "0" || y.empty()) return x;    return gcd(y, mod(x, y)) ;}

可以看见特判了1, 这是因为y=1要执行10*len(x)次高精减法及判断

并且可以发现, 在y变大时, 执行减法次数逐渐缩小, 而很小时取膜可以让较大的数减少一个很大的值(说了这么多就是玄学算法过了2333)

T1

题意

给出一颗二叉树的前序遍历和后序遍历,求有多少种这样的二叉树

解法

考虑递归的求解, 一个节点的子树是他在前序遍历中的位置到他在后序遍历中的位置

那么如果一个节点只有一颗子树, 挂在左边/右边并不会影响遍历, 即方案数乘2

知识点

递归

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std ;#define int long longint power(int a,int b){ int res=1, car=a ; while(b){ if(b&1) res*=car ; car*=car ; b>>=1 ; } return res; }string p, q; int len ; int cnt;void calc(int a1,int b1,int a2,int b2){ int i; if(a1>=b1) return; for(i=a2;i<=b2-1;++i) if(p[a1+1] == q[i]) break; if(i==b2-1) ++cnt; calc(a1+1,a1+1+(i-a2),a2,i); calc(a1+1+(i-a2)+1,b1,i+1,b2-1);}signed main(){ freopen("tree.in", "r", stdin); freopen("tree.out", "w", stdout); cin>>p>>q ; len = p.size() ; calc(0,len-1,0,len-1); printf("%lld\n", power(2, cnt));}
         
        
       
      
     
    

T2

题意

定义一个八连通的联通块的块大小为其权值, 求所有的权值中

1) 最大的是多少

2) 大于等于一个给定k的有多少个

解法

无脑暴力BFS即可

O(NM)

错误

在判断能否走向一个方向时, 写错函数名(复制时忘记修改)导致考场爆0

现已修改

知识点

BFS

代码

#pragma optimize(2)#pragma optimize(3)#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define pir pair
          
           using namespace std ;int mp[1005][1005]; int n,m,k ; queue< pir > q; int vis[1005][1005] ;int chk(pir x) {return mp[x.first][x.second]=='.'; } pir up(pir x){ return make_pair(x.first-1, x.second) ; } pir dn(pir x){ return make_pair(x.first+1, x.second) ; } pir le(pir x){ return make_pair(x.first, x.second+1) ; } pir ri(pir x){ return make_pair(x.first, x.second-1) ; } pir ul(pir x){ return make_pair(x.first+1, x.second-1) ; } pir ur(pir x){ return make_pair(x.first+1, x.second+1) ; } pir dl(pir x){ return make_pair(x.first-1, x.second-1) ; } pir dr(pir x){ return make_pair(x.first-1, x.second+1) ; }#define put(X) cout<<"At "<
           
            <<" "<
            
             <
             
              >p; for(int j=1;j<=m;++j) mp[i][j]=p[j-1]; } scanf("%d", &k); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(!vis[i][j] && chk(make_pair(i, j))) { int pm = bfs(i, j, 1) ; //cout<
              
               <
               
                = k) ++pans ; } cout<
                
                 <<" "<
                 
                  <
                 
                
               
              
             
            
           
          
         
        
       
      
     
    

T3

题意

求两个大数的gcd

解法

暴力gcd, 套个高精度即可

知识点

高精度, gcd

代码

#pragma optimize(2)#pragma optimize(3)#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std ;int cmp(string str1,string str2){ if(str1.size()!=str2.size()) return str1.size() < str2.size() ; else for(int i=0; i
          
           =0; --i) str1[i+Q]-=(str2[i]-'0') ; for(int i=str1.size()-1; i>0; --i) if(str1[i] < '0') str1[i]+=10, --str1[i-1] ; str1.erase(0,str1.find_first_not_of('0'));return str1 ; }string mod(string str1,string str2){ string ans ; ans.clear() ; for(int i=0; i
           
            >p>>q; if(p=="1" || q=="1") return puts("1"),0; cout<
           
          
         
        
       
      
     
    

T4

题意

石子合并

解法

原题……

众所周知石子合并满足四边形不等式, 打个(我从没打过)的四边形不等式即可

代码奇短?

知识点

四边形不等式, DP

代码

#pragma optimize(2)#pragma optimize(3)#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std ;int a[4005], sum[4005]; int dp[4005][4005], P[4005][4005], ans=0x3f3f3f3f, n;int main(){ freopen("stone.in", "r", stdin); freopen("stone.out", "w", stdout) ; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); a[i+n]=a[i]; sum[i]=sum[i-1]+a[i]; P[i][i]=i; } for(int i=1+n;i<=(n<<1);i++){ sum[i]=sum[i-1]+a[i]; P[i][i]=i; } for(int i=(n<<1)-1;i;i--) for(int j=i+1,pos=0,tmp=0x3f3f3f3f;j<=(n<<1);j++,pos=0,tmp=0x3f3f3f3f) for(int k=P[i][j-1];k<=P[i+1][j];k++) if(dp[i][k]+dp[k+1][j]+(sum[j]-sum[i-1])