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

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

Solution

容易知道：

$x=t_1(y+z)$
$x=t_2(y-z)$

可以利用上式构造出任意的点 $x=k_1y+k_2z$ ，故计算能走到点的个数即可。
求 $y$ 和 $z$ 的最大公约数就行了，我们所能构造的最小的 $temp=gcd(y,z)$ ，个数为 $ans=\frac{n}{temp}$ 。

如果你不知道为什么求最大公约数就行了，可以看下文更相损减术(转载自百度文库):

更相减损术
《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”

　　翻译成现代语言如下：

　　第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

　　第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

　　则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

　　其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b); }

void solve(){
    ll n,a,b;
    cin>>n>>a>>b;
    int temp=gcd(a,b);
    int ans=n/temp;
    if(ans&1) cout<<"Yes\n";
    else cout<<"No\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

B.伤害计算

Solution

按照题目意思模拟就行了。
坑点：没注意输出结尾要求需要判断一下。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1e5 + 5;

char s[N];

double solve(int x) {return (1+x)/2.0;}

int main(){
    cin>>s+1;
    int n=strlen(s+1);
    double ans=0;
    int j=0;
    int k=0;
    for(int i=1;i<=n;i++){
        while(isdigit(s[i]) && i<=n){
            j=j*10+(s[i]-'0');
            i++;
        }
        if(s[i]=='d'){
            i++;
            while(isdigit(s[i]) && i<=n){
                k=k*10+(s[i]-'0');
                i++;
            }
            ans+=j*solve(k);
            j=k=0;
        }else{
            ans+=j;
            j=0;
        }
    }
    if(fmod(ans,1)<=eps) printf("%lld\n",(ll)ans);
    else printf("%.1f\n",ans);
    return 0;
}

D.车辆调度

Solution

注意题目的数据范围极小，故可以直接搜索，我写了个DFS，本来按道理是应该1A的，但是比赛的时候数据有问题一直卡在90.91，赛后重测果然本来应该是1A的，后面还陆续改了一个小时想着debug啥的，也找不出啥，下次还是考虑过了一定时间就换题吧。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 10 + 5;

int n,m,K,cnt;
char s[N][N];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
bool book[N][N];
vector<pair<int,int> >V;

void dfs(int x,int y,int cnt){
    if(book[x][y] && cnt==K){
        cout<<"YES\n";
        exit(0);
    }
    if(cnt>=K) return;
    for(int i=0;i<V.size();i++){
        for(int j=0;j<4;j++){
            int x=V[i].first,y=V[i].second;
            int tx=x,ty=y;
            while(s[tx+dx[j]][ty+dy[j]]=='.') tx+=dx[j],ty+=dy[j];
            swap(s[tx][ty],s[x][y]);
            V[i].first=tx,V[i].second=ty;
            dfs(tx,ty,cnt+1);
            V[i].first=x,V[i].second=y;
            swap(s[tx][ty],s[x][y]);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>m>>n>>K;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>s[i][j];
            if(s[i][j]=='R') V.push_back({i,j});
            if(s[i][j]=='D') {s[i][j]='.',book[i][j]=true;}
        }
    }
    dfs(0,0,0);
    cout<<"NO\n";
    return 0;
}

E.弦

Solution

前置知识：卡特兰数。
首先要能看出来这个 $2n$ 的圆上连线且不相交的情况为卡特兰数。
卡特兰数常用的递推公式:

$f[n]=\frac{C_{2n}^{n}}{n+1}$
$f[n]=\frac{f[n-1](4n-2)}{n+1}$

然后答案就是 $\frac{连线不相交的个数}{连线的方法数}$
接着就是求连线的方法数了，这是排列组合， $\frac{(2n)!}{2^nn!}$ ， $2n!$ 代表 $2n$ 排列为一排的个数， $2^n$ 代表两个为一组的重复情况， $n!$ 代表不同组数的排列情况。

$\frac{(2n)!}{(n+1)!}$

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

ll qpow(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;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;cin>>n;
    ll ans=1;
    for(int i=2;i<=n+1;i++)    ans=ans*i%mod;
    cout<<qpow(2,n)*qpow(ans,mod-2)%mod<<'\n';
    return 0;
}

F.排列计算

Solution

差分裸题，贪心只有出现次数越多的点填的数字越大，才能满足最优解。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 2e5 + 5;

ll n,m;
ll d[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(ll i=1;i<=m;i++){
        ll l,r;cin>>l>>r;
        d[l]++,d[r+1]--;
    }
    for(ll i=1;i<=n;i++){
        d[i]+=d[i-1];
    }
    sort(d+1,d+1+n);
    ll ans=0;
    for(ll i=1;i<=n;i++){
        ans+=d[i]*i;
    }
    cout<<ans<<'\n';
    return 0;
}