[CF 518F] Pasha and Pipe

作法：

真是麻煩的題目@@ 總之大概是分成沒有轉彎，轉一次彎和轉兩次彎討論，但對四個方向都做一次實在太麻煩了，所以我直接存原本的盤面和轉90度、180度、270度的盤面，把對稱的東西直接用一個函式作四次。另外再作轉兩次彎的時候，要用DP先處理好「每格往左(右)走至少2步，再往上走到底，並且不能碰到角落格子」的方法數。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=2000+10 ;
 
int a[4][maxn][maxn],s[4][maxn][maxn] ;
 
int sum(int id,int x1,int y1,int x2,int y2)
{
    return s[id][x2][y2]-s[id][x1-1][y2]
        -s[id][x2][y1-1]+s[id][x1-1][y1-1] ;
}
 
LL cal0(int id,int n,int m)
{
    LL ret=0LL ;
    for(int i=2;i<m;i++) if(!sum(id,1,i,n,i))
        ret++ ;
    return ret ;
}
 
LL cal1(int id,int n,int m)
{
    LL ret=0LL ;
    for(int i=2;i<n;i++) for(int j=2;j<m;j++)
        if(!sum(id,i,1,i,j)&&!sum(id,1,j,i,j)) ret++ ;
    return ret ;
}
 
int num[4][2][maxn][maxn] ;
void getnum(int id,int n,int m)
{
    for(int i=2;i<n;i++) for(int j=4;j<m;j++)
    {
        if(a[id][i][j]) { num[id][0][i][j]=0 ; continue ; }
        num[id][0][i][j]=num[id][0][i][j-1] ;
        if(!sum(id,i,j-2,i,j)&&!sum(id,1,j-2,i,j-2))
            num[id][0][i][j]++ ;
    }
    for(int i=2;i<n;i++) for(int j=m-3;j>=2;j--)
    {
        if(a[id][i][j]) { num[id][1][i][j]=0 ; continue ; }
        num[id][1][i][j]=num[id][1][i][j+1] ;
        if(!sum(id,i,j,i,j+2)&&!sum(id,1,j+2,i,j+2))
            num[id][1][i][j]++ ;
    }
}
 
LL cal2(int id,int n,int m)
{
    LL ret=0LL ;
    for(int i=2;i<n;i++) for(int j=3;j<=m;j++)
        if(!sum(id,1,j,i,j)) ret+=num[id][0][i][j] ;
    return ret ;
}
 
LL cal3(int id,int n,int m)
{
    LL ret=0LL ;
    for(int i=2;i<n;i++) for(int j=2;j<m;j++)
        if(!sum(id,i,j,n,j))
    {
        ret+=num[id][0][i][j] ,
        ret+=num[id][1][i][j] ;
        if(j>2&&!sum(id,1,j-1,i,j-1)) ret++ ;
        if(j<m-1&&!sum(id,1,j+1,i,j+1)) ret++ ;
    }
    return ret ;
}
 
main()
{
    int n,m ;
    scanf("%d%d",&n,&m) ;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
    {
        char c=getchar() ;
        while(c!='#'&&c!='.') c=getchar() ;
        int x=(c=='#') ;
        a[0][i][j]=a[1][j][n+1-i]=x ;
        a[2][n+1-i][m+1-j]=a[3][m+1-j][i]=x ;
    }
 
    for(int i=0;i<4;i++)
    for(int j=1;j<=max(n,m);j++) for(int k=1;k<=max(n,m);k++)
        s[i][j][k]=s[i][j][k-1]+s[i][j-1][k]-s[i][j-1][k-1]+a[i][j][k] ;
 
    LL ans=0LL ;
    ans+=cal0(0,n,m)+cal0(1,m,n) ;
    ans+=cal1(0,n,m)+cal1(1,m,n)+cal1(2,n,m)+cal1(3,m,n) ;
    getnum(0,n,m) ; getnum(1,m,n) ;
    getnum(2,n,m) ; getnum(3,m,n) ;
    ans+=cal2(0,n,m)+cal2(1,m,n)+cal2(2,n,m)+cal2(3,m,n) ;
    ans+=cal3(0,n,m)+cal3(1,m,n) ;
    printf("%I64d\n",ans) ;
}
 

