百度之星合集链接

初赛一

1 公园

三遍 dij 求最短

//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x, y, sizeof(x))
#define debug(x) cout << #x << " = " << x << '\n'
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << '\n'
#define int long long

using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
/*

*/
const int maxm = 4e4 + 5, mod = 998244353;
const ll inf = 1e10;
vector<int> e[maxm];
int te, fe, s, t, f, n, m;
vector<vector<ll>> dis;

void dij(int u, int c){
	dis[c][u] = 0;
	vector<bool> vis(n + 1, false);
	priority_queue<pii, vector<pii>, greater<pii>> q;
	for(auto v : e[u]){
		q.push({1, v});
	}
	while(!q.empty()){
		pii t = q.top(); q.pop();
		// debug2(t.first, t.second);
		if(vis[t.second]) continue;
		vis[t.second] = true;
		dis[c][t.second] = t.first;
		for(auto v : e[t.second]){
			if(!vis[v] && dis[c][v] > dis[c][t.second] + 1){
				q.push({dis[c][t.second] + 1, v});
			}
		}
	}
	return ;
}

void solve(){
	cin >> te >> fe >> s;
	cin >> t >> f >> n >> m;
	dis = vector<vector<ll>> (3, vector<ll> (n + 1, inf));
	for(int i = 0; i < m; ++ i){
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dij(t, 0);
	dij(f, 1);
	dij(n, 2);
	ll ans = inf;
	for(int i = 1; i <= n; ++ i){
		ans = min(ans, dis[0][i] * te + dis[1][i] * fe + dis[2][i] * (te + fe - s));
	}
	if(ans == inf) cout << "-1\n";
	else cout << ans << '\n';
	return ;
}

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

5 糖果促销

先买 1 糖果，接下来每次买 p - 1 个糖果即可再换出一个糖果，如此循环，不足 p - 1 个时单买

//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x, y, sizeof(x))
#define debug(x) cout << #x << " = " << x << '\n'
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << '\n'
#define int long long

using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
/*

*/
const int maxm = 2e5 + 5, inf = 0x3f3f3f3f, mod = 998244353;

void solve(){
	ll p, k;
	cin >> p >> k;
	if(k == 0){
		cout << "0\n";
		return ;
	}
	ll n = k / p, ans = 1;
	ll yu = k - n * p;
	if(yu) -- yu;
	ans = n * (p - 1) + yu + 1;
	cout << ans << '\n';
	return ;
}

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

8 除法游戏 - 还在理解中

nim 游戏改版，本题的关键在于怎么快速求出每堆石子的 sg 值
假设某堆石子数为 t

• 当 \(t = 2 ^ k\) 为 2 的幂次时，其仅能被划分为偶数堆，每堆石子数相等，易知这些石子堆异或的结果一定是 0，所以此时 \(sg(2^k) = 1\)
• 剩下的情况，如果划分为偶数堆时，sg 值异或和一定为0；那么最终影响 sg 值的仅有划分为奇数堆石子，又因为每次划分后的每堆石子均相等，那么划分为这一划分的 sg 值即为 \(sg(\frac{t}{p})\)，p 为奇数
  那其实就相当于，每次操作可以都可以从一堆石子中取出一些奇因子

那么，最终 \(sg(t) = \lfloor 2 | t \rfloor + cnt_{奇因子个数}\)

那么对于每一堆石子求出其 sg 值，再利用 sg 定理即可

下为代码

//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define lll __int128
#define ull unsigned long long
#define mem(x,y) memset(x, y, sizeof(x))
#define debug(x) cout << #x << " = " << x << '\n'
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << '\n'
//#define int long long

using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
/*

*/
const int maxn = 2e5 + 5, inf = 0x3f3f3f3f, mod = 998244353;

lll qmksm(ll a,ll b,ll m){
	lll s=1,z=a%m;
	while(b>0){
		if(b&1==1){
			s*=z;
			s%=m;
		}
		z*=z;
		z%=m;
		b>>=1;
	}
	return s;
}

bool millerrabin(ll n){
	if(n<3) return n==2;
	if(n%2==0) return 0;
	ll i,j,d=n-1,r=0,tss[8]={-1,2,325,9375,28178,450775,9780504,1795265022};
	while(d%2==0) d/=2,r++;
	for(i=1;i<=7;i++){
		lll zc=qmksm(tss[i],d,n);
		if(zc<=1 or zc==n-1) continue;
		for(j=0;j<=r-1;j++){
			zc=(zc%n*zc%n)%n;
			if(zc==n-1 and j!=r-1){
				zc=1;
				break;
			}
			if(zc==1) return 0;
		}
		if(zc!=1) return 0;
	}
	return 1;
}

int N = 1e4 + 5, cnt = 0;
vector<bool> isprime(N, true);//判断素数
vector<long long> prime;//存储素数
void pre(){
	long long t;
	isprime[1] = false;
	for(long long i = 2; i < N; ++ i){
		if(isprime[i]){
			prime.push_back(i);
			++ cnt;
		}
		for(int j = 0; j < cnt; ++ j){
			t = i * prime[j];
			if(t > N) break;
			isprime[t] = false;
			if(i % prime[j] == 0) break;
		}
	}
	return ;
}

void solve(){
	pre();
	int n;
	cin >> n;
	int sum = 0;
	for(int i = 0; i < n; ++ i){
		ll cur, c = 0;
		cin >> cur;
		if(cur % 2 == 0) c = 1;
		while(cur % 2 == 0) cur /= 2;
		for(int j = 0; j < cnt; ++ j){
			while(cur % prime[j] == 0){
				++ c;
				cur /= prime[j];
			}
		}
		if(cur != 1){
			++ c;
			if(!millerrabin(cur)) ++ c;
		}
		sum ^= c;
	}
	puts(sum ? "Xiaodu" : "Duduxiong");
	return ;
}

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