# 【题解】第五届石家庄铁道大学程序设计竞赛题解 精

## A-SOUL Eileen Fan F

```#include <bits/stdc++.h>
using namespace std;
int main(){
string a,b,c;
cin>>c>>a>>b;
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
reverse(c.begin(),c.end());
string s;

int up=0,sum,k;
while(a.length()!=b.length()){
if(a.length()>b.length())
b += '0';
else
a += '0';
}
for(int i=0;i<a.length();i++){
sum = a[i]-'0'+b[i]-'0'+up;
if(i>c.length()-1 || c[i]=='0')
k=10;
else
k=c[i]-'0';
up = sum/k;
sum %= k;
s = (char)(sum + '0') + s;
}
if(up > 0)
s = (char)(up + '0') + s;
int count = 0;
while(s[count] == '0' && s.length() > 1)
s.erase(count, 1);
cout<<s<<endl;
return 0;

}```

## 打牌

```#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

int main(){
int t;
cin >> t;
while(t--){
ll diff = 0,n;
cin >> n;
ll arr[200005];
for(ll i = 0; i < n; i++){
cin >> arr[i];
}
sort(arr,arr + n);
for(ll i = n - 1; i >= 1; i -= 2){
ll a = 0,b = 0;
if(arr[i] % 2 == 0)
a = arr[i];
if(arr[i - 1] % 2 != 0)
b = arr[i - 1];
diff = diff + a - b;
}
if(n % 2 == 1)
if(arr[0] % 2 == 0)
diff += arr[0];
if(diff > 0)
cout << "T" << endl;
else if(diff < 0)
cout << "X" << endl;
else cout << "Tie" << endl;
}
return 0;
}
```

## BJS and HT

• 直接使用`unsigned long long`储存Hash值，计算时不处理算术溢出问题(产生溢出时相当于自动对取模，这样可以避免低效的mod运算)，且一般取哈希进制数P为131或13331
• 区间的字符串哈希值公式为：
• 串中找连续的 个字符，和 串前 个字符匹配上，之后检验其余部分是否能匹配上即可，最终复杂度为，其中 为字符串总长度

```#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N=5e5+10;
int t,k,n;
ll ha[N],hb[N],po[N];
char a[N],b[N];
ll hasha(int l,int r){
l--;
return ha[r]-ha[l]*po[r-l];
}
ll hashb(int l,int r){
l--;
return hb[r]-hb[l]*po[r-l];
}
int cnt=0;
int main(){
scanf("%d",&t);
while(t--){
scanf("%s%s%d",a+1,b+1,&k);
int n=strlen(a+1);

if(strlen(b+1)!=n || k>n){
continue;
}

po[0]=1;
for(int i=1;i<=n;i++)
ha[i]=131*ha[i-1]+a[i],
hb[i]=131*hb[i-1]+b[i],
po[i]=po[i-1]*131;

ll val=hashb(1,k);//H最前面一段

bool flag=0;

//枚举截取B的左端点i
for(int i=1;i+k-1<=n;i++)
if(hasha(i,i+k-1)==val)
//其他部分匹配上
if(hasha(1,i-1)==hashb(k+1,k+i-1) && hasha(i+k,n)==hashb(i+k,n))
flag=1;

if(flag) {
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}```

## F爱玩炉石传说

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

bool a[1000000];
int n;
int main() {
cin >> n;
int t;
bool flag = 0;
int k = 0;
for (int i = 0; i < n; i++) {
cin >> t;
//cout<<t;
if (!a[t]) {
a[t] = 1;
k++;
}
}
for (int i = 1; i <= k; i++)
if (!a[i]) {
flag = 1;
break;
}
if (flag)
cout << "Nevermind, just use the Twisting Nether." << endl;
else
cout << "This is a textbook-like blasphemy!" << endl;

}
```

## A+B Problem

```#include <iostream>
#include <algorithm>
#include <cstring>
#define pb push_back
using namespace std;

