2025牛客暑期多校训练营4-做题&补题记录

赤石场。不多评价

---

F For the Treasury!

修正物品价值，排序，然后补回多减掉的价值。做完了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,k,c;
const int N=3e5+10;
struct node{
    int a,id;
    ll b;

    bool operator<(const node& B) const{
        return b<B.b;
    }
}t[N];

void solve()
{
    cin>>n>>k>>c;
    for(int i=1;i<=n;++i)
    {
        cin>>t[i].a;
        t[i].b=t[i].a-1ll*c*(i-1);
    }
    sort(t+1,t+n+1);
    ll ans=0;
    for(int i=n;i>=n-k+1;--i)  ans+=t[i].b;
    ans+=1ll*(0+k-1)*k/2*c;
    cout<<ans<<"\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int TxT=1;
    //cin>>TxT;
    while(TxT--) solve();
    return 0;
}

B Blind Alley

神秘题目。调了两小时，最后改了一下搜索枚举的维度顺序就过了。现在也不知道为什么过不了，也不知道为什么就过了。

/*

This code template was updated by Yukii_P on 2025/4/4.

*/
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << #__VA_ARGS__ << " = "; dbg1(__VA_ARGS__)
void dbg2() { std::cerr << "\n"; }
template<typename T, typename... T2>
void dbg2(T x, T2... args) {
    std::cerr << ", " << x;
    dbg2(args...);
}
template<typename T, typename... T2>
void dbg1(T x, T2... args) {
    std::cerr << x;
    dbg2(args...);
}
#else
#define debug(...) 
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

int dx[]{1, -1, 0};
int dy[]{0, 0, 1};

int dx2[]{1, -1, 0, 0};
int dy2[]{0, 0, 1, -1};

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    // vector<int> fa(n * m + 1);
    vector<int> mn(n * m + 1, 1e9), mx(n * m + 1);
    // iota(all(fa), 0);
    // auto find = [&](int x) -> int {
    //     while (x != fa[x]) {
    //         x = fa[x] = fa[fa[x]];
    //     }
    //     return x;
    // };
    vector<vector<char>> s(n + 1, vector<char>(m + 1));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> s[i][j];
        }
    }
    // if (k >= m + 1) {
    //     cout << "YES\n";
    //     return;
    // }
    vector vis(n + 1, vector(m + 1, false));
    vector<vector<vector<tuple<int, int>>>> pre(n + 1, vector<vector<tuple<int, int>>>(m + 1));
    vector ok(n + 1, vector(m + 1, false));
    {
        queue<tuple<int, int>> q;
        q.emplace(1, 1);
        while (q.size()) {
            auto [x, y] = q.front();
            // debug(x, y);
            q.pop();
            if (vis[x][y]) continue;
            vis[x][y] = 1;
            for (int i = 0; i < 3; ++i) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx <= 0 || nx > n || ny <= 0 || ny > m || s[nx][ny] == '1') continue;
                q.emplace(nx, ny);
                pre[nx][ny].emplace_back(x, y);
            }
        }
        
        q.emplace(1, m);
        while (q.size()) {
            auto [x, y] = q.front();
            // debug("?", x, y);
            q.pop();
            if (ok[x][y]) continue;
            ok[x][y] = 1;
            for (auto [_x, _y] : pre[x][y]) {
                q.emplace(_x, _y);
            }
        }
    }
    // for (int i = 1; i <= n; ++i) {
    //     for (int j = 1; j <= m; ++j) {
    //         if (!vis[i][j]) s[i][j] = '1';
    //     }
    // }
    vector vis2(n + 1, vector(m + 1, false));
    //vector vis3(n + 1, vector(m + 1, false));
    auto bfs = [&](int f, int sx, int sy) {
        queue<tuple<int, int>> q;
        q.emplace(sx, sy);
        while (q.size()) {
            auto [x, y] = q.front();
            q.pop();
            // debug(x, y);
            if (vis2[x][y]) continue;
            vis2[x][y] = 1;
            for (int i = 0; i < 3; ++i) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx <= 0 || nx > n || ny <= 0 || ny > m || !(!ok[nx][ny] && vis[nx][ny])) continue;
                // if (ny < sy) continue;
                // int id = m * (nx - 1) + ny;
                //fa[id] = f;
                mn[f] = min(mn[f], ny);
                mx[f] = max(mx[f], ny);
                q.emplace(nx, ny);
            }
        }
    };
    for (int j = 1; j <= m; ++j) {
        for (int i = 1; i <= n; ++i) {
            // debug(i, j);
            //cout << (!ok[i][j] && vis[i][j]) << "\n "[j != m];
            if (!ok[i][j] && vis[i][j] && !vis2[i][j]) {
                int id = m * (i - 1) + j;
                mn[id] = mx[id] = j;
                bfs(id, i, j);
            }
        }
    }
    // for (int i = 1; i <= n; ++i) {
    //     for (int j = 1; j <= m; ++j) {
    //         cout << vis2[i][j] << " \n"[j == m];
    //     }
    // }
    // debug(222);
    int flag = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int id = m * (i - 1) + j;
            int t = mx[id] - mn[id] + 1;
            // t = max<i64>(t, 0);
            // cout << t << " \n"[j == m];
            // cout << id << " \n"[j == m];
            if (t >= k) {
                //debug(i, j, t);
                flag = 0;
                break;
            }
        }
    }
    if (!ok[1][1]) flag = 0;
    assert(ok[1][1]);
    cout << (!flag ? "Yes" : "No") << "\n";
}

