2017–2018 ACM-ICPC Northern Subregional Contest St Petersburg

Posted on | In , | Visitors:

This is my blog.
又恢复正常了……
第一个礼拜开始练习……
经过CCPC杭州站的打击
大家都比之前更加努力，更加坚定了
既然做了，就要做到做好，
何况我们的目标不小，还是需要加油的
经过这些时段的练习，感觉是有进步的，但是体现的不明显
革命尚未成功，同志仍需努力啊！！！
（未完待续）

题目在Codeforces上可以下载到，就暂且不叙述了。

A. Auxiliary Project

水题，分析一下每个数字，找出最优解，分类讨论即可……文件输入输出居然写错了，真神奇！！！

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
    freopen("auxiliary.in","r",stdin);
    freopen("auxiliary.out","w",stdout);
    int n;
    cin>>n;
    if(n%3==0){
        cout<<7*(n/3)<<endl;
    }
    else if(n%3==1){
        cout<<7*(n/3-1)+4<<endl;
    }
    else{
        cout<<7*(n/3)+1<<endl;
    }
    return 0;
}

B. Boolean Satisfiability

其实看到这种题目，第一反应就是不看了。这个描述，太绕了……补题的时候，发现其实还……只有两个符号|和~，所以，对于一个表达式来说，如果同一个变量既有正又有取反符号，则每个变量都可以既取真又取假，则有2^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
32
33
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
const int maxn=100;//65-122
bool True[maxn],False[maxn];
int main(){
    freopen("boolean.in","r",stdin);
    freopen("boolean.out","w",stdout);
    string s;
    cin>>s;
    int len=s.length();
    for(int i=0;i<len;i++){
        if(s[i]=='|') continue;
        if(s[i]=='~'){
            i++;
            False[s[i]-'A']=1;
        }
        else{
            True[s[i]-'A']=1;
        }
    }
    bool flag=0;int sum=0;
    for(int i=0;i<maxn;i++){
        if(False[i]==1&&True[i]==1) flag=1;
        if(False[i]==1||True[i]==1) sum++;
    }
    if(flag) printf("%lld\n",(1LL<<sum));
    else printf("%lld\n",(1LL<<sum)-1);
    return 0;
}

C. Consonant Fencity

今天补完，有点感觉……
刚开始看题的时候，没看懂……但直觉告诉我可以做（哪儿来的自信……
题目要求使合法对最多。合法对是由两个大小写不同的辅音字母组成。
字母挺少的，配对的情况也很少。只需要确定两个字母组成的对，然后暴力枚举可能的情况。
看到网上很多有dfs的……其实感觉原理差不多

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
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
int cons[30][30];
int counts[30];
bool is_vowels(char a){
    if(a=='a'||a=='e'||a=='i'||a=='o'||a=='u'||a=='w'||a=='y')
        return true;
    return false;
}
int main(){
    freopen("consonant.in","r",stdin);
    freopen("consonant.out", "w", stdout);
    int num=0;
    for(int i='a';i<='z';i++){
        if(!is_vowels(i))
            counts[i-'a']=num++;
    }
    string s;
    cin>>s;
    int len=s.length();
    
    for(int i=0;i<len-1;i++){
        if(!is_vowels(s[i])&&!is_vowels(s[i+1])){
            if(s[i]<s[i+1]) cons[counts[s[i]-'a']][counts[s[i+1]-'a']]++;
            else cons[counts[s[i+1]-'a']][counts[s[i]-'a']]++;
        }
    }
    
    int ans=-1,anss=0;
    for(int i=0;i<(1<<19);i++){
        int tmp=0;
        for(int j=0;j<19;j++){
            for(int k=j+1;k<19;k++){
                if(((i>>j)&1)^((i>>k)&1))
                    tmp+=cons[j][k];
            }
        }
        if(tmp>ans){
            ans=tmp;
            anss=i;//to record the condtion
        }
    }
    
    //cout<<ans<<endl;
    for(int i=0;i<len;i++){
        if((anss>>counts[s[i]-'a'])&1)
            printf("%c",s[i]-'a'+'A');
        else
            printf("%c",s[i]);
    }
    printf("\n");
    return 0;
}

D. Dividing Marbles

