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

题目链接

按难度顺序

F. 排列计算

题意：



题解：



AC代码

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

ll a[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        a[l]++,a[r+1]--;
    }
    for(int i=1;i<=n;i++)a[i]+=a[i-1];
    sort(a+1,a+1+n);
    ll ans=0;
    for(ll i=1;i<=n;i++){
        ans+=i*a[i];
    }
    cout<<ans;
    return 0;
}

B. 伤害计算

题意：




题解：












AC代码

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};


int main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
   string s;
    cin>>s;
    double ans=0;
    int i=0;
    while(i<s.length()){
        double a=0,b=0;
        while(isdigit(s[i])&&i<s.length())a=a*10+s[i]-'0',i++;
        if(i==s.length()){ans+=a;break;}
        if(s[i]!='d'){ans+=a;i++;continue;}
        i++;
        while(isdigit(s[i])&&i<s.length())b=b*10+s[i]-'0',i++;
        i++;
        ans+=a*(b+1)/2;
    }
    ll res=ans;
    if(res==ans)cout<<res;
    else printf("%.1lf",ans);
    return 0;
}

A.张老师和菜哭武的游戏

题意：




题解：






AC代码

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

ll a[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    while(t--){
        int n,a,b;
        cin>>n>>a>>b;
        if((n/__gcd(a,b))&1)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

D.车辆调度

题意：






题解：











AC代码

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

int n,m,k;
char g[20][20];
set<pii> e;
vector<pii> s;
bool ok(int x,int y){
    if(x>=1&&x<=n&&y>=1&&y<=m&&g[x][y]=='.')return 1;
    return 0;
}
void dfs(int cur){
    if(cur==k)return;
    for(auto &i:s)
        for(int p=0;p<4;p++){
            int cx=i.fi,cy=i.se;
            int x=i.fi,y=i.se;
            int dx=x+dir[p][0];
            int dy=y+dir[p][1];
            while(ok(dx,dy))x=dx,y=dy,dx+=dir[p][0],dy+=dir[p][1];
            if(e.count(mp(x,y))){cout<<"YES";exit(0);}
            swap(g[cx][cy],g[x][y]);
            i.fi=x,i.se=y;
            dfs(cur+1);
            i.fi=cx,i.se=cy;
            swap(g[cx][cy],g[x][y]);
        }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>m>>n>>k;
    for(int i=1;i<=n;i++)cin>>g[i]+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(g[i][j]=='R')s.pb(mp(i,j));
            if(g[i][j]=='D')e.insert(mp(i,j)),g[i][j]='.';
        }
    dfs(0);
    cout<<"NO"<<endl;
    return 0;
}

E.弦

题意：

题解：










AC代码

在这里插入代码片`/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

ll Pow(ll a, ll b){
    ll ans = 1;
    while(b > 0){
        if(b & 1){
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
//逆元
ll inv(ll b){
    return Pow(b,mod-2);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ll n;
    cin>>n;
    ll a=Pow(2,n),b=1;
    for(ll i=1;i<=n+1;i++)b=b*i%mod;
    ll ans=a*inv(b)%mod;
    cout<<ans;
    return 0;
}
`

C. 张老师的旅行

题意：






题解：


















AC代码

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

int dp[1010][1010][2],a[1010],t[1010];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int pos;
    for(int i=1;i<=n;i++){
        cin>>t[i];
        if(t[i]==0)pos=i;
    }
    memset(dp,inf,sizeof dp);
    dp[pos][pos][0]=dp[pos][pos][1]=0;
    for(int len=1;len<=n;len++)
        for(int l=max(1,pos-len+1),r;l<=pos&&l+len-1<=n;l++){
            r=l+len-1;
            if(dp[l+1][r][0]+a[l+1]-a[l]<=t[l])
                dp[l][r][0]=min(dp[l][r][0],dp[l+1][r][0]+a[l+1]-a[l]);
            if(dp[l+1][r][1]+a[r]-a[l]<=t[l])
                dp[l][r][0]=min(dp[l][r][0],dp[l+1][r][1]+a[r]-a[l]);
            if(dp[l][r-1][1]+a[r]-a[r-1]<=t[r])
                dp[l][r][1]=min(dp[l][r][1],dp[l][r-1][1]+a[r]-a[r-1]);
            if(dp[l][r-1][0]+a[r]-a[l]<=t[r])
                dp[l][r][1]=min(dp[l][r][1],dp[l][r-1][0]+a[r]-a[l]);
        }
    int ans=min(dp[1][n][0],dp[1][n][1]);
    if(ans==inf)cout<<-1;
    else cout<<ans;
    return 0;
}

