EOJ Monthly 2018.8(A,B,C,D)

A. A Simple Convolution

卷积

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int mi[105][105];
int conv[105][105];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) scanf("%d",&mi[i][j]);
    }
    int w,h;
    scanf("%d%d",&w,&h);
    for(int i=1;i<=w;i++)
    {
        for(int j=1;j<=h;j++) scanf("%d",&conv[i][j]);
    }
    for(int i=1;i<=n-w+1;i++)
    {
        for(int j=1;j<=m-h+1;j++)
        {
            int ans=0;
            for(int p=i;p<i+w;p++)
            {
                for(int q=j;q<j+h;q++) ans+=mi[p][q]*conv[p-i+1][q-j+1];
            }
            printf("%d ",ans);
        }
        printf("\n");
    }
}

B. Bad Queen

暴力蛇形遍历

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int vis[105][105];
int main()
{
    int n,m,x,y;
    scanf("%d%d%d%d",&n,&m,&x,&y);
    vis[x][y]=1;
    if(!vis[1][y]) vis[1][y]=1,printf("1 %d\n",y);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(!vis[i][j]&&i&1) printf("%d %d\n",i,j),vis[i][j]=1;
            else if(!vis[i][m-j+1]&&!(i&1)) printf("%d %d\n",i,m-j+1),vis[i][m-j+1]=1;
        }
    }
}

C. Channel On Live

类似差分标记的O(n)暴力

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<int,int> >pii;
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    double sum=0;
    for(int i=0;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        pii.push_back(make_pair(a,1));
        pii.push_back(make_pair(b+1,-1));
        sum+=b-a+1;
    }
    sort(pii.begin(),pii.end());
    int cnt=0;
    int Max=0;
    for(auto x:pii) cnt+=x.second,Max=max(Max,cnt);
    printf("%d\n",Max);
    printf("%.12f",sum/(1.0*m));
}

D. Delivery Service

tarjan求lca,树上差分计算边覆盖次数,贪心匹配大覆盖次数与小边权.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
struct edge
{
    int next,to,dis;
} e[maxn<<1],q[maxn<<1];
struct Point_pair
{
    int len,lca,u,v;
}pp[maxn];
int head[maxn],cnt,headq[maxn],dis[maxn],s[maxn],f[maxn],w[maxn],pos,tot[maxn];
bool vis[maxn];
inline int read()
{
    int x=0;
    char ch=getchar();
    while(ch>'9'||ch<'0') ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
    return x;
}
inline void add_edge(int x,int y,int d)
{
    e[++cnt].next=head[x];
    e[cnt].to=y;
    e[cnt].dis=d;
    head[x]=cnt;
}
inline void add_que(int x,int y)
{
    q[++cnt].next=headq[x];
    q[cnt].to=y;
    headq[x]=cnt;
}
inline int find(int x)
{
    return f[x]==x?f[x]:f[x]=find(f[x]);
}
inline int dfs(int u,int pre)
{
    int ans=s[u];
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].to;
        if(v==pre) continue;
        ans+=dfs(v,u);
    }
    tot[++pos]=ans;
    return ans;
}
bool cmp(int x,int y)
{
    return x>y;
}
ll cal(int n,int m)
{
    memset(s,0,sizeof(s));
    for(int i=1; i<=m; i++)
    {
        s[pp[i].u]++;
        s[pp[i].v]++;
        s[pp[i].lca]-=2;
    }
    dfs(1,0);
    ll ans=0;
    sort(w+1,w+n);
    sort(tot+1,tot+pos,cmp);
    for(int i=1;i<pos;i++) ans+=w[i]*tot[i];
    return ans;
}
inline void tarjan(int u,int pre)
{
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].to;
        if(v==pre) continue;
        dis[v]=dis[u]+e[i].dis;
        tarjan(v,u);
        int f1=find(v),f2=find(u);
        if(f1!=f2) f[f1]=find(f2);
        vis[v]=1;
    }
    for(int i=headq[u]; i; i=q[i].next)
    {
        if(vis[q[i].to])
        {
            int p=(i+1)>>1;
            pp[p].lca=find(q[i].to);
            pp[p].len=dis[u]+dis[q[i].to]-2*dis[pp[p].lca];
        }
    }
}
int main()
{
    int n=read();
    for(int i=1; i<n; i++)
    {
        int x=read(),y=read(),t=read();
        add_edge(x,y,t),add_edge(y,x,t),w[i]=t;
    }
    for(int i=1; i<=n; i++) f[i]=i;
    cnt=0;
    int m=read();
    for(int i=1; i<=m; i++)
    {
        int x=read(),y=read();
        pp[i].u=x,pp[i].v=y;
        add_que(x,y),add_que(y,x);
    }
    tarjan(1,0);
    ll ans=cal(n,m);
    printf("%lld\n",ans);
}