2019 年 “游族杯” 上海市高校程序设计邀请赛 (同步赛)暨ECNU校赛线上赛

Click to teleport

A - As Much As 996

题目大意
给定一个数字字符串，表示早上开始上班时间，下午（晚上？）下班时间，一周工作几天，比如 $996$ 就是早上 $9$ 点到晚上 $9$ 点，一周工作 $6$ 天。

分析
没啥分析的，签到题

#include <cstdio>
#include <iostream>
using namespace std;

int main(){
    int n,s,t,d,ans=0;
    scanf("%d",&n);
    d=n%10; n/=10;
    if(n%100==10 || n%100==11) {t=n%100;n/=100;}
    else {t=n%10;n/=10;}
    s=n;
    ans= (12-s+t)*d;
    printf("%d",ans);
}

B-Black Peter

题目大意
一副特制的扑克牌，有 $2$ 种花色，每种花色有 $n$ 张牌，点数为 $1,2,...,n$ ，其中有一张牌被抽走，也即有 $n-1$ 对点数相同的牌， $1$ 张点数独特的牌(称之为乌龟牌)，共 $2n-1$ 张牌。两人轮流行动，每次随机从对方手牌中抽出一张牌放入己方牌堆，并立即丢弃掉所有已经组成一对的手牌。如果某一方无手牌则此方获胜。求给定初始手牌情况下的获胜概率。

题目分析
开局二人肯定先把所有已经组成对子的牌扔掉，手上剩下的牌全是单独一张，并且乌龟在某个人手上。因此，二者的手牌数必定相差 $1$ 而且多的那张牌就是乌龟牌。我们用 $f(i,j,k)$ 表示处于 $(i,j,k)$ 状态下的获胜概率。 $i$ 表示除去乌龟牌还剩下多少对牌。 $j=0$ 表示乌龟牌在对方手上, $j=1$ 表示乌龟牌在自己手上， $k=0$ 表示己方回合， $k=1$ 表示对方回合。

明显的有：
己方抽牌，乌龟在对方手上， $\frac{1}{i+1}$ 概率抽乌龟, $\frac{1}{i+1}$ 概率消去一对.
$f(i,0,0)=\frac{f(i,1,1)+if(i-1,0,1)}{i+1}$

己方抽牌，乌龟在自己手上，抽对面的牌必然消去一对自己的手牌。
$f(i,1,0)=f(i-1,1,1)$

对面抽牌，乌龟在对方手上，抽自己的牌必然消去一对对方的手牌。
$f(i,0,1)=f(i-1,0,0)$

对面抽牌，乌龟在自己手上， $\frac{1}{i+1}$ 概率抽乌龟， $\frac{1}{i+1}$ 概率消去一对
$f(i,1,1)=\frac{f(i,0,0)+if(i-1,1,0)}{i+1}$

将 $f(i,1,1)$ 与 $f(i,0,0)$ 联立解方程即可得到：
$f(i,1,1)=\frac{f(i-1,0,1)+(i+1)f(i-1,1,0)}{i+2}$

$f(i,0,0)=\frac{f(i-1,1,0)+(i+1)f(i-1,0,1)}{i+2}$

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
char s1[1001000],s2[1001000];
double f[1001000][2][2];
int main(){
    f[0][1][1]=f[0][1][0]=0;
    f[0][0][1]=f[0][0][0]=1.0;
    for(int i=1;i<=1000000;i++){
        f[i][1][0]=f[i-1][1][1];
        f[i][0][1]=f[i-1][0][0];
        f[i][1][1]=f[i-1][0][1]/(double)(i+2) + (double)(i+1)/(i+2) * f[i-1][1][0];
        f[i][0][0]=f[i-1][1][0]/(double)(i+2) + (double)(i+1)/(i+2) * f[i-1][0][1]; 
    }
    int _;scanf("%d",&_);
    while(_--){
        int l,n=0;scanf("%d",&l);
        scanf("%s%s",s1+1,s2+1);
        int in;
        for(int i=1;i<=l;i++){
            if(s1[i]=='1' && s2[i]=='1') n++;
            if(s1[i]=='1' && s2[i]=='0') in=1;
            if(s1[i]=='0' && s2[i]=='1') in=0;
        }
        printf("%.12lf\n",f[n][in][0]);
        
    }
}