自己觉得能分一半的分一半，不能分一半的分成三等分，否则，就分成1和剩下的。WA了……到时候再想想，争取今天补完……
看网上的一份题解，讲的是用二进制和贪心的想法……
看代码也是除三和除二……
（心情不好，看不下去……改天吧……

E. Equal Numbers

当时漏想了，互为因子的情况；然后就……
博博昨天说了一种思路，感觉挺对的……
估计得明天实现了……
再看了别人的代码，感觉和博博的思路是差不多的。
对于lcm在其中的，可以按照递减的方法；对于不存在的，需要找到因子，然后维护一个ans数组。

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
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e6+100;
const int maxx=1e6;
const ll INF=0x3f3f3f;
int cnt[maxn],que1[maxn],que2[maxn],dp[maxn];
int main(){
    freopen("equal.in","r",stdin);
    freopen("equal.out","w",stdout);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        cnt[x]++;
        dp[i]=INF;
    }
    
    int num=0,m1=0,m2=0;
    for(int i=1;i<=maxx;i++){
        if(cnt[i]){
        //find whether there is the number is the other's divisor
            num++;
            bool ok=false;
            que1[++m1]=cnt[i];
            for(int j=i+i;j<=maxx;j+=i){
            //find it,and que2[++m2]=cnt[i]
            //so,the x,xy take it consideration.
                if(cnt[j]){
                    ok=true;
                    break;
                }
            }
            if(ok){
                que2[++m2]=cnt[i];
            }
        }
    }
    
    sort(que1+1,que1+1+m1);
    sort(que2+1,que2+1+m2);
    
    dp[0]=num;
    int sum=0;
    for(int i=1;i<=m2;i++){
        sum+=que2[i];
        dp[sum]=num-i;
    }
    sum=que1[1];
    for(int i=2;i<=m1;i++){
        sum+=que1[i];
        dp[sum]=min(num+1-i,dp[sum]);
    }
    
    printf("%d",num);
    for(int i=1;i<=n;i++){
        dp[i]=min(dp[i],dp[i-1]);
        printf(" %d",dp[i]);
    }
    printf("\n");
    return 0;
}

F. Fygon 2.0

又是这种表达式，表示还没看题

G. Grand Test

H. Hidden Supervisors

I. Intelligence in Perpendicularia

总周长减去在外部的周长即可。

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 <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1100;
int a[maxn],b[maxn];
int main(){
    freopen("intel.in","r",stdin);
    freopen("intel.out","w",stdout);
    int n;
    scanf("%d",&n);
    scanf("%d%d",&a[0],&b[0]);
    ll C=0;
    for(int i=1;i<n;i++){
        scanf("%d%d",&a[i],&b[i]);
        C+=abs(a[i]-a[i-1])+abs(b[i]-b[i-1]);
    }
    C+=abs(a[n-1]-a[0])+abs(b[n-1]-b[0]);
    sort(a,a+n);
    sort(b,b+n);
    printf("%lld\n",C-2*(a[n-1]-a[0]+b[n-1]-b[0]));
    return 0;
}

J. Joker

K. Kotlin Island

在规定的规模下，用.和#将区域分为指定的块数。
求出最大可分出的块数，去掉不可能解；因为h，w都挺小的，所以我得到的每行每列的最大可分块数也很小，双重循环，看是否能合成。

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
#include <iostream>
#include <cstdio>
using namespace std;
int mmap[110][110];
int main(){
    freopen("kotlin.in","r",stdin);
    freopen("kotlin.out","w",stdout);
    int h,w,n;
    scanf("%d%d%d",&h,&w,&n);
    int r,c;//max
    r=(h+1)/2;
    c=(w+1)/2;
    if(n==1){
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                printf(".");
            }
            printf("\n");
        }
        return 0;
    }
    if(r*c<n){
        printf("Impossible\n");
        return 0;
    }
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            if(i*j==n){
                //cout<<i<<" "<<j<<endl;
                for(int k=1;k<i;k++){
                    for(int t=1;t<=w;t++){
                        mmap[k*2][t]='#';
                    }
                }
                for(int k=1;k<j;k++){
                    for(int t=1;t<=h;t++){
                        mmap[t][k*2]='#';
                    }
                }
                for(int k=1;k<=h;k++){
                    for(int t=1;t<=w;t++){
                        if(mmap[k][t]=='#') printf("#");
                        else printf(".");
                    }
                    printf("\n");
                }
                return 0;
            }
        }
    }
    printf("Impossible\n");
    return 0;
}

