首页 > 代码库 > 2013.21.A

2013.21.A

2024-07-07 09:46:22   221人阅读

随便点了一套刷，这套质量挺棒的，学了不少的东西，并且碰到了很久都没有打的题目

//很久没有刷一套题了吧，最近发生的东西实在可怕到我都难以接受了....clam down clam dowm 先管好自己的事再说吧~

1.card
+ View Code?
题1  集卡片
【问题描述】
lzh小时候很喜欢收集卡片，他经常要去商店购买新到的卡片。
商店出售的卡片有N张，是连续的，并且都连在一起成为一个长串，商店阿姨告诉lzh只能购买连续的一段，这一串卡片共有M种，每种卡片都有一个价格，lzh拿的钱数为V，他想花最少的钱来集齐所有种类的卡片，你能帮帮他吗？
 
【输入格式】
第1行 三个正整数 N，M，V
第2行共M个正整数，第i个数Ti表示第i种卡片的价格
第3行 N个正整数，表示卡片序列。
 
【输出格式】
1行 1个整数ans，表示lzh剩余的钱数，若不能集齐，输出’NO ans’,不含引号。
 
【输入样例】
5 2 20
10 5
1 1 2 2 1
【输出样例】
5
 
注释
【样例解释】
购买2-3 或者 4-5 都可，花费15，剩余钱数20-15=5.
     
【数据范围】
对于100%的数据 N<=1000000 ，M<=2000 ，Ti<=2000 ,  V<=10^9
对于30% 的数据 N<=2000

　　

很久没有感受指针的题目了...打起来确实很陌生了

先说一下思路吧，大概是这样的根据队列的思想，设有h,w两个头尾指针

边读边处理，如果头元素在这个队列里出现了2次，那么就把它清除，即h++;

以及判断所有的数是否全都在队列里面，找到最优的值

主要部分是这样的
?
for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        t++;b[a[i]]++;
        s=s+w[a[i]];
        if(b[a[i]]==1) l++;
        while(b[a[h]]>1){
            b[a[h]]--;
            s-=w[a[h]];
            h++;
        }
        if(l==m){
            if(s<ans) ans=s;
        }
    }
　　2.line
+ View Code?
题2  染色
【问题描述】
    有编号为0到M 的（M+1）个格子，现在有N个操作 （x，y），表示将从x 到 y的格子染色，问一共有多少个格子被染色。
【输入样例】line.in
    3 10
    0 5
    2 6
    8 9
【输出样例】line.out
    9
【数据规模】
    30%  N，M<=10000
100%   N,  M<=1000000; 任何操作保证0<=x<=y<=M。

　　

 
之前曾在usaco里看到一道类似的题目，不过那是没有考虑这么多，两个for过去，貌似当时也没有超时...
但是这里明显是不行的

=-=然后就默默地偷瞥了眼题解，看到那个图顿时有一种恍然大悟的感觉！...做法很巧妙


用f,g两个数组分别记录头和尾

然后 s+=h[i];
    if(s>0) ans++;
    s-=g[i];
很棒的想法是不是？是~

主代码
?
for(int i=0;i<n;i++){
    scanf("%d%d",&x,&y);
    h[x]++;
    w[y]++;
}
for(int i=0;i<m;i++){
    s+=h[i];
    if(s>0) t++;
    s-=w[i];
}
　3.　rectangle
+ View Code?
题3  数矩形
【问题描述】
    这注定是个不眠之夜！
    因为MSH达到了RPK的要求，所以RPK给了MSH第二个惊喜。RPK把MSH带到了一个硕大而神秘的广场，如此广阔的空间只有两个人，而一切静匿到足以听见对方的心跳。
    MSH沉醉了。
    RPK：“你知道我有多少话想跟你说么？”
    MSH摇了摇头。
    RPK：“你可以数出来啊，在这个广场上的地面上你能数到矩形的数量，就是我想说的话的数量。”
    MSH数了数，实在是太多了，她完全数不尽。
    整个广场的地面由两个行和列分别为N1，M1和N2，M2的矩形组成，这两个矩形交叉成十字（N1＜N2，M1＞M2），在这个图形中，一共有多少个矩形呢？
【输入格式】
    一共四行，每行一个数，分别表示N1，M1和N2，M2。
【输出格式】
    一个数表示矩形的数量
【输入样例】
    7
    9
    10
    6
【输出样例】
    1827
【数据规模】
    20%的数据每个数≤100；
    40%的数据每个数≤10000；
    100%的数据每个数≤10^99；
