SCNUOJ 2019 欢送(迫害)CGY杯题解

作者: myleosu | 来源:发表于2019-04-29 01:03 被阅读0次

火车出站

Problem Description

CGY管理着一个火车站的调度问题，这个车站有个中转站，可以停靠任意多节的火车，但末端封顶，驶入中转站的火车必须按照相反的顺序驶出。现在有N节火车，编号为1~N，这些火车按照1,2,3…N的顺序进站。CGY每天看着这些火车真的很无聊，他现在在想这些火车会有多少种出站顺序。

Input

输入的第一行是一个整数T,表示有T(1≤T≤100)组数据
接下来包含T行，每行一个整数N(1≤N≤35)，表示火车的节数。

Output

输出T行，每行一个整数，表示可能的出站顺序

Sample Input

3
1
2
3

Sample Output

1
2
5

Hint

对于2节火车，有12和21两种出站顺序
对于3节火车，有123,132,213,231,321五种出站顺序

思路：

这是道规律题，数列为卡特兰数。
注意一下数据范围，卡特兰数第35项刚好比long long小一点，但用不同的递推式中途数据long long可能会爆掉.
//至于什么是卡特兰数，请自行百度(谷歌)

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long long cat[40];
int n,t;
void init()
{
    memset(cat,0,sizeof(cat));
    cat[0]=cat[1]=1;
    for(int i=2;i<36;i++)
    {
        for(int j=0;j<i;j++)
            cat[i]+=cat[j]*cat[i-1-j];
    }
}
int main()
{
    init();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        printf("%lld\n",cat[n]);
    }
    return 0;
}

棋子翻转

Problem Description

CGY是一个下棋高手，现有一个4*4的棋盘，上面放着16颗双面棋，一面是黑色，另一面是白色。CGY可以主动翻转棋盘中的任意一颗棋子，某颗棋子被主动翻转后，会使它上下左右四颗棋子被动翻转（如果存在的话）。当所有棋子都白色朝上或者黑色朝上时，则视作目标完成。GGY觉得这个问题没有挑战性，现在请你设计程序计算出完成目标的最小主动翻转次数。

Input

输入包括4行，每行包括4个字符”a”或者”b”，”a”表示白色，”b”表示黑色。

Output

输出包括一行，输入完成目标的最小主动翻转次数，如果无论怎么样翻转都无法完成目标则输出”Impossible”。

Sample Input

bbbb
bbbb
bbab
baaa

Sample Output

1

Hint

思路：

方法一：本题的数据比较小，只有16个棋子，每个棋子只有两种状态，即有被主动翻转和没有被主动翻转。只要我们用暴力法枚举出每一行棋子的翻转情况就可以求出最小的主动翻转次数，总共会有 $2^{16}$ 种情况。
这里我们用到二进制来描述装置，1表示被主动翻转，0表示没有被主动翻转。比如说第一行的状态是5，转换为二进制就是0101，它所表示的含义就是在这一行的第二和第四个位置都被主动翻转过了，这样我们就可以用四个变量来描述四行棋子的状态了。
接着，我们就需要判断在这个状态下，是否全部棋子都是相同颜色的。如果可以完成目标而且主动翻转次数比之前找到的解更小，就把他记录下来。判断棋子颜色也很简单，比如说要判断某颗棋子是不是黑色，如果先前为“b”，就计数器num就为1，然后再记录周围（上左下右中5个位置）的主动翻转次数，最后计数器的值为为奇数说明它是黑色，否则为白色。
LWH(出题人)：//位运算不会？回去补呀~
方法二：DFS或for循环暴力枚举所有情况

代码(方法一)：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm> 

using namespace std;
char s[6][6];
int zt[5];
int mark[6][6];
int move[]={1,0,0,1,-1,0,0,-1,0,0};
int res=17;

bool is_black(int x,int y){
    int num=0;
    if(s[x][y]=='b')num++;
    for(int i=0;i<10;i+=2){
        if(mark[x+move[i]][y+move[i+1]])
            num++; 
    }
    if(num&1) return true;
    else return false;
}

