SWERC Southwestern Europe Regional Contest 2015

Posted on | In , | Visitors:

This is my blog.
越来越不爱听英语了
不知道四级怎么办
但确实是静不下心来学习了
有点害怕
假期太长
有点嫌弃
（未完待续）


今天学习了一些东西，像是发现了新大陆一样很开心。
题解还没有拿到，就先放过的题吧。

Promotions

Black Vienna

Canvas Painting

题意

给画布染颜色，让每一块画布的颜色都不一样。但每次染花布只能从左到右，但可以指定起始位置和个数。每次所需的墨汁的数量为布的尺寸大小，求染布的最小需要的墨汁数

题解

刚开始是用queue做的，但是没有看清题目，题目中表示画布的顺序可以交换。所以就可以转换为Huffman树了，每次取出队列中最小的两个节点，将其和为一个新节点，再插入队列中，直到成为一颗树时，停止。

AC代码

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
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
priority_queue<ll,vector<ll>,greater<ll> >q;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        while(!q.empty())
            q.pop();
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            ll x;
            scanf("%lld",&x);
            q.push(x);
        }
        if(n==1)printf("0\n");
        else{
            ll ans=0;
            while(q.size()>=2){
                ll x;
                x=q.top();
                q.pop();
                ll y=q.top();
                q.pop();
                ans+=x+y;
                q.push(x+y);
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}

小记

priority_queue<ll,vector<ll>,greater<ll> >q;优先队列定义中的greater是个比较器，默认为从小到大。STL大法好。

Dice Cup

题意

给你两个骰子，骰子的最大点数已知，现问投掷骰子后，出现什么数字的概率最大。若最大的数字有多个，将其全部输出。

题解

可以画一下，你会发现靠近中间的会多。我是根据数字感觉就是(m+n+2)/2的附近，而附近的个数与m-n有关，然后再看了一下例子都是偶数，然后举了奇数的例子。写了一下选择语句，就过了。看来是水题。

AC代码

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
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main() {
    int n,m;
    scanf("%d%d",&n ,&m);
    int x=abs(n-m);
    if(x%2){
        x=(x-1)/2;
        int y=(n+m+1)/2;
        for(int i=y-x;i<=y;i++){
            printf("%d\n",i);
        }
        for(int i=y+1;i<=y+x+1;i++){
            printf("%d\n",i);
        }
    }
    else{
        x/=2;
        int y=(n+m+2)/2;
        for(int i=y-x;i<=y;i++){
            printf("%d\n",i);
        }
        for(int i=y+1;i<=y+x;i++){
            printf("%d\n",i);
        }
    }
    return 0;
}

Wooden Signs

Landscaping

Game of Cards

Sheldon Numbers

题意

题目中提到了很多很多数字：什么素数啊，回文数啊……反正我是看不懂专业术语的。仅认识这两个字。但题目要求的是Sheldon numbers。题中对它的解释是let us introduce the concept of a Sheldon number: a positive integer whose binary representation matches the pattern ABABAB . . . ABA or the pattern ABABAB . . . AB, where all the occurrences of A represent a string with N occurrences of the bit 1 and where all the occurrences of B represent a string with M occurrences of the bit 0, with N > 0 and M > 0. Furthermore, in the representation, there must be at least one occurrence of the string A (but the number of occurrences of the string B may be zero).

题解

将AB的情况列出来，然后将这个字符串改为数字。预处理将这些数保存起来，然后再范围内查找。

AC代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;
set<ll>s;
set<ll>::iterator it;
int main(){
    ll num;
    for(int len=1;len<=64;len++){
        for(int a=1;a<=len;a++){
            for(int b=0;b<=len-a;b++){
                string t="";
                num=0;
                if(len%(a+b)==0){
                    for(int i=0;i<len/(a+b);i++){//ABABAB . . . AB
                        t.append(a,'1');
                        t.append(b,'0');
                    }
                }
                else if(len%(a+b)==a){//ABABAB . . . ABA
                    for(int i=0;i<len/(a+b);i++){
                        t.append(a,'1');
                        t.append(b,'0');
                    }
                    t.append(a,'1');
                }
                for(int i=t.length()-1;i>=0;i--)
                    num+=(t[i]-'0')*(ll)pow(2, t.length()-i-1);
                s.insert(num);
            }
        }
    }
    ll x,y;
    scanf("%lld%lld",&x,&y);
    ll cnt = 0;
    s.erase(0);
    for(it=s.begin();it!=s.end();it++){
        if((*it)>=x&&(*it)<=y){
            cnt++;
        }
    }
    printf("%lld\n",cnt);
    return 0;
}

小记

不得不说，STL真的是太友好了。但总是set、vector等等不知道选择什么，也没有彻底了解它们的作用。反正这题，我觉得这样做是挺好的呢。

Text Processor

Saint John Festival

题意

有一个什么节日，估计是主办方当地的特色吧！就不管一大堆什么人文背景了（我能说我看着头疼，还看不懂吗？）我只知道，给出大灯笼和小灯笼的位置，求有多少小灯笼在任意三个大灯笼围成的三角形中。

题解

凸包问题，再用一下二分判断小灯笼是不是在凸包中。不会凸包，博博也不在。所以偷偷上网找了一份模版，套了一下。看了一下解释，大概算是可以上了吧！一交居然AC。glory国说几何问题尽量少碰，很容易出现精度的问题，看来这次是降低难度了。

AC代码

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
struct Point{
    ll x,y;
    Point(){}
    Point(ll _x,ll _y){x=_x;y=_y;}
    bool operator<(const Point& b)const{
        if(x==b.x) return y<b.y;
        return x<b.x;
    }
};
int n,m;
Point points[maxn];
int _stack[maxn],top;  /*_stack保存凸包构成点，逆时针*/
int sign(ll x){
    if(x == 0) return 0;
    return x<0? -1:1;
}
/*x>0逆时针 x<0顺时针 x=0三点共线  考虑精度*/
ll xmul(Point p0,Point p1,Point p2){
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
/*求两点间距离*/
double dis(Point p1,Point p2){
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
//相对于list[0]的极角排序
int cmp(Point p1,Point p2){
    double tmp=xmul(points[0],p1,p2);
    if(sign(tmp)>0) return 1;
    else if(sign(tmp)==0&&sign(dis(points[0],p1)-dis(points[0],p2))<0)
        return 1;
    else return 0;
}
void Graham(int n){   /*最终凸包点为_stack[0]~_stack[top-1],共top个*/
    int pos=0;
    Point p0;
    p0.x=points[0].x;p0.y=points[0].y;
    //找最下边的一个点
    for(int i=1;i<n;i++){
        if(sign(p0.y-points[i].y)>0||(sign(p0.y-points[i].y)==0&&sign(p0.x-points[i].x)>0)){
            p0.x=points[i].x;
            p0.y=points[i].y;
            pos=i;
        }
    }
    points[pos]=points[0];
    points[0]=p0;
    sort(points+1,points+n,cmp); //按极角排序
//    if(n == 1){
//        top = 1;
//        _stack[0] = 0;
//        return;
//    }
//    if(n == 2){
//        top = 2;
//        _stack[0] = 0;
//        _stack[1] = 1;
//        return ;
//    }
    _stack[0] = 0;
    _stack[1] = 1;
    top = 2;
    for(int i = 2; i < n; i++){ //最终凸包的各顶点的编号依次存在stack[]中。
        while(top>1&&sign(xmul(points[_stack[top-2]],points[_stack[top-1]],points[i]))<=0) top--;
        _stack[top++]=i;
    }
}
//叉积
double cross(Point p0, Point p1, Point p2){
    return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}
/*二分法判断点是否在凸多边形内(或边界上)*/
bool is_in(int index[], int n, Point p) {
    int l=1, r=n-2,mid;
    while(l<=r) {
        mid = (l+r) >> 1;
        double a1 = xmul(points[index[0]], points[index[mid]], p);
        double a2 = xmul(points[index[0]], points[index[mid+1]], p);
        if(sign(a1)>=0 && sign(a2)<=0){
            if(sign(xmul(points[index[mid]], points[index[mid+1]],p))>=0) 
            	return 1;
            return 0;
        }
        else if(sign(a1) < 0){
            r = mid -1;
        }
        else{
            l = mid+1;
        }
    }
    return 0;
}
int main(){
    int n, m;
    scanf("%d", &n);
    for(int i=0; i<n; i++) {
        scanf("%lld%lld", &points[i].x,&points[i].y);
    }
    Graham(n);
    scanf("%d", &m);
    int ans = 0;
    while(m--) {
        Point cur;
        scanf("%lld%lld", &cur.x,&cur.y);
        if(is_in(_stack, top, cur)) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

小记

需要学习的还很多，凸包还得再看看。毕竟代码是复制黏贴的。

后记

等待题解喽。
要静下心来，听听力啊！
英语烂成什么样了。
忘记数模这件事情了，又是拖后腿的。
去学习数模好像更有意思点，至于昨天的题，真的俄文不想动。

转载请注明出处，谢谢。

愿 我是你的小太阳


买糖果去喽