　　高精=-=表示真的真的很久很久没有打了！！
   学长友情教我打了一个模板~跪跪跪~
   自己mark一下

?
    
          
1
      
2
      
3
      
4
      
5
      
6
      
7
      
8
      
9
      
10
      
11
      
12
      
13
      
14
      
15
      
16
      
17
      
18
      
19
      
20
      
21
      
22
      
23
      
24
      
25
      
26
      
27
      
28
      
29
      
30
      
31
      
32
      
33
      
34
      
35
      
36
      
37
      
38
      
39
      
40
      
41
      
42
      
43
      
44
      
45
      
46
      
47
      
48
      
49
      
50
      
51
      
52
      
53
      
54
      
55
      
56
      
57
      
58
      
59
      
60
      
61
      
62
      
63
      
64
      
65
      
66
      
67
      
68
      
69
      
70
      
71
      
72
      
73
      
74
      
75
      
76
      
77
      
78
      
79
      
80
      
81
      
82
      
83
      
84
      
85
      
86
      
87
      
88
      
89
      
90
          
      
#include<cstring>
      
#include<cstdio>
      
#include<algorithm>
      
using namespace std;
      
struct hugeint{
      
    int l,s[300];
      
    hugeint () {
      
        l = 1; memset (s, 0, sizeof (0));
      
    }
      
    bool operator <(const hugeint & a)const{
      
        if(l!=a.l)return l<a.l;
      
        for(int i=a.l;i;i--) 
      
            if (a.s[i]!=s[i]) return s[i]<a.s[i];
      
        return 0;
      
    }
      
    hugeint operator*(const hugeint &a){
      
        hugeint c;
      
        for(int i=1;i<=l;i++)
      
           for(int j=1;j<=a.l;j++){
      
               c.s[i+j-1]+=s[i]*a.s[j];
      
               c.s[i+j]+=c.s[i+j-1]/10;
      
               c.s[i+j-1]%=10; 
      
           }
      
        c.l = l+a.l;
      
        while (c.l > 1 && !c.s[c.l]) c.l--;
      
        return c;
      
    }
      
    hugeint operator+(const hugeint &a){
      
        hugeint c;
      
        for(int i=1;i<=max(a.l,l);i++){
      
            c.s[i]+=a.s[i]+s[i];
      
            c.s[i+1]+=c.s[i]/10;
      
            c.s[i]%=10;
      
        }
      
        c.l=max(a.l+1,l+1);
      
        while (c.l > 1 && !c.s[c.l]) c.l--;
      
        return c;
      
    }
      
    hugeint operator-(const hugeint &a){
      
        hugeint c;
      
        for(int i=1;i<=max(a.l,l);i++){
      
            c.s[i]+=s[i]-a.s[i];
      
            if(c.s[i]<0) c.s[i]+=10, c.s[i+1]--;
      
        }
      
        c.l=l;
      
        while (c.l > 1 && !c.s[c.l]) c.l--;
      
        return c;
      
    }
      
    hugeint operator/(const int &a){
      
        hugeint c;
      
        for(int i=l;i>=1;i--){
      
            c.s[i]=s[i]/4;
      
            if(c.s[i]!=0){
      
                c.s[i+1]+=c.s[i]%4;
      
                c.s[i]/=4;
      
            }
      
        }
      
        c.l=l;
      
        while (c.l > 1 && !c.s[c.l]) c.l--;
      
        return c;
      
    }
      
     
      
};
      
hugeint into(){
      
    char s[300];
      
    scanf("%s",s);
      
    hugeint c;
      
    c.l = strlen (s);
      
    for (int i=0; i<c.l; i++)
      
        c.s[i] = s[c.l-i+1]-‘0‘;
      
    return c;
      
}
      
int main(){
      
    freopen("rectangle.in","r",stdin);
      
    freopen("rectangle.out","w",stdout);
      
    hugeint n1,m1,n2,m2,n,m,a,b;
      
    n1=into();
      
    m1=into();
      
    n2=into();
      
    m2=into();
      
    hugeint one;
      
    one.s[1]=1;
      
    a=n1*(n1+one)*m1*(m1+one)/4;
      
    b=n2*(n2+one)*m2*(m2+one)/4;
      
    n=min(n1,n2);
      
    m=min(m1,m2);
      
    n=n*(n+one)*m*(m+one)/4;
      
    printf("%lld",a+b-n);
      
    return 0;
      
}
　　哦对了，以及矩形个数要记得(n+1)*n*(m+1)*m/4;




 






























        

            
                
                  
                
                

                    联系

                    我们