题解

40 条题解

  • 0
    @ 2015-10-17 17:01:52

    没用二分居然过了
    #include <cstdio>
    #include <cstdlib>
    #include <cctype>

    using namespace std;

    struct N {
    int x, next;
    } node[51][200005];

    int n, k, p;
    int color[200005], cost[200005], next[200005];
    int tot[51];

    inline int in() {
    int RV = 0;
    char p = getchar();
    while(!isdigit(p)) {
    p = getchar();
    }
    while(isdigit(p)) {
    RV *= 10;
    RV += (p - '0');
    p = getchar();
    }
    return RV;
    }
    int main(int argc, const char argv[]) {
    scanf("%d %d %d", &n, &k, &p);
    for (int i = 1; i <= n; ++i) {
    color[i] = in();
    cost[i] = in();
    }
    for (int i = n; i >= 1; --i)
    {
    if (cost[i] <= p)
    next[i] = i;
    else
    next[i] = next[i + 1];
    }
    for (int i = 0; i < k; ++i) {
    for (int j = 1; j <= n; ++j) {
    if (color[j] == i) {
    node[i][++tot[i]].x = j;
    node[i][tot[i]].next = next[j];
    }
    }
    }
    int ans = 0;
    for (int i = 0; i < k; ++i) {
    for (int j = 1; j < tot[i]; ++j) {
    if (node[i][j].next == 0)
    break;
    /

    int l = j + 1, r = tot[i], mid;
    mid = (l + r) / 2;
    while (l + 1 <= r) {
    mid = (l + r) / 2;
    if (mid == l || mid == r)
    break;
    if (node[i][mid].x < node[i][j].next)
    {
    l = mid;
    }
    if (node[i][mid].x == node[i][j].next)
    break;
    if (node[i][mid].x > node[i][j].next)
    r = mid;
    }
    //printf ("%d %d %d\n", i, j, mid);
    if (node[i][mid].x < node[i][j].next)
    continue;*/
    int ss = j + 1;
    for (ss = j + 1; ss <= tot[i]; ++ss)
    if (node[i][ss].x >= node[i][j].next)
    break;
    ans += (tot[i] - ss + 1);
    }
    }
    printf("%d\n", ans);
    return 0;
    }

  • 0
    @ 2015-10-09 21:41:23

    include<iostream>
    include<cstdio>
    include<algorithm>
    include<vector>
    using namespace std;
    const int MAXN=200010;
    int n,k,p;
    long long ans;
    int c[MAXN],l[MAXN],cost[MAXN];
    int G[110][200010];
    int cnr[200010];
    int main(){
    cin>>n>>k>>p;
    int count=0;
    for (int i=1;i<=n;i++) {
    scanf("%d%d",&c[i],&p[i]);
    G[c[i]][cnr++]=i;
    if (l[i]<=p)
    cost[i]=cost[i-1]+1;
    else cost[i]=cost[i-1];
    }
    for (int i=0;i<k;i++) {
    int x=0;
    for (int j=1;j<=cnr[i];j++) {
    if (cost[G[i][j]]-cost[G[i][j-1]-1]>0) {
    ans=ans+(j-x)*(cnr[i]+1-j);
    x=j;
    }
    }
    }
    cout<<ans<<endl;
    return 0;
    }

  • 0
    @ 2015-09-30 14:31:45

    ###O(n)
    #include <iostream>
    #include <cstring>
    using namespace std;

    int n,k,p;
    int c[51][200001], top[51];
    long long total=0;

    int main()
    {
    memset(top,-1,sizeof(top));
    memset(c,0,sizeof(c));

    ios::sync_with_stdio(false);
    cin>>n>>k>>p;

    int cnt=0;
    bool P=false;
    for (int i=0; i<n; i++)
    {
    int x,y;
    cin>>x>>y;

    int t=++top[x];
    if (y<=p || P)
    cnt++;
    c[x][t]=cnt;

    P = y<=p;
    }

    for (int color=0; color<k; color++)
    {
    int prev=c[color][0];
    long long sum=0;

    for (int i=0; i<=top[color]; i++)
    {
    if (c[color][i]-prev>0) sum=i;
    total+=sum;
    prev=c[color][i];
    }
    }

    cout<<total<<endl;
    return 0;
    }

  • 0
    @ 2015-08-20 22:37:19

    #include<cstdio>
    using namespace std;
    const int MAXN = 200000+10;

    int f[MAXN], s[MAXN], ans[MAXN], num[MAXN];

    int main()
    {
    int n, p, k, c, l, da=0;
    scanf("%d%d%d", &n, &k, &p);
    for(int i=1; i<=n; i++){
    scanf("%d%d", &c, &l);
    c %= k;
    if(l <= p)
    f[i] = f[i-1]+1;
    else
    f[i] = f[i-1];
    if(s[c] == 0){
    s[c] = i;
    num[c]++;
    continue;
    }
    if(f[i]-f[s[c]-1] > 0)
    ans[i] = num[c];
    else
    ans[i] = ans[s[c]];
    s[c] = i;
    num[c]++;
    }

    for(int i=1; i<=n; i++)
    da += ans[i];
    printf("%d", da);
    return 0;
    }
    模拟,O(n)。

  • 0
    @ 2015-06-24 09:29:27

    O(nk)算法,稍加改动就是O(n)算法了(去掉i=0~k-1循环,为basic、num、front建立数组对应每种色调即可)
    不过O(nk)跑得也不慢,懒得改了

    #include<stdio.h>
    int colors[200001]={0},price[200001]={0},sc[200001][2];//sc[j][1]表示到j为止情况数总和,sd[j][2]表示客栈j的情况数
    int main( )
    {

    int n,k,p;
    int i,j,flag=0,front=0,num=0,ans=0,basic=0;

    scanf("%d %d %d",&n,&k,&p);

    for(i=1;i<=n;i++)
    scanf("%d %d",&colors[i],&price[i]);

    for(i=0;i<=n;i++)
    for(j=0;j<=1;j++)
    sc[i][j]=0;

    for(i=0;i<=k-1;i++)
    {
    front=0; //上一个客栈位置
    num=0; //客栈数
    basic=0; //上一个可被选择的客栈位置
    flag=0; //记录两个客栈之间是否有符合消费的咖啡馆

    for(j=1;j<=n;j++)
    {
    if(price[j]<=p) flag++;

    if(colors[j]==i)

    {
    if(flag==0) {sc[j][0]=sc[front][0]+sc[front][1];sc[j][1]=sc[basic][1];}

    else
    {
    basic=j;

    sc[j][0]=sc[front][0]+sc[front][1];sc[j][1]=num;

    if(price[j]>p) flag=0;
    }

    num++;
    front=j;
    }
    }

    ans=ans+sc[front][0]+sc[front][1];

    }

    printf("%d",ans);

    return 0;
    }

  • 0
    @ 2015-01-10 17:26:45

    来个组合的
    #include<cstdio>
    using namespace std;
    int n,k,p,ans=0,s[51],c[51],over[51];
    int cb(int a)
    {
    return a*(a-1)/2;
    }
    int main()
    {
    scanf("%d%d%d",&n,&k,&p);
    for(int i=0,a,b;i<n;i++)
    {
    scanf("%d%d",&a,&b);
    s[a]++;
    if(b<=p)
    for(int i=0;i<k;i++)
    c[i]+=cb(over[i]),over[i]=0;
    else over[a]++;
    }
    for(int i=0;i<k;i++)
    c[i]+=cb(over[i]);
    for(int i=0;i<k;i++)
    if(s[i]>1)
    ans+=cb(s[i])-c[i];
    printf("%d",ans);
    return 0;
    }

  • 0
    @ 2014-11-03 19:54:17

    type
    yu=longint;
    var z:array[1..2,1..200000]of longint;
    x:array[0..50,1..2]of longint;
    sum:int64;

    procedure tonglie;
    var s,d,f:yu;
    begin
    for s:=0 to 50 do
    if (x[s,1]>0)and(x[s,2]>0)
    then begin
    inc(sum,x[s,1]*x[s,2]);
    x[s,2]:=0;
    end;
    end;

    procedure main;
    var n,k,p,a:longint;
    begin
    fillchar(z,sizeof(z),0);
    fillchar(x,sizeof(x),0);
    readln(n,k,p);
    for a:=1 to n do
    begin
    readln(z[1,a],z[2,a]);
    inc(x[z[1,a],1]);
    end;
    for a:=1 to n do
    begin
    if z[2,a]<=p
    then tonglie;
    dec(x[z[1,a],1]);
    inc(x[z[1,a],2]);
    if z[2,a]<=p
    then tonglie;
    end;
    writeln(sum);
    end;

    begin
    main;
    end.
    大概是O(50n)复杂度

  • 0
    @ 2014-10-03 00:17:38

    program hotel;
    var i,m,ans,t,n,k,p:longint;
    lc,w,c:array[1..200000]of longint;
    l,r:array[0..50]of longint;

    procedure cal(x:longint);
    var j:longint;
    begin
    for j:=0 to k-1 do
    inc(ans,l[j]*r[j]);
    inc(ans,l[c[lc[x]]]-1);
    end;

    begin
    readln(n,k,p);
    t:=0;
    ans:=0;
    for i:=1 to n do
    begin
    readln(c[i],w[i]);
    if w[i]<=p then
    begin
    inc(t);
    lc[t]:=i;
    end;
    end;
    for i:=1 to n do
    begin
    if i<=lc[1] then
    inc(l[c[i]])
    else inc(r[c[i]]);
    end;
    cal(1);
    for i:=2 to t do
    begin
    fillchar(l,sizeof(l),0);
    for m:=lc[i-1]+1 to lc[i] do
    begin
    inc(l[c[m]]);
    dec(r[c[m]]);
    end;
    cal(i);
    end;
    writeln(ans);
    end.
    //时间复杂度和空间复杂度均为O(n)的算法,不知道怎么想出来的。。。

  • 0
    @ 2014-07-21 15:37:01

    var m,q:array[0..50]of longint;
    n,k,p,i,a,b,s:longint;
    begin
    readln(n,k,p);
    for i:=1 to n do begin
    readln(a,b);
    inc(s,m[a]);
    if b<=p then fillchar(q,sizeof(q),0) else begin
    dec(s,q[a]);
    inc(q[a]);
    end;
    inc(m[a]);
    end;
    writeln(s);
    end.
    //Accepted, time = 201 ms, mem = 612 KiB, score = 100

  • 0
    @ 2013-10-26 22:41:52

    var
    n,k,p,c,m,ans,i,j:longint;
    col,sum:array[0..50]of longint;
    begin
    readln(n,k,p);
    for i:=1 to n do
    begin
    readln(c,m);
    inc(col[c]);
    if m<=p then
    begin
    inc(ans,col[c]-1);
    for j:=0 to k-1 do
    begin
    inc(ans,sum[j]*col[j]);
    sum[j]:=sum[j]+col[j];
    col[j]:=0;
    end;
    end;
    end;
    for j:=0 to k-1 do
    inc(ans,sum[j]*col[j]);
    writeln(ans);
    end.
    O(n)算法,直接统计

  • 0
    @ 2013-10-18 19:15:30

    var
    n,k,p,i,j,g,h,s:longint;
    no,yes,c:array[0..50]of longint;
    begin
    readln(n,k,p);
    for i:=1 to n do
    begin
    readln(g,h);
    s:=s+yes[g];
    if h<=p then begin
    s:=s+no[g];
    fillchar(c,sizeof(c),0);
    inc(yes[g]);
    end
    else begin
    s:=s+no[g]-c[g];
    inc(c[g]);
    inc(no[g]);
    end;
    end;
    writeln(s);
    end.

  • 0
    @ 2013-10-18 15:23:00
  • 0
    @ 2013-09-26 19:56:51

    s[i]:到i为止最小消费<=p的客栈个数
    a[i,j]:颜色为i的客栈序列
    t[i]:颜色为i的客栈总数
    然后枚举每一种颜色c
    再枚举c里A选择的客栈ID
    往右二分查找找到第一个客栈j满足s[j]-s[i-1]>0的j,对答案的贡献为t[c]-j+1
    时间复杂度O(nlogn)

  • 0
    @ 2013-08-15 13:08:03

    o( ̄▽ ̄)o 1A!
    Var n,k,p,i,j,ans:longint;
    f:array[0..200000,0..50] of 0..200000;
    pre,c,color:array[0..200000] of longint;
    Begin
    readln(n,k,p);
    For i:=1 to n do
    Begin
    readln(color[i],c[i]);
    For j:=0 to k-1 do f[i,j]:=f[i-1,j];
    inc(f[i,color[i]]);
    End;
    For i:=1 to n do
    If c[i]<=p then pre[i]:=i Else pre[i]:=pre[i-1];
    For i:=1 to n do
    If pre[i]<>i then ans:=ans+f[pre[i],color[i]]
    Else ans:=ans+f[pre[i]-1,color[i]];
    writeln(ans);
    readln;
    End.

  • 0
    @ 2013-06-15 18:18:37

    用总的线段数去剪掉不包含可行咖啡厅的线段数目,复杂度O(kn)
    思路貌似有点奇怪。。。
    #include <cstring>
    #include <cstdio>

    using namespace std;

    #define MAXN 200001
    #define MAXK 50

    int suff[MAXN];
    int color[MAXN],cost[MAXN];

    struct node {
    node *next;
    int rank;
    };

    node *head[MAXK];

    int num[MAXK];

    int n,k,c;

    bool check(int l,int r){
    if (suff[r]-suff[l-1]){
    return true;
    }
    return false;
    }

    int main(){
    scanf("%d%d%d",&n,&k,&c);
    suff[0]=0;
    for (int i=0;i<k;i++){
    head[i]=NULL;
    }
    memset(num,0,sizeof(num));
    for (int i=0;i++<n;){
    scanf("%d%d",&color[i],&cost[i]);
    node *p=new(node);
    (*p).next=head[color[i]];
    (*p).rank=i;
    head[color[i]]=p;
    num[color[i]]++;
    suff[i]=suff[i-1];
    if (cost[i]<=c){
    suff[i]++;
    }
    }
    int ans=0;
    for (int i=0;i<k;i++){
    if (num[i]>1){
    int last=0;
    ans+=((num[i]*(num[i]-1))/2);
    node *p=head[i];
    while ((p).next!=NULL){
    if (!check((
    (*p).next).rank,(p).rank)){
    last++;
    } else {
    if (last){
    ans-=((last)
    (last+1)/2);
    last=0;
    }
    }
    p=(p).next;
    }
    if (last){
    ans-=((last)
    (last+1)/2);
    }
    }
    }
    printf("%d\n",ans);
    return 0;
    }

  • 0
    @ 2012-11-09 16:09:16

    #include

    #include

    #include

    using namespace std;

    int lowprice[200001],color[200001],f[200001]; // the sum of element before n+1

    vector pairs[51]; // color the same

    int main()

    {

    int n,k,p,l;

    bool flag=false;

    unsigned long long tot=0;

    cin>>n>>k>>p;

    for(int i=1;i

  • 0
    @ 2012-11-07 22:08:07

    用 i 枚举 后一个人住的旅馆

    i = 1 →n

    pre 表示 在 i 旅店之前 有合适酒店可选的 最后一个旅店

    rank 表示 当前旅店在同颜色旅店中的排位

    last 表示 此颜色 在i之前 最后一个旅店

    can 表示 在 i 旅店之前 离他最近 的酒店

    num 表示 第二个人住 i 旅店时,第一个人可能的旅店个数。

    can[i]=i(pcost[now])

    pre[i]=last(last=can[i])

    num[i]=rand[pre[i]]

    答案就是 ∑num[i]

    时间复杂度 O(n)

    空间复杂度 O(n)

    在线做 离线做 都可以

  • 0
    @ 2012-10-08 20:41:39

    f[i] 表示以i结尾的方案的个数

    back[i]表示同种颜色上一次出现的位置那么

    num[i]表示 i之前的店当中 和i颜色相同的个数

    答案则是sum(f[i])

    转移方程为

    f[i] = num[i](min[back[i],i]k)

    令r[i]=min[back[i],i]

    r数组可以在 o(k*n)的时间内预处理出来

    总复杂度是O(k*n)

  • 0
    @ 2012-10-06 09:04:58

    #include

    #include

    #include

    #include

    using namespace std;

    int N, K, P;

    int ans;

    int a[200005];

    int b[60];

    void read_data()

    {

        scanf("%d%d%d", &N, &K, &P);

        for(int i = 0; i < N; i++)

        {

            int cost, k;

            scanf("%d%d", &k, &cost);

            if (cost > P)

            {

                if (b[k] == 0)

                {

                    a[k]++;

                }

                if (b[k] > 0)

                {

                    ans += b[k];

                    a[k] ++;

                }

            }

            if (cost

  • -1
    @ 2017-09-10 19:33:50

    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cmath>
    using namespace std;
    int a[51]={0},f[51]={0};//a 按风格存储 f 实际可住的人
    int n,k,p;
    int main()
    {
    int i,j,x,y,ans;
    cin>>n>>k>>p;
    for(j=1;j<=n;j++)
    {
    scanf("%d%d",&x,&y);
    a[x]++;
    if(y<=p)
    {
    for(i=0;i<=k;i++)
    {
    f[i]=a[i];
    }
    }
    ans+=f[x];
    if(f[x]==a[x]) ans--;
    }
    cout<<ans;
    return 0;
    }

信息

ID
1737
难度
6
分类
数据结构 | 单调队列 点击显示
标签
递交数
3860
已通过
1162
通过率
30%
被复制
8
上传者