int main(){
string a,b;
while(cin>>a>>b){
//补0和小数点
int posa=-1,posb=-1;
for(int i=0;i<a.size();i++){
if(a[i]=='.'){
posa=i;
break;
}
}
for(int i=0;i<b.size();i++){
if(b[i]=='.'){
posb=i;
break;
}
}
if(posa==-1){
a.pb('.');
a.pb('0');
}
else if(posb==-1){
b.pb('.');
b.pb('0');
}

if(a.size()<b.size()){
swap(a,b);
}
//看小数点的位置
posa=posb=0;
for(int i=0;i<a.size();i++){
if(a[i]=='.'){
break;
}
posa++;
}
for(int i=0;i<b.size();i++){
if(b[i]=='.'){
break;
}
posb++;
}
if(posa<posb){
string tem="";
for(int i=0;i<posb-posa;i++){
tem.pb('0');
}
tem+=a;
a=tem;
}
else{
string tem="";
for(int i=0;i<posa-posb;i++){
tem.pb('0');
}
tem+=b;
b=tem;
}

int d=a.size()-b.size();
for(int i=0;i<d;i++){
b.push_back('0');
}
int x=a.size(),y=b.size();
if(a.size()<b.size()){
for(int i=0;i<(y-x);i++){
a.pb('0');
}
}

reverse(a.begin(),a.end());
reverse(b.begin(),b.end());

string ans="";
int up=0;
for(int i=0;i<a.size();i++){
if(a[i]=='.'){
ans.pb('.');
continue;
}
ans.pb((a[i]-'0'+b[i]-'0'+up)%10+48);
up=(up+a[i]-'0'+b[i]-'0')/10;
}
if(up){
ans.pb(up+48);
}
reverse(ans.begin(),ans.end());

int pos=-1;
for(int i=0;i<ans.size();i++){
if(ans[i]=='.'){
pos=i;
break;
}
}

//去除后导零
bool flag=1;
for(int i=pos+1;i<ans.size();i++){
if(ans[i]!='0'){
flag=0;
break;
}
}
if(flag){//全是0
for(int i=0;i<pos;i++){
cout<<ans[i];
}
cout<<endl;
}
else{
int len=ans.size();
for(int i=ans.size()-1;i>=0;i--){
if(ans[i]=='0'){
len--;
}
else{
break;
}
}
for(int i=0;i<len;i++){
cout<<ans[i];
}
cout<<endl;
}
}
return 0;
}```

## 懒虫读诗

```#include <bits/stdc++.h>
using namespace std;
const int N=300+10;
int f[N][N];
vector<int> table[N];
int n,m;

void dp(int a){
for(auto i : table[a]){
dp(i);
//类似背包
for (int j=m+1;j>=1;j--)
for(int k=0;k<j;k++)
f[a][j]=max(f[a][j],f[a][j-k]+f[i][k]);
}
}
int main(){
cin>>n>>m;
int ki=0;
for(int i=1;i<=n;i++){
cin >> ki >> f[i][1];
table[ki].push_back(i);
}

dp(0);
cout<<f[0][m+1];
}```

## A Hard Calculation Problem

```#include <bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define f(i,a,n) for(int i=a;i<n;++i)
#define ff(i,a,n) for(int i=a;i<=n;++i)
const int INF=0x3f3f3f3f;
using namespace std;
typedef long long ll;
typedef double dbl;
typedef pair<int, int> pi;
int t;
int q=2021-5;
int main(){
cin>>t;
int x;
while(t--){
cin>>x;
cout<<x+q<<endl;
}
return 0;
}```

## 水果蛋糕

1. 计算蛋糕的大小：观察题目，我们可以知道蛋糕的宽都是相同的，因此判断每块蛋糕的面积的大小只需要判断蛋糕上下底边的和的大小即可
2. 统计每块蛋糕上水果的个数：枚举每个水果的坐标，使用二分查找（通过向量的叉积判断水果在断口的左边还是右边）水果左边最右边的断口（或右边最左边的断口），统计每个断口被查找的次数即可求出每块蛋糕上水果的次数（蛋糕边缘的切割点的坐标可以利用前缀和求出）
3. 找出所求蛋糕：可以通过记录当前最优解查找，也可使用结构体排序后直接选出

```#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
double us[10000020],ds[10000020];
double u[10000020],d[10000020];
int cnt[5000010];
double cj(double x1,double y1,double x2,double y2){
return x1*y2-x2*y1;
}
double pd(double x1,double y1,double x2,double y2,double x3,double y3){
return cj(x2-x1,y2-y1,x3-x1,y3-y1);
}
struct Cake{
int cnt,sqr,num;
}c[10000020];

