apple

#include<bits/stdc++.h>
using namespace std;
//数学+模拟
int main() 
{
	int n;
	cin >> n;
	if (n <= 3) 
	{
    	cout << n << " " << n << endl;
    	return 0;
  	}
  	
  	int day = 0, ans = 0;
  	while (n > 3) 
	{
    	day ++ ;
    	if (!ans && n % 3 == 1) ans = day;
    	n -= ceil(n * 1.0 / 3);
    	if (n <= 3) 
		{
      		day += n;
      		if (!ans) ans = day;
      		break;
    	}
 	}
 	
  	cout << day << " " << ans << endl;
 
   	return 0;
}

road

#include<bits/stdc++.h>
using namespace std;
/*解法：贪心+模拟-时间复杂度-O(n)-100pts*/
#define int long long
const int N = 1e5 + 10;
int s[N];//距离的前缀和数组-用于求解任意两点间的距离
int p[N];//每个站点对应的油价price
signed main() 
{
  	int n, d;
  	cin >> n >> d;
  	for (int i = 2; i <= n; i ++ ) 
	{
    	int v;
		cin >> v;
    	s[i] = s[i - 1] + v;//预处理距离的前缀和
  	}
  	for (int i = 1; i <= n; i ++ )
	  	cin >> p[i];

  	//处理油价的降序序列
  	vector<int> ds;
	ds.push_back(1);
  	int minv = p[1];
  	for (int i = 2; i <= n; i ++ ) 
  	{
  		if (p[i] < minv) 
	 	{
  	   	 	minv = p[i];
  	   	 	ds.push_back(i);
  	  	}
 	}

 	if (ds[ds.size() - 1] != n) ds.push_back(n);

 	int l_dist = 0/*剩余距离*/, ans = 0;
 	 //沿着油价的降序序列进行贪心+模拟
  	for (int i = 0; i < ds.size() - 1; i ++ ) 
 	{
 	   	int r_dist = s[ds[i + 1]] - s[ds[i]];//相邻两点间的距离
 	   	if (r_dist < l_dist) l_dist -= r_dist;
 	   	else 
		{
  	   		 r_dist -= l_dist;
  	    	int nums = ceil(r_dist * 1.0 / d);//针对当前距离需要买多少升油
   	   		ans += p[ds[i]] * nums;
   	   		l_dist = nums * d - r_dist;
  	  	}
 	}
	cout << ans << endl;
    return 0;
}

uqe

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

int t, m;
//最大公约数，约分时候使用
int gcd(int a, int b) 
{
  return b == 0 ? a : gcd(b, a % b);
}

int main() 
{
  	cin >> t >> m;
  	while (t--) 
  	{
    	int a, b, c;
		cin >> a >> b >> c;
	    int delta = b * b - 4 * a * c;
	    //若delta<0，方程无实数解，输出NO
	    if (delta < 0) 
		{
	      cout << "NO" << endl;
	      continue;
	    }
	    //delta>=0，方程有两个解分别为x1,x2，a的符号不同，则两者中较大的不同
	    //x的通用表示为x=p/q+sqr_del/q
	    int sqr_del = 1;
    	//求根号delta->sqr_del
	    for (int i = 2; i * i <= delta; i ++ ) 
		{
	      while (delta % (i * i) == 0)
	        sqr_del *= i, delta /= i * i;
	    }
	    int p = -b, q = 2 * a;
	    if (q < 0) q = -q, p = -p;
	    //如果sqr_del是整数，那么p需要加上sqr_del
	    if (delta == 1) delta = 0, p += sqr_del;
	    //x=p/q+sqr_del/q,考虑约分，需要分别求p,q和sqr_del，q的最大公约数g1,g2
	    int g1 = gcd(abs(p), q), g2 = gcd(sqr_del, q);
	    //如果sqr_del是整数那么答案为p/q
	    if (delta == 0) 
		{
	      if (p % q == 0) cout << p / q;
	      else cout << p / g1 << "/" << q / g1;//约分
	    }
	    //如果sqr_del不是整数，则需要分别处理p/q和sqr_del/q
	    else 
		{
	      if (p != 0) 
		  {
	        if (p % q == 0) cout << p / q;
	        else cout << p / g1 << "/" << q / g1;//约分
	        cout << "+";
	      }
	      
	      if (sqr_del / g2 != 1) cout << sqr_del / g2 << "*";
	      cout << "sqrt(" << delta << ")";
	      if (q / g2 != 1) cout << "/" << q / g2;
		}
    cout << endl;
  	}
  	return 0;
}

bus

#include<bits/stdc++.h>
using namespace std;
//解法2：每个点到达时间按照对k取余进行分类构建k层分层图，使用堆优化dijkstra跑分层图的最短路，时间复杂度-O（nk*log(nk)）
const int N = 1e6 + 10;
vector<pair<int, int>> g[N];//邻接表
int min_dis [N];//最短路数组-最短到达时间

int main() 
{
	int n, m, k;  
  	cin >> n >> m >> k;
  	for (int i = 1; i <= m; i ++ ) 
  	{
	    int u, v, a;  
		cin >> u >> v >> a;
	    for (int j = 0; j < k; j ++ ) 
		{
	      //构建k层分层图，每个点到达时间按照对k取余进行分类
	      g[j * n + u].push_back({(j + 1) % k * n + v, a});
	    }
  	}
  	//初始化最短路数组 
  	for (int i = 1; i <= n * k; i ++ ) min_dis[i] = 1e9;

  	//用堆优化dijkstra跑分层图求最短路
  	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  	min_dis[1] = 0; 
    pq.push({0,1});

  	while (!pq.empty()) 
  	{
	    int t = pq.top().first, cur = pq.top().second;
		pq.pop();
	    if (t <= min_dis[cur]) 
		{
	      	for (auto e : g[cur]) 
		  	{
		        int tmp = min_dis[cur] + 1;
		        //如果到达当前节点的时刻小于当前节点的开放时间，则重置使满足条件的最早到达时间
		        if (min_dis[cur] < e.second) tmp += ceil((e.second - min_dis[cur]) * 1.0 / k) * k;
		        //更新最短路数组
		        if (tmp < min_dis[e.first]) 
				{
		          min_dis[e.first] = tmp;
		          pq.push({ min_dis[e.first],e.first });
		        }
      		}
    	}
  	}
  	if (min_dis[n] == 1e9) cout << "-1" << endl;
	else cout << min_dis[n] << endl;
	return 0;
}