石家庄铁道大学2021年天梯赛选拔赛题解

开心签到

签到

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    string s;
    while(n){
        s+=n%10+'0';
        n/=10;
    }
    cout<<s<<endl;
    return 0;
}

开心模拟

推荐桶排

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e4+5;
int a[maxn];
int main(){
    int n,k,max=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>k;
        a[k]++;
    }
    for(int i=1;i<=30000;i++)
        if(a[i]>max)
            max=a[i];
    for(int i=1;i<=30000;i++)
        if(a[i]==max)
            cout<<i<<" "<<a[i]<<endl;
    return 0;
}

开心的斐波那契

注意开 long long

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main() {
    ll a[105]={0,0,1};
    int n;
    scanf("%d",&n);
    for(int i=3;i<=n;i++) 
        a[i]=a[i-1]+a[i-2];
    printf("%lld",a[n]);
    return 0;
}

开心晚会

• 法一：map来累加个数,然后遍历
• 法二：异或（xor）满足结合律与交换律，如果最后有不成对的就会留下，所以遍历所有数字，剩下的就是那个孤立的数字（xor：只有在两个比较的位不同时其结果是1，否则结果为0）

法一：

#include<iostream>
#include<map>
using namespace std;
int main(){
    int n;
    map<int,int> a;
    cin>>n;
    int t;
    for(int i=0;i<n;i++){
        cin>>t;
        a[t]++;
    }
    for(map<int,int>::iterator i=a.begin();i!=a.end();i++)
        if((i->second)%2==1){
            cout<<i->first<<endl;
            break;
        }
}

法二：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int ans,n;
    cin>>n>>ans;
    for(int i=2;i<=n;i++){
        int t;
        cin>>t;
        ans=ans^t;
    }
    cout<<ans;
    return 0;
}

开心树

法一：

一天一天模拟即可，

#include<iostream>
using namespace std;
long long ans,n;
int cnt=1;
int main(){
    cin>>n;
    int j=0;
    for(int i=1;i<=n;i++){
        ans+=cnt;
        j++;
        if(j==cnt) cnt++,j=0;
    }
    cout << ans << endl;
}

法二：

卡时间时，这是通解，，当然可以二分找 ，那么就 了

推公式，先找到一个 满足,然后求即可

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
    int n;
    cin >> n;
    int d;
    for(int i=0;i<=sqrt(2*n)+1;i++){
        if(i*(i+1)/2>n){
            d=i;break;
        }
    }
    d--;
    ll sum=0;
    sum+=(1+d)*(n-d*(d+1)/2);
    for(int i=1;i<=d;i++)
        sum+=i*i;
    cout<<sum<<endl;
}

开心数

本题不能暴力去做，题解是薛同写的，orz，在此放上

解释：

题意不太清楚，在此道歉，开心数应该是它的二进制数位上有且仅有一位是为0的

思路：

找出所有在二进制表示的情况下，所有位数都为1的数。然后拿这些数分别减2的次幂（其指数比该数的最高位数低）的所有情况，一 一列举

例如：

11 10

111 110 101

1111 1110 1101 1011

先将上述的枚举数存到数组，再根据给的范围得出所喜欢的数的个数

#include<iostream>
using namespace std;
typedef long long ll;
ll n[61] = { 1 };
ll m[2000] = { 0 };
int cnt = 1;
void init(){
    //n存储2的0-60次幂，因为10^18的二进制位位数为60
    for (int i = 1; i < 61; i++)
        n[i] = n[i-1] * 2;
    //选择一个1挖掉,m存储二进制仅含一个零的数（m数组一定严格递增）
    for (int i = 2; i < 61; i++)
        for (int j = i - 2; j >= 0; j--)
            m[cnt++] = n[i] -1 - n[j] ;//枚举喜欢的数
}
int main() {
    init();
    int t;
    cin >> t;
    while (t--) {
        ll l, r;
        cin >> l >> r;
        int pos = 0;
        while (m[pos] < l) pos++;
        int count = 0;
        for (; pos <= cnt; pos++) {
            if (m[pos] > r)
                break;
            count++;
        }
        cout << count << endl;
    }
}

开心整数

思路：

暴力打表判断就好(不打表也能过)，好多人wa在了0的判断，0!=1，那么0不能表示成为一些互不相同的整数的阶乘之和，所以输出NO即可