[CF 518E] Arthur and Questions

作法：

原題條件等價於每跳 k 個數都是嚴格遞增的，所以可以把模 k 不同餘的數分開作。所以可以把問題簡化成在兩個數中間有一些問號，要填上數字使得這個數列嚴格遞增，並讓絕對值總和最小。而這只要好好的把兩個數字的正負的情況討論出來就好了，蠻煩的不過不會很難。

code :

#include<bits/stdc++.h>
#define INF 2000000000
using namespace std;
const int maxn=100000+10 ;
 
bool solve(vector<int> &v)
{
    int sz=v.size() ;
    for(int i=0;i<sz-1;i++) if(v[i]!=INF && v[i+1]!=INF
        && v[i+1]<=v[i]) return 0 ;
    for(int i=0;i<sz-1;i++) if(v[i+1]==INF)
    {
        int j ;
        for(j=i+1;j<sz && v[j]==INF;j++) ;
        int num=j-i-1 ;
        if(v[i]+num>=v[j]) return 0 ;
        if(v[j]<=1) for(int z=i+1;z<j;z++)
            v[z]=z-j+v[j] ;
        else if(v[i]>=-1) for(int z=i+1;z<j;z++)
            v[z]=z-i+v[i] ;
        else
        {
            int l=0 , r=0 ; num-- ;
            while(num--)
            {
                if(r==v[j]-1 || (r+l>0 && l>v[i]+1)) l-- ;
                else r++ ;
            }
            for(int z=i+1;z<j;z++)
                v[z]=z-i-1+l ;
        }
    }
    return 1 ;
}
 
int n,k ;
int a[maxn] ;
vector<int> tmp ;
main()
{
    scanf("%d%d",&n,&k) ;
    for(int i=1;i<=n;i++)
    {
        char s[20] ; scanf("%s",s) ;
        if(s[0]=='?') a[i]=INF ;
        else sscanf(&s[0],"%d",&a[i]) ;
    }
    for(int i=1;i<=k;i++)
    {
        tmp.clear() ;
        tmp.push_back(-INF+1) ;
        for(int j=i;j<=n;j+=k) tmp.push_back(a[j]) ;
        tmp.push_back(INF-1) ;
        if(!solve(tmp))
        {
            printf("Incorrect sequence\n") ;
            return 0 ;
        }
        for(int j=i,cnt=0;j<=n;j+=k) a[j]=tmp[++cnt] ;
    }
    for(int i=1;i<=n;i++) printf("%d%c",a[i],i==n?'\n':' ') ;
}
 

[CF 518D] Ilya and Escalator

作法：

一般的機率DP題，去作過了 i 秒且現在有 j 個人在上面的機率就好了。

code :

#include<bits/stdc++.h>
#define DB double
using namespace std;
const int maxn=2000+10 ;
 
DB dp[maxn][maxn] ;
 
main()
{
    int n,t ; DB p ;
    scanf("%d%lf%d",&n,&p,&t) ;
    dp[0][0]=1.0 ;
    for(int i=1;i<=t;i++) for(int j=0;j<=n;j++)
    {
        if(j==n) dp[i][j]=p*dp[i-1][j-1]+dp[i-1][j] ;
        else dp[i][j]= j ? p*dp[i-1][j-1]+(1-p)*dp[i-1][j] :
            (1-p)*dp[i-1][j] ;
    }
    DB ans=0.0 ;
    for(int i=1;i<=n;i++) ans+=dp[t][i]*i ;
    printf("%.9f\n",ans) ;
}
 

[CF 519E] A and B and Lecture Rooms

這題真是蠻容易想錯的XD

作法：

設要查詢的兩個數是 x , y ，首先可以知道如果 x 走到 y 的步數是奇數，那麼無解，因為從 x 開始的任何一條路徑都是先經過部分的(或沒有) xy 之間的路徑再分岔出去(或沒有分岔)，奇偶性會矛盾。

