Nordic Collegiate Programming Contest 2016

Posted on | In , | Visitors:

This is my blog.
今天西安雨下的很大 很冷很冷 走在黄叶铺满的小路上 白鞋子还是脏了
我还是穿着裙子 喝着奶茶 随便解决了我的午饭
学校里没有什么店 也没有什么人
很安静很安静 真好
（未完待续）


其实很不想回答的问题就是：你吃饭了吗？吃了什么？
如果我没有 你也不能陪我吃啊
一个人能吃什么呢
去了G楼 有些人已经到了 有些人在宿舍打着
宿舍断了网 还有就是环境不适合
其实我何尝不想出去走走呢 只是一个人 不愿罢了

不过
昨天倒是和大太阳出去溜达溜达了
其实挺不好意思麻烦他的
他很迁就我
不知道他玩的开不开心
应该不开心的吧
其实应该告诉我你喜欢什么的
一年的友谊 一年的快乐时光
你做了我一年的大太阳
一年的闲聊
幸好 我们还有话聊
友谊天长地久
希望他能找到他喜欢的事情
继续发光
至于其他的还是写在日记中吧
毕竟我不知道谁在看

仅仅的留校舍友 照例和男朋友腻歪着
博博的女友 很漂亮 画的画 也很好
真好 真好
明明继续他的数学之旅 一路给我讲“炉石传说的天梯制”
真好 真好
而我 与代码在一起
继续听着歌 不知道敲打了多少次的#include <iostream>
以前觉得有意思的事情 现在也会因为这种种 而没有了过多的热情了
说不上嫌弃吧 只是有时会突然什么都不想动 没有当初那么纯粹了
再者 他们都说这太难了
嗯 我知道 很难很难
可是 我能如何呢
我没有那么渴望奖 但也没有完全不受它的影响
只是觉得有时候有点无聊 但不想打扰任何人
看着QQ消息 有些对话 不想回复 有些人 不想打扰 有些头像 再也不敢点开 有些东西 石沉大海吧
就这样 一天又过了。
果然雨天就是悲伤的
想多了 不好

补题吧！
值得庆幸的是 偶然发现了claris的博客

这次没有题目链接，我也不知道去哪儿提交，貌似那个网站我越不了
很可能是我哪里傻了

A.Artwork

10.3

题解

10.3.1

AC代码

暂无（claris的没有看懂）[纠结ing，不会二维的并查集，准确来说没有用过并查集，但今天看了一下原理，感觉是看懂了]

B.Bless You Autocorrect!

10.3.2
Output
For each word to type, output a line containing the minimum number of keystrokes required to type the corresponding word.
懒得截图了，就看题意中的那个例子好了。

题解

这是最长的题解 没有看。claris说是将字典和询问串都插入Trie中，建好图然后BFS即可。
一下子写不出来。

AC代码

照例没有，总不能放claris的代码吧！想要代码就去他博客吧！

C. Card Hand Sorting

10.3.3

题解：

1.Try all 4! = 24 possible ways of ordering the 4 suits.
2.Try all 2^4 = 16 possible ways of choosing ascending/descending order within suits
3.Maximum number of cards that can remain in place is length of longest increasing subsequence with respect to the chosen ordering.
4.枚举花色的顺序以及升降序，那么此时最小移动次数=n−LIS

AC代码

看过claris代码的，哎。太弱了。

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
#include<iostream>
#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<int,int>pi;
const int maxn=55;
pi a[maxn],b[maxn];
string hs="shdc";
int rev[4*maxn],idx[maxn],dp[maxn],n;
int p[4]={0,1,2,3};
int cmp(int x,int y){
    return b[x]<b[y];
}
int solve(int mask){
    for(int i=0;i<n;i++){
        b[i]=a[i];
        if(mask>>b[i].first&1){
            b[i].second=16-b[i].second;
        }
        b[i].first=p[b[i].first];
    }
    for(int i=0;i<n;i++)idx[i]=i;
    sort(idx,idx+n,cmp);
    int ret=0;
    
    for(int i=0;i<n;i++){
        dp[i]=0;
        for(int j=0;j<i;j++)if(idx[j]<idx[i])dp[i]=max(dp[i],dp[j]);
        dp[i]++;
        ret=max(ret,dp[i]);
    }
    return n-ret;
}
int getnum(char c){
    if(c>='2'&&c<='9')return c-'0';
    if(c=='T')return 10;
    if(c=='J')return 11;
    if(c=='Q')return 12;
    if(c=='K')return 13;
    return 14;
}
int main(){
    for(int i=0;i<4;i++)rev[hs[i]]=i;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        char s[10];
        scanf("%s",s);
        a[i]=pi(rev[s[1]],getnum(s[0]));
    }
    int ans=1e9;
    for(int mask=0;mask<1<<4;mask++){
        do{
            ans=min(ans,solve(mask));
        }while(next_permutation(p,p+4));
    }
    printf("%d\n",ans);
    return 0;
}

