CSP-J2023 题解

#include <bits/stdc++.h>
using namespace std;

int n,ans;

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	for(int i = n; i; i -= (i+2)/3) ++ans;
	cout<<ans<<" ";
	for(int i = n, j = 1; i; i -= (i+2)/3, ++j) if( i % 3 == 1 ) { cout<<j; break; }
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define For(i,x,y,...) for(int i=(x),##__VA_ARGS__;i<=(y);++i)
typedef long long LL;
auto ckmin=[](auto &x,auto y) { return y<x ? x=y,true : false; };

const int N = 1e5+5;
int n;
LL d,ans,v[N],a[N];

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n>>d; For(i,2,n) cin>>v[i]; For(i,1,n) cin>>a[i];
	LL mn = a[1], rest = 0;
	For(i,2,n) {
		rest += v[i];
		LL x = (rest+d-1) / d;
		rest -= x * d, ans += mn * x;
		ckmin(mn,a[i]);
	}
	cout<<ans;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
template<typename T=int>T read() { T x; cin>>x; return x; }

int a,b,c,dlt;

pair<int,int> frac(int x,int y) {
	if( y < 0 ) x = -x, y = -y;
	int d = abs(__gcd(x,y));
	return make_pair(x/d,y/d);
}
void print(int x,int y) {
	tie(x,y) = frac(x,y);
	cout<<x;
	if( y != 1 ) cout<<"/"<<y;
}

void MAIN() {
	cin>>a>>b>>c; if( a < 0 ) a = -a, b = -b, c = -c;
	dlt = b*b-4*a*c;
	if( dlt < 0 ) cout<<"NO";
	else {
		int k = 0;
		for(int i = 1; i*i <= dlt; ++i) if( !(dlt % (i*i)) ) k = i;
		if( k*k == dlt ) print(-b+k,2*a);
		else {
			if( b ) print(-b,2*a), cout<<"+";
			int x,y; tie(x,y) = frac(k,2*a);
			if( x != 1 ) cout<<x<<"*";
			cout<<"sqrt("<<dlt/k/k<<")";
			if( y != 1 ) cout<<"/"<<y;
		}
	}
	cout<<'\n';
} signed main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int lft=read(); read(); while( lft-- ) {
		MAIN();
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define For(i,x,y,...) for(int i=(x),##__VA_ARGS__;i<=(y);++i)
#define pb emplace_back
#define sz(a) int((a).size())
typedef long long LL; typedef pair<int,int> Pii; typedef tuple<int,int,int> Tiii;

const int N = 1e4+5, inf = 0x3f3f3f3f;
int n,m,k,dis[N][105];
bitset<105> vis[N];
vector<pair<int,int>> e[N];
priority_queue<Tiii,vector<Tiii>,greater<Tiii>> pq;

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m>>k; For(i,1,m, x,y,z) cin>>x>>y>>z, e[x].pb(y,z);
	memset(dis,0x3f,sizeof dis);
	dis[1][0] = 0, pq.emplace(0,1,0);
	while( sz(pq) ) {
		int u = get<1>(pq.top()), x = get<2>(pq.top()); pq.pop();
		if( vis[u][x] ) continue; vis[u][x] = 1;
		for(auto [v,w] : e[u]) {
			int d = dis[u][x] + 1, y = (x + 1) % k;
			if( dis[u][x] < w ) d += (w-d+1+k-1) / k * k;
			if( d < dis[v][y] ) pq.emplace(dis[v][y]=d,v,y);
		}
	}
	cout<<(dis[n][0]<inf?dis[n][0]:-1);
	return 0;
}