夏令营7.13总结

今天又模考了。

时间线

$8:30\sim8:50做T1，AC$
$8:50\sim9:07做T2，AC$
$9:07\sim10:35思考T3-T4$
$10:35\sim11:00做T4，失败$
$11:00\sim12:00做T3，做了3次，22分$

时间线详解

T1

考试的时候想着两层for里面嵌套两个for，但是复杂度直接起飞，TLE67。

第二次尝试从嵌套两个变成一个，但是还是TLR67。

最后，用了两个$O(n\times m)$复杂度的for，竟然过了。

T2

这题是个找规律，发现了规律：行或列，会有一个在正负1之间有一个完全平方数，行和列分别时奇数的和偶数的。

找到这个规律之后，就可以直接根据规律写了，时间复杂度时$O(t)$。

T3

这题用dp

状态定义：$f[i][j][k]:从前i个问题里选j个，所选问题的优美度之和不小于k，所选总满意度的最大值$

$如果无法做到。令$f[i][j][k]=-inf$

$0\le i\le N$
$0\le j\le i$
$0\le k\le K$

递推式

考虑第$i$个问题选或不选。

• 选：$f[i-1][j-1][max(0,k-b_i)]+A_i$
• 不选：$f[i-1][j][k]=1$

$$
f[i][j][k]=max(f[i-1][j-1][max(0,k-b_i)]+A_i,f[i-1][j][k]=1)
$$

子问题数量$O(N\times D\times K)$

内存：$1.25\times 10^8\times 8B=爆炸，超256MiB$

节约空间

$f[i][0][0]=0,0\le i\le N$

01背包的省空间写法：滚动数组

我们注意到有一个维度是只用一次的（你说一次性也行），就只要从前往后枚举，就可以节省空间。

long long f[maxn][maxn];
for(int i=1;i<=n;i++)
    for(int j=min(i,d);j>=1;k++)
        for(int k=0;k<=K【大写！】;k++)
            f[j][k]=max(f[j-1][max(0,k-b[i])]+a[i],f[j][k]);

这里$1\le i\le N,1\le j$

T4

考试的时候没有想通这个逻辑。

就是如果一个人出现了两次超过同一个人，就不可能在同一圈，因为其他人都是不能后退的。

如果想通了这个逻辑，就很简单了。

int n,q;
cin>>n>>q;
vector<int> overmake(n,-1);
int ans=0;
int last=0;
for(int i=1;i<=q;i++){
    int x;
    cin>>x;
    if(x>0){
        if(overmake[x]>=last){
            ans++;
            last=i;
        }
        overmake[x]=i;
    }
    else{
        overmake[-x]=-1;
    }
}
cout<<ans;

$\Huge the \ end$