AcWing第80场周赛总结

第一题没什么好讲的，直接秒了，下次尽量要在5min内写完。
T2：寻找数字
第二题sb了，一直在想贪心的办法，但是考虑到这个比赛的难度 ，其实最原始的dfs才是正解。dfs的妙处在于：省去了对于各类可能不合法的情况的分类讨论，直接通过一个判断全部筛掉，而且可以保证答案的最小性，因为是dfs序。这题的时间复杂度理论上是O(n*lgn)的，但是实际上跑得飞快，只用了24ms就过了。所以就可以写出如下代码：

#include
#include
using namespace std;
const int N=35;
typedef long long ll;
int n,m;
ll ans=1e18;
int a[N];
void dfs(int u,int len,int s4,int s7){
    if(s4>(len+1)/2 || s7>(len+1)/2) return;
    if(u==len){
        ll res=0;
        for(int i=len;i>=1;i--){
            res=res*10+(ll)a[i];
        }
        if(res>=(ll)n) ans=min(ans,res); 
        return;
    }
    a[u+1]=4;
    dfs(u+1,len,s4+1,s7);
    a[u+1]=7;
    dfs(u+1,len,s4,s7+1);
    a[u+1]=0;
}
int main(){
    cin>>n;
    m=(int)(log(n)/log(10))+1;
    if(m&1) dfs(0,m+1,0,0);
    else dfs(0,m,0,0);
    if(ans==1e18){
        dfs(0,m+2,0,0);
    }
    cout<<ans<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

T3：摆放棋子
这题显然是一个dp，但是我用自己的神奇推法并没有办法AC，所以需要借鉴一下别人的优美写法：设f_i,j,0/1表示填了前i个位置，且一共填了j个白子，最后一个子为白子(0)或黑子(1)。那么这种写法实际上是一种线性DP的写法，并且巧妙地找到了最后一个不同点：最后一个子的黑白。那么转移就非常简单了：
f_i,j,0=${\sum }_{k=1}^{k2}{f}_{i-k,j-k,1}$
f_i,j,1=${\sum }_{k=1}^{k1}{f}_{i-k,j,0}$
边界：f_0,0,0=f_0,0,1=1
代码较易，不予展示。
P.S.:y总的代码感觉无法透彻地理解，所以还是采用了nickxiao大佬的解法。

赛后总结

时间紧迫，不能迟到，然后不能思维定式，可以通过一些较为“朴素”的手法来简化问题，最后就是要多积累一些题目。