J.斐波那契和

题意：


题解：






模版来自:https://www.cnblogs.com/zzqsblog/p/6877339.html 

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};


const int MOD=998244353;
const int SZ=maxn;
ll qp(ll a,ll b)
{
    ll x=1; a%=MOD;
    while(b)
    {
        if(b&1) x=x*a%MOD;
        a=a*a%MOD; b>>=1;
    }
    return x;
}
namespace linear_seq {
inline vector<ll> BM(vector<ll> x)
{
    vector<ll> ls,cur;
    int pn=0,lf,ld;
    for(int i=0;i<int(x.size());++i)
    {
        ll t=-x[i]%MOD;
        for(int j=0;j<int(cur.size());++j)
            t=(t+x[i-j-1]*(ll)cur[j])%MOD;
        if(!t) continue;
        if(!cur.size())
        {cur.resize(i+1); lf=i; ld=t; continue;}
        ll k=-t*qp(ld,MOD-2)%MOD;
        vector<ll> c(i-lf-1); c.pb(-k);
        for(int j=0;j<int(ls.size());++j) c.pb(ls[j]*k%MOD);
        if(c.size()<cur.size()) c.resize(cur.size());
        for(int j=0;j<int(cur.size());++j)
            c[j]=(c[j]+cur[j])%MOD;
        if(i-lf+(int)ls.size()>=(int)cur.size())
            ls=cur,lf=i,ld=t;
        cur=c;
    }
    vector<ll>&o=cur;
    for(int i=0;i<int(o.size());++i)
        o[i]=(o[i]%MOD+MOD)%MOD;
    return o;
}
int N; ll a[SZ],h[SZ],t_[SZ],s[SZ],t[SZ];
inline void mull(ll*p,ll*q)
{
    for(int i=0;i<N+N;++i) t_[i]=0;
    for(int i=0;i<N;++i) if(p[i])
        for(int j=0;j<N;++j)
            t_[i+j]=(t_[i+j]+p[i]*q[j])%MOD;
    for(int i=N+N-1;i>=N;--i) if(t_[i])
        for(int j=N-1;~j;--j)
            t_[i-j-1]=(t_[i-j-1]+t_[i]*h[j])%MOD;
    for(int i=0;i<N;++i) p[i]=t_[i];
}
inline ll calc(ll K)
{
    for(int i=N;~i;--i) s[i]=t[i]=0;
    s[0]=1; if(N!=1) t[1]=1; else t[0]=h[0];
    for(;K;mull(t,t),K>>=1) if(K&1) mull(s,t); ll su=0;
    for(int i=0;i<N;++i) su=(su+s[i]*a[i])%MOD;
    return (su%MOD+MOD)%MOD;
}
inline int gao(vector<ll> x,ll n)
{
    if(n<int(x.size())) return x[n];
    vector<ll> v=BM(x); N=v.size(); if(!N) return 0;
    for(int i=0;i<N;++i) h[i]=v[i],a[i]=x[i];
    return calc(n);
}
}
ll fff[3000]={1,1,1};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ll n,k;
    cin>>n>>k;
    vector<ll> qqq;
    qqq.pb(0);
    for(int i=3;i<2000;i++)
        fff[i]=(fff[i-1]+fff[i-2])%MOD;
    for(int i=1;i<=1000;i++){
        ll sss=0;
        for(int j=1;j<=i;j++)
            sss=(sss+qp(j,k)*fff[j])%MOD;
        qqq.pb(sss);
    }
    cout<<linear_seq::gao(qqq,n);
    return 0;
}
全部评论