E - ECNU MNIST

题目大意
按照已经给出的神经网络数据，构建一个文字识别的神经网络，要求给定 $n$ 幅二值化后的 $28×28$ 像素的图片，识别出是字符 $E,C,N,U$ 的哪一个。例如，输入：

0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000111100000001111111000
0000001111111111111111111000
0000000111111111111111000000
0000001111111111110000000000
0000001111000000000000000000
0000001111000000000010000000
0000001110000000001110000000
0000001100000000011110000000
0000111100000001111110000000
0000111100111111111000000000
0000111111111111000000000000
0000111111111111000000000000
0001111110000000000000000000
0000111000000000000000000000
0001111000000000111000000000
0001111010000000111000000000
0001111111111111110000000000
0001111111111111100000000000
0000111111111110000000000000
0000111111110000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000

应该识别出来是字符 $E$ .
题目分析
就是把原题目看懂，弄明白每个操作，写就完事了。输入第一行数字不用管，接下来的输入分别是：卷积层 $1$ 的权重和偏移量，卷积层 $2$ 的权重和偏移量。全连接层 $1$ 的权重和偏移量，全连接层 $2$ 的权重和偏移量。

卷积层 $1$ 的权重矩阵是 $4$ 个 $5×5$ 的矩阵。假设我们输入的图片信息保存在数组 $in[i][j]$ 中，那么 $in$ 是一个 $28×28$ 的矩阵。对于 $in$ 矩阵中每一个 $5×5$ 的子矩阵，将其按顺序与卷积层 $1$ 的权重矩阵相“乘”，注意这里的乘不是矩阵相乘，而是对应位置上的元素相乘之和，作为一个值。也就是说，把 $in$ 矩阵的每一个 $5×5$ 的子矩阵都算出来一个特征值，特征值加上对应的偏移量，生成一个 $24×24$ 的新矩阵。接下来的每一个操作都与这个类似。

下面的每一行的 $out$ 都将成为下一行的 $in$
$卷积层1：in(28×28) -> 4×out(24×24)$

