“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛

B，伤害计算

题意

给出一个字符串，字符串里有单个的整数和ndm用+相连，ndm表示扔n个m面的色子，求ndm的期望，然后求出这个字符串的总和。

解析

看到很多多大佬的做法都是先读入一整个字符串，然后对字符串进行处理，我是逐步读入每一个字符，然后当出现d或者+的时候进行标记，然后分别处理，ndm的期望比较简单，就是(1+m)/2*n即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
    char a;
    int flag=0;
    a=getchar();
    double sum=0;
    while(a!='\n'){   //逐步读入每一个字符串
        ll b=0,c=0,flag=0;
        while(a!='d'&&a!='+'&&a!='\n'){    
            b=b*10+a-'0';
            a=getchar();
        }                      //出现d进行标记和处理
        if(a=='d'){
            flag=1;
            a=getchar();
            while(a!='d'&&a!='+'&&a!='\n'){
                c=c*10+a-'0';
                a=getchar();
            }
        }
        if(flag){            //有标记的
            sum+=b*(c+1)/2.0;
        }
        else{                   //无标记的
            sum+=b;
        }
        if(a=='\n') break;            //最后退出
        a=getchar();
    }
    ll sum1=sum;
    if(sum-sum1>0.3) cout<<fixed<<setprecision(1)<<sum<<endl;
    else cout<<sum1<<endl;
    return 0;
}

关于精度

我一开始为了方便直接在输出那里用的printf("%g\n",sum);但是wa了，为什么我也不知道，期望里只是除以二的话也不会出现第二位小数，所以也不会出现不符合题意的地方，如果有大佬看到了这里知道为什么请务必告诉我。

F，排列计算

题意

有长度为n的序列a，m次询问每次询问一个区间和问结果最大是多少

解析

想要结果最大，必定是最大的数取最多次，采用前缀和

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
const int mod = 1e9+7;
const int maxn = 8000*8000+5;
ll num[200005];
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int main(void){
    int n=read(),m=read();
    while(m--){
        int l=read(),r=read();
        num[l]++;
        num[r+1]--;
    }
    for(int i = 0 ; i <= n ; ++i ) num[i]+=num[i-1];
    sort(num+1,num+1+n);
    ll ans = 0;
    for(int i = 1 ; i <= n ;++i){
        ans += (i*num[i]);
    }
    printf("%lld\n",ans);
    return 0;
}

这个题目我也想bb一句

不用快读会超时。。。我看到别人的代码也没用快读哇。。。

A，张老师和菜哭式的游戏

题意

一共有n个数，张老师和菜哭式首先将a，b两个数放到集合里，张老师先手，两个人轮流选一个数，这个数必须是集合里的两个数的和或者差，取不到数的人输，问张老师是否能赢

解析

拓展欧几里得这道题给出了a，b，直接求解gcd即可，用n除掉gcd就是可以拿走的数。在对这个数判断奇偶即可

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

int main() {
    int T = read();
    while (T--) {
        int n = read(), a = read(), b = read();
        int tmp = __gcd(a, b);
        if (tmp != 1) n /= tmp;
        if (n & 1)    puts("Yes");
        else    puts("No");
    }
    return 0;
}

写到后面

附上一个大佬的代码

图片说明

以后的比赛能不能ak就靠这个了

D,车辆调度

题意

有一张w∗h的图，有一个或多辆车，每辆车可以向上下左右任意一个方向行驶边界或者撞到另外一辆车或障碍物可以向上下左右任意一个方向行驶边界或者撞到另外一辆车或障碍物（也就是说不能自动停，一定要有什么挡住）每个操作一分钟图中存在一个或多个目标，问你是否可能在k分钟的时候，有任一一辆车到任一一个目标点。

解析

暴力！！！

图片说明

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
const int mod = 1e9 + 7;
const int maxn = 8000 * 8000 + 5;
inline ll read() {
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int w, h, kk;
char Map[15][15];
bool dfs(int x) {
    if (x > kk) return false;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (Map[i][j] == 'R') {
                Map[i][j] = '.';
                int k;
                if (i > 0 && Map[i - 1][j] == '.' || Map[i - 1][j] == 'D') {
                    for (int k = i - 1; k >= 0; k--)
                        if (k == 0 || Map[k - 1][j] == 'R' || Map[k - 1][j] == 'X') {
                            if (Map[k][j] == 'D') return true;
                            Map[k][j] = 'R';
                            if (dfs(x + 1)) return true;
                            Map[k][j] = '.';
                            break;
                        }
                }
                if (i + 1 < h && Map[i + 1][j] == '.' || Map[i + 1][j] == 'D') {
                    for (int k = i + 1; k < h; ++k) {
                        if (k == h - 1 || Map[k + 1][j] == 'R' || Map[k + 1][j] == 'X') {
                            if (Map[k][j] == 'D') return true;
                            Map[k][j] = 'R';
                            if (dfs(x + 1)) return true;
                            Map[k][j] = '.';
                            break;
                        }
                    }
                }
                if (j + 1 < w && Map[i][j + 1] == '.' || Map[i][j + 1] == 'D') {
                    for (int k = j + 1; k < w; ++k) {
                        if (k == w - 1 || Map[i][k + 1] == 'R' || Map[i][k + 1] == 'X') {
                            if (Map[i][k] == 'D') return true;
                            Map[i][k] = 'R';
                            if (dfs(x + 1)) return true;
                            Map[i][k] = '.';
                            break;
                        }
                    }
                }
                if (j > 0 && Map[i][j - 1] == '.' || Map[i][j - 1] == 'D') {
                    for (int k = j - 1; k >= 0; k--)
                        if (k == 0 || Map[i][k - 1] == 'R' || Map[i][k - 1] == 'X') {
                            if (Map[i][k] == 'D') return true;
                            Map[i][k] = 'R';
                            if (dfs(x + 1)) return true;
                            Map[i][k] = '.';
                            break;
                        }
                }
                Map[i][j] = 'R';
            }
        }
    }
    return false;
}
int main() {
    w = read(), h = read(), kk = read();
    for (int i = 0; i < h; ++i)
        scanf("%s", Map[i]);
    if (dfs(1)) puts("YES");
    else puts("NO");
}