void check(int a,int b,int c,int d){
    memset(mark,0,sizeof(mark));
    int ans=0;
    zt[1]=a,zt[2]=b,zt[3]=c,zt[4]=d;
    for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++){
            if(zt[i]&1){
                mark[i][j]=1;
                ans++;
            } 
            zt[i]>>=1;
        }
    int numb=0,numw=0;
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            if(is_black(i,j))numb++;
            else numw++;
            if(numb && numw)return ;
        }   
    }
    if(ans<res)res=ans;
    return ;
}

int main()
{
    for(int i=1;i<=4;i++)
        scanf("%s",s[i]+1);
    
    for(int a=0;a<(1<<4);a++)
        for(int b=0;b<(1<<4);b++)
            for(int c=0;c<(1<<4);c++)
                for(int d=0;d<(1<<4);d++)
                    check(a,b,c,d);
    if(res==17)
        cout<<"Impossible"<<endl;
    else
        cout<<res<<endl; 
    return 0;
}

CGY出差

Problem Description

CGY刚来公司不久，公司就有一个大型的差事交给CGY：让CGY乘坐公司的无人汽车外出M国出差。CGY通过LXY知道了一些情报：沿途城市中的某样宝石的交易价格不都相同。其中第i座城市的宝石价格为ai元。CGY每到一座城市（编号为i）可以有以下三种操作：
1.花ai元买入一块宝石
2.以ai元卖出一块宝石
3.do not thing
由于城市对宝石的管控十分严格，所以每次最多买入或卖出一块宝石。CGY想知道自己去M国的路途中最多可以赚多少钱，当然，CGY并不想花多余的力气与商人交易，所以交易的次数也要尽可能的少。你可以假设CGY一开始带着无限的金钱。

Input

输入的第一行为一个数字t (1<= t <= 10)，代表有t组数据。对于每一组数据：
每组数据的第一行为一个数字n (1<= n <= 10^5)
每组数据的第二行为n个数字，空格隔开，代表沿途中第i个城市某样宝石的交易价格ai (1<= ai <= 10^9)

Output

对于每一组数据，输出两个数字——CGY能最多可以赚的钱数和在此条件下最少的交易次数。

Sample Input

3
4
1 2 10 9
5
9 5 9 10 5
2
2 1

Sample Output

16 4
5 2
0 0

Hint

思路：

本题大多数同学都能想到贪心，每次都从队列中的最小值购入，最大值卖出，但采用的是每经过一次城市，将右边剩余的数进行排序，若最大值大于当前城市交易价格就购入并删除最大值对应的城市。很明显，这种策略是正确的，但时间复杂度是0(n*n*lgn)显然会超时。
所以本题的正解是：优先队列+贪心。假设三座城市的交易价格一次为A1，A2，A3，其中A3>A2>A1。我们可以发现A3-A1=(A3-A2) + (A2-A1)。
也就是我们用A1元买入一块宝石，以A2元买出，赚了a元，然后发现A3元大于A2元，可以再用A3元-A2元得到b元，其中A3-A1=a+b，也就是说，A2元购入并不影响最终结果，也就说没有中间商赚差价。
所以我们可以用一个优先队列来维护前面的交易价格的最小值，然后当前交易价格Ai大于队列最小值时，购入，最小值出列，将Ai入队两次(因为Ai有可能是中间商)，并标记Ai。如果队列最小值被标记过了，则表明之前的Aj的交易为中间商，总次数-1即可。时间复杂度O(nlgn)。
题目主要是考一个思维，将每次的交易价格入队两次的思维比较巧妙。

代码：

#include<iostream>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>

using namespace std;

const int MAXN = 1e5+10;

struct Node{
    int id;
    int value;
    bool operator < (const Node&s1) const{
        if(s1.value == value) return id>s1.id;
        else return value>s1.value;
    }
}a[MAXN];

priority_queue<Node> q;

