20170820四校聯考

來看看IOIAu巨神zzx的名言

不用循環輸入就會狗啊哥哥！

上題目：

T1：

填算式（expr）

【題目描述】

填算式是一種簡單的數學游戲，可以形式化描述如下：n 個數字a1; a2; …… ; an 排成一排（1<= ai<=9），相鄰兩個數字之間有一個空格。你可以在每個空格內填入運算符+- * 之一，也可以不填，要求得到的算式的運算結果等于k。你的任務是計算有多少種不同的正確算式。比如n = 3，3 個數字為2; 2; 2，k = 24時，有兩種不同的正確算式：22 + 2 = 24，2 + 22 = 24。

【輸入格式】
從文件expr.in 中讀入數據。
輸入的第一行包含兩個整數n; k，表示數字個數和要求的答案。
接下來一行，包含n 個整數，第i 個數為ai。相鄰兩個整數用一個空格隔開。
【輸出格式】
輸出到文件expr.out 中。
輸出一個整數，表示不同的正確算式個數。
【樣例1 輸入】
4 11
1 2 3 4
【樣例1 輸出】
3
【樣例1 解釋】
3 個正確的算式為：12 + 3 ?? 4 = 11，1 + 2 3 + 4 = 11，1 ?? 2 + 3 4 = 11。
【樣例2 輸入】
7 1
1 1 1 1 1 1 1
【樣例2 輸出】
241

【樣例3 輸入】
10 3276
7 7 8 6 1 4 1 1 1 4
【樣例3 輸出】
104

【子任務】
子任務會給出部分測試數據的特點。如果你在解決題目中遇到了困難，可以嘗試只
解決一部分測試數據。
每個測試點的數據規模及特點如下表：

題解：

比較簡單的搜索吧（雖然我打掛了）
直接DFS從左到右枚舉每個空格填+,-,×還是不填，然后計算這個式子的值，這樣復雜度是4^(n-1)*n，期望得分95分

在DFS的參數里面存儲當前運算結果，可以一邊DFS一邊計算，具體做法如下：
維護參數 a,b,c，初始 a=c=0，b=1
不填，則 c->10c+x[i]
填+，則 a->a+bc,b=1,c=x[i]
填-，則 a->a+bc,b=-1,c=x[i]
填×，則 b->bc,c=x[i]
最后 a+bc就是運算結果
復雜度優化到4^(n-1)，期望得分100分

部分分算法：
如果不會DFS，可以用三重循環通過測試點1~12，期望得分60分

如果不會循環，可以用條件語句通過測試點1~4或者1~8，期望得分20~40分

代碼：

#include<cstdio>
#define r register
#define Fn "expr"
typedef long long ll;
int n,k,ans,x[15];
bool check(ll a,ll b,ll c){return a+b*c==k;}
void dfs(int st,ll a,ll b,ll c){
    if(st==n){ans+=check(a,b,c);return;}
    dfs(st+1,a,b,c*10+x[st]);
    dfs(st+1,a+b*c,1,x[st]);
    dfs(st+1,a+b*c,-1,x[st]);
    dfs(st+1,a,b*c,x[st]);
}
int main(){
    freopen(Fn".in","r",stdin);
    freopen(Fn".out","w",stdout);
    scanf("%d%d",&n,&k);
    for(r int i=0;i<n;i++)scanf("%d",x+i);
    dfs(1,0,1,x[0]);
    printf("%d\n",ans);
    return 0;
}

View Code

T2：

閉合子圖（closure）

【樣例1 輸入】
5 5
1 3
3 4
5 4
1 5
2 1
【樣例1 輸出】
5

題解：

部分分算法：枚舉子集
枚舉 V 的非空子集 S，根據定義判定是否滿足條件，更新答案
判定部分實現優秀的話可以做到O(1)，期望得分20~25分

部分分算法：枚舉區間
注意到點集構成的區間只有 n(n+1)/2 個，可以枚舉區間然后將區間內的點作為S，進行判定
直接實現的復雜度 O(n^2*m)，期望得分35分

注意到對于一個點u的出邊(u,v)，只有最小的v和最大的v是有用的，可以將m縮小到2n
復雜度 O(n^3)，期望得分40分

進一步地，可以枚舉左端點，然后從小到大枚舉右端點，維護區間內出邊指向點的最小值和最大值
復雜度 O(n^2)，期望得分50分

部分分算法：樹的數據

對于測試點11,12，顯然所有形如[1,i]的區間都滿足條件
所以答案為n，復雜度O(n)，期望得分10分，結合上述算法期望得分60分

部分分算法：DAG的數據

