2015-2016 ACM-ICPC, NEERC, Northern Subregional Contest

Posted on | In , | Visitors:

This is my blog.
我今天忘记了字母表是24个还是26个呢
真的是后悔后悔……
（未完待续）


没有报名今晚的CF，不过明天有两场练习，估计也是很醉的。
虽然最近的练习题都没有补完，但感觉自己还是有进步的。代码还是照样会写错，但比之前不敢敲已经好了很多。我是有多渴望AC啊。希望之后能一遍就过，别WA了。我的心拔拔凉的呢！
这次计蒜客上貌似没把数据处理好，SPJ没开，小数点也必须精确。

Alex Origami Squares

题意

给你一个长方形的尺寸，问能塞下三个相同正方形时，正方形的最大边长。

题解

1.二分
估计是小数点必须六位吧！CF上过了。
2.分类讨论
只有两种情况，再比较一下就好。这次估计是数据的原因，绝望地把精确到3位改到6位就对了，估计是因为样例吧！

AC代码-1

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps = 0.0001;
int h, w;
bool check(double edge){
    int a = h / edge;
    int b = w / edge;
    if(a * b < 3)   return 0;
    return 1;
}
int main(){
    scanf("%d%d", &h, &w);
    double L = 0, R = 10000;
    while(R - L > eps){
        double mid = (L + R) / 2;
        if(check(mid))  L = mid;
        else    R = mid;
    }
    printf("%.6lf\n", (L + R) / 2);
    return 0;
}

AC代码-2

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
    int w,h;
    scanf("%d%d",&w,&h);
    if(w>h)swap(w,h);
    printf("%.3lf\n",max(min(w*1.0/2,h*1.0/2),min(w*1.0,h*1.0/3)));
    return 0;
}

Black and White

题意

有黑色’@’和白色’.’的砖块，现告诉你黑色和白色连通块的个数，让你输出满足条件的布局。

题解

想到四周包围，这样就可以满足连通块了。先满足黑色的，再满足白色的。所以要预留一个来作为剩下围墙的材料。这样，最大为1000。假设我边长为n，则有(n-1/2)^2个，这样n最小为65。所以我全以13065来做边长（分上半部分和下半部分）。当然当有一个为1时则用6565，否则的就不是四面围了。

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
#include <iostream>
#include <cstdio>
using namespace std;
int b,w;
void work(char x,char y,int num){
    for(int i=1;i<=65;i++){
        if(i%2){
            for(int j=1;j<=65;j++)
                printf("%c",x);
        }
        else{
            for(int j=1;j<=65;j++){
                if(num>0&&(!(j%2))){
                    printf("%c",y);
                    num--;
                }
                else printf("%c",x);
            }
        }
        printf("\n");
    }
}
int main(){
    freopen("black.in","r",stdin);
    freopen("black.out","w",stdout);
    scanf("%d%d",&b,&w);
    if(b==1){
        printf("65 65\n");
        work('@','.',w);
    }
    else if(w==1){
        printf("65 65\n");
        work('.','@',b);
    }
    else{
        printf("130 65\n");
        if(b<w){
            work('@','.',w-1);
            work('.','@',b-1);
        }
        else{
            work('.','@',b-1);
            work('@','.',w-1);
        }
    }
    return 0;
}

Concatenation

题意

给两个字符串A，B，A取非空前缀，B取非空后缀，组合成新的字符串，问有多少种新字符串。

题解