map<int,int>ma;

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        long long res = 0,cnt = 0;
        int n,x;
        scanf("%d",&n);
        while(!q.empty()){q.pop();}
        ma.clear();
        for(int i = 1;i<=n;i++){
            scanf("%d",&x);
            a[i].id = i;
            a[i].value = x;
            if(!q.empty() && x>q.top().value){
                int prex = q.top().value; q.pop();
                res+=(long long)x-prex;
                cnt++;
                if(ma[prex]){
                    cnt--;
                    ma[prex]--;
                }
                ma[x]++;
                q.push(a[i]);
            }
            q.push(a[i]);
        }
        printf("%lld %lld\n",res,cnt*2);
    }
    return 0;
}

Jump

Problem Description

CGY在玩闯关游戏，在这个游戏中，有N块石头，现在CGY站在某块石头上，终点在另一块石头上，CGY需要跳到目标石头上。虽然CGY有着惊人的跳跃力，但他想隐藏自己的实力，他想在到达终点的前提下，使自己每一步的跳跃尽可能的小。他想知道他必须要跳的最小距离是多少。

Input

输入的第一行是一个整数N，表示有N个石头(2 <= N <= 200)
接下来是N行，每行包含两个整数xi，yi(0 <= xi，yi <= 1000)，表示每一块石头的坐标。其中第一行是CGY现在的位置，第二行是目标石头的位置

Output

输出一行，表示CGY需要跳的最小距离，输出三位小数

Sample Input

3
0 0
2 0
1 1

Sample Output

1.414

Hint

对于样例，CGY直接从1->2需要的跳跃距离为2，但CGY从1->3->2则每步需要跳跃1.414

思路：

题目要求源点到终点的路径的最长边的最小值，
最短路变形，可以用dijkstra变形，
改变松弛条件,
dis[j]=min(dis[j],max(dis[mink],ma[mink][j]));
dis[i]表示源点到i点的路径的最长边的最小值

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#define inf 0x3f3f3f3f
using namespace std;
double ma[210][210];
bool vis[210];
double dis[210];
int n,kase=1;
int x[210],y[210];
void init()
{
    for(int i=1;i<=n;i++)
    {
        vis[i]=false;
        dis[i]=inf;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            if(i==j)
                ma[i][j]=0;
            else
                ma[i][j]=inf;
    }
}
void dijkstra(int s)
{
    dis[s]=0;
    for(int i=1;i<=n;i++)
    {
        int mink;
        double minl=inf;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&minl>dis[j])
            {
                minl=dis[j];
                mink=j;
            }
        }
        vis[mink]=true;
        for(int j=1;j<=n;j++)
        {
            dis[j]=min(dis[j],max(dis[mink],ma[mink][j]));
        }
    }
}
double distance(int x1,int y1,int x2,int y2)
{
    return sqrt(pow(x1-x2,2)+pow(y1-y2,2));
}
int main()
{
    scanf("%d",&n);
    init();
    for(int i=1;i<=n;i++)
        scanf("%d%d",&x[i],&y[i]);
    for(int i=1;i<=n-1;i++)
    {
        for(int j=i+1;j<=n;j++)
            ma[i][j]=ma[j][i]=distance(x[i],y[i],x[j],y[j]);
    }
    dijkstra(1);
    printf("%.3f\n",dis[2]);
    return 0;
}

心态不炸

Problem Description

自从开学之后就开始忙碌了起来，总以为下个月就可以闲下来，但是总发现下个月会更下忙碌。CGY是一个心理承受能力良好的人，从来心态不炸，他擅长把压力把转化为前进的动力。他受到1，2，3，4，5点压力时，分别会获得2，3，5，6，8点动力。当受到6点以上（包含6点）的压力时，CGY获得的动力就会发生质变，其值为它之前五种情况的值之和。例如，受到6，7点压力时，分别可以获得24,46点动力。现在请你编程求出他受到n-1，由于结果可能会很大，所以结果需要对1000000007求模。

Input

输入包含多行，每行包括一个整数n( $2 \leq n \leq 10^{15}$ )，表示CGY受到的压力数。当输入为”0”时，结束输入（”0”不用处理）。

Output

对于每行输入，对应输出一行CGY受到n-1点和n点压力时能获得的动力数，结果需要对1000000007求模，中间以空格隔开。