設 x 走到 y 的路徑是 a_0=x , a_1 , ... , a_(2d)=y ，那麼原題的答案就是把原本的樹砍掉 a_(d-1)a_d 和 a_d a_(d+1) 這兩條邊之後，x 和 y 都不在的那個連通塊的大小，這還必須多討論 a_d 恰好就是 x 和 y 的 LCA 的情況，蠻容易寫錯的。

另外有可能 x 和 y 在同一點，原本一小時內就把這題寫完了，但到最後才突然想到這個情況才AC ......

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 ;
 
vector<int> v[maxn] ;
 
int anc[20][maxn] ;
int dep[maxn],size[maxn] ;
 
void dfs(int x,int f)
{
    anc[0][x]=f ; size[x]=1 ;
    for(auto i : v[x]) if(i!=f)
    {
        dep[i]=dep[x]+1 ;
        dfs(i,x) ;
        size[x]+=size[i] ;
    }
}
 
int n ;
void build()
{
    for(int i=1;i<20;i++) for(int j=1;j<=n;j++)
        anc[i][j]=anc[i-1][anc[i-1][j]] ;
}
 
int query_fa(int x,int d)
{
    if(!d) return x ;
    for(int i=19;i>=0 && d;i--) if(d&(1<<i))
    {
        x=anc[i][x] ;
        d^=(1<<i) ;
    }
    return x ;
}
 
int LCA(int x,int y)
{
    if(dep[x]!=dep[y]) return
        dep[x]>dep[y] ? LCA(query_fa(x,dep[x]-dep[y]),y) :
                        LCA(x,query_fa(y,dep[y]-dep[x])) ;
    if(x==y) return x ;
    for(int i=19;i>=0;i--) if(anc[i][x]!=anc[i][y])
        x=anc[i][x] , y=anc[i][y] ;
    return anc[0][x] ;
}
 
main()
{
    scanf("%d",&n) ;
    for(int i=1;i<n;i++)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
    }
    dep[1]=0 ;
    dfs(1,1) ;
    build() ;
    int Q ; scanf("%d",&Q) ;
    while(Q--)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        int f=LCA(x,y) ;
        if(x==y) printf("%d\n",n) ;
        else if((dep[x]+dep[y])%2) printf("0\n") ;
        else if(dep[x]==dep[y])
        {
            int d=dep[x]-dep[f] ;
            int x1=query_fa(x,d-1) , y1=query_fa(y,d-1) ;
            printf("%d\n",n-size[x1]-size[y1]) ;
        }
        else
        {
            int d=(dep[x]+dep[y])/2-dep[f] ;
            int f1,f2 ;
            if(dep[x]>dep[y]) f1=query_fa(x,d-1) ;
            else f1=query_fa(y,d-1) ;
            f2=anc[0][f1] ;
            printf("%d\n",size[f2]-size[f1]) ;
        }
    }
}
 

[CF 519D] A and B and Interesting Substrings

作法：

題目等價於要找滿足「 i>=j , sum[ i ] = sum[ j ] , a[ i+1 ] = a[ j ] 」 的 ( i , j ) 組數，sum 是字母得分從 1 加到 i 的值，a 是原本的字串。所以直接用 pair 把 ( sum[ i ] , a[ i ] ) 包起來，用 map 記錄每個 pair 出現了幾次，然後作到 i 的時候直接查詢就好了。

然後記得 sum 要開 long long ，我有 hack 到一個沒開 long long 的人 XD

code :

#include<bits/stdc++.h>
#define LL long long
#define mkp(x,y) make_pair(x,y)
using namespace std;
const int maxn=100000+10 ;
 
map< pair<LL,char>,int > mp ;
int w[27] ;
char s[maxn] ;
LL sum[maxn] ;
main()
{
    for(int i=0;i<26;i++) scanf("%d",&w[i]) ;
    scanf("%s",s+1) ;
    int n=strlen(s+1) ;
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+w[s[i]-'a'] ;
    LL ans=0LL ;
    for(int i=1;i<n;i++)
    {
        mp[mkp(sum[i],s[i])]++ ;
        ans+=mp[mkp(sum[i],s[i+1])] ;
    }
    printf("%I64d\n",ans) ;
}
 

