2021年中国大学生程序设计竞赛女生专场

2021年中国大学生程序设计竞赛女生专场

概况

前五题去年的这个时候VP的，今年学校要去打女生赛，我先帮她们看看

C - 连锁商店

一眼状压，但发现 \(n \geq 36\) 二进制位状态 \(S\) 记录是否选了这个公司，会发现根本开不了那么大的数组，也没有那么多的时间

易得出最多重复的公司数量只有 \(m \leq 18\) 个，我们用二进制位状态 \(S\) 记录是否选了有重复的点即可

int n, m, a[37], w[37], c[N], res[N], id, cnt[37], f[37][1 << 19];
map<int, int> mp;
vector<int> e[37];
void solve()
{
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
    {
        cin>>c[i];    cnt[c[i]]++;
    }
    for(int i = 1; i <= n; i++)
        cin>>a[i];
    for(int i = 1; i <= n; i++)
        w[i] = a[c[i]];
    for(int i = 1; i <= m; i++)
    {
        int u, v;   cin>>u>>v;
        e[u].push_back(v);
    }
    for(int i = 1; i <= n; i++)
        if(cnt[c[i]] == 1)
            c[i] = 0;
        else if(cnt[c[i]] > 1)
        {
            if(mp[c[i]] == 0)
                mp[c[i]] = ++id;
            c[i] = mp[c[i]];
        }
    for(int i = 1; i <= n; i++)
        c[i]--;
    memset(f, ~0x3f, sizeof f);
    if(c[1] == -1)
    {
        f[1][0] = w[1];
        // cout<<"!\n";
        // cout<<f[1][0]<<'\n';
    }
    else 
    {
        f[1][1 << c[1]] = w[1];
        // cout<<f[1][1 << c[1]]<<'\n';
    }
    
    res[1] = w[1];
 
    // for(int u = 1; u <= n; u++)
    //     cout<<c[u]<<" "<<' ';
    // cout<<'\n';
    // cout<<"id : "<<id<<"  (1 << id) : "<<(1 << id)<<'\n';
    for(int u = 1; u < n; u++)
    {
        for(int S = 0; S < (1 << id); S++)
        {
            if(f[u][S] <= 0)    continue;
            for(auto v : e[u])
            {
                if(c[v] != -1 && ((S >> c[v]) & 1))
                {
                    f[v][S] = max(f[u][S], f[v][S]);
                    res[v] = max(f[v][S], res[v]);
                    // cout<<"tag : "<<1<<"  u : "<<u<<"  v : "<<v<<" S : "<<S<<" "<<f[v][S]<<"  "<<res[v]<<'\n';
                }
                else
                {
                    if(c[v] == -1)
                    {
                        f[v][S] = max(f[u][S] + w[v], f[v][S]);
                        res[v] = max(f[v][S], res[v]);
                        // cout<<"tag : "<<2<<"  u : "<<u<<"  v : "<<v<<" S : "<<S<<" "<<f[v][S]<<"  "<<res[v]<<'\n';
 
 
                    }
                    else
                    {
                        f[v][S | (1 << c[v])] = max(f[u][S] + w[v], f[v][S | (1 << c[v])]);
                        res[v] = max(f[v][S | (1 << c[v])], res[v]);
                        // cout<<"tag : "<<3<<"  u : "<<u<<"  v : "<<v<<" S : "<<(S | (1 << c[v]))<<" "<<f[v][S | (1 << c[v])]<<"  "<<res[v]<<'\n';
                    
                    }
                }
            }
        }
    }
    for(int i = 1; i <= n; i++)
        cout<<res[i]<<'\n';
}

B - 攻防演练

构造子序列，贪心地去选择最近距离下，离当前位置最远的字母，但这样直接做是\(O(qN^2)\) 的

用倍增优化这个选择即可

const int N = 2e5 + 10;
const int LOGN = 20;
typedef long long ll;

int n, m, q, ne[30], fa[N][LOGN + 2];
int a[N];
string s;

void lca_init()
{
    for(int i = n; i >= 0; i--)
        for(int j = 1; j <= LOGN; j++)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
int lca_query(int u, int v)
{
    int res = 0;
    for(int j = LOGN; j >= 0; j--)
        if(fa[u][j] <= v && fa[u][j] != 0)    
            u = fa[u][j], res += (1 << j);
    return res;
}
void solve()
{
    cin>>m>>n;
    cin>>s; s = "a" + s;
    for(int i = 0; i <= n; i++)
        a[i] = (s[i] - 'a' + 1);

    for(int j = 1; j <= m; j++)
        ne[j] = n + 1;

    for(int i = n; i >= 0; i--)
    {
        for(int j = 1; j <= m; j++)
            fa[i][0] = max(ne[j], fa[i][0]);
        if(i)
            ne[a[i]] = i;
    }
    lca_init();
    cin>>q;
    for(int i = 1; i <= q; i++)
    {
        int l, r;   cin>>l>>r;
        cout<<lca_query(l - 1, r) + 1<<'\n';
    } 
}