$最大池化：4×in(24×24) ->4×out(12×12）$

最大池化指的是将 $(24×24)$ 的矩阵划分成 $(12×12)$ 块，每一块对应原来的 $（2×2）$ 子矩阵，取子矩阵中的最大值作为新矩阵对应位置的值。
$ReLU（激励函数）：4×in(12×12）-> 4×out(12×12)$

$ReLU激励函数$ 是指讲矩阵中每个元素与 $0$ 比较取 $max$ .
$卷积层2:4×in(12×12) -> 9×out(10×10）$

卷积层2里每一个 $（12×12）$ 都会转化成一个 $(10×10)$ ,卷积层2的权重矩阵有 $9×4$ 个，每4个转化后的 $(10×10)$ 求和作为一个 $out(10×10)$

$最大池化：9×in（10×10）-> 9×out（5×5）$

$ReLU（激励函数）：9×in(5×5）-> 9×out(5×5)$

$展平:9×in（5×5）-> out(1×225)$

也即 $out(25i+5j+k)=in(i,j,k),默认从0,0,0开始$
$降维：in(1×225)->out(1× 64)$

$ReLU（激励函数）：in(1×64）-> out(1×64)$

$降维：in(1×64）-> out(1×4)$

看 $out$ 里面哪一个元素最大，假设最大的元素为 $out(i)，i=0,1,2,3$ 分别对应 $C,E,N,U$ 。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

int MagicNumber,T;
double Conv_1_w[4][5][5];
double Conv_1_b[4];
double Conv_2_w[9][4][3][3];
double Conv_2_b[9];
double FC_1_w[64][225];
double FC_1_b[64];
double FC_2_w[4][64];
double FC_2_b[4];

char inputLine[30];
double in[30][30];

double max(double L,double R){
    return L>R?L:R;
}

void init(){
    scanf("%d",&MagicNumber);
    for(int i=0;i<4;i++)
        for(int j=0;j<5;j++)
            for(int k=0;k<5;k++)
                scanf("%lf",&Conv_1_w[i][j][k]);

    for(int i=0;i<4;i++)
        scanf("%lf",&Conv_1_b[i]);

    for(int i=0;i<9;i++)
        for(int j=0;j<4;j++)
            for(int k=0;k<3;k++)
                for(int l=0;l<3;l++)
                    scanf("%lf",&Conv_2_w[i][j][k][l]);

    for(int i=0;i<9;i++)
        scanf("%lf",&Conv_2_b[i]);

    for(int i=0;i<64;i++)
        for(int j=0;j<225;j++)
            scanf("%lf",&FC_1_w[i][j]);

    for(int i=0;i<64;i++)
        scanf("%lf",&FC_1_b[i]);

    for(int i=0;i<4;i++)
        for(int j=0;j<64;j++)
            scanf("%lf",&FC_2_w[i][j]);

    for(int i=0;i<4;i++)
        scanf("%lf",&FC_2_b[i]);
    //cout<<FC_2_b[3]<<endl;
    scanf("%d",&T);//cout<<T<<endl;


}

void inC(){
    for(int i=0;i<28;i++){
        scanf("%s",inputLine);
        for(int j=0;j<28;j++)
            in[i][j]=double(inputLine[j]-'0');
    }
}

double Out_Conv1[4][24][24];
double Out_max_Conv1[4][12][12];
double Out_Conv2[9][10][10];
double Out_Flat[225];
double Out_FC[64];
double Out[4];

int main(){
    init();
    while(T--){
        inC();
        for(int i=0;i<4;i++)
            for(int j=0;j<24;j++)
                for(int k=0;k<24;k++){
                    Out_Conv1[i][j][k]=Conv_1_b[i];
                    for(int dj=0;dj<5;dj++)
                        for(int dk=0;dk<5;dk++)
                            Out_Conv1[i][j][k]+=Conv_1_w[i][dj][dk]*in[j+dj][k+dk];
                }

        for(int i=0;i<4;i++)
            for(int j=0;j<12;j++)
                for(int k=0;k<12;k++)
                    Out_max_Conv1[i][j][k]=max(0.0,max(
                            max(Out_Conv1[i][j*2][k*2],Out_Conv1[i][j*2+1][k*2+1]),
                            max(Out_Conv1[i][j*2+1][k*2],Out_Conv1[i][j*2][k*2+1])));


        for(int i=0;i<9;i++)
            for(int j=0;j<10;j++)
                for(int k=0;k<10;k++){
                    Out_Conv2[i][j][k]=Conv_2_b[i];
                    for(int p=0;p<4;p++)
                        for(int dj=0;dj<3;dj++)
                            for(int dk=0;dk<3;dk++)
                                Out_Conv2[i][j][k]+=Out_max_Conv1[p][j+dj][k+dk]*Conv_2_w[i][p][dj][dk];
                }

        for(int i=0;i<9;i++)
            for(int j=0;j<5;j++)
                for(int k=0;k<5;k++)
                    Out_Flat[i*25+j*5+k]=max(0.0,max(
                            max(Out_Conv2[i][j*2][k*2],Out_Conv2[i][j*2+1][k*2+1]),
                            max(Out_Conv2[i][j*2+1][k*2],Out_Conv2[i][j*2][k*2+1])));

        for(int i=0;i<64;i++){
            Out_FC[i]=FC_1_b[i];
            for(int j=0;j<225;j++)
                Out_FC[i]+=FC_1_w[i][j]*Out_Flat[j];
            Out_FC[i]=max(0,Out_FC[i]);
        }

        for(int i=0;i<4;i++){
            Out[i]=FC_2_b[i];
            for(int j=0;j<64;j++)
                Out[i]+=FC_2_w[i][j]*Out_FC[j];
            Out[i]=max(0,Out[i]);
        }

        double mini=-999.9;int ans=-1;
        for(int i=0;i<4;i++)
            if(Out[i]>mini){
                mini=Out[i];
                ans=i;
            }
        if(ans==0) printf("C\n");
        if(ans==1) printf("E\n");
        if(ans==2) printf("N\n");
        if(ans==3) printf("U\n");
    }
    return 0;
}

F - Foreigners’s Trouble

题目大意
外国姓名的缩写是每个单词的首字符大写。现在给出n个外国名，求有多少对外国人的姓名缩写相同。
题目分析
先提取出缩写，然后排序，缩写相同的一定排在一起。顺序扫一遍，扫到有 $k$ 个相同的缩写答案就加上 $C_{k}^{2}$ .

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef unsigned long long LL;
#define maxn 500010

const LL base=31;
int cnt;LL a[maxn];char s[maxn*22];
int main()
{
    int n,i,j;LL ans,num;
    cnt=0;
    scanf("%d\n",&n);
    for (i=1;i<=n;i++)
    {
        scanf("%[^\n]%*c", s);
        LL sum=0;
        int len=strlen(s);
        for (j=0;j<len;j++)
         if (s[j]>='A' && s[j]<='Z') 
          sum=sum*base+(s[j]-'A'+1);
        a[++cnt]=sum;
    }
    sort(a+1,a+1+cnt);
    ans=0;num=1;
    for (i=2;i<=cnt;i++)
     if (a[i]==a[i-1]) num++;
     else
     {
        ans+=num*(num-1)/2;
        num=1;
     }
    ans+=num*(num-1)/2;
    printf("%llu\n",ans);
    return 0;
}

H - Huashui Clock

题目大意
一天有h小时，每小时m分钟，因此时钟的显示是从 $00:00$ 到 $h-1:m-1$ .如果某个时刻时钟的显示分钟数大于等于显示的时钟数，则可以划水。问一天的划水时长占总多少比例，输出最简分数。
题目分析
没啥分析的，暴力算就行。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
long long gcd(long long x,long long y){
    if(x%y==0) return y;
    else return gcd(y,x%y);
}
int main(){
    long long n,m;cin>>n>>m;
    long long a,b;
    if(n>=m){
        a=m+1;b=2*n;
    }
    else{
        a=2*m-n+1;
        b=2*m;
    }
    long long div=gcd(a,b);
    a/=div;b/=div;
    cout<<a<<"/"<<b;
}

L - Liwa River

题目大意
ACM 来了许多队伍参加，队伍的人数最少 $1$ 人最多 $6$ 人。要为这些队伍安排长凳。每一个长凳都可以坐至多 $6$ 个人。来自同一个队伍的人不能坐在不同的长凳上。现在给出人数为 $1,2,...,6$ 的队伍各自有多少队，求最少长凳需求数。
题目分析
贪心，优先安排队伍人数多的队伍。 $6$ 人队不必多说， $5$ 人队尽量多插一些 $1$ 人队， $4$ 人队安排后优先让 $2$ 人队拼凳，其次在考虑 $1$ 人队。 $3$ 人按顺序优先级依次考虑 $3+3,3+2+1,3+1+1+1$ ,

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int main(){
    int _;scanf("%d",&_);
    while(_--){
        int f[7];
        for(int i=1;i<=6;i++)
            scanf("%d",&f[i]);
        int p;
        int ans=0;
        ans+=f[6];  //  cout<<"+"<<ans<<endl;
        ans+=f[5];  //  cout<<"+"<<ans<<endl;
        
            f[1]-=f[5];f[1]=max(f[1],0);
        ans+=f[4];      //cout<<"+"<<ans<<endl;
        
            p=min(f[4],f[2]);
            f[2]-=p;f[4]-=p;
            p=min(2*f[4],f[1]);
            f[1]-=p;
        
        ans+=(f[3]/2+(f[3]%2!=0));//cout<<"+"<<ans<<endl;
        
            f[3]%=2;
            if(f[3]==1){
                if(f[2]>0) {
                    f[2]--;f[1]--;
                    f[1]=max(f[1],0);
                }
                else{
                    f[1]-=3;
                    f[1]=max(f[1],0);
                }
            }
        ans+=(f[2]/3+(f[2]%3!=0));// cout<<"+"<<ans<<endl;
        
            p=f[2]%3;
            if(p==2) f[1]-=2;
            if(p==1) f[1]-=4;
            f[1]=max(f[1],0);
        ans+=f[1]/6+(f[1]%6!=0);//cout<<"+"<<ans<<endl;
        
        printf("%d\n",ans);
    }
}

最后编辑于：2019.04.28 15:47:52

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 215,294评论 6赞 497
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,780评论 3赞 391
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 161,001评论 0赞 351
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,593评论 1赞 289
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,687评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,679评论 1赞 294
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,667评论 3赞 415
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,426评论 0赞 270
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,872评论 1赞 307
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,180评论 2赞 331
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,346评论 1赞 345
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,019评论 5赞 340
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,658评论 3赞 323
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,268评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,495评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,275评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,207评论 2赞 352