D.Daydreaming Stockbroker

10.3.4

题解

只有两种情况，买或卖。

代码（没有地方交）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    int pre=1<<30;
    int res=100;
    for(int i=1;i<=n;i++){
        int now;
        scanf("%d",&now);
        if(now>=pre){
            res+=min((res/pre),100000)*(now-pre);
        }
        pre=now;
    }
    printf("%d\n",res);
    return 0;
}

提醒一句，题目中虽说不超过2^32,但不可以用2^32,而是用一个略小的数字2^30，否则第一组除数为0.

E.Exponial

10.3.5

题解

欧拉降幂公式套一下就好

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
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
ll n,m,ans;
ll getphi(ll n){
    ll ans=n;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0){
            ans-=ans/i;
            while(n%i==0)
                n/=i;
        }
    }
    if(n>1)//n is prime
        ans-=ans/n;
    return ans;
}
ll fast_mod(ll x,ll n,ll Max){
    ll res=1;
    while(n>0){
        if(n & 1)
            res=(res*x)%Max;
        x=(x*x)%Max;
        n >>= 1;
    }
    return res;
}
ll func(ll n,ll m){
    if(m==1) return 0;
    if(n<=5){
        ll ans=1;
        for(int i=1;i<=n;i++){
            ans=fast_mod(i,ans,m);
        }
        return ans;
    }
    else{
        ll phi=getphi(m);
        ll z=func(n-1,phi);
        ans=fast_mod(n,phi+z,m);
    }
    return ans;
}
int main(){
    scanf("%lld%lld",&n,&m);
    printf("%lld\n",func(n,m));
    return 0;
}

F.Fleecing the Raffle

10.3.6

题解

化简一下公式，就好。我没有化到最简，但也过了。
Cxy表示x在上，y在下，纯属个人笔记，作为注释而已。见谅，没心情打数学公式给你们看。
//x=1 C11C(p-1)n/Cp(n+1)=p/(n+1)
//x=2 C12C(p-1)n/Cp(n+2)=2p(n-p+2)/(n+2)/(n+1)
//x=y-1 C1(y-1)C(p-1)n/Cp(n+y-1)=(y-1)p[(n-p+y-1)(n-p+y-2)……(n-p+2)]/[(n+y-1)(n+y-2)……(n+1)]
//x=y C1yC(p-1)n/Cp(n+y)=yp[(n-p+y)(n-p+y-1)……(n-p+2)]/[(n+y)(n+y-1)……(n+1)]
//a[i]=a[i-1]/(i-1)i(n-p+i)/(n+i)
后面是正解的继续化简
// x n−p+x
//—- · ———
//x−1 n+x
//化简1+[(1-p)x+n]/[x^2+(n-1)x-n]
//[(1-p)*x+n]<=0
//x>=n/(p-1)
//max happens at x = ⌊n/(p − 1)⌋
//Some calculus ⇒ increase if x < n , decrease otherwise p−1 ⇒ max happens at x = ⌊n/(p − 1)⌋.

AC代码（未最简）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,p;
int main(){
    scanf("%d%d",&n,&p);
    double ans=1.0*p/(n+1);
    for(int i=2;i<=n;i++){
        double tmp=ans/(i-1)*i*(n-p+i)/(n+i);
        if(tmp<ans)break;
        ans=tmp;
    }
    printf("%.7f\n",ans);
    return 0;
}