[TIOJ 1246] 老鼠走迷宮

作法：

把往每個方向走的時候會造成限制的格子都找出來，建成陣列，然後BFS就好了。

code :

#include<bits/stdc++.h>
#define INF 100000000
using namespace std;
const int maxn=1200+10 ;
 
int dx[]={0,-3,-4,-5,-4,-3,0,3,4,5,4,3} ;
int dy[]={5,4,3,0,-3,-4,-5,-4,-3,0,3,4} ;
int chx[12][4]={{0,0,0,0},{-1,-1,-2,-2},{-1,-2,-2,-3},{-1,-2,-3,-4},
{-1,-2,-2,-3},{-1,-1,-2,-2},{0,0,0,0},{1,1,2,2},{1,2,2,3},
{1,2,3,4},{1,2,2,3},{1,1,2,2}} ;
int chy[12][4]={{1,2,3,4},{1,2,2,3},{1,1,2,2},{0,0,0,0},{-1,-1,-2,-2},
{-1,-2,-2,-3},{-1,-2,-3,-4},{-1,-2,-2,-3},{-1,-1,-2,-2},
{0,0,0,0},{1,1,2,2},{1,2,2,3}} ;
 
bool G[maxn][maxn] ;
queue<int> q ;
int d[maxn][maxn] ;
 
main()
{
    int n,m,k ;
    while(scanf("%d%d%d",&n,&m,&k)==3 && n+m+k)
    {
        memset(G,0,sizeof(G)) ;
        while(k--)
        {
            int x,y ; scanf("%d%d",&x,&y) ;
            G[x][y]=1 ;
        }
        int sx,sy,ex,ey ;
        scanf("%d%d%d%d",&sx,&sy,&ex,&ey) ;
        fill(d[0],d[n-1]+m,INF) ;
        while(!q.empty()) q.pop() ;
        q.push(sx) ; q.push(sy) ; d[sx][sy]=0 ;
        while(!q.empty())
        {
            int x=q.front() ; q.pop() ;
            int y=q.front() ; q.pop() ;
            for(int i=0;i<12;i++)
            {
                int nx=x+dx[i] , ny=y+dy[i] ;
                if(nx<0||nx>=n||ny<0||ny>=m) continue ;
                if(G[nx][ny] || d[nx][ny]!=INF) continue ;
                bool ok=1 ;
                for(int j=0;j<4;j++)
                    if(G[x+chx[i][j]][y+chy[i][j]])
                        {ok=0 ; break ;}
                if(!ok) continue ;
                d[nx][ny]=d[x][y]+1 ;
                q.push(nx) ; q.push(ny) ;
            }
        }
        if(d[ex][ey]==INF) printf("No Way!\n") ;
        else printf("%d\n",d[ex][ey]) ;
    }
}
 

[TIOJ 1676] 烏龜疊疊樂

作法：

這題用到了DP的斜率優化，APIO 2010 Commando ( HOJ 236 ) 也用到這個技巧，相關的東西可以在這個網站裡看到。

題目簡單來說就是要把一個數列分成 k 陀 ，使得第一坨裡的總和 * 0，加第二陀裡的總和 * 1 ，一直加到 第 k 陀的總和 * (k-1) ，再扣掉每坨的大小的平方，這個數字要最大。而會發現把整個數列先反過來會比較好DP，所以如果第一步是先把整個數列反過來，設 dp[ i ] 代表 1~ i 的最佳答案，那麼就可以寫出轉移式

dp[ i ] = max { dp[ j ] + S[ j ] - ( i-j )^2 } , j = max( 0,i-k ) ~ i-1

其中 S[ j ] 是前綴和。顯然直接作是O(n^2)的，如果把這條式子化簡，會得到

-i^2 + 2 * i * j - j^2 + dp[ j ] + S{ j ]

