/ Vijos / 题库 / 海港 /

题解

9 条题解

  • 2
    @ 2017-09-03 15:54:52

    //使用一个队列来表示目前在24小时内的乘客信息,tot[x]表示目前有tot[x]个x国的人在队列中。
    //每一次删除已不在范围内的。
    #include<bits/stdc++.h>
    using namespace std;
    int n,t,k,x;
    int tot[100010];
    struct xy{
    int time,num;
    };
    int ans;
    queue<xy> q;
    int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
    scanf("%d%d",&t,&k);
    while(!q.empty()&&q.front().time<=t-86400){
    tot[q.front().num]--;
    if(tot[q.front().num]==0) ans--;
    q.pop();
    }
    for(int j=1;j<=k;j++){
    scanf("%d",&x);
    tot[x]++;
    xy tmp;
    tmp.time=t;
    tmp.num=x;
    q.push(tmp);
    if(tot[x]==1) ans++;
    }
    printf("%d\n",ans);
    }
    }

  • 1
    @ 2021-08-29 17:20:06
    #include<bits/stdc++.h>
    using namespace std;
    #define rei register int
    
    int n,t,m,x,ans;
    int temp_nation[1000005];
    struct node
    {
        int s, t;
    };
    
    queue<node>ship;
    node h;
    int main()
    {
        cin>>n;
        for(rei i=1; i<=n; i++){
            cin>>t>>m;
            while(!ship.empty()){
                h = ship.front();
                if(h.t+86400<=t){
                    temp_nation[h.s]--;
                    if(temp_nation[h.s]==0)
                        ans--;
                    ship.pop();
                    continue;
                }
                break;
            }
            for(rei j=1; j<=m; ++j){
                cin>>x;
                h.s=x;
                h.t=t;
                ship.push(h);
                temp_nation[x]++;
                if(temp_nation[x]==1)
                    ans++;
            }
            printf("%d\n",ans);
        }
        return 0;
    }
    
  • 0
    @ 2017-04-02 16:58:47

    #include <iostream>
    #include <iomanip>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <algorithm>
    using namespace std;
    struct pe
    {
    int tim;
    int co;
    }p,t;
    struct qu
    {
    pe data[1000005];
    int f;
    int r;

    }q;
    void CLear()
    {
    q.f=q.r=0;
    }
    void Push(pe k)
    {
    q.data[q.r++]=k;
    }
    void Pop()
    {
    q.f++;
    }
    pe Gettop()
    {
    return q.data[q.f];
    }
    bool Isempty()
    {
    return q.r==q.f;
    }
    int n,i,ki,ti,j,f[100005],ans;
    int main()
    {
    cin>>n;
    for(i=0;i<n;i++)
    {
    cin>>p.tim>>ki;
    for(j=0;j<ki;j++)
    {
    cin>>p.co;
    Push(p);
    if(f[p.co]==0) ans++;
    f[p.co]++;
    }
    while(p.tim-86400>=Gettop().tim)
    {
    f[Gettop().co]--;
    if(f[Gettop().co]==0) ans--;
    Pop();
    }
    cout<<ans<<endl;
    }
    system("pause");
    return 0;
    }

  • 0
    @ 2017-03-26 10:35:40

    这个题目黑科技。
    注意到人的信息是不变的而且也不多
    ×××所以我们以人为对象维护一个队列
    ×××队列有头尾俩指针,头指针为人总数(包括24小时之外的)
    ×××尾指针为最后一个被剔除的人的下一个人

    然后有一个nation数组 下标为国家编号 元素是该国人总数
    但这个数组咱永远不能扫描它否则就是超时
    ×××只需要在加入人的时候判断是否有一个国家人数从0上涨,有的话就ans+1
    ×××在剔除人的时候判断是否有一个国家人数降到0,有的话就ans-1
    最后记录ans

    以及这个题目数组开大一点感觉数据有点不老实(???反正我是把runtime error 当初TLE瞎提交了十几次233333真是笑死大牙了!)

    
    var
    n0,old,i,j,new,tot,lastp,lasts,ans:longint;
    //n0是船总数,old是对于剔除人时有多少国家人空了,new是对于加入人时有多少新国家,
    //lastp是最后一条剔除的船的下一条船,lasts是最后一个剔除的人的下一个人。
    n,t,k,inf,an:array[1..1000000] of longint;
    //n是国家数组,t是每条船的到达时间,k是每条船人数,inf是人的国家编号数组,an是答案数组
    
    begin
        readln(n0);
        lasts:=1;
        lastp:=1;
        for i:= 1 to n0 do
        begin
            read(t[i],k[i]);
            new:=0;
            old:=0;
            for j:= 1 to k[i] do
            begin
                inc(tot);
                read(inf[tot]);
                if n[inf[tot]]=0 then inc(new);
                inc(n[inf[tot]]);
            end;
            while t[lasts]+86400<=t[i] do
            begin
                for j:= 1 to k[lasts] do
                    begin
                        dec(n[inf[lastp]]);
                        if (n[inf[lastp]]=0) then inc(old);
                        inc(lastp); 
                    end;
                inc(lasts);
            end;
            ans:=ans+new-old; 
            an[i]:=ans;
        end;
        for i:= 1 to n0 do
        begin
            writeln(an[i]);
        end;
    end.
    
  • -1
    @ 2019-05-11 15:59:53

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=300300;
    const int maxm=100300;
    int qt[maxn],qx[maxn],qs[maxm];
    int main()
    {
    int head=1,tail=1,n,ti,xi,ki,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    cin>>ti>>ki;
    for(int j=1;j<=ki;j++)
    {
    cin>>xi;
    qt[tail]=ti;
    qx[tail]=xi;
    if(qs[xi]==0) ans++;
    qs[xi]++;
    tail++;
    }
    while(qt[head]<=ti-86400)
    {
    xi=qx[head];
    qs[xi]--;
    if(qs[xi]==0) ans--;
    head++;
    }
    cout<<ans<<endl;
    }
    return 0;
    }

  • -1
    @ 2017-10-14 12:31:35

    用队列来维护:

    #include <stdio.h>
    #include <iostream>
    #include <queue>
    using namespace std;
    const int T=86400;
    int n,t[100005],ans,m,tim;
    struct node{
      int ti,c;
    };
    deque<node> Q;
    void read(int &x){
      char c; x=0;
      for(c=getchar();c<'0'||c>'9';c=getchar());  x=x+c-'0';
      for(c=getchar();c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+c-'0';
    }
    void clear(int tim){
      while(!Q.empty()&&Q.front().ti<=tim-T){ 
       t[Q.front().c]--;
       if(t[Q.front().c]==0) ans--;
       Q.pop_front(); 
    }
      return ;
    }
    int main(){
     read(n);
     for(int i=1;i<=n;i++){
       read(tim),read(m);
       clear(tim);
       for(int j=1;j<=m;j++){
         int x; read(x);
        if(t[x]==0) ans++;
         t[x]++; Q.push_back((node){tim,x});
       }
       cout<<ans<<endl;
     }
      return 0;
    }
    
  • -1
    @ 2017-09-21 20:50:01

    jiandan
    #include<bits/stdc++.h>
    using namespace std;
    int mon[13]={-1,31,28,31,30,31,30,31,31,30,31,30,31};
    int main()
    {
    int d1,d2,f=0;
    cin>>d1>>d2;
    int y1=d1/10000;
    int y2=d2/10000;
    int sum=0;
    for(int i=y1;i<=y2;i++)
    {
    int d=i*10000+i%10*1000+i%100/10*100+i%1000/100*10+i%10000/1000;
    int m=d%10000/100;
    int day=d%100;
    //cout<<d<<" "<<i<<"/"<<m<<"/"<<day<<endl;
    if(m>=1&&m<=12)
    {
    if(day>=1&&day<=mon[m])sum++;//cout<<d<<" "<<i<<"/"<<m<<"/"<<day<<endl;
    }
    if(i==9220)sum++;
    }
    cout<<sum<<endl;
    return 0;
    }

  • -1
    @ 2017-03-31 17:07:37

    #include <iostream>
    #include <queue>
    using namespace std;

    struct person//每一个人的时间、国家
    {
    int cty;
    int t;
    };
    queue <person> q;
    int s[100005]={};//储存每个国家的人数
    int main() {
    int n, k, sum = 0;
    cin >> n;
    person nowp;//用于储存当前队尾的人的信息
    while (n--) {
    cin >> nowp.t;//每艘船上的人时间一样
    cin >> k;
    while (k--) {
    cin >> nowp.cty;//每个人的国家
    q.push(nowp);//压进队列
    if (s[nowp.cty] == 0)//如果该国家人数为0
    sum++;//总国家数加一
    s[nowp.cty]++;//该国家人数加一
    }
    while (nowp.t - 86400 >= q.front().t)//当队首的时间距现在大于等于24小时
    {
    s[q.front().cty]--;//该国家人数减一
    if (s[q.front().cty] == 0)//若该国家已无人
    sum--;//总国家数减一
    q.pop();//弹出队首
    }
    cout << sum << endl;//输出
    }
    return 0;
    }

  • -4
    @ 2017-02-20 12:36:06

    用iostream就会超时,比较莫名

    #include<stdio.h>

    int n,ti,ki,i,j,k,ans,front,back;
    int f[1000000],tim[1000000],country[1000000];

    int main()
    {
    scanf("%d",&n);
    for( i = 0; i < n; ++i)
    {
    scanf("%d%d",&ti,&ki);
    for( j = 0; j < ki; ++j)
    {
    scanf("%d",&k);
    tim[back] = ti;
    country[back++] = k;
    if(f[k] == 0) ans++;
    ++f[k];
    }
    while(ti - 86400 >= tim[front])
    {
    k = country[front];
    f[k]--;
    if(f[k] == 0) ans--;
    front++;
    }
    printf("%d\n",ans);
    }
    return 0;
    }

    • @ 2017-10-14 22:13:14

      不会超时啊。我就用的。

  • 1

信息

ID
2011
难度
4
分类
(无)
标签
递交数
869
已通过
235
通过率
27%
被复制
11
上传者