HLOJ-DAY 9

Posted on By 张, 高畅 HLOJ-DAY 9无评论

怎么又是模拟赛(悲

怎么每次都能炸(悲

[A]

(找不到原而复制原题面的屑ETG)

现在有一个长度为 n 的序列 a_1,a_2,…,a_n，满足 \forall i,j 且 ij \leq n 有 a_{ij}=a_i+a_j。

现在有 q 个长度为 n 的合法序列。卡密想要对这 q 个序列做一点修改，他会对每一个序列选择一个位置，修改这个位置的值。对于每个序列，我们要在不改动已经更改的元素的情况下，修改序列中的其他元素使得序列仍然合法。现在我们想要知道，对于每个序列，我们最小需要修改序列中多少个位置的元素才能使其合法。

很显然这题就是让你求最大质因子，直接 O(\sqrt n) 分解质因数就可以了。

至于质数筛这种科技，还是放在第四题用吧。

CODE

#include<bits/stdc++.h>
using namespace std;
int n,m;
int main()
{
    freopen("log.in","r",stdin);
    freopen("log.out","w",stdout);
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int x;
        scanf("%d",&x);
        if(x==1)puts("-1");
        else
        {
            int t=x,res=0;
            for(int i=2;i<=x/i;i++)
            {
                if(t%i==0)
                {
                    while(t%i==0)t/=i;
                    res=max(res,i);
                }
            }
            if(t>1)res=max(res,t);
            printf("%d\n",n/res-1);
        }
    }
    return 0;
}

[B]

(又找不到原而复制题面的ZGC)

对于一个正整数序列 a_i，若它可以被划分为两个不相交的子序列（可以不连续，每个位置恰好属于其中一个子序列），两个子序列的和相等，那么称这个序列为好序列。
对于一个正整数序列 A，若其所有长度为 k 的连续子序列都是好序列，那么称这个序列为 k-序列。
给你 T 个正整数序列，对于每个序列，求出它是 k-序列 的所有 k 的值。

显然这题我们需要考虑如何快速判断区间 [l,r] 是否合法。

考虑DP，令 f(i) 为到当前的右端点 r 时，从 a_1,a_2,…,a_r 中任意取出一些数和为 i 时左端点 l 的最大值。

这个转移写起来像一个 01背包问题，因此转移时注意内层循环倒序。

转移方程 $f_S=max(fS,f{S-ar})，每一次DP完后令f{a_r}=r$

这样子，判断 [l,r] 是否合法，其实只需要判断 [l,r] 的和是否是偶数， f_{cnt/2} 是否 \geq l（是的TJ这里写错了(应该吧)）。

注意我们每一次实际只使用 f_{cnt/2} ，因此做DP的时候值域可以压缩一半。

CODE:

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5,M=1e5+5;
int n,a[N],s[N],f[M],st[N];
void work()
{
    memset(f,-0x3f,sizeof f);
    memset(st,0,sizeof st);
    scanf("%d",&n);
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        s[i]=s[i-1]+a[i];   
    }
    f[0]=1;
    st[1]=1;
    for(int r=1;r<=n;r++)
    {
        for(int S=s[n]/2;S>=a[r];S--)f[S]=max(f[S],f[S-a[r]]);
        f[a[r]]=r;
        for(int l=1;l<r;l++)
        {
            int cnt=s[r]-s[l-1];
            if((cnt&1)||(f[cnt/2]<l))st[r-l+1]=1;
        }
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(!st[i])cnt++;
    }
    printf("%d ",cnt);
    for(int i=1;i<=n;i++)
    {
        if(!st[i])printf("%d ",i);
    }
}
int main()
{
    freopen("part.in","r",stdin);
    freopen("part.out","w",stdout);
    int T;
    scanf("%d",&T);
    for(int i=0;i<T;i++)
    {
        if(i)puts("");
        work();
    }
    return 0;
}

[C]

原题
TG的题，但还是写一下吧。

首先先将行与列拆开，变成二分图的形式进行连边。

如果在二分图上出现了环，那么肯定是合法的，输出这一个环即可。

但如果没有出现环，也不代表一定不合法。

我们考虑从叶子节点开始树形DP。

（其实就是将子节点返回的结果异或起来）

如果为 0 ，代表此节点向上的那一条边是一定要选的，而此时如果这个节点为根节点，显然是不合法的。

注意偶数时找环的细节。

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int n,m,st[N],f[N];
vector<int>res;
vector<pair<int,int>>path,G[N];
void dfs(int u,int father,int id)
{
    st[u]=1;
    path.push_back({u,id});
    for(auto [j,k]:G[u])
    {
        if(j==father)continue;
        if(st[j])
        {
            puts("TAK");
            int cnt=1;
            for(int i=path.size()-1;~i&&path[i].first!=j;i--)cnt++;
            printf("%d\n",cnt);
            printf("%d ",k);
            for(int i=path.size()-1;~i&&path[i].first!=j;i--)printf("%d ",path[i].second);
            exit(0);
        }
        dfs(j,u,k);
    }
    path.pop_back();
}
int DFS(int u,int father,int id)
{
    st[u]=1;
    for(auto [j,k]:G[u])
    {
        if(j==father)continue;
        f[u]^=DFS(j,u,k);
    }
    if(!f[u])
    {
        res.push_back(f[u]=id);
        return 1;
    }
    return 0;
}
int main()
{
    freopen("trap.in","r",stdin);
    freopen("trap.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        G[a].push_back({b+n,i});
        G[b+n].push_back({a,i});
    }
    for(int i=1;i<=(n<<1);i++)
    {
        if(!st[i])dfs(i,-1,-1);
    }
    memset(st,0,sizeof st);
    for(int i=1;i<=(n<<1);i++)
    {
        if(!st[i])DFS(i,-1,-1);
    }
    for(int i=1;i<=(n<<1);i++)
    {
        if(f[i]==-1)
        {
            puts("NIE");
            return 0;
        }
    }
    puts("TAK");
    printf("%d\n",res.size());
    for(auto i:res)printf("%d ",i);
    return 0;
}

[D][E]

前面的区域，以后再来探索吧。（

训练日志

发表回复