相关推荐

11-24 13:35
云南大学 Web前端
避雷拼多多
网上都说这里是“11116”模式（早11晚11，一周6天），但实际上，工时会比这高得多，具体要看你所在的团队和老板。刚进公司的时候，很多同事都能在10点多就走，没有硬性要求加班。午餐和晚餐各有2小时的休息，感觉还算能接受，毕竟互联网公司加班是常态。不过，时间久了，工时越来越长，周末基本上都是单休，假期也少。还有个很无语的现象，就是部门间工时排名。每个部门的工时都会被拉出来比较。偶尔公司会严查一下，午休和晚休的时间会被缩短，HR会来查岗，没在位置上的同事会被记录下来
理想江南137：同行业水平比较的话的确感觉需要避雷11.11.6这样的工作。但是自己却进不了这样的大厂
拼多多集团-PDD公司氛围 517人发布
点赞 评论 收藏
分享
头像
昨天 16:16
山东大学 嵌入式软件工程师
提前预习，Leader的PUA话术
实习er：“你表现得很好，部门领导给你打分都很高，转正希望很大”“过两天新来几个实习生，他们简历很优秀，在XX大厂实习过”“这个项目单独给你做，挤一挤时间完成他，其他实习生我没给，对转正有用”“就你这工作态度，以后哪个公司敢要你？”“这么简单的任务都完成不好，你还想不想转正了？”“你别觉得自己了不起，你离我的要求还差得远呢。”“别人怎么都能做好，就你不行？你是不是能力有问题？”“你要是再这样下去，实习评价肯定好不了。”“我对你很失望，你根本没有发挥出你的潜力。”“你怎么这么笨啊？教了你多少次了还不会，我都怀疑你是不是根本没用心。”“你看看你做的这点事儿，就这水平还大学生呢？我随便找个高中生都比...
你觉得哪一届的校招最难？ 上班苦还是上学苦呢？
点赞 评论 收藏
分享
10-07 10:41
天津理工大学中环信息学院 硬件开发
投麻了没人回复呀，求大佬指点
勇敢的联想人前程似锦：如果我是你，身体素质好我会去参军，然后走士兵计划考研211只需要200多分。
校招求职吐槽
点赞 评论 收藏
分享
11-01 19:50
安徽农业大学 Java
点赞 评论 收藏
分享
11-23 15:10
华南理工大学 Java
点赞 评论 收藏
分享
1 1 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
352682次浏览 3436人参与
# 我的实习求职记录 #
6085441次浏览 83682人参与
# 北方华创开奖 #
49963次浏览 450人参与
# 地方国企笔面经互助 #
5226次浏览 13人参与
# 职场吐槽大会 #
90681次浏览 752人参与
# 选完offer后，你后悔学本专业吗 #
23019次浏览 165人参与
# 阿里云管培生offer #
42013次浏览 962人参与
# ai智能作图 #
3419次浏览 71人参与
# 运营商笔面经互助 #
92681次浏览 1335人参与
# 实习中的菜狗时刻 #
278833次浏览 2739人参与
# 腾讯求职进展汇总 #
199724次浏览 1663人参与
# 如果有时光机，你最想去到哪个年纪？ #
24776次浏览 509人参与
# 当下环境，你会继续卷互联网，还是看其他行业机会 #
37548次浏览 343人参与
# 风评不好的公司，你会去吗？ #
20712次浏览 94人参与
# 上班苦还是上学苦呢？ #
90804次浏览 783人参与
# 大疆求职进展汇总 #
413609次浏览 2934人参与
# 国企还是互联网，你怎么选？ #
90171次浏览 702人参与
# 硬件兄弟们 甩出你的华为奖状 #
73572次浏览 609人参与
# 远程面试的尴尬瞬间 #
20483次浏览 296人参与
# 软件开发2024笔面经 #
2325746次浏览 48224人参与
# 如果中了500万，你会离职吗？ #
13612次浏览 145人参与
# 如何一边实习一边秋招 #
999961次浏览 12697人参与
牛客网
牛客企业服务