2023icpc省赛3/13

枫系 / 2023-05-22 / 原文

代码未经测试仅供参考

C题

正常写的话就组合数搞一搞

但是不取模，那么问题就有趣起来了

众所周知，Σc(奇数,sum)=Σ(偶数,sum)，是很对称的，所以我刚开始猜了每个点的贡献只有1或-1，试了几个菊花图后发现贡献和儿子数量有关：a[x]*(1-x的儿子数量)

找找规律：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read()
{
    ll x;scanf("%lld",&x);return x;
}
int fa[100],d[100],sum[100];
int n;
vector<int>e[100],a;
int lca(int x,int y)
{
    while(d[x]>d[y])
        x=fa[x];
    while(d[x]<d[y])
        y=fa[y];
    while(x!=y)
        x=fa[x],y=fa[y];
    return x;
}
void dfs(int x)
{
    for(auto y:e[x])
    {
        if(y==fa[x])continue;
        fa[y]=x;
        d[y]=d[x]+1;
        dfs(y);
    }
}
void work(int d)
{
    if(d==n+1)
    {
        if(a.size()==0)return ;
        int t=a[0];
        for(auto x:a)
            t=lca(x,t);
        if(a.size()&1)
            sum[t]++;
        else
            sum[t]--;
        return ;
    }
    a.push_back(d);
    work(d+1);
    a.pop_back();
    work(d+1); 
}
int main()
{
    n=read();
    for(int i=1;i<n;i++)
    {
        int x=read(),y=read();
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1);
    work(1);
    for(int i=1;i<=n;i++)
        cout<<sum[i]<<' ';
}

找规律

可以ac的代码(大概：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read()
{
    ll x;scanf("%lld",&x);return x;
}
int n;
ll sum[200010],ans;
int main()
{
    n=read();
    for(int i=1;i<n;i++)
        sum[read()]--;
    for(int i=1;i<=n;i++)
        ans+=(1-sum[i])*read();
    cout<<ans;
}

二维前缀和板子题

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read() {
    ll x;
    scanf("%lld",&x);
    return x;
}
int n,m,k,sum[4][1010][1010];
int a,b,c,d;
char s[1010];
int main()
{
    n=read();m=read();k=read();
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        for(int j=1;j<=m;j++)
        {
            sum[1][i][j]=sum[1][i-1][j]+sum[1][i][j-1]-sum[1][i-1][j-1]+(s[j]=='C');
            sum[2][i][j]=sum[2][i-1][j]+sum[2][i][j-1]-sum[2][i-1][j-1]+(s[j]=='M');
            sum[3][i][j]=sum[3][i-1][j]+sum[3][i][j-1]-sum[3][i-1][j-1]+(s[j]=='F');
        }
    }
    for(;k;k--)
    {
        a=read();b=read();c=read();d=read();
        for(int i=1;i<=3;i++)
            printf("%d ",sum[i][c][d]-sum[i][c][b-1]-sum[i][a-1][d]+sum[i][a-1][b-1]);
        printf("\n");
    }
}

理解题意后发现只需要对每个商家的物品从大到小排序，选前第i大的物品做背包，体积是i，假价值是(Σai)-X。f[i][j]表示前i个商家用j个物品最多卖多少钱。复杂度m*n+n*n

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read() {
    ll x;
    scanf("%lld",&x);
    return x;
}
int n,m,k;
int x[1010],f[1010][1010];
vector<int>a[1010];
int main()
{
    n=read();m=read();k=read();
    for(int i=1;i<=m;i++)
        x[i]=read();
    for(int i=1;i<=n;i++)
    {
        int v=read();
        a[read()].push_back(v);
    }
    for(int i=1;i<=k;i++)
        f[0][i]=-1e9;
    for(int i=1;i<=m;i++)
    {
        for(int kk=1;kk<=k;kk++)
            f[i][kk]=f[i-1][kk];
        sort(a[i].begin(),a[i].end(),greater<int>());
        for(int j=0,cnt=1,sum=0;j<a[i].size();j++,cnt++)
        {
            sum+=a[i][j];
            for(int kk=k;kk>=cnt;kk--)
                f[i][kk]=max(f[i][kk],f[i-1][kk-cnt]+sum-x[i]);
        }
    }
    cout<<f[m][k];
}