對于測試點13,14，判定區間[l,r]是否滿足要求只需要[l,r]內的點指向的點編號均不超過r
用p[i]表示i指向的點的編號（不存在則p[i]=i），則可以枚舉r，找出第一個滿足p[i]>r的i，那么l=i+1,i+2,...,r都是合法的，答案加上r-i
從左到右維護p[i]的遞減單調棧即可，復雜度O(n)，期望得分15分。
結合上述算法期望得分75分

算法：分治

考慮分治，假設當前統計的是[L,R]有多少個子區間合法，取mid=[(L+R)/2]，統計包含mid和mid+1的合法區間個數
記p[i],q[i]分別表示i的出邊指向點的最小值和最大值（不存在則為i）
則區間[l,r]合法的條件是
對于l<=i<=mid，p[i]>=l (1) 且 q[i]<=r (2)
對于mid<i<=r，p[i]>=l (3) 且 q[i]<=r (4)
條件(1)只和l有關，條件(4)只和r有關，做一遍前綴/后綴最值把合法的l,r處理出來即可
記Q[l]=max{q[i]|l<=i<=mid}，條件(2)就是r>=Q[l]
如果記r'為最小的r>=mid滿足p[r']<l，那么條件(3)就是r<r'，且r'隨l的減小而增大
那么只需從大到小枚舉l，維護Q[l]，單調維護r'，答案加上[Q[l],r')內的合法r個數，這一部分復雜度是線性的
總復雜度O(nlogn)，期望得分100分
如果復雜度不小心多寫了一個log可能只有95分

代碼：

#include<cstdio>
#define maxn 300010
#define reg register
#define Fn "closure"
#define mod 1000000007
#define mid (lt+rt>>1)
typedef long long ll;
int n,m,ans;
int l[maxn],r[maxn],s[maxn];
inline int read(){
    reg int x=0,f=1;reg char c=getchar();
    for(;c<'0'||c>'9';f=c=='-'?-1:1,c=getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c=getchar());
    return x*f;
}
void bs(int lt,int rt){
    if(rt-lt==1){ans+=l[lt]==lt&&r[lt]==lt;return;}
    reg int mr=0;
    s[mid-1]=0;
    for(reg int i=mid;i<rt;i++){
        if(r[i]>mr)mr=r[i];
        s[i]=s[i-1]+(mr==i);
    }
    reg int ml=1<<30,pos=mr=mid;
    for(reg int i=mid;i-->lt;){
        if(l[i]<ml)ml=l[i];
        if(r[i]>mr)mr=r[i];
        while(pos<rt&&l[pos]>=i)pos++;
        if(ml==i&&pos>mr)(ans+=s[pos-1]-s[mr-1])%=mod;
    }
    bs(lt,mid);
    bs(mid,rt);
}
int main(){
    freopen(Fn".in","r",stdin);
    freopen(Fn".out","w",stdout);
    n=read();m=read();
    for(reg int i=1;i<=n;)l[i]=r[i]=i++;
    while(m--){
        reg int s=read(),t=read();
        if(t<l[s])l[s]=t;
        if(t>r[s])r[s]=t;
    }
    bs(1,n+1);
    printf("%d\n",ans);
    return 0;
}

View Code

T3：

題解：

部分分算法：搜索
暴搜t步移動，復雜度 O(4^t)，期望得分32分

部分分算法：最短路+搜索

注意到，兩個相鄰的金幣（或起點、終點）之間走的路徑一定是最短路
所以BFS預處理出起點、終點和k個金幣兩兩之間的最短路，然后搜索經過金幣的順序
復雜度 O(knm+k!)，期望得分56分
如果偷懶把搜索部分寫成 k!*k，可能只有52分

部分分算法：最短路+狀壓DP
同樣先BFS處理最短路，用 d(i,j) 表示金幣 i,j 的距離，起點為 0，終點為 k+1
記 f(i,S) 為當前位于第 i 個金幣處（假設起點是第 0 個金幣），之后經過金幣集合 S 到終點的最短時間
當 S 為空時 f(i,S) = d(i,k+1)
否則 f(i,S) = min{f(j, S-{j}) + d(i,j) | j屬于S}
復雜度 O(knm+2^k*k^2)，期望得分64~68分

分析性質：
迷宮可認為是(n+1)(m+1)個點，(n+1)m+(m+1)n-nm=nm+n+m=(n+1)(m+1)-1邊的無向連通圖，即樹
樹上任意兩點間存在唯一簡單路徑
考慮從起點s到終點t，拾取集合 S 內的金幣的最優走法
記 P 為 s 到 t 路徑，顯然位于 P 上的邊要走奇數次，其余邊要走偶數次
將 P 上的點當作根，那么對于任意 S 中的點 v，v 到根的路徑必須被經過，其余邊都可以不經過
記 P 為s到 E' 為所有 S 中的點 v 到根的路徑經過的邊集
那么至少需要 |P|+2|E'| 的時間，顯然按 P 的順序逐個DFS子樹可以達到這個下界

