省常中联测题选IV HGOI1021 【转自beautiful_cxw】

转自cxw的博客原文

NOIP2016 提高组模拟赛

IzumiKonata
题目名Tetrix Tree Copier
输入文件名tetrix.in tree.in copier.in
输出文件名tetrix.out tree.out copier.out
时间限制1s 1s 1s
内存限制256M 256M 256M
测试点数量10 10 10
Linux 下评测。
1
1 Tetrix
1s; 256M
1.1 题目描述
俄罗斯方块是一款历史悠久的休闲小游戏。
下面考虑一种和俄罗斯方块无关的游戏,我们将它称为Tetrix。
Tetrix 在一个大小为N M 的方格中进行。玩家可以使用恰由4 个单位方格
组成的任意连通图形不重叠地覆盖这些方格。玩家得到的分数为被覆盖的方格数。
对于给定的N 和M,请求出最大可能的得分,并相应地给出一种覆盖方案。
1.2 输入格式
第一行一个正整数T 表示数据组数。
接下来T 行,每行包含2 个正整数N 和M。
1.3 输出格式
对于每组测试数据:
第一行包含一个正整数,表示最大得分。
接下来N 行,每行M 个整数,描述一个矩阵A,即你的覆盖方案。
1.3.1 覆盖方案格式的约定
Ai;j 在32 位有符号整数范围内。
Ai;j = 0 当且仅当方格(i; j) 没有被覆盖。
Ai1;j1 = Ai2;j2
?= 0 当且仅当方格(i1; j1) 和(i2; j2) 被同一连通块覆盖。
1.4 样例输入
13
7
1.5 样例输出
20
2 2 3 3 3 5 5
1 2 2 3 0 5 5
1 1 1 4 4 4 4
1.6 数据规模
对于20% 的数据,1  N;M  5。
对于100% 的数据,1  N;M  32,1  T  5。
对于每个测试点,若你的最大得分均正确而方案至少有一个错误,可获得30%
的部分分。
2
2 Tree
1s; 256M
2.1 题目描述
魔法森林里有一棵魔法之树,树上的每一根枝干都蕴藏着巨大的魔力。然而,
它最近的样子有点异常。
经过一番调查后发现,这是一棵包含N 个节点的有根树,根节点的编号为1。
每条边有一个魔力值vi,每个节点有一个容量值bi。如果对于一个节点i,存在它
的一个祖先j,满足i 的容量值小于从i 到j 路径上的魔力值之和,那么节点i 处
就会发生魔力溢出。
为了避免魔力溢出,我们希望剪去这棵树的若干子树(也可以不剪),使得剩
余的树中不存在魔力溢出的节点。为了尽可能减少损失,请你求出剪去的节点个
数的最小值。
2.2 输入格式
第一行一个正整数N,表示节点个数。
第二行N 个正整数b1; b2; :::; bn。
第三行N ?? 1 个正整数p2; p3; :::; pn,其中pi 表示节点i 的父亲。
第四行N ?? 1 个整数v2; v3; :::; vn,其中vi 表示边(pi; i) 的魔力值。
2.3 输出格式
一行一个非负整数,表示剪去的节点个数的最小值。
2.4 样例输入
9
88 22 83 14 95 91 98 53 11
3 7 1 1 9 5 6 3
24 -8 67 64 65 12 -80 8
2.5 样例输出
5
2.6 样例解释
被删除的节点编号为2; 4; 6; 8; 9。
2.7 数据规模
对于30% 的数据,1  N  10。
对于60% 的数据,1  N  3000。
对于100% 的数据,1  N  100000; 1  pi < i; 1  bi  109; jvij  109。
3
3 Copier
1s; 256M
3.1 题目描述
K 终于下定决心摆脱NEET 生活,开始经营一家复印店。
K 有N 台复印机。第i 台复印机工作时,每ti 秒可以将一份文件复印一份。
多台复印机可以同时工作,但每台正在工作的复印机都必须占用一份文件用于复
印。你可以在这些复印机停止工作后回收被占用的文件。
K 每天只接待一位客户(因为懒)。通过使用某种与时间有关的能力,她知道
在接下来的M 天中,第i 天的客户将要求把一份文件复印ai 份。
特别地,在同一天内,K 按编号逐个递增的顺序使用这些复印机。即对于任意
的i > 1,只有在编号小于i 的所有复印机都在工作时,K 才会让编号为i 的复印
机开始工作。
现在K 希望知道,在接下来的M 天里,她每天至少需要工作多少秒。
注意:由于K 拥有某种与时间有关的能力,你可以认为一天的时长为1018 秒,
即当天的请求一定会在当天完成。
3.2 输入格式
第一行2 个正整数N 和M。
第二行N 个正整数ti。
第三行M 个正整数ai。
3.3 输出格式
一行M 个正整数ansi,表示第i 天的最小工作时间。
3.4 样例输入
3 3
3 2 2
4 5 6
3.5 样例输出
7 7 9
3.6 样例解释
考虑ai = 5 的情况:
时刻0,把原件交给复印机#1,#1 开始工作。
时刻3,#1 完成了一份复印件。把这份复印件交给#2,#2 开始工作。
时刻5,#2 完成了一份复印件。把这份复印件交给#3,#3 开始工作。
时刻6,#1 完成了一份复印件。
时刻7,#2; 3 各完成了一份复印件。至此完成了5 份复印件。
4
3.7 数据规模