bool cmp(struct Cake a,struct Cake b){
if(a.cnt != b.cnt )return a.cnt > b.cnt ;
else if(a.sqr!=b.sqr )return a.sqr >b.sqr ;
else return a.num<b.num;
}
int main(){
int n,m;
scanf("%d %d",&n,&m);
int xx,yy;
scanf("%d %d",&xx,&yy);
for(int i=1;i<=n;i++){
scanf("%lf %lf",&us[i],&ds[i]);
u[i]=u[i-1]+us[i];
d[i]=d[i-1]+ds[i];
c[i].sqr=us[i]+ds[i];
c[i].num=i;
}
c[n+1].sqr=xx-u[n]+xx-d[n];
c[n+1].num=n+1;
for(int i=0;i<m;i++){
double x,y;
scanf("%lf %lf",&x,&y);
int l=1,r=n+1;
while(l!=r){
int mid=(l+r)/2;
if(pd(u[mid],yy,d[mid],0,x,y)>0){
l=mid+1;
}else{
r=mid;
}
}
c[l].cnt++;
}
sort(c+1,c+n+2,cmp);
printf("%d",c[1].num);
} ```

## Digital Logic and Bit Operation

```#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long

int main(){
ll ans;
ll l,r;
int t;
cin >> t;
while(t--){
cin >> l >> r;
ll now = 0;
while((l|(ll)1 << now) < r){
l |= ((ll)1 << now);
now++;
}
cout << (l|r) << endl;
}
}```

## 蛋糕惨案

1. 快速的求出范围内的所有质数：很明显使用定义来判断质数的总时间复杂度为，而本题的数据范围在1e7，肯定会超时，接下来采用埃氏筛，其效率是，虽然已经很快了，但是在残暴数据1e7面前仍会超时，最后便是本题的正解：欧拉筛（线性筛）正如名字那样，他的时间复杂度为，在利用线性筛打好表后，我们只需要枚举每个数，判断他们是否是素数，如果是则把他们存在一个数组中
2. 对数组进行排序：大概有个素数，最后我们直接进行排序就好（排序使用时间复杂度不超过即可）

```#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
bool cmp(int a,int b){
return a<b;
}
int primes[10000010], cnt;
bool st[10000010];
int s[10000010];
int main(){
st[1]=1;
for (int i = 2; i <= 1e7; i ++ ){
if (st[i]) continue;
primes[cnt ++ ] = i;
for (int j = i + i; j <= 1e7; j += i)
st[j] = true;
}
int n;
scanf("%d",&n);

int top=0;
for(int i=0;i<n;i++){
int now;
scanf("%d",&now);
if(st[now]==0){
s[top++]=now;
}
}
sort(s,s+top,cmp);
printf("%d\n",top);
if(top==0)printf("-1");
else {
for(int i=0;i<top;i++){
printf("%d ",s[i]);
}
}
}```

## Equation

```#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
#define ll long long

double fx(double x,double y){
return 6 * pow(x,7) + 8 * pow(x,6) + 7 * x*x*x + 5 * x*x - y * x;
}

double gx(double x,double y){
return 42 * pow(x,6) + 48 * x*x*x*x*x + 21 * x*x + 10 * x - y;
}

int main(){
int t;
cin >> t;
while(t--){
double y;
cin >> y;
if(gx(100,y) <= 0){
cout << fx(100,y) << endl;
continue;
}
else{
double low = 0,high = 100,mid;
while(high - low > 0.00001){
mid = (high + low)/2;
if(gx(mid,y) >= 0) high = mid;
else low = mid;
}
printf("%.4lf\n",fx(mid,y));
}
}
return 0;
}```

## 树上宝藏

```#include<iostream>
#include<cstring>
using namespace  std;
typedef long long ll;
const int N=1e5+10;

