目录
初赛一
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 值
下为代码
//>>>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;
}