N  M  ti  ai 

0 5 5 5 100
1 50 50 100
2 100 100 N ?? 1
3 100
4 5000 N ?? 1
5 5000
6 1
7 N ?? 1
8
9
所有测试点均满足:1  N  2  105; 1  M  103; 1  ti  103; 1  ai  109。

T1

题意:求用四个方格联通块能在不互相覆盖最大覆盖一个矩阵

直接蛇形排列,解决了。
(注意矩阵小于四个的时候稍微特判一下,要全输出0)

#include<bits/stdc++.h>
using namespace std;
int a[40][40],n,m,cnt,p=0;
int main()
{
//  freopen("tetrix.in","r",stdin);
//  freopen("tetrix.out","w",stdout);
    int T;
    scanf("%d",&T);
    while (T--)
      {
        scanf("%d%d",&n,&m);
        cnt=n*m%4;
        printf("%d\n",n*m-cnt);
        memset(a,0,sizeof(a));
        int i=1,j=1,color=1,numc=1,nowc=1,js=1;
        a[i][j]=color;
        while (numc<n*m-cnt)
          {
            if (nowc==4) nowc=0,color++;
            j+=js;
            if (j>m) i++,js=-1,j=m;
            if (j<1) i++,js=1,j=1;
            a[i][j]=color; 
            numc++;
            nowc++;
          }
        for (int i=1; i<=n; i++)
        {
          for (int j=1; j<=m; j++)
            if (n*m-cnt==0) cout<<"0 "; else printf("%d ",a[i][j]);
          printf("\n");
        }
      }
}

T2
题意:给你一棵树,有点权有边权,删去一些点使之满足每个点的权大于根到它的边权和

