The 16-th BIT Campus Programming Contest

SMU Autumn 2024 Contest Round 14

2024.11.23 12:30————17:30

过题数7/13
补题数7/13

• Gifts in box
• BIT Palindrome
• Combination
• ZYW with BIT
• Equal
• ZYW with books
• Get off work
• Happiness Index
• String
• Stones
• ZYW with tutors
• Fake Travelling Salesman Problem
• Counting in Tree

[A - Gifts in box]

题解：
一个长n，宽m，高h的纸箱子里有一些长宽高均为1的礼物，现在以h为高从顶部看下去看到的礼物数字以一个nm的序列给出。将纸箱子翻倒，以n作为高，请输出从顶部往下看的礼物分布，以hm的序列输出。
根据样例可以想象，礼物会分布在上半部分，这一列上有礼物的行都会堆叠一个，以此往下方堆叠。
代码：

#include <iostream>
#include <set>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<string>
#include<string.h>
#include<map>
#include<math.h>

using namespace std;
#define int long long
int n,m,h;
int a[110][110];
int b[110][110];

void solve(){
    cin >> n >> m >> h;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    }
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= m; j++) {
            int res = 0;
            for (int p = 1; p <= n; p++) {
                if(a[p][j] > 0) res++;
                a[p][j]--;
            }
            b[i][j] = res;
            cout << b[i][j] << ' ';
        }cout << endl;
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t = 1;
 //   cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

[B - BIT Palindrome]