算法：樹形DP

首先 P 上的金幣都可以拾取，接下來令 t'=[(t-|P|+1)/2]，然后把 P 縮成一個點 root
先預處理 s(i) 為以 i 為根的子樹中的金幣數量
記 f(i,j) 為以 i 為根的子樹中取 j 個金幣，經過邊數的最小值
設 i 的子結點有 c[1],c[2],...,c[m]
g(i,j) 為以 c[1],c[2],...,c[i] 為根的子樹中取 j 個金幣，經過邊數的最小值
那么 g(i,j)=max{g(i-1,j-j')+f(c[i],j')+[j'>0] | 0<=j'<=s(c[i]) 且 0<=j-j'<=s(c[1])+...+s(c[i-1])}
f(i,j) = g(m,j) + [i點有金幣]
答案就是滿足 f(root,ans)<=t' 的最大 ans
時間復雜度 O(knm)，期望得分100分

代碼：

#include<cstdio>
#define inf 0x3f3f3f3f
#define r register
#define Fn "maze"
#define maxn 505
#define maxe 251115
typedef long long ll;
int n,m,t,k,len;
int px[maxe],py[maxe];
bool w[maxn][maxn][4],c[maxe],vis[maxn][maxn];
const int dir[2][4]={{-1,0,0,1},{0,-1,1,0}};
#define C(a,b) (a*(m+1)+b)
inline int read(){
    r int x=0,f=1;r char c=getchar();
    for(;c<'0'||c>'9';f=c=='-'?-1:1,c=getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c=getchar());
    return x*f;
}
bool dfs(int x,int y){
    vis[x][y]=1;px[len]=x;py[len++]=y;
    if(x==n&&y==m)return 1;
    for(r int d=0;d<4;d++)
        if(!w[x][y][d]){
            r int xx=x+dir[0][d],yy=y+dir[1][d];
            if(xx>=0&&yy>=0&&xx<=n&&yy<=m&&!vis[xx][yy]&&dfs(xx,yy))return 1;
        }
    len--;return vis[x][y]=0;
}
int sz[maxe],f[maxe][101],g[101];
void dfs(int x,int y,int z){
    vis[x][y]=1;
    if(c[z])sz[z]++;
    for(r int d=0;d<4;d++)
        if(!w[x][y][d]){
            r int xx=x+dir[0][d],yy=y+dir[1][d];
            if(xx>=0&&yy>=0&&xx<=n&&yy<=m&&!vis[xx][yy]){
                r int v=C(xx,yy);dfs(xx,yy,v);
                for(r int i=0;i<=sz[z]+sz[v];i++)
                    g[i]=i<=sz[z]?f[z][i]:inf;
                for(r int i=0;i<=sz[z];i++)
                    for(r int j=1;j<=sz[v];j++)
                        if(f[z][i]+f[v][j]+1<g[i+j])g[i+j]=f[z][i]+f[v][j]+1;
                for(r int i=0;i<=sz[z]+sz[v];i++)
                    f[z][i]=g[i];
                sz[z]+=sz[v];
            }
        }
}
int main(){
    freopen(Fn".in","r",stdin);
    freopen(Fn".out","w",stdout);
    n=read();m=read();t=read();
    for(r int i=0;i<n*m;i++){
        r int x1=read(),y1=read(),x2=read(),y2=read(),d=0;
        for(;d<4&&(x2!=x1+dir[0][d]||y2!=y1+dir[1][d]);d++);
        w[x1][y1][d]=w[x2][y2][3-d]=1;
    }
    k=read();r int tot;
    for(r int i=0;i<k;i++)c[C(read(),read())]=1;
    dfs(tot=0,0);
    t=t-len+1>>1;
    for(r int i=0;i<len;i++){
        if(c[C(px[i],py[i])])tot++,k--;
        c[C(px[i],py[i])]=0;dfs(px[i],py[i],0);
    }
    for(;k&&f[0][k]>t;k--);
    printf("%d\n",k+tot);
    return 0;
}

View Code

AristocratMarser將于每周日或周一推送四校聯考題解，請大佬們多多指教。

posted @ 2017-08-20 22:07 AristocratMarser 閱讀(313) 評論(0) 收藏舉報

刷新頁面返回頂部

20170820四校聯考

公告