暴力做吧,注意当加上下一条边时候如果边权和小于原先权值和时,此时边权和清零。

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int head[maxn],n,m,cnt,fa[maxn],nsum[maxn];
long long a[maxn],ans; 
struct node
{
    int v,nxt;
    long long w;
}e[maxn<<1];
inline void add(int u,int v,int w)
{
    cnt++;
    e[cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
inline void build(int fath,int u)
{
    for (int i=head[u]; i; i=e[i].nxt)
      {
        int v=e[i].v;
        //cout<<u<<' '<<v<<endl;
        if (v==fath) continue; 
        build(u,v);
        nsum[u]+=nsum[v];
      }
    nsum[u]++;
}
inline void dfs(int fath,int u,long long num)
{
    for (int i=head[u]; i; i=e[i].nxt)
    {
        int v=e[i].v;
        if (v==fath) continue;
        if (max(num+e[i].w,e[i].w)>a[v]) 
          {
            //cout<<u<<' '<<v<<' '<<num<<' '<<nsum[v]<<endl;
            ans+=nsum[v];
            continue;
          }
        dfs(u,v,max(e[i].w,e[i].w+num));
    }
}
int main()  
{
    scanf("%d",&n);
    for (int i=1; i<=n; i++) scanf("%d",&a[i]);
    for (int i=2; i<=n; i++) scanf("%d",&fa[i]);
    for (int i=2; i<=n; i++) 
      {
        int x;
        scanf("%d",&x);
        add(i,fa[i],x);
        add(fa[i],i,x);
      }
    build(0,1);
    //for (int i=1; i<=n; i++)
      //cout<<nsum[i]<<" ";
    dfs(0,1,0);
    printf("%lld",ans);
}

T3
题意:有一个很社保的老板用打印机打印东西,要按照顺序打印,必须在前一个打印机完成一份打印之后才能开始打印,求每天打印任务最少完成时间

做的时候大概想了想,用暴力二分,统计每个时间点能完成的任务数量,二分找$a[i]$,搞定。

正解就是上面那个方法加上优先队列等等优化(……完全不是一个方法了喂!!!!!!!!!!!)
首先,要么在所有机器都启用之前完成该任务,要么之后,
先用优先队列把每个时间能完成的任务都记录下来
然后二分时间

#include<bits/stdc++.h>
#define ll long long
#define Max(x,y) (x>y ? x : y)
#define Min(x,y) (x<y ? x : y)
using namespace std;
template<typename tn> void read(tn &a){
    tn x=0,f=1; char c=' ';
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    a=x*f;
}
const int N = 201000;
int n,m,t[N],p[N],h[1010],f[1010][1010];
ll s[1010],ans[1010];
struct node{
    int s,num;
}q[1010];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > qq;
bool cmp(node a,node b){return a.s<b.s;}
bool check(ll tim,int sum){
    ll sss=0;
    for(int i=1;i<=1000;i++){
        sss+=h[i]*(ll)(tim/i)-s[i]-f[i][tim%i+1];
    }
    return sss>=sum;
}
bool check2(ll tim,int sum){
    ll sss=0;
    for(int i=1;i<=n;i++) sss+=(tim-p[i])/t[i];
    return sss>=sum;
}
int main(){
    for(int i=1;i<=n;i++) read(t[i]);
    for(int i=1;i<=m;i++){
        read(q[i].s); q[i].num=i;
        } 
    int k=1,now=1;
    sort(q+1,q+m+1,cmp);
    qq.push(make_pair(t[1],1));
    if(n>1)
    while(!qq.empty()){
        int u=qq.top().second,tim=qq.top().first; qq.pop();
        p[++now]=tim;
        while(k<=m&&q[k].s<now)
            ans[q[k].num]=tim,k++;
        if(now==n) break;
        qq.push(make_pair(tim+t[u],u));
        qq.push(make_pair(tim+t[now],now));
    }
    while(!qq.empty()) qq.pop();
    for(int i=1;i<=n;i++)
        h[t[i]]++,f[t[i]][p[i]%t[i]]++,s[t[i]]+=p[i]/t[i];
    for(int i=1;i<=1000;i++)
        for(int j=i-1;j>=0;j--)
            f[i][j]+=f[i][j+1];
    ll lst=p[n];
    for(int i=k;i<=m;i++){
        ll l=lst-1,r=(ll)(1e12)/(ll)n+1000;
        if(n<=2500){
            while(l+1<r){
                ll mid=l+r>>1;
                if(check2(mid,q[i].s)) r=mid;
                else l=mid;
            }
        }
        else{
            while(l+1<r){
                ll mid=l+r>>1;
                if(check(mid,q[i].s)) r=mid;
                else l=mid;
            }
        }
        ans[q[i].num]=lst=r;
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<' ';
    return 0;
}


发表评论

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