L. Little Difference

首先去掉可以用2的次方，因为一定可以用无穷多个1和2的乘积来表示。
接着最小的因数为2，所以可以枚举总次数。然后二分因数。
注其实做题的时候，对于数据范围应该要很敏感才对么……就比如说【见其他】，根据数据的范围来确定做法。并且因为数据很大，所以能用除法就不要用乘法，同时注意除法时的去小数部分的情况。所以尽量除数为较小的数。

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
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
struct ty{
    ll a,b,x;//a big times;b small times;x big number
}ans[maxn];
ll n;
int judge(ll mid,int a,int b){
    ll tmp=1;
    for(int i=1;i<=a;i++){
        tmp*=mid;
        if((n/tmp)<mid&&i<a) return 1;//too big
    }
    ll temp=1;
    for(int i=1;i<=b;i++){
        temp*=(mid-1);
        if((n/temp)<(mid-1)&&i<b) return 1;
    }
	  //the followings are wrong
    //if(tmp*temp<n)
    //if(temp<n/tmp)
    if(tmp<n/temp)
    {
        return -1;
    }
    if(n%temp==0&&tmp==n/temp) return 0;//find!!!
    return 1;//too big
}
int main(){
    freopen("little.in","r",stdin);
    freopen("little.out","w",stdout);
    scanf("%lld",&n);
    ll tmp=n;
    while(tmp%2==0)tmp/=2;
    if(tmp==1){
       printf("-1\n");
       return 0;
    }
    ll cnt=0;
    for(int i=1;i<64;i++){//2^64>1e18 times
        for(int j=1;j<=i;j++){
            
            ll l=2,r=1e18;//number
            while(l<=r){
                ll mid=(l+r)>>1;//bigger number
                int flag=judge(mid, j, i-j);//i total times,j small times
                if(flag==-1){
                    l=mid+1;
                }
                else if(flag==1){
                    r=mid-1;
                }
                else{
                    ans[cnt].a=j;
                    ans[cnt].b=i-j;
                    ans[cnt++].x=mid;
                    break;
                }
            }
        }
    }
    printf("%lld\n",cnt);
    for(ll i=0;i<cnt;i++){
        printf("%lld",ans[i].a+ans[i].b);
        for(int j=0;j<ans[i].a;j++)
            printf("% lld",ans[i].x);
        for(int j=0;j<ans[i].b;j++)
            printf(" %lld",ans[i].x-1);
        printf("\n");
    }
    return 0;
}

其他

题目

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。
马路上有一些区域要用来建地铁，这些区域用它们在数轴上的起始点和终止点表示。已知任意区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两颗树）移走。你的任务是计算将这些树都移走后，马路上还有多少树。有M个区域。

解法

小范围

1<=L<=10000 1<=M<=100
开个10000的数组，然后每一个区域标记一下，最后遍历一遍输出。
最坏的情况（1e6）

大范围

1<=L<=100000 1<=M<=100000
给M的左界和右界分别排个序，遍历第一遍，遇到左界+1，遇到右界-1；最后扫一遍整体，遇到值“0”，ans++

超大范围

1<=L<=10^9 1<=M<=100000
设置一个结构体

1
2
3
struct ty{
	int x,b;
}

根据左开右闭的原则

1
2
3
4
5
a[2*i-1].x=x;
a[2*i-1].b=1;
a[2*i].x=y+1;
a[2*i].b=-1;

根据左界排序，之后一个for循环计算。这里的for循环的最大值是2*M，而对于第二种的for循环的最大值是L。

注 区间是一个点的时候，应该把区间作为左开右闭，可以画图看看。比如1-3和4-6，实际上连起来是1-6，但是你的区间就成了断开的。所以应该看作[1,4)和[4,7)。这里用到的一个思想就是离散化。不过，离散数学学到现在，并没觉得有什么用啊……（也有可能是我没体会到它的精髓。不知道图论学完后，还会是这个感觉么 ：）

转载请注明出处，谢谢。

愿 我是你的小太阳


买糖果去喽