8.31 下午 梦熊联盟 NOIP 模拟赛总结 & 题解

T1 北极星

一个比较好想到的点是从后往前枚举数，计算得出它需要的操作次数，然后给所有前面的数都加上这个操作次数，这样就把每个数独立出来了。

所以这道题就变成了如何快速通过这些操作得到一个指定的数。

观察大样例的输出，发现每一个数都是 11?1?1? 的形式，其中问号为 + 或 c，我们可以考虑从需要的数倒着找怎么让它最快变成 1。

其实就是，如果是偶数就除以二，是奇数就减一，然后再顺着推回去就得到每个数了，时间复杂度 $O(k \log V)$。

代码贴在下面(100pts)：

stack<char> st;
int n,add,a[1005];
void dfs(int x){
    if(x==1) return st.push('1');
    st.push('+'),add++;
    (x&1)?(st.push('1'),dfs(x-1)):(st.push('c'),dfs(x>>1));
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)  scanf("%d",a+i);
    for(int i=n;i>=1;i--)  dfs(a[i]+add);
    while(!st.empty())  printf("%c",st.top()),st.pop();
}

T2 T3 T4 暴力

不会做，等我什么时候会做了，过了再来写。