代码（正解思路，但未测试过）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,p;
int main(){
    scanf("%d%d",&n,&p);
    int x=n/(p-1);
    double ans=double(x*p)/(n+1);
    for(int i=2;i<=x;i++){
        ans*=double(n-p+i)/(n+i);
    }
    printf("%.7f\n",ans);
    return 0;
}

G.Game Rank

10.3.7
Output
Output a single line containing a rank after having played the given sequence of games; either an integer between 1 and 25 or “Legend”.
照例截不下样例。

题解：

模拟题。挺麻烦的。明明说这是“炉石传说”背景下的题目。还是他比较适合。嗯嗯，题目太长，很容易漏条件。

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
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int book[30]= {0,5,5,5,5,5,5,5,5,5,5,4,4,4,4,4,3,3,3,3,3,2,2,2,2,2};
char ch[10010];
int main()
{
    scanf("%s",ch);
    int length = strlen(ch);
    int rank = 25;
    int stars = 0;
    int liansheng = 0;
    bool flag = false;
    for(int i = 0; i<length; i++)
    {
        if(rank <= 0)       
        {
            flag = true;
            break;
        }
        if(ch[i] == 'W')
        {
            liansheng++;
            if(rank > 5 && liansheng >= 3)
            {
                stars += 2;
            }
            else
            {
                stars++;
            }
        }
        else
        {
            liansheng = 0;
            if(rank <= 20)
            {
                stars--;
            }
        }
        if(stars > book[rank])
        {
            stars -= book[rank];
            rank--;
        }
        if(stars == -1 && rank < 20)
        {
            rank++;
            stars = book[rank] - 1;
        }
        if(stars == -1 && rank == 20)
        {
            stars = 0;
        }
    }
    if(rank <= 0)
    {
        flag = true;
    }
    if(flag)
    {
        printf("Legend\n");
    }
    else
    {
        printf("%d\n",rank);
    }
    return 0;
}

H.Highest Tower

10.3.8

题解

还没有看。但这是我第二道看的题，第一题是A题。有点郁闷，挑的都不是我会的。不会算时间复杂度，然后就暴力，其实也感觉没有优化，怪怪的。顺利的TLE了。

AC代码

所以怎么可能会有呢！

I.Interception

10.3.9

题解：

这应该是我看的第三题了，为什么我不去看榜呢！震惊了。题目是看懂了，没想法。

AC代码

仍然没有

J.Jumbled Compass

10.3.10

题解：

判断一下就好了。
今晚有点脑抽，不会化简，看一下就好

AC代码：

claris的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    while(scanf("%d%d",&a,&b)!=EOF){
        int t1=b-a;
        if(t1<0)t1+=360;
         
        int t2=a-b;
        if(t2<0)t2+=360;
        if(t1<=t2){
            printf("%d\n",t1);
        }
        else{
            printf("%d\n",-t2);
        }
    }
}

明明的

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>
using namespace std;
int main()
{
    int n1, n2;
    int flag = 1;
    scanf("%d%d",&n1,&n2);
    int num = 0, num1 = 0, num2 = 0;
    if(n1 >n2)
    {
        flag = 0;
    }
    if(flag)
    {
        num1 = n2 - n1;
        num2 = n2 - n1 - 360;
    }
    else
    {
        num1 = n2 - n1;
        num2 = 360 - n1 + n2;
    }
    printf("%d\n",abs(num2)<abs(num1)?num2:num1);
    return 0;
}

代码（未测试）

因为明明做了，所以现场的时候我没看，所以没测试。反正我的第一想法是这个，最好有个反例来告诉我一声呢。不过我发现我弄的评论还得注册，确实挺麻烦的呢！可以私聊我。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main(){
    int x,y;
    scanf("%d%d",&x,&y);
    int ans=y-x;
    if(abs(ans)<=180)
        printf("%d\n",ans);
    else{
        if(ans<0)
            printf("%d\n",ans+360);
        else
            printf("%d\n",ans-360);
    }
    return 0;
}

K.Keeping the Dogs Apart

10.3.11

题解

题目都未看，哪来的题解

AC代码

没有。哎

后记

好抱歉，越写越郁闷。这么多都是不会的。很多知识点还没有搞懂。
只能怪下雨天咯。
睡觉睡觉。
晚安 世界。

转载请注明出处，谢谢。

愿 我是你的小太阳



买糖果去喽