( 提醒一個小細節： -i^2 會爆 int ，記得轉成 long long 再乘。 )
因為 -i^2 不影響取不同的 j 的值之間的大小關係，所以可以先不理他，我們要讓後面那坨最大，所以考慮直線 y = ( 2 * j ) x + ( dp[ j ] + S[ j ] - j^2 ) ，記 A[ j ] 和 B[ j ] 分別代表 x 前的係數和常數項，所以這樣等於是要讓 i 這個點代入某條直線 A[ j ] * x + B[ j ] 之後要最大，並且因為每條直線是按照斜率由小到大加入的，又因為每次查詢的 x 坐標是遞增的，所以就可以用上面那個網站講的方法用 deque 作。

具體作法是，每次詢問時先從後面 pop 掉過期的直線( 他不在 i-k ~ i-1 的範圍內，所以不能考慮 )，然後從 deque 的後面開始，如果 i 代入最後一個直線比代入最後第二個直線的值小，則也把最後一個 pop 掉，因為從今以後最後一個都不會比最後第二個好了( 因為斜率遞增且詢問的值遞增!! )。處理完之後就可以得到目前在 deque 的最後的直線就是我們要的。然後要從 deque 前面加入這個 i 代表的直線，記在deque裡前面數來第二條直線叫L1，最前面的叫L2，現在要加入的叫L3，那麼如果L3和L2的交點在L1和L2的交點的左邊的話，L2就廢掉了，必須把他pop掉，pop完之後再加入 L3 就可以了。

但這個作法只拿到 WA 30分，我另外寫了個直接O(n^2)的作法傳上去，沒有TLE的測資都是AC的，這代表是後面斜率優化的地方出問題了，之後我自己 random 生測資並且在剛算出來 dp[ i ] 的時候 assert 那條最原始的式子，發現他常常出錯，於是我仔細把每個階段 deque 裡的東西 print 出來才發現，我有可能在處理 i 的時候，已經把最佳的直線 pop 掉了!

回到那條最佳的直線被 pop 掉的時候，這時候是在「加入新的直線並 pop 廢掉的直線」的階段，也就是L1和L3聯手把L2幹掉的時候，這代表我們認為「在L1和L3的交點以前，L1是最佳選擇，以後的話則是L3是最佳選擇」，但「在L1和L3的交點以前」有可能 L1 已經過期了!!! 也就是這裡的「直線」其實只是「線段」，不能完全按照之前的作法作。所以當在決定 L2 是否廢掉的時候，必須把L1和L2的交點和「L1線段的右端點 x 坐標」取 min ，再去和 L3和L2的交點比較。並且我們知道 L1 是在它的起點 x 座標 + k 的時候過期的。

對了，題目也沒有提到任何數字範圍，我也很怕在判斷交點那邊交叉相乘後 long long 會爆掉，轉成 double 因為數字太大精準度感覺會爛掉，還好最後是沒有爆 XD。

另外，這個網站也有這題的作法喔，也可以看看XD

code : (好短阿(汗

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1000000+10 ;
 
LL a[maxn] ;
LL dp[maxn],s[maxn],A[maxn],B[maxn] ;
int dq[maxn] ;
 
main()
{
    int n,k ; scanf("%d%d",&n,&k) ;
    for(int i=1;i<=n;i++) scanf("%lld",&a[n+1-i]) ;
 
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i] ;
    dp[0]=0LL ; A[0]=B[0]=0LL ;
    int l=0 , r=1 ; dq[0]=0 ;
    for(int i=1;i<=n;i++)
    {
        while(dq[l]+k<i) l++ ;
        while(l+1<r && A[dq[l]]*i+B[dq[l]] <=
                        A[dq[l+1]]*i+B[dq[l+1]]) l++ ;
        dp[i]=-((LL)i)*((LL)i)+A[dq[l]]*i+B[dq[l]] ;
 
        A[i]=2*i ; B[i]=dp[i]+s[i]-((LL)i)*((LL)i) ;
        while(l+1<r && (B[dq[r-2]]-B[dq[r-1]])*(A[i]-A[dq[r-1]])
              >= (B[dq[r-1]]-B[i])*(A[dq[r-1]]-A[dq[r-2]]) &&
              (dq[r-2]+k)*(A[i]-A[dq[r-1]]) >=
              B[dq[r-1]]-B[i]) r-- ;
        dq[r++]=i ;
    }
    printf("%lld\n",dp[n]) ;
}