枚举：

#include<iostream>
using namespace std;
int n;
int m[10] = { 1 };
int main() {
    for (int i = 1; i < 10; i++)
        m[i] = m[i - 1] * i;
    while (cin >> n && n >= 0) {
        if (n != 0) {
            for (int i = 9; i >= 0; i--) {
                if (n >= m[i])
                    n = n - m[i];
                if (n == 0) {
                    cout << "YES" << endl;
                    break;
                }
            }
            if (n)
                cout << "NO" << endl;
        }
        else
            cout<<"NO"<<endl;
    }
}

dfs:

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int mod=100003;
ll a[13];
bool st[1000010];
//现在的开心数，阶乘所在位置
void dfs(int x, int p){
    if(p==-1) return;
    st[x+ a[p]]=1;
    dfs(x, p - 1);//不加
    dfs(x + a[p], p - 1);//加
}
int main(){
    a[0]=a[1]=1;
    for(int i=2;i<10;i++) {
        a[i]=a[i-1]*i;
    }
    dfs(0, 9);
    int x;
    while(scanf("%d",&x),x>=0){
        if(st[x]) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

开心扫雷

思路：

简单bfs，3X3的块间没有干扰，所以queue也不需要，枚举就可以

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
char mp[103][103];
int dir[][2] = {1, 0, 0, 1, 1, -1, -1, 1, -1, 0, 0, -1, -1, -1, 1, 1};
int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; ++i) {
        cin >> (mp[i + 1] + 1);
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(mp[i][j] == '*') {
                cout << "*";
                continue;
            }
            int cnt = 0;
            for(int k = 0; k < 8; ++k) {
                int x = i + dir[k][0];
                int y = j + dir[k][1];
                if(mp[x][y] == '*') cnt++;
            }
            cout << cnt;
        }
        cout << endl;
    }
    return 0;
}

奇怪的比赛

思路：

并查集，如果2个人是朋友，就union起来，如果是敌人，就把自己和对方的朋友union起来，中间标记一下自己的敌人就行

#include<iostream>
using namespace std;
int p[1005];
int d[1005];
int find(int x) {
    if (x == p[x]) return x;
    return p[x] = find(p[x]);
}
void un(int x, int y) {
    int a = find(x);
    int b = find(y);
    if (a != b) p[b] = a;
}
int main() {
    int n, m;
    int v, x, y;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) p[i] = i;
    for (int i = 0; i < m; i++) {
        cin >> v >> x >> y;
        if (!v){
            un(x, y);//连接队友
        }
        else {//x和y是敌人
            if (d[x])
                un(y, d[x]);//x的敌人是y的朋友，连接2个集合
            if (d[y])
                un(x, d[y]);//y的敌人是x的朋友，连接2个集合
            //标记敌人
            d[x] = y;
            d[y] = x;
        }
    }
    int s = 0;
    for (int i = 1; i <= n; i++)
        if (p[i] == i)
            s++;
    cout << s;
}

开心括号

题目全半角搞混了，在此道歉QAQ

思路：

栈的基本应用，用数组模拟或者写一个栈就好

数组：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char c[300];
int cnt;
int main(){
    string s;
    cin>>s;
    int len=s.size();
    for(int i=0;i<len;i++){
        if(cnt!=0 && (s[i]==')'&&c[cnt]=='(' || s[i]==']'&&c[cnt]=='[')) cnt--;
        else c[++cnt]=s[i];
    }
    if(cnt==0) cout<<"happy"<<endl;
    else cout<<"unhappy"<<endl;
}

STL(这里直接find函数了):

#include<iostream>
using namespace std;
int cnt;
int main(){
    string s;
    cin>>s;
    string::iterator it=s.begin();
    while(1){
        int pos=0;
        if(s.find("()")!=-1){
            pos=s.find("()");
            s.erase(it+pos,it+pos+2);
        }
        else if(s.find("[]")!=-1){
            pos=s.find("[]");
            s.erase(it+pos,it+pos+2);
        }
        else break;
    }
    if(s.size()==0) cout<<"happy"<<endl;
    else cout<<"unhappy"<<endl;
}

开心糖葫芦

思路：