int h[N],e[N*2],ne[N*2],idx;
ll w[N],ans;
int n,m;

e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool flag=0;
void dfs(int u,int fa,int v,ll d){
if(u==v){
w[v]+=d;
flag=1;
return ;
}
w[u]+=d;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==fa)continue;
dfs(j,u,v,d);
if(flag)return ;
}
w[u]-=d;
}

void dfs_1(int u,int fa,int v,int res){
if(u==v){
res+=w[u];
ans=res;
return ;
}
res+=w[u];
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==fa)continue;
dfs_1(j,u,v,res);
}
res-=w[u];
return ;
}

int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++){
cin>>w[i];
}
for(int i=0;i<n-1;i++){
int a,b;
scanf("%d%d",&a,&b);
}
for(int i=0;i<m;i++){
int u,v;cin>>u>>v;
ll d;cin>>d;
flag=0;
dfs(u,-1,v,d);
}
for(int i=0;i<m;i++){
int u,v;cin>>u>>v;
ans=0;
dfs_1(u,-1,v,0);
cout<<ans<<endl;
}
return 0;
}```

## Rescue Hostage

```#include<iostream>
#include<queue>
#include<string>
using namespace std;
const int N = 1010;
int ansa[205][205];
int ansb[205][205];
char s[205][205];
const int dx[4] = { 1,-1,0,0 };
const int dy[4] = { 0,0,1,-1 };
int xy, yy, xm, ym;
int n, m;
struct node{
int x, y;
};
int lans = 10010;
bool judge(int x0, int y0, int ans[205][205]){
if (x0 < 0 || x0 >= n || y0 < 0 || y0 >= m)
return false;
if (ans[x0][y0])
return false;
if (s[x0][y0] == '#')
return false;
else
return true;
}
void bfs(int x, int y, int ans[205][205]){
queue<node> q;
node p1;
p1.x = x;
p1.y = y;
ans[x][y] = 0;
q.push(p1);
while (!q.empty()){
node p2;
p2 = q.front();
q.pop();
for (int i = 0; i < 4; i++){
p1.x = p2.x + dx[i];
p1.y = p2.y + dy[i];
if (judge(p1.x, p1.y, ans)){
ans[p1.x][p1.y] = ans[p2.x][p2.y] + 1;
q.push(p1);
}
}
}
}
int main(){
cin >> n >> m;
lans = 10010;
memset(ansa, 0, sizeof(ansa));
memset(ansb, 0, sizeof(ansb));
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> s[i][j];
if (s[i][j] == 'F'){
xy = i;
yy = j;
}
else if (s[i][j] == 'X'){
xm = i;
ym = j;
}
}
}
bfs(xy, yy, ansa);
bfs(xm, ym, ansb);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++){
if (s[i][j] == 'H' && ansa[i][j] != 0){
int temp = ansa[i][j] + ansb[i][j];
lans = min(lans, temp);
}
}
cout << lans << endl;
}```

## 嘉然的问题

```#include<bits/stdc++.h>
using namespace std;
string s;
void judge(int pos,int len){
string s1=s.substr(pos,len);
string s2=s1;
reverse(s1.begin(),s1.end());
if(s1==s2)cout<<s1<<endl;
}
int main(){
getline(cin,s);
int l=s.length();
for(int i=2;i<=l;i++)
for(int j=0;j+i<=l;j++)
judge(j,i);

return 0;
}```

# 近期热帖

• 回复(0) 发表于 2022-01-26 18:58:35
• 回复(0) 发表于 2022-01-26 11:25:53

# 等你来战

• 报名截止时间：2022-01-28 14:00
• 报名截止时间：2022-01-31 16:00
• 报名截止时间：2022-01-28 18:00
• 报名截止时间：2022-02-14 17:00

# 热门推荐

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题