刚开始发现了匹配的规律，但以为要将每个子串和A匹配，KMP不熟练，心灰意冷，而且觉得会TLE。放弃之后，博博看我做了那么久，看了几眼。转了几个圈，灵机一动，呀，这不用看连续的子串，可以分开来么。于是乎，写了出来。就是敲代码的时候，我忘记了字母表有几个，被嘲笑了。不知道就用30么。。。过了之后，回来补题的时候发现CF上未过，偷偷看了一下网上的思路，没错啊，于是瞎改，AC。知道可以看别人代码后，又偷偷看了博博的代码，呀！乘法，就应该用long long啊，傻了。

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
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
typedef long long ll;
ll a[30],b[30];
int main(){
    freopen("concatenation.in","r",stdin);
    freopen("concatenation.out","w",stdout);
    string A,B;
    cin>>A>>B;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    ll len1=A.length();
    ll len2=B.length();
    ll ans=len1*len2;
    for(int i=1;i<len1;i++){
        a[A[i]-'a']++;
    }
    for(int i=0;i<len2-1;i++){
        b[B[i]-'a']++;
    }
    for(int i=0;i<26;i++){
        ans-=(a[i]*b[i]);
    }
    cout<<ans<<endl;
    return 0;
}

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
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
typedef long long ll;
int a[30];
int main(){
    freopen("concatenation.in","r",stdin);
    freopen("concatenation.out","w",stdout);
    string A,B;
    cin>>A>>B;
    memset(a,0,sizeof(a));
    ll len1=A.length();
    ll len2=B.length();
    ll ans=len1*len2;
    for(int i=1;i<len1;i++){
        a[A[i]-'a']++;
    }
    for(int i=0;i<len2-1;i++){
        ans-=a[B[i]-'a'];
    }
    cout<<ans<<endl;
    return 0;
}

Distribution in Metagonia

题意

题解

AC代码

Easy Arithmetic

题意

给你一个只含加减运算的公式，你可以任意给其中加上‘+’和‘-’，但是要让公式合法。输出使结果最大的公式。

题解

