“科大讯飞杯”第十七届同济大学程序设计预选赛题解
比赛链接：https://ac.nowcoder.com/acm/contest/5477
A.张老师和菜哭武的游戏
题解：博弈论，要想被取走要满足z=ax+by有解，那么显然z必须要是gcd（a,b）的倍数，所以可以取走n/gcd（a，b）-2个数，即判断n/gcd（a，b）-2奇偶即可。
附代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;cin>>t;
while(t--){
int n,a,b;cin>>n>>a>>b;
if((n/__gcd(a,b)-2)%2==1)cout<<"Yes";
else cout<<"No";
cout<<'\n';
}
return 0;
}
B.伤害计算
题解：只要按照题意将字符串转化为对应的数值信息，就可以计算出来，要注意对字符串的操作，不过有个细节，不要使用cout输出流，不然可能输出科学计数法表示的数，让你莫名的WA。
附代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;cin>>s;
double ans=0;
for(int i=0;i<s.size();i++){
if(s[i]>='0'&&s[i]<='9'){
int k=0;
while(s[i]>='0'&&s[i]<='9')k*=10,k+=s[i]-'0',i++;
if(s[i]=='d'){
int p=0;i++;
while(s[i]>='0'&&s[i]<='9')p*=10,p+=s[i]-'0',i++;
ans+=k*(1+p)/2.0;
}
else {
ans+=k;
}
}
}
if(ans-(int)ans<1e-9)cout<<(int)ans;
else printf("%.1f",ans);
return 0;
}
C.张老师的旅行
这题单独拿出来写了，这里就不重复了
参见地址：https://blog.csdn.net/weixin_43802332/article/details/106039870
D.车辆调度
题解：数据范围不大，直接按题意暴搜即可，dfs传递参数时可以传递一个pair数组，用来记录当前各个车辆的位置，每次操作依次选择一辆遥控车向四个方向前进，边界判断要注意一下。
附代码：
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int, int> pii;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
int w,h,k,n;
pii car[5];
string s[11];
void dfs(pii *now,int cnt){
if(cnt>k)return;
for(int i=1;i<=n;i++){
int x=now[i].fi;
int y=now[i].se;
if(s[x][y]=='D'){cout<<"YES";exit(0);}
}
for(int i=1;i<=n;i++){
pii next[5];
for(int i=1;i<=n;i++)next[i].fi=now[i].fi,next[i].se=now[i].se;
int x=now[i].fi;
int y=now[i].se;
for(int j=0;j<4;j++){
int xx=x,yy=y;
while(1){
int xxx=xx+dir[j][0],yyy=yy+dir[j][1];
if(xxx<=0||xxx>=h+1||yyy<=0||yyy>=w+1)break;
int f=1;
for(int k=1;k<=n;k++){
if(k!=i&&xxx==now[k].fi&&yyy==now[k].se){f=0;break;}
}
if(!f)break;
if(s[xxx][yyy]=='X')break;
xx+=dir[j][0],yy+=dir[j][1];
}
if(xx!=x||yy!=y){
next[i].fi=xx,next[i].se=yy;
dfs(next,cnt+1);
}
}
}
}
int main(){
cin>>w>>h>>k;
for(int i=1;i<=h;i++)cin>>s[i],s[i]='@'+s[i];
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
if(s[i][j]=='R')n++,car[n]=make_pair(i,j);
}
}
dfs(car,0);
cout<<"NO";
}
E.弦
题解：这个题是一个裸的卡特兰数，显然概率可以通过合法方案数/总方案数来计算。
总方案数：
C(2n, 2) * C(2n – 2, 2) … C(2, 2) / n! = (2n)! / n! / 2^n
除以n!表示这n次选择没有先后
合法方案数为第n个卡特兰数，Catalan数令h(1)=1，这个题卡特兰数对应模型为（这2n个点是有标号的）：
h(n) = h(0)*h(n-1) +h(1)*h(n-2) + ... + h(n-1)h(0)
计算时可以采用通项公式：
h(n)=C(n,2n)/(n+1)=(2n)!/((n!)*(n+1)!)
得到合法数量：
2^n / (n + 1)!
由于取余为质数，用费马小定理求逆元即可
附代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e7 + 5;
ll qpow(ll x,ll y){
ll ans=1,t=x;
while(y>0){
if(y&1)ans*=t,ans%=mod;
t*=t,t%=mod;
y>>=1;
}
return ans%mod;
}
ll n,fac;
int main(){
cin>>n;
fac=1;
for(int i=1;i<=n+1;i++)fac =fac*i%mod;
cout<<qpow(2,n)*qpow(fac,mod-2)%mod;
return 0;
}
F.排列计算
题解：当时看这个题还以为是树状数组+差分，然而只是个简单的差分。根据贪心思想，每个数对答案的贡献是它被查询的次数乘以它自身，所以应该将查询次数最大的地方放上最大的数。用差分统计每个位置被查询的次数（单点查询而且有顺序的），排一下序，计算答案即可。
附树状数组代码代码：
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
typedef long long ll;
const int N = 2e5+5;
ll tree[N],a[N];
int n, m;
void add(int x, ll num) {
while (x <= n) {
tree[x] += num;
x += lowbit(x);
}
}
ll query(int x) {
ll ans = 0;
while (x) { ans += tree[x]; x -= lowbit(x); }
return ans;
}
int main(){
cin>>n>>m;
while (m--) {
int x, y;
cin>>x>>y;
add(x, 1);//差分处理
add(y + 1, -1);
}
for(int i=1;i<=n;i++)a[i]=query(i);
sort(a+1,a+1+n);
ll ans=0;
for(int i=1;i<=n;i++)ans+=a[i]*i;
cout<<ans;
return 0;
}
CVTE公司福利 264人发布