Sample Input

3
6
7
0

Sample Output

3 5
8 24
24 46

Hint

思路：

SLF：本次数据的多行输入格式出错了，所有题目都已重判(不过没用到矩阵快速幂的同学错的还是错)，出题人包菜已经被我们祭天了，请放心食用~
LWH(出题人)：
题意很明显，就是要求以下递推式的值。
$f(n)=\begin{cases} 2,n=1 \\ 3,n=2 \\ 5,n=3 \\ 6,n=4 \\ 8,n=5 \\ f(n-1)+f(n-2)+f(n-3)+f(n-4)+f(n-5),n\leq6 \end{cases}$
如你们所见这道题的数据最大去到 $2^{15}$ ，无论是利用递归还是转换成循环，O(n)时间复杂度的算法都会时间超限。正解是矩阵快速募，式子如下：
$\begin{pmatrix} f(n) \\ f(n-1) \\ f(n-2) \\ f(n-3) \\ f(n-4) \end{pmatrix} =\begin{pmatrix} 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{pmatrix}^{n-5}* \begin{pmatrix} f(5) \\ f(4) \\ f(3) \\ f(2) \\ f(1) \end{pmatrix}$
//听说校赛也出过这个知识点哦，坑补了吗？
//能用上学过的线性代数知识了，是不是很开心？

代码：

#include <iostream> 
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long ll;

const int mod=1e9+7;
ll n,ans1=0,ans2=0,f[]={0,8,6,5,3,2};
struct Matrix{
    ll m[6][6];
    Matrix(){
        memset(m,0,sizeof(m));
    }
    //Operator overloading
    Matrix operator * (const Matrix &a){
        Matrix res;
        for(int i=1;i<=5;i++)
            for(int j=1;j<=5;j++)
                for(int k=1;k<=5;k++)
                    res.m[i][k]=(res.m[i][k]+(m[i][j]*a.m[j][k])%mod)%mod;
        return res;
    }
}T,E; //E stand for unit matrix

void init(){
    memset(T.m,0,sizeof(T.m));
    for(int i=1;i<=5;i++){
        E.m[i][i]=1;
        T.m[1][i]=1;
        T.m[i][i-1]=1;
    }
    ans1=0;
    ans2=0; 
}

Matrix matrix_pow(ll n){
    Matrix base=T,res=E;
    while(n){
        if(n&1)res=res*base;
        base=base*base;
        n>>=1;
    }
    return res;
}


int main()
{
    while(scanf("%d",&n)&&(n!=0)){
        if(n<=5){
            cout<<f[5-n+2]<<" "<<f[5-n+1]<<endl;
        }else{
            init();
            T=matrix_pow(n-5);
            for(int i=1;i<=5;i++){
                ans1=(ans1+T.m[1][i]*f[i])%mod;
                ans2=(ans2+T.m[2][i]*f[i])%mod;
            }   
            cout<<ans2<<" "<<ans1<<endl;
        }
    }
    return 0;
}

CGY树

Problem Description

CGY要暂时离开301了，301种有一颗小树苗，SLF和LXY觉得应该为CGY留个纪念，于是就把这颗树叫做CGY树。
CGY树有N个结点，结点编号依次为1到N，每条边都有一个权值L。其中CGY树会有一个1到N的排列。
CGY给这颗树定义了一个的幸运值。幸运值计算规则如下：CGY树的排列中，每个数字代表相应的结点。幸运值就等于排列中所有相邻的两个结点最短距离之和。例如N=4且一个排列为4231，则幸运值为dis(4,2)+dis(2,3)+dis(3,1)。
现在，CGY想知道CGY树所有可能的幸运值之和是多少？

Input

输入有多组数据。（数据保证最多只有10组数据）
每组数据的第一行为一个整数N(1<=N<=1e5)，代表CGY树的结点数。
接下来N-1行，描述CGY树的边。
N-1行中每行有三个整数X，Y，L，以空格隔开，代表结点X到结点Y有一条边，边的长度为L。数据保证1<=X<=N，1<=Y<=N，1<=L<=1e9