刚开始点开链接的题目都很长，抱着对easy认识的份上，打开了题目。一般来说，easy都是骗人的。看了几眼，觉得就是分类讨论。写完后，给自己挑刺，加了几个特判就过了。突然，很开心。代码略丑！

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
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
string s;
string ans="";
int i;
unsigned long long len=0;
void add(){
    while(s[i]!='-'&&s[i]!='+'&&i<len){
        //cout<<i<<" "<<s[i]<<endl;
        ans+=s[i];
        i++;
    }
}
void addzero(){
    //cout<<i<<" "<<s[i]<<endl;
    ans+=s[i];
    i++;
    if(s[i]!='-'&&s[i]!='+'&&i<len){
        //cout<<i<<" "<<s[i]<<endl;
        ans+="+";
        if(s[i]!='0')   add();
        else addzero();
    }
}
int main() {
    cin>>s;
    len=s.length();
    for(i=0;i<len;){
        while(s[i]!='-'&&i<len){
            //cout<<i<<" "<<s[i]<<endl;
            ans+=s[i];
            i++;
        }
        if(s[i]=='-'){
            //cout<<i<<" "<<s[i]<<endl;
            ans+=s[i];
            i++;
            //cout<<i<<" "<<s[i]<<endl;
            ans+=s[i];
            i++;
            if(s[i]!='-'&&s[i]!='+'&&i<len){
                //cout<<i<<" "<<s[i]<<endl;
                ans+="+";
                if(s[i]!='0'){
                    //cout<<i<<" "<<s[i]<<endl;
                    add();
                }
                else{
                    //cout<<i<<" "<<s[i]<<endl;
                    addzero();
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

Fygon

题意

给出一段代码，算时间复杂度

题解

不知道是不是不懂python的原因，可是我明明记得python是按照对齐来判断结束的呀！这里的5 * (n*n + 1)是什么鬼？

AC代码

Graph

题意

题解

AC代码

Hash Code Hacker

题意

给出一个k，输出k个通过hash运算值相等的字符串（字符串不超过1000）。
hash函数为：s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]。
其中，这个机器为32位的。

题解

看作31位就好。但刚开始受2进制影响，以为最高位减一，其他位增一，最后位增二，就相等。突然，灵光一现，应该是某位减一，比它第一位的加31就可以了。看了一下大写小写都可以，很开心。博博码代码，我休息，很开心。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
char s[1005];
int main(){
    for(int i = 1; i <= 1000; i ++) s[i - 1] = 'M';
    int k, idx = 0;
    scanf("%d", &k);
    for(int i = 1; i < k; i ++){
        s[idx] --;
        s[idx + 1] += 31;
        printf("%s\n", s);
        s[idx]++;
        s[idx + 1] -= 31;
        idx ++;
    }
    printf("%s\n", s);
    return 0;
}

Insider’s Information

题意

题解

AC代码

Journey to the “The World’s Start”

题意

有n-1张地铁卡，地铁卡有自己的乘车范围（可以从i-r到i+r，i为当前站）和价格，你只能买一张地铁卡。某人要经过n站地铁，但是它没钱，所以要省钱，但是要满足在限定的时间内到达。问最少的话费。

题解

刚开始想要从钱少的开始试，深搜加剪枝，可惜不成功。后来博博用了线段树从范围来剪。因为如果地铁卡小范围可以的话，大范围一定也可以。后来看到网上的优先队列，和刚开始的思路不一样，理解有点吃力，勉强看懂了。本来深搜想加一个最少停的站数*最小在站台花费时间与剩余时间比较的剪枝的，蜜汁WA。不是很懂。

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
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<queue>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=5e4+10;
const LL INF=1e18;
LL n,T;
LL cost_money[maxn];
LL cost_time[maxn];
struct node{
    LL pos,time;
    bool operator < (const node &n1)const{
        return this->time > n1.time;
    }
}in,out;
//inline bool scan_d(LL &num){
//    char in;bool IsN=false;
//    in=getchar();
//    if(in==EOF) return false;
//    while(in!='-'&&(in<'0'||in>'9')) in=getchar();
//    if(in=='-'){ IsN=true;num=0;}
//    else num=in-'0';
//    while(in=getchar(),in>='0'&&in<='9'){
//        num*=10,num+=in-'0';
//    }
//    if(IsN) num=-num;
//    return true;
//}
bool ok(LL x){
    priority_queue<node>Q;
    Q.push((node){1,0});
    LL ans=0;
    for(int i=2;i<=n;i++){
        while(!Q.empty()&&(i-Q.top().pos>x))Q.pop();
        in.pos=i;
        in.time=Q.top().time+cost_time[i];
        Q.push(in);
        ans=in.time;
    }
    return ans<=T;
}
int main(){
//    freopen("journey.in","r",stdin);
//    freopen("journey.out","w",stdout);
    scanf("%lld%lld",&n,&T);
    for(LL i=1;i<n;i++){
        scanf("%lld",&cost_money[i]);
    }
    for(LL i=2;i<n;i++){
        scanf("%lld",&cost_time[i]);
    }
    T-=n-1;
    LL l=0,r=n-1,Pos=0;
    while(l<=r){
        LL mid=(l+r)/2;
        if(ok(mid)){
            Pos=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    LL ans=INF;
    if(Pos==0)Pos=1;
    for(LL i=Pos;i<n;i++){
        ans=min(ans,cost_money[i]);
    }
    printf("%lld\n",ans);
    return 0;
}

TLE代码-深搜+剪枝

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=5e5+5;
struct node{
    int range,price;
    bool operator <(const node a)const{
        return price<a.price;
    }
}card[maxn];
int d[maxn],vis[maxn];
int Max,n;
bool dfs(int range,int time,int stop){
    if(time>Max)return false;
    for(int i=1;i<=range;i++){
        int to=stop+i;
        if(to>=n){
            return true;
        }
        if(vis[to]&&time+d[to]>=vis[to])continue;
        vis[to]=time+d[to];
        if(dfs(range,time+d[to],to))return true;
    }
    return false;
}
inline bool scan_d(int &num){
    char in;bool IsN=false;
    in=getchar();
    if(in==EOF) return false;
    while(in!='-'&&(in<'0'||in>'9')) in=getchar();
    if(in=='-'){ IsN=true;num=0;}
    else num=in-'0';
    while(in=getchar(),in>='0'&&in<='9'){
        num*=10,num+=in-'0';
    }
    if(IsN) num=-num;
    return true;
}
int main(){
//    freopen("journey.in","r",stdin);
//    freopen("journey.out","w",stdout);
    scan_d(n);
    scan_d(Max);
    for(int i=1;i<=n-1;i++){
        scan_d(card[i].price);
        card[i].range=i;
    }
    sort(card+1,card+n);
    int Min=0x7f7f;
    for(int i=2;i<=n-1;i++){
        scan_d(d[i]);
        Min=min(d[i],Min);
    }
    Max-=n-1;
    int rangemax=0;
    for(int i=1;i<=n-1;i++){
        if(card[i].range<=rangemax)continue;
        memset(vis,0,sizeof(vis));
        if(dfs(card[i].range,0,1)){
            printf("%d\n",card[i].price);
            break;
        }
        else{
            rangemax=max(rangemax,card[i].range);
        }
    }
    return 0;
}

TLE代码-二分法

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=5e5+5;
struct node{
    int range,price;
}card[maxn];
int d[maxn],vis[maxn];
int Max,n;
inline bool scan_d(int &num){
    char in;bool IsN=false;
    in=getchar();
    if(in==EOF) return false;
    while(in!='-'&&(in<'0'||in>'9')) in=getchar();
    if(in=='-'){ IsN=true;num=0;}
    else num=in-'0';
    while(in=getchar(),in>='0'&&in<='9'){
        num*=10,num+=in-'0';
    }
    if(IsN) num=-num;
    return true;
}
bool dfs(int range,int time,int stop){
    if(time>Max)return false;
    for(int i=range;i>=1;i--){
        int to=stop+i;
        if(to>=n){
            return true;
        }
        if(vis[to]&&time+d[to]>=vis[to])continue;
        vis[to]=time+d[to];
        if(dfs(range,time+d[to],to))return true;
    }
    return false;
}
int main(){
//    freopen("journey.in","r",stdin);
//    freopen("journey.out","w",stdout);
    scan_d(n);scan_d(Max);
    for(int i=1;i<=n-1;i++){
        scan_d(card[i].price);
        card[i].range=i;
    }
    for(int i=2;i<=n-1;i++){
        scan_d(d[i]);
    }
    Max-=n-1;
    int l=1,r=n-1;
    int ans=0;
    while(l<=r){
        memset(vis,0,sizeof(vis));
        int mid=(l+r)/2;
        if(dfs(card[mid].range,0,1)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    if(ans==0)ans=1;
    int anss=1e9;
    for(int i=ans;i<n;i++) anss= min(anss, card[i].price);
    printf("%d\n",anss);
    return 0;
}

Kingdom Trip

题意

题解

AC代码

Lucky Chances

题意

给你一个棋盘，找有多少个数它沿一个方向一直走，所经过的数都小于它。注意不同方向算多次。

题解

暴力

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
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=105;
int mmap[maxn][maxn];
int dirx[4]={0,0,1,-1};
int diry[4]={1,-1,0,0};
int main() {
    freopen("lucky.in", "r", stdin);
    freopen("lucky.out", "w", stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf("%d",&mmap[i][j]);
        }
    }
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            for(int k=0;k<4;k++){
                int flag=1;
                int x=i+dirx[k];
                int y=j+diry[k];
                while(x<n&&y<m&&x>=0&&y>=0){
                    if(mmap[x][y]>=mmap[i][j]){
                        flag=0;
                        break;
                    }
                    x+=dirx[k];
                    y+=diry[k];
                }
                ans+=flag;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

后记

如果有一天 我敢在别人注视下 静心地码代码 那我应该就真正不害怕了吧
以后多多找机会 不过应该不会有人那么闲的 珍惜每次训练吧
虽然每次去都怕爆零 看来只有变得更强大咯
昨天帮舍友搭博客 发现linux的一些命令有些淡忘了，果然自己的记忆力不行啊
每天努力一点点吧 至少现在觉得很充实
也觉得很幸福 因为我是个有团体的人啦
一个不是很多时候觉得迷茫的人呢！
要学的还有很多 还有最近吃多了
看来要打卡跑步了呢

转载请注明出处，谢谢。

愿 我是你的小太阳



买糖果去喽