CSP-J2023年复赛

P9748 [CSP-J 2023] 小苹果

Code 

#include<iostream>
#include<cmath>
using namespace std;
int n , ans , sum;
int main(){cin >> n;while(n){sum ++;if(n % 3 == 1 && !ans) ans = sum;n -= ceil(n / 3.0);}cout << sum << " " << ans << endl;return 0;
}

P9749 [CSP-J 2023] 公路

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+100;
int n , d , v[N] , a[N];
int main(){cin >> n >> d;for(int i = 1; i < n; i ++) cin >> v[i];for(int i = 1; i <= n; i ++) cin >> a[i];int i = 1;double r = 0;long long ans = 0;while(i < n){int j = i + 1;double s = 0;while(!(j == n || a[j] < a[i])){s += v[j - 1];++ j;}s += v[j - 1];int x = ceil(s / d - r);ans += a[i] * 1LL * x;i = j;r = r + x - s / d;if (j == n) break;}cout << ans ;return 0;
} 

P9750 [CSP-J 2023] 一元二次方程

Code

#include<iostream>
#include<cmath>
using namespace std;
int t , m;
int gcd(int a , int b){return b == 0 ? a : gcd(b , a % b);} int main(){
//	freopen("in.txt" , "r" , stdin);
//	freopen("out.txt" , "w" , stdout);cin >> t >> m;while(t --){int a , b , c;cin >> a >> b >> c;int lop = b * b - 4 * a * c;if(lop < 0){cout << "NO" << endl;}else if(lop == 0){/*-b / 2a  */int x = gcd(abs(b) , abs(2 * a));if(b == 0) cout << "0" << endl;else{if(a * b > 0) cout << "-";b = abs(b) / x;a = abs(2 * a) / x;if(a == 1) cout << b << endl;else cout << b << "/" << a << endl;}}else if (lop > 0){// sqrt(dt) * kint k = 1;for(int i = 2 ; i * i <= lop; i ++){while(lop % (i * i) == 0){k *= i;lop /= (i * i);}}if(lop == 1){ // (-b / 2a + k / 2a) if(a < 0){b = -b - k;a = 2 * a;}else if (a > 0){b = -b + k;a = 2 * a;}// b / aif(a * b == 0){cout << 0 << endl;continue;}if(a * b < 0) cout << "-";int x = gcd(abs(b) , abs(a));b = abs(b) / x;a = abs(a) / x;if(a == 1) cout << b << endl;else cout << b << "/" << a << endl;}else{// -b/2a + k * sqrt(lop) / 2aint A = abs(a * 2);a = 2 * a;int x = gcd(abs(b) , abs(a));if(a * b < 0){b = abs(b) / x;a = abs(a) / x;if(a == 1) cout << b;else cout << b << "/" << a;}else if(a * b > 0){cout << "-";b = abs(b) / x;	a = abs(a) / x;if(a == 1) cout << b;else cout << b << "/" << a;}else if(a * b == 0){}if(b != 0) cout << "+"; // k * sqrt(lop) / Aint y = gcd(k , A);k /= y;A /= y;if(k != 1) printf("%d*sqrt(%d)" , k , lop);else printf("sqrt(%d)" , lop);if(A != 1) cout << "/" << A << endl;else cout << endl;}}}return 0;
}

P9751 [CSP-J 2023] 旅游巴士

Code

#include<iostream>
#include<vector>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int , int> PII;
const int N = 1e4 + 110;
int n , m , k;
int dp[N][150] , vis[N][150];
struct e{int v , w;e(int v , int w):v(v) , w(w){}};vector<e> g[N];
int main(){cin >> n >> m >> k;for(int i = 1; i <= m; i ++){int u , v , w;cin >> u >> v >> w;g[u].push_back(e(v , w));}memset(dp , 0x3f3f3f3f , sizeof dp);dp[1][0] = 0;priority_queue<PII> q;q.push(make_pair(0 , 1));while(!q.empty()){int u = q.top().second , d = abs(q.top().first); q.pop();if(vis[u][d % k]) continue;vis[u][d % k] = 1;int j = d % k;for(int i = 0; i < g[u].size(); i ++){int v = g[u][i].v , a = g[u][i].w;if(d >= a){if(dp[u][j] + 1 < dp[v][(j + 1) % k]){dp[v][(j + 1) % k] = dp[u][j] + 1;q.push(make_pair(-dp[v][(j + 1) % k] , v));}}else{int w = ceil((a - dp[u][j]) * 1.0 / k);if(dp[u][j] + w * k + 1 < dp[v][(j + 1) % k]){dp[v][(j + 1) % k] = dp[u][j] + w * k + 1;q.push(make_pair(-dp[v][(j + 1) % k] , v));}}}}if(dp[n][0] == 0x3f3f3f3f) cout << "-1";else cout << dp[n][0];return 0;
}