省赛选拔赛——组队赛第四场

发表于 分类于 Disqus：

Rank 2。
开场照着书上敲了一道题，然后就没出题。赛后补了一道数学＋枚举的题。
A：HDU 2333
照着蓝书敲的，书上给的貌似是c++11标准的，CE了一次。

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
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;
int cnt;
map<string,int> id;
int ID(string s){
    if(!id.count(s)) id[s]=cnt++;
    return id[s];
}
const int maxn=1010;
struct Com{
    int price;
    int quality;
    Com(int p,int q):price(p),quality(q){}
};
int n,b;
vector<Com> comp[maxn];
bool ok(int q){
    int sum=0;
    for(int i=0;i<cnt;++i){
        int cheapest=b+1,m=(int)comp[i].size();
        for(int j=0;j<m;++j)
            if(comp[i][j].quality>=q) cheapest=min(cheapest,comp[i][j].price);
        if(cheapest==b+1) return false;
        sum+=cheapest;
        if(sum>b) return false;
    }
    return true;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&b);
        cnt=0;
        for(int i=0;i<n;++i) comp[i].clear();
        id.clear();
        int maxq=0;
        for(int i=0;i<n;++i){
            char type[30],name[30];
            int p,q;
            scanf("%s%s%d%d",type,name,&p,&q);
            maxq=max(maxq,q);
            comp[ID(type)].push_back(Com(p,q));
        }
        int L=0,R=maxq;
        while(L<R){
            int M=L+(R-L+1)/2;
            if(ok(M)) L=M;else R=M-1;
        }
        printf("%d\n",L);
    }
    return 0;
}

C：HDU 2335
首先对n处理，使之变为平面矩形的个数，再从1到sqrt(n)枚举求最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL inf=0x3f3f3f3f3f3f3f3f;
int main(){
    LL t,n;
    cin>>t;
    while(t--){
        cin>>n;
        n=(n+4)/5;
        LL ans=inf,last=inf,x=0,y=0;
        for(LL i=1;i*i<=n;++i){
            LL j=(n+i-1)/i,a=10*j+2,b=44*i+4,cur=a*b;
            if(cur<ans||(cur==ans&&abs(a-b)<last)) ans=cur,x=a,y=b,last=abs(a-b);
        }
        if(x<y) swap(x,y);
        cout<<x<<" X "<<y<<" = "<<ans<<endl;
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

相关文章