signed main() {
    
    FIO;
    TESTS {
        solve();
    }

    return 0;
}

/*

  _  _                            _____             _               _               _    
 | \| |    ___    _ _      ___   |_   _|    _ _    (_)    __ __    (_)    __ _     | |   
 | .` |   / _ \  | ' \    |___|    | |     | '_|   | |    \ V /    | |   / _` |    | |   
 |_|\_|   \___/  |_||_|   _____   _|_|_   _|_|_   _|_|_   _\_/_   _|_|_  \__,_|   _|_|_  
_|"""""|_|"""""|_|"""""|_|     |_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| 
"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-' 

(Font: ASCII - Train)

"El Psy Kongroo." -- Hououin Kyoma

"私は極色カスタ推しです...だが、狽音ウルシと夜鳴トバリも推す :)" -- Yukii_P

*/

D Determinant of 01-Matrix

有点意思的构造。但是不会做。思洋依旧力挽狂澜。

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i32 = int;
using i64 = long long;
using i128 = __int128;

template<typename T1,typename T2>
ostream& operator<<(ostream& o,const tuple<T1,T2>& t){
	return o<<"("<<get<0>(t)<<","<<get<1>(t)<<")";
}

template<typename T1,typename T2,typename T3>
ostream& operator<<(ostream& o,const tuple<T1,T2,T3>& t){
	return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";
}

template<typename T>
ostream& operator<<(ostream& o,const vector<T>& vec){
	for(int i=(o<<"[",0);i<vec.size();++i)o<<vec[i]<<(i+1<vec.size()?",":"");
	return o<<"]\n";
}

constexpr int M = 200, mod = 1e9+7;// 998244353;
constexpr double pi = acos(-1), eps = 1e-9;

void solve(){
	int n;
	cin>>n;
	if(n==1){
		cout<<"1\n1\n";
		return;
	}
	vector mat(M,vector<ll>(M));
	auto f=[&](int x,int y,ll z){
		for(int i=0;i<M;++i)mat[x][i]+=mat[y][i]*z;
	};
	auto g=[&](int x,int y,ll z){
		for(int i=0;i<M;++i)mat[i][x]+=mat[i][y]*z;
	};
	mat[0][0]=n;
	for(int i=1;i<M;++i)mat[i][i]=1;
	int s=0,t=M-1;
	while(n){
		int m=n>>1;
		f(0,s+1,m);
		g(s,s+1,-2);
		f(s+1,t,1);
		f(s+1,t-1,1);
		g(s,t,1);
		g(s,t-1,1);
		n=m,++s,----t;
	}
	cout<<M<<"\n";
	for(auto& i:mat){
		for(auto& j:i){
			cout<<j<<" ";
		}
		cout<<"\n";
	}
	
	return;
}

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

I I, Box

好像不难。还没补。