一道简单数学题，正向考虑卖不出去的个数有点难搞，那就逆向，考虑能卖出去的情况数，1号小圆球可以有M个情况，2号小圆球就有(M-1)个情况，3号小圆球也是(M-1)个情况，以此类推得到能卖出去的情况数为：,总方案数为：，注意模数作差即可

#include<iostream>
using namespace std;
typedef long long ll;
const ll mod= 100003;
ll n,m,p;
//快速幂
ll qpow(ll a,ll b){
    ll ans = 1;
    while(b){
        if(b&1) ans = (ans*a)%mod;
        b/=2;
        a = (a*a)%mod;
    }
    return ans;
}
int main(){
    cin>>m>>n;
    printf("%lld\n",(qpow(m,n)-(m*qpow(m-1,n-1))%mod+mod)%mod);
    return 0;
}

开心矩阵

思路：

abc 3个矩阵的乘积方式有abc，acb，bac，bca，cab，cba 6种

那么枚举这6种的开心值，如果开心值不存在，就是-1

最后如果6种情况都是-1，输出ERROR，反之输出这六个数的最大值

#include<bits/stdc++.h>
#define ll long long
#define fo(i,a,b) for(int i=a;i<b;i++)
using namespace std;
ll a[105][105],b[105][105],c[105][105];
ll d[105][105],e[105][105];
ll happy[10];
const ll mod=1e9+7;
//计算[n,m] * [m,p]的乘积，存于后一个矩阵
void calculate(ll n, ll m, ll p, ll t1[105][105], ll t2[105][105]){
    memset(d,0,sizeof d);
    int row=0;//记录d矩阵到哪一行了
    int col=0;//记录d矩阵到哪一列了
    fo(i,0,n)fo(j,0,p){
        ll sum=0;
        fo(k,0,m){
            sum+= 1LL * t1[i][k] * t2[k][j];
        }
        if(j!=p-1)
            d[row][col++]=sum;
        else { //要换行了
            d[row][col++]=sum;
            row++;
            col=0;
        }
    }
}
void calculate2(ll n, ll m, ll p, ll t1[105][105], ll t2[105][105]){
    memset(e,0,sizeof e);
    int row=0;//记录e矩阵到哪一行了
    int col=0;//记录e矩阵到哪一列了
    fo(i,0,n)fo(j,0,p){
            ll sum=0;
            fo(k,0,m){
                sum+= 1LL * t1[i][k] * t2[k][j];
            }
            if(j!=p-1)
                e[row][col++]=sum;
            else { //要换行了
                e[row][col++]=sum;
                row++;
                col=0;
            }
        }
}
//计算矩阵开心值
ll calculate3(ll n,ll m,ll t[105][105]){
    ll sum=1;
    fo(i,0,n)fo(j,0,m){
        sum*=t[i][j];
        sum%=mod;
    }
    return sum;
}
int main(){
    int n1,m1,n2,m2,n3,m3;
    //输入3个矩阵
    cin>>n1>>m1;
    fo(i,0,n1)fo(j,0,m1)scanf("%lld",&a[i][j]);

    cin>>n2>>m2;
    fo(i,0,n2)fo(j,0,m2)scanf("%lld",&b[i][j]);

    cin>>n3>>m3;
    fo(i,0,n3)fo(j,0,m3)scanf("%lld",&c[i][j]);
    //求6次开心值
    //abc型([n1,m1] * [n2,m2] * [n3,m3])
    if(m1==n2&&m2==n3){//存在开心值
        calculate(n1,m1,m2,a,b);
        calculate2(n1,m2,m3,d,c);
        happy[0]=calculate3(n1,m3,e);
    }
    else happy[0]=-1;
    //acb型([n1,m1] * [n3,m3] * [n2,m2])
    if(m1==n3&&m3==n2){
        calculate(n1,m1,m3,a,c);
        calculate2(n1,m3,m2,d,b);
        happy[1]=calculate3(n1,m2,e);
    }
    else happy[1]=-1;
    //bac型([n2,m2] * [n1,m1] * [n3,m3])
    if(m2==n1&&m1==n3){
        calculate(n2,m2,m1,b,a);
        calculate2(n2,m1,m3,d,c);
        happy[2]=calculate3(n2,m3,e);
    }
    else happy[2]=-1;
    //bca型([n2,m2] * [n3,m3] * [n1,m1])
    if(m2==n3&&m3==n1){
        calculate(n2,m2,m3,b,c);
        calculate2(n2,m3,m1,d,a);
        happy[3]=calculate3(n2,m1,e);
    }
    else happy[3]=-1;
    //cab型([n3,m3] * [n1,m1] * [n2,m2])
    if(m3==n1&&m1==n2){
        calculate(n3,m3,m1,c,a);
        calculate2(n3,m1,m2,d,b);
        happy[4]=calculate3(n3,m2,e);
    }
    else happy[4]=-1;
    //cba型([n3,m3] * [n2,m2] * [n1,m1])
    if(m3==n2&&m2==n1){
        calculate(n3,m3,m2,c,b);
        calculate2(n3,m2,m1,d,a);
        happy[5]=calculate3(n3,m1,e);
    }
    else happy[5]=-1;

    ll mx=-1;
    for (int i = 0; i < 6; ++i) {
        mx=max(mx,happy[i]);
    }
    if(mx==-1)cout<<"ERROR";
    else cout<<mx;
    return 0;
}