刚读完题就跑去博弈论了，从这题开始就没参与讨论。
题解：
给定一个数字n，要求返还有多少个满足条件的字符串，字符串刚好包含一个回文子串并且仅仅由b，i，t三个字母组成。
找规律。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+10;
const int p=1e9+7;
int n, m;
void solve(){
    cin>>n;
    if(n==1) cout<<0<<endl;
    else if(n==2) cout<<3<<endl;
    else if(n==3) cout<<18<<endl;
    else {
        cout<<6*(n+1)%p<<endl;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

[D - ZYW with BIT]

题意非常复杂，听了俩三遍，思路比较简单，但是代码冗长，我只做了一点纠错小工作，持续学习SG中，傅姐图论太厉害啦！
题解：
把等待时间当作点权，最短路的变形题。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int >
const int maxn=1e15;
const int N=510;
int n,m,T;
int w[N][N];
int ti[N][N];
int an[N];
int st[N];
int aaa[N];
vector<int>a[N];
void dj(int x,int y){
    for(int i=0;i<=n;i++) an[i]=maxn,st[i]=0;
    an[x]=y;
    priority_queue<PII,vector<PII>,greater<PII> >q;
    q.push({y,x});
    while(q.size()){
        auto [x1,y1]=q.top();
        q.pop();
        if(st[y1]) continue;
        st[y1]=1;
        int tim=ti[y1][x1%T]-1+x1;
        for(int i=0;i<a[y1].size();i++){
            if(tim+w[y1][a[y1][i]]<an[a[y1][i]]) {
                an[a[y1][i]]=tim+w[y1][a[y1][i]];
                q.push({an[a[y1][i]],a[y1][i]});
            }
        }
    }
}
void chu(){
    for(int i=1;i<=n;i++){
        int k=0;
        int time=1;
        int cnt=-1;
        bool flag=0;
        for(int j=0;j<T;j++){
            if(ti[i][j]){
                if(cnt==-1)cnt=j;
                for(int p=k;p<=j;p++){
                    ti[i][p]=time;
                    time--;
                }
                k=j+1;
                flag=0;
            }
            else{
                if(!flag) k=j,flag=1;
            }
            time++;
        }
        if(cnt==-1) {
            for(int j=0;j<T;j++){
                ti[i][j]=maxn;
            }
        }
        else{
            if(k!=0){
                int cn=T-k+cnt+1;
                for(int p=k;p<T;p++){
                    ti[i][p]=cn--;
                }
            }
        }
    }
}
void solve(){
   cin>>n>>m>>T;
   for(int i=1;i<=n;i++){
       string s;
       cin>>s;
       for(int j=0;j<T;j++){
           ti[i][j]=s[j]-'0';
       }
   }
   for(int i=0;i<m;i++){
       int x,y,ww;
       cin>>x>>y>>ww;
       w[x][y]=ww;
       w[y][x]=ww;
       a[x].push_back(y);
       a[y].push_back(x);
   }
   chu();
//   for(int i=1;i<=n;i++){
//       for(int j=0;j<T;j++){
//           cout<<ti[i][j]<<" ";
//       }
//       cout<<endl;
//   }
    for(int i=0;i<T;i++){
//        cout<<i+ti[1][i]-1<<" ";
        dj(1,i);
        aaa[i]=an[n]-an[1];
    }
    for(int i=0;i<T;i++){
        cout<<aaa[i]<<" ";
    }

}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
//    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
//
//10 3
//1 2
//2 3
//3 4
//4 5
//5 6
//6 7
//7 8
//8 9
//9 10

[E - Equal]

题解：
签到题。给定俩个数字x和y，可以进行俩个操作，x+1或y+2，用最少的操作次数让俩个数相等。
代码：

#include <iostream>
#include <set>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<string>
#include<string.h>
#include<map>
#include<math.h>

using namespace std;
#define int long long
int x,y;

void solve(){
    cin >> x >> y;
    if(x <= y) cout << y-x;
    else {
        int ls = x-y;
        if(ls%2 ==0 ) cout << ls/2;
        else cout << ls/2+2;
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t = 1;
 //   cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

[G - Get off work]

还是傅姐的图论，廷哥and me持续学习SG中…傅姐带飞直接
题解：
n个员工，每辆车最多可以做k个人，给定连接关系，问需要多少辆车才能把所有员工送回家，车辆不回头。
反向思维，把所有员工从家送回来，所以每个叶子节点都至少需要一辆车。往公司送的同时计算此时这个点处能接送几个人，如果接送不了这个人，加一辆车。
代码：

#include <iostream>
#include <set>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<string>
#include<string.h>
#include<map>
#include<math.h>

using namespace std;
#define int long long
int n,k;
const int N = 2e5+10;
vector<int>a[N];
int st[N];
int ans;

void dfs(int x,int fa) {
    if(a[x].size() == 1 && x != 1) st[x]=k,ans++;
    for (int i = 0; i < a[x].size(); i++) {
        if(a[x][i]==fa)continue;
        dfs(a[x][i],x);
        st[x] += (st[a[x][i]]-1);
    }
    if(st[x] < 1 && x != 1) ans++,st[x] = k;
}

void solve(){
    ans = 0;
    cin >> n >> k;
    for (int i = 0;i <= n+1; i++) a[i].clear(),st[i] = 0;
    for (int i = 1; i < n; i++) {
        int u,v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }dfs(1,0);
    cout << ans << endl;
    return ;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t = 1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

[J - Stones]

哦贯穿始终的博弈论啊，最后还是廷哥一点一点改出来的，主打一个啥也不懂但能造样例。
题解：
n堆石子，Alice先手拿，每次可以拿一堆石子的1到（数量+1）/2颗，谁先拿不了谁就输。
没有什么技巧真的硬试出来的，服气。
注意map底部逻辑是红黑树，如果tle可以考虑换一种方式。
代码：

#include <iostream>
#include <set>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<string>
#include<string.h>
#include<map>
#include<math.h>

using namespace std;
const int N=1e6+10;
int n;
int a[N];
int pass[30]={0,2,6,14,30,62,126,254,510,1022,2046,4094,8190,16382,32766,65534,131070,262142,524286,1048574,2097150,4194302,8388606,16777214,33554430,67108862,134217726,268435454,536870910,1073741822};


int sg(int num){
    for(int j=0;j<30;++j) if(num==pass[j]){return 0;}
    if(num&1) return num-(num+1)/2+1;
    else{
        return sg(num/2-1);
    }
}

void solve(){
    int x = 2;

    cin >> n;
    int res = 0;
    bool flag = 1;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        if(a[i] == 0) continue;
        flag = 0;
        for(int j=0;j<30;++j) if(a[i]==pass[j]){flag=1; break;}
        if(flag) continue;
        res = res xor (sg(a[i]));
    }  //cout << res << endl;
    if(res) cout << "Alice";
    else cout << "Bob";
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t = 1;
    //   cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

[K - ZYW with tutors]

签到吧，不过不是我签的。
题解：
给出一个行列式，可以更改一个数字使得行列式的值最小。
由于当行列式的左上——右下对角线上有数字0时，行列式的值也是数字0，所以输出0即可。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+10;
int n, m;
int a[N][N];
void solve(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
        }
    }
    cout<<0<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
//    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}