Output

输出一个整数，代表CGY树所有可能的幸运值之和

Sample Input

3
1 2 1
2 3 1
3
1 2 1
1 3 2

Sample Output

16
24

Hint

对于样例中的第一组数据：
123排列的幸运值为：1+1 = 2
132排列的幸运值为：2+1 = 3
213排列的幸运值为：1+2 = 3
231排列的幸运值为：1+2 = 3
312排列的幸运值为：2+1 = 3
321排列的幸运值为：1+1 = 2
所以CGY树所有可能的幸运值之和为2+3+3+3+3+2=16

思路：

对于每一条边，可以看做当前边把一颗树上的结点分隔成两部分，其中两部分的结点个数分别为a，b。假设结点u，v分别为两部分中的点。对于每一组u，v，全排列中有(N-1)*2种可能，其余的点有(N-2)!种可能，于是一条边对于幸运值之和的贡献次数为：a*b*(N-1)*2*(N-2)!次，即a*b*2*(N-1)!次。
所以用dfs求出每条边左右两部分个数a，b，然后得出当前边的贡献为a*b*2*(N-1)!*length,最后求和每条边的贡献值即可。
//为什么没人提交我这道题，下次就把这题放第一题o(╥﹏╥)o

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int MAXN = 1e5+10;
const long long MOD = 1e9+7;

long long res;
long long ans[MAXN];
int n;

struct Node{
    vector<int> child;
    vector<int> len;
}a[MAXN];

void dfs(int u){
    if(a[u].child.empty()){
        ans[u] = 1;
        return;
    }
    long long t = 0;
    for(int i = 0;i<a[u].child.size();i++){
        int to = a[u].child[i];
        dfs(to);
        t+=ans[to];
    }
    ans[u] = t+1;
    return;
}

int main(){
    while(scanf("%d",&n) != EOF){
        for(int i = 0;i<=n;i++){
            a[i].child.clear();
            a[i].len.clear();
        }
        memset(ans,0,sizeof(ans));
        for(int i = 0;i<n-1;i++){
            int x,y,l;
            scanf("%d%d%d",&x,&y,&l);
            a[x].child.push_back(y);
            a[x].len.push_back(l);
        }
        dfs(1);
        res = 0;
        long long t = 1;
        for(int i = 1;i<=n-1;i++)
            t=t*i%MOD;
        for(int i = 1;i<=n;i++){
            for(int j = 0;j<a[i].child.size();j++){
                int to = a[i].child[j];
                int len = a[i].len[j];
                res+=((ans[to]*((long long)n-ans[to])%MOD)*len%MOD*2%MOD)*t%MOD;
                res%=MOD;
            }
        }
        printf("%lld\n",res);
    }
    return 0;
}

总结

//咳咳
其实这次比赛的签到题应该是B题翻转棋子，因为直接暴力枚举即可，但不懂为什么这么多人在没推出公式的情况下要去莽A题，可能这就是人均猛男吧。
本次比赛的题目难度比之前举办的比赛都要大，主要是板子题和搜索，两题金的情况和我们出题人预想的一样，希望软院的同学们继续加油吧，多训练继续开拓自己的视野，做多了题总归是有好处的~
//道理我都懂，但为什么SLF的两题都没人A o(╥﹏╥)o

SCNUOJ 2019 欢送(迫害)CGY杯 题解

火车出站

Problem Description

Input

Output

Sample Input

Sample Output

Hint

思路：

代码：

棋子翻转

Problem Description

Input

Output

Sample Input

Sample Output

Hint

思路：

代码(方法一)：

CGY出差

Problem Description

Input

Output

Sample Input

Sample Output

Hint

思路：

代码：

Jump

Problem Description

Input

Output

Sample Input

Sample Output

Hint

思路：

代码：

心态不炸

Problem Description

Input

Output

Sample Input

Sample Output

Hint

思路：

代码：

CGY树

Problem Description

Input

Output

Sample Input

Sample Output

Hint

思路：

代码：

总结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

SCNUOJ 2019 欢送(迫害)CGY杯题解