消费卷

思路：

先跑一次spfa看能不能到终点，如果能，那就看距离是不是超过了cnt（这次spfa边权都是1），如果超过了，那就进入正题，我们可以二分最小花费cost，对于如何check，把这张图的边权映射为1或0（大于cost为1，反之为0），再跑spfa就可以了，如果最后终点的最短路小于等于cnt，check就返回true，反之返回false，二分正确是因为解是单调最优的，cost越大就越容易成功，cost越小就越难成功

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
int n,m;
int h[N],e[N],w[N],ne[N],idx;
int S,T,num;
int d[N];
bool st[N];
void spfa(){
    memset(st,0,sizeof st);
    queue<int> q;
    q.push(S);
    st[S] = 1;
    while(q.size()){
        int t = q.front();
        q.pop();
        for(int i = h[t];~i;i = ne[i]){
            int j = e[i];
            if(st[j]) continue;
            st[j] = true;
            d[j] = d[t] + 1;//权值设为1
            q.push(j);
        }
    }
}
void add(int x,int y,int z){
    ne[idx] = h[x],e[idx] = y,w[idx] = z,h[x] = idx++;
}
bool spfa2(int mid){
    memset(st,0,sizeof st);
    memset(d,0x3f,sizeof d);
    d[S] = 0;
    queue<int> q;
    q.push(S);
    while(q.size()){
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t];~i;i = ne[i]){
            int j = e[i];
            int p = w[i] > mid ? 1 : 0;
            if(d[j] > d[t] + p){
                d[j] = d[t] + p;
                if(!st[j]){
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return d[T] <= num;
}
int main(){
    memset(h,-1,sizeof h);
    cin>>n>>m>>S>>T>>num;
    while(m--){
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z),add(y,x,z);
    }
    spfa();
    if(!st[T]){
        puts("No");
        return 0;
    }
    puts("Yes");
    if(d[T] <= num){
        puts("0");
        return 0;
    }
    int l = 0,r = 1e9;
    while(l < r){
        int mid = (l + r) >> 1;
        if(spfa2(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d\n",l);
    return 0;
}

排队

思路：

贪心的去想，权值越大的越要在最靠边的位置上，那么我们把比较大的值放最右边还是最左边呢，这就需要 了，因此我们就去讨论放在左边多少个，右边多少个，然后状态转移， 表示按从大到小的分配顺序，所有左边分配 人，右边分配 人的分配方式的最大值

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    ll f[n+1][n+1];
    memset(f,0,sizeof f);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first;
        a[i].second = i + 1;
    }
    //按第一维从大到小排序
    sort(a.rbegin(), a.rend());
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            int k = i - j;
            //放左边
            f[j + 1][k] = max(f[j + 1][k], f[j][k] + 1ll * a[i].first * abs(a[i].second - (j + 1)));
            //放右边
            f[j][k + 1] = max(f[j][k + 1], f[j][k] + 1ll * a[i].first * abs(n - k - a[i].second));
        }
    }
    ll ans = 0;
    for (int i = 0; i <= n; i++) ans = max(ans, f[i][n - i]);
    cout << ans << '\n';
    return 0;
}