Codeforces Round #540 (Div. 3)

Posted by

A. Water Buying

写的。。有点麻烦。。。 其实可以省略许多东西的。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
typedef long long ll;
static const ll INF=1e18;
using namespace std;
int q,a,b;
ll n,ans=INF;
inline int iread(){
    int x=0;bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
inline ll lread(){
    ll x=0;bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
inline void init(){
    ans=INF;
}
inline ll get_min(ll a,ll b){
    return a<b?a:b;
}
int main(){
    q=iread();
    for(int i=1;i<=q;i++){
        n=lread();a=iread();b=iread();
        if(n==1){
            printf("%d\n",a);
            init();
            continue;
        }
        if(a<b){
            ans=get_min(ans,(ll)(n*a));
            ans=get_min(ans,(ll)((ll)((n/2)*b)+(ll)((n%2)*a)));
        }
        else ans=get_min(ans,(ll)((ll)((n/2)*b)+(ll)((n%2)*a)));
        if(n%3==0){
            ans=get_min(ans,(ll)((n/3)*(a+b)));
        }
        else{
            if(n%3==1) ans=get_min(ans,(ll)((n/3)*(a+b)+a));
            else ans=get_min(ans,(ll)((n/3)*(a+b)+get_min(2*a,b)));
        }
        printf("%I64d\n",ans);
        init();
    }
    return 0;
}

B. Tanya and Candies

暴力前缀和。。和官方写法不同。但也能过。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
typedef long long ll;
static const int MAXN=200050;
using namespace std;
int ans1,ans2,n,a[MAXN],sum1[MAXN],sum2[MAXN],num1,num2;
vector<int> Ans;
inline int iread(){
    int x=0;bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
int main(){
    n=iread();
    //n==1!!!!!
    for(int i=1;i<=n;i++){
        a[i]=iread();
        if(i%2) sum1[++num1]=sum1[num1-1]+a[i];
        else sum2[++num2]=sum2[num2-1]+a[i];
    }
    if(n%2==1){
        ans1+=sum2[(n>>1)]-sum2[0];
        ans2+=sum1[(n>>1)+1]-sum1[1];
    }
    else{
        ans1+=sum2[(n>>1)]-sum2[0];
        ans2+=sum1[(n>>1)]-sum1[1];
    }
    if(ans1==ans2) Ans.push_back(1);
    for(int i=2;i<=n;i++){
        ans1=ans2=0;
        if(i%2==0){
            ans1+=(sum1[i/2]-sum1[0]);
            ans2+=(sum2[(i/2)-1]-sum2[0]);
            if(n%2==0){
                ans1+=sum2[(n>>1)]-sum2[i/2];
                ans2+=sum1[(n>>1)]-sum1[i/2];
            }
            else{
                ans1+=sum2[(n>>1)]-sum2[i/2];
                ans2+=sum1[(n>>1)+1]-sum1[i/2];
            }
        }
        else{
            ans1+=(sum1[(i-1)/2]-sum1[0]);
            ans2+=(sum2[(i/2)]-sum2[0]);
            if(n%2==0){
                ans1+=sum2[(n>>1)]-sum2[i/2];
                ans2+=sum1[(n>>1)]-sum1[i/2+1];
            }
            else{
                ans1+=sum2[(n>>1)]-sum2[i/2];
                ans2+=sum1[(n>>1)+1]-sum1[i/2+1];
            }
        }
        if(ans1==ans2) Ans.push_back(i);
    }
    printf("%d\n",(int)Ans.size());
    return 0;
}

C. Palindromic Matrix

暴力枚举。对于n为偶数的,直接填即可。 对于n为奇数的情况,先填边缘部分,最后填中间的行列。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <cmath>
static const int lim=1005;
static const int MAXN=25;
using namespace std;
int n,x,num[lim],ans[MAXN][MAXN];
inline int read(){
    int x=0,sign=0;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
int main(){
    n=read();
    for(int i=1;i<=(int)pow(n,2);i++){
        x=read();
        num[x]++;
    }
    for(int i=1;i<=n/2;i++){
        for(int j=1;j<=n/2;j++){
            bool flag=false;
            for(int k=1;k<=lim-5;k++){
                if(num[k]>=4){
                    ans[i][j]=ans[i][n-j+1]=ans[n-i+1][j]=ans[n-i+1][n-j+1]=k;
                    num[k]-=4;
                    flag=true;
                    break;
                }
            }
            if(!flag) return 0&printf("NO\n");
        }
    }
    if(n%2==1){
        for(int i=1;i<=n/2;i++){
            bool flag=false;
            for(int k=1;k<=lim-5;k++){
                if(num[k]>=2){
                    ans[i][n/2+1]=ans[n-i+1][n/2+1]=k;
                    num[k]-=2;
                    flag=true;
                    break;
                }
            }
            if(!flag) return 0&printf("NO\n");
        }
        for(int j=1;j<=n/2;j++){
            bool flag=false;
            for(int k=1;k<=lim-5;k++){
                if(num[k]>=2){
                    ans[n/2+1][j]=ans[n/2+1][n-j+1]=k;
                    num[k]-=2;
                    flag=true;
                    break;
                }
            }
            if(!flag) return 0&printf("NO\n");
        }
        bool flag=false;
        for(int k=1;k<=lim-5;k++){
            if(num[k]==1){
                ans[n/2+1][n/2+1]=k;
                num[k]--;
                flag=true;
                break;
            }
        }
        if(!flag) return 0&printf("NO\n");
    }
    printf("YES\n");
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) printf("%d%c",ans[i][j],j==n?'\n':' ');
    }
    return 0;
}

D1&D2. Coffee and Coursework

二分天数,贪心每次取当前剩余序列中最大值。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll;
static const int MAXN=200050;
using namespace std;
int n,m,l,r,mid,ans,a[MAXN];
ll sum;
inline int read(){
    int x=0;bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
inline bool cmp(int a,int b){
    return a>b;
}
inline bool check(int day){
    int page,cnt=1,lose=0;
    ll sumnow=0;
    for(int i=1;i<=n;i++){
        page=max(0,a[i]-lose);
        sumnow+=page;
        if(sumnow>=m) return true;
        if(++cnt>day){
            lose++;
            cnt=1;
        }
    }
    return false;
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++) a[i]=read(),sum+=a[i];
    if(sum<m) return 0&printf("-1\n");
    sort(a+1,a+n+1,cmp);
    l=1,r=200050,ans=-1;
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}

E. Yet Another Ball Problem

直接枚举。枚举前判断可行性。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
typedef long long ll;
static const int MAXN=200050;
using namespace std;
int num,cnt,o[MAXN],b[MAXN];
ll n,k;
int main(){
    scanf("%I64d %I64d",&n,&k);
    ll s=(k*(k-1));
    if(n>s) return 0&printf("NO\n");
    printf("YES\n");
    for(int i=1;i<=k;i++){
        for(int j=i+1;j<=k;j++){
            printf("%d %d\n",i,j);
            if(++num>=n) return 0;
            printf("%d %d\n",j,i);
            if(++num>=n) return 0;
        }
    }
    return 0;
}

F1. Tree Cutting (Easy Version)

预先统计每颗子树下红,蓝颜色的个数。然后再搜一遍判断一下即可。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
static const int MAXN=300050;
using namespace std;
struct Edge{
    int to,nextt;
}edge[MAXN<<1];
int n,u,v,ans,num,head[MAXN],red[MAXN],blue[MAXN],a[MAXN];
bool vis[MAXN];
inline int read(){
    int x=0;bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
inline void addedge(int u,int v){
    edge[++num].to=v;
    edge[num].nextt=head[u];
    head[u]=num;
}
void dfs1(int x){
    if(a[x]==1) red[x]++;
    else if(a[x]==2) blue[x]++;
    for(int i=head[x];i;i=edge[i].nextt){
        int to=edge[i].to;
        if(vis[to]) continue;
        vis[to]=true;
        dfs1(to);
        red[x]+=red[to];
        blue[x]+=blue[to];
    }
}
void dfs2(int x,int from){
    if(from!=-1&&(red[1]-red[x]==0||blue[1]-blue[x]==0)&&(!red[x]||!blue[x])) ans++;
    for(int i=head[x];i;i=edge[i].nextt){
        int to=edge[i].to;
        if(vis[to]) continue;
        vis[to]=true;
        dfs2(to,x);
    }
}
int main(){
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n-1;i++){
        u=read();v=read();
        addedge(u,v);
        addedge(v,u);
    }
    vis[1]=true,dfs1(1);
    memset(vis,false,sizeof(vis));
    vis[1]=true,dfs2(1,-1);
    printf("%d\n",ans);
    return 0;
}

F2. Tree Cutting (Hard Version)

dfs求出每个点的深度及其父亲节点。 然后把相同颜色的点加入一个优先队列中,设现在有一个点x,颜色为w。 把离x最远的相同颜色的点与x之间(包括两头)的路径上无颜色的点标上颜色w。 在往上跳的过程中,若发现一个点的颜色已经有颜色了,且这个颜色不为当前颜色,则显然无法完全的分离两种颜色,即无解。最终记录一下颜色为w的深度最低的点lca[w]。 然后建新图。建新图的意义是,把可以对答案有贡献的边连上。对于颜色相同的点,若都无颜色,则将两个点进行连边;否则不管。因为对于相同颜色的点,显然之间的边不能切割。对于两个点其中一个点无颜色一个点颜色为w的情况,将这个点与lca[w]连边。否则将两个颜色不同的点lca[w1],lca[w2]相连。 因为连上的点是lca[w],所以可以大大缩小图的规模。因为相同颜色的点之间不能断边,所以其lca[w]到任意一个颜色为w的点之间的“链”不能断开。就相当于是把颜色相同的点进行“缩点”。 接下来就是dp过程。 设状态转移方程f[x][2],其中f[x][0]表示以x为根节点的子树中(包括根节点)存在无颜色节点时的方案数,f[x][1]表示以x为根节点的子树中(包括根节点)存在有颜色节点时的方案数。 对于初值的设定:

    \[ f[x][0]=(a[x]==0) f[x][1]=(a[x]!=0) \]

则:

    \[ f[x][1] = \sum \limits_{k \in g(x)} \prod \limits_{to \in g(x), to \ne k} f[k][1] \cdot (f[to][0] + f[to][1]) \]

且:

    \[ f[x][0] = \prod \limits_{to \in g(x)} (f[to][0] + f[to][1]) \]

#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
typedef long long ll;
static const int MAXN=300050;
static const int mod=998244353;
using namespace std;
priority_queue<pair<ll,ll> > q[MAXN];
vector<pair<ll,ll> > Edge;
struct node{
    int to,nextt;
}edge[MAXN<<1];
int n,k,u,v,num,lca[MAXN],a[MAXN],head[MAXN],fa[MAXN],dep[MAXN];
ll f[MAXN][2];
inline int read(){
    int x=0;bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
inline void addedge(int u,int v){
    edge[++num].to=v;
    edge[num].nextt=head[u];
    head[u]=num;
}
void init(){
    memset(head,0,sizeof(head));
    num=0;
}
void dfs1(int x,int from,int depth){
    fa[x]=from;
    dep[x]=depth;
    for(int i=head[x];i;i=edge[i].nextt){
        int to=edge[i].to;
        if(to==from) continue;
        dfs1(to,x,depth+1);
    }
}
void solve(int x,int from){
    f[x][0]=(a[x]==0);f[x][1]=(a[x]!=0);
    for(int i=head[x];i;i=edge[i].nextt){
        int to=edge[i].to;
        if(to==from) continue;
        solve(to,x);
        f[x][1]=((f[x][0]*f[to][1])%mod+(f[x][1]*(f[to][0]+f[to][1]))%mod)%mod;
        f[x][0]=(f[x][0]*(f[to][0]+f[to][1]))%mod;
    }
}
int main(){
    n=read();k=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<n;i++){
        u=read();v=read();
        Edge.push_back(make_pair(u,v));
        addedge(u,v);addedge(v,u);
    }
    dfs1(1,0,1);
    for(int i=1;i<=n;i++) q[a[i]].push(make_pair(dep[i],i));
    for(int i=1;i<=k;i++){
        while(q[i].size()>1){
            int now=q[i].top().second;q[i].pop();
            if(a[fa[now]]&&a[fa[now]]!=i) return 0&printf("0\n");
            else if(!a[fa[now]]) a[fa[now]]=i,q[i].push(make_pair(dep[fa[now]],fa[now]));
        }
        lca[i]=q[i].top().second;
    }
    init();
    for(int i=0;i<(int)Edge.size();i++){
        u=Edge[i].first;v=Edge[i].second;
        if(a[u]==a[v]){
            if(a[u]) continue;
            addedge(u,v);addedge(v,u);
        }
        else if(!a[u]||!a[v]){
            if(!a[u]) swap(u,v);
            addedge(lca[a[u]],v);addedge(v,lca[a[u]]);
        }
        else addedge(lca[a[u]],lca[a[v]]),addedge(lca[a[v]],lca[a[u]]);
    }
    solve(1,0);
    printf("%I64d\n",f[1][1]);
    return 0;
}
  ]]>

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注