2021,10,29 模拟赛题解报告

2023-12-27 14:15:57

T1 generals

题面

solution

二分+贪心

一个很显然的贪心，敌人都放在最后打一定比前面打了更优。

直接二分结束在哪个回合，然后 \(O(n)\) check 就好了。

复杂度 \(O(nlogn)\)

code

#include<bits/stdc++.h>
using namespace std;
const int MAXA = 1e4 + 5;
const int MAXB = 1e5 + 5;
const int MAXC = 1e6 + 5;
int read() {
  int x = 0, f = 1; char c = getchar();
  while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
  while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
  return x * f;
}
int n, m, d[MAXB], a[MAXB], Ans = -1, vis[MAXB], fag[MAXB];
bool Check(int mid) {
  memset(vis, 0, sizeof vis);
  memset(fag, 0, sizeof fag);
  for (int i = mid; i >= 1; i--) {
  	if(vis[d[i]]) continue;	
	else vis[d[i]] = i, fag[i] = d[i];
  }
  for (int i = 1; i <= m; i++) 
  	 if(!vis[i]) return false;
  int ret = 0;
  for (int i = 1; i <= mid; i++){
    if(fag[i]) {
      if(ret < a[fag[i]]) return false;
      else ret -= a[fag[i]];
	}
	else ret++;
  }
  return true;
}
int main() {
   n = read(), m = read();
   for (int i = 1; i <= n; i++) d[i] = read();
   for (int i = 1; i <= m; i++) a[i] = read();
   int l = 1, r = n;
   while (l <= r) {
   	 int mid = (l + r) >> 1;
   	 if(Check(mid)) Ans = mid, r = mid - 1;
   	 else l = mid + 1;
   }
   cout<<Ans;
   return 0;
}

T2 function

题面

T2

给定 \(x\) , 求 \(f(x)\)

求 \(f(x) = \begin{cases} 0, x = 1\\f(\phi(x)) + 1 \end{cases}\)

solution

你会发现，答案就是把 \(x\) 一直取 \(\phi\) 直到为 \(1\) 的次数。

设 \(x = \prod_{i = 1}^{m} p_i^{q_i}\)

其中 \(p_i\) 为质数（也就是将它质因数分解）

因为 \(\phi(x) = x \prod_{i = 1}^{m} \frac{p_i - 1}{p_i}\)

把 \(x = \prod_{i = 1}^{m} p_i^{q_i}\) 代进去得到：

\(\phi(x) = \prod_{i = 1}^{m} p_i^{q_i - 1} \times (p_i - 1)\)

观察这个柿子：

发现每次取 \(\phi\) 就可以等价于把 \(x\) 质因数分解后，每个质因数的幂 \(-1\) ，同时产生一个 \(p_i - 1\)；

当 \(p_i \neq 2\) 时：

因为质数除了 2 都是奇数，如果不是 2 的话， \(p_i - 1\) 一定是个偶数，所以 \(p_i - 1\) 一定可以分解为 \(2\times y\) 的形式放到里面，所以向里面添加了至少一个 \(2\)。

当 \(p_i = 2\) 时：

因为 \(2^{q_i} \rightarrow 2^{q_i - 1}\times 1\)

所以相当在质因数分解中减掉一个 2 。

因为每轮最多减掉一个 \(2\)，所以求出所有数能产生 \(2\) 的个数，就是答案。

注意如果 \(x\) 是奇数的话，答案要 \(+1\) ，因为第一轮没有 \(2\) 可以减。

求 \(2\) 的个数可以 \(O(n)\) 递推来实现，也可以 \(O(\sqrt n)\) 直接实现。

递推原理：

是质数的时候 \(\phi(i) = i-1\), 所以 \(f_i = f_{i-1}\) 不是质数的时候因为 \(Min_i * (i / Min_i) = i\), 所以 \(f_i = f_{Min_i} + f_{i / Min_i}\)

#include<bits/stdc++.h>
using namespace std;
const int MAXA = 1e4 + 5;
const int MAXB = 1e5 + 5;
const int MAXC = 1e6 + 5;
int read() {
  int x = 0, f = 1; char c = getchar();
  while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
  while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
  return x * f;
}
int f[MAXC], tot, Min[MAXC], prime[MAXC];
bool vis[MAXC];
void Init(){
   vis[1] = 1;
   for (int i = 2; i <= MAXC; i++) {
   	  if(!vis[i]) prime[++tot] = i;
   	  for (int j = 1; j <= tot && i * prime[j] <= MAXC; j++){
   	     vis[i * prime[j]] = 1;
	     Min[i * prime[j]] = prime[j];
		 if(i % prime[j] == 0) break;	
	  }
   }
   f[2] = 1;
   for (int i = 3; i <= MAXC; i++) {
   	  if(!vis[i])  f[i] = f[i - 1];
   	  else f[i] = f[Min[i]] + f[i / Min[i]];
   }
}
int T, n, add;
long long Ans;
int main() {
   Init();
   T = read();
   while(T--) {
   	 n = read();
   	 add = 1, Ans = 0;
   	 for (int i = 1; i <= n; i++) {
   	   int p = read(), q = read();
	   Ans = Ans + f[p] * q;
	   if(p == 2) add = 0;	 
	 }
	 printf("%lld\n", Ans + add);
   }
   return 0;
}

T3 （CF618E Robot Arm）

题面

solution

以下是题解：

考虑用线段树维护每条线段所对应的向量（即终点和起点的相对位置）。

由于向量可以平移，那么就先将所有线段的起点平移到原点，设平移后终点坐标为 \((x,y)\)。

对于操作 \(1\)，由相似，有：

\[\begin{cases} \frac{l}{\sqrt{x^2 + y^2}} = \frac{\Delta x}{x}\\ \frac{l}{\sqrt{x^2 + y^2}} = \frac{\Delta y}{y}\\ \end{cases} \]

得到

\[\Delta x = \frac{lx}{\sqrt{x^2 + y^2}} \Delta y = \frac{ly}{\sqrt{x^2 + y^2}} \]

所以直接将第 \(i\) 条线段的向量分别加上 \(\Delta x\), \(\Delta y\) 即可，直接在线段树上单点修改。

对于操作 \(2\)，先将给出的角度制转化为弧度制，设第 \(i\) 条线段原来相对于坐标轴的角度为 \(\theta\)，由三角恒等变换，有：

\(x' = \sqrt{x^2 + y^2} cos(\theta - \alpha)\)

\(y' = \sqrt{x^2 + y^2} sin(\theta - \alpha)\)

得到

\(x' = x ~cos ~\alpha + y~sin~\alpha\)

\(y' = y ~cos ~\alpha - x~sin~\alpha\)

在线段树上打一个旋转角的 \(\text{lazy tag}\)，对于第 \(i\sim n\) 条线段区间修改即可。

由于向量可以平移，那么将每次操作后得到的线段重新收尾相接相对位置不变，且最后一条线段终点坐标为所有向量相加。

每次答案即为线段树根节点的值。

复杂度：\(O(mlogn)\)

code

#include<bits/stdc++.h>
using namespace std;
const int MAXA = 1e4 + 5;
const int MAXB = 3e5 + 5;
const int MAXC = 1e6 + 5;
const double pi = acos(-1);
int read() {
  int x = 0, f = 1; char c = getchar();
  while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
  while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
  return x * f;
}
int n, m;
namespace Seg{
   #define ls rt << 1
   #define rs rt << 1 | 1
   struct Tree{
     double Sumx, Sumy, lzy;
   }T[MAXB << 2];
   void push_up(int rt) {
   	 T[rt].Sumx = T[ls].Sumx + T[rs].Sumx;
   	 T[rt].Sumy = T[ls].Sumy + T[rs].Sumy;
   }
   void build(int rt, int l, int r) {
   	  if(l == r) {
	     T[rt].Sumx = 1, T[rt].Sumy = 0, T[rt].lzy = 0;
	     return ;
	  }
	  int mid = (l + r) >> 1; 
	  build(ls, l, mid), build(rs, mid + 1, r);
      push_up(rt);
   }
   void push_down(int rt) {
   	  if(!T[rt].lzy) return ;
   	  double tag = T[rt].lzy;
   	  double sumx = T[ls].Sumx, sumy = T[ls].Sumy;
   	  T[ls].Sumx = sumx * cos(tag) + sumy * sin(tag);
   	  T[ls].Sumy = sumy * cos(tag) - sumx * sin(tag);
   	  sumx = T[rs].Sumx, sumy = T[rs].Sumy;
   	  T[rs].Sumx = sumx * cos(tag) + sumy * sin(tag);
   	  T[rs].Sumy = sumy * cos(tag) - sumx * sin(tag);
	  T[ls].lzy += T[rt].lzy, T[rs].lzy += T[rt].lzy;
	  T[rt].lzy = 0;
   } 
   void Modify(int rt, int l, int r, int pos, double x, double y) {
   	  if(l == r) {
	    T[rt].Sumx += x, T[rt].Sumy += y;
	    return ;
	  }
	  push_down(rt);
	  int mid = (l + r) >> 1;
	  if(pos <= mid) Modify(ls, l, mid, pos, x, y);
	  if(pos > mid) Modify(rs, mid + 1, r, pos, x, y);
	  push_up(rt);
   }
   void update(int rt, int l, int r, int L, int R, double k) {
      if(L <= l && r <= R) { 
        double sumx = T[rt].Sumx, sumy = T[rt].Sumy;
       	T[rt].Sumx = sumx * cos(k) + sumy * sin(k);
   	    T[rt].Sumy = sumy * cos(k) - sumx * sin(k);
		T[rt].lzy += k;
		return;
	  } 
	  int mid = (l + r) >> 1;
	  push_down(rt);
	  if(L <= mid) update(ls, l, mid, L, R, k);
	  if(R > mid) update(rs, mid + 1, r, L, R, k);
	  push_up(rt);
   }
   Tree Query(int rt, int l, int r, int pos) {
   	  if(l == r) return T[rt];
   	  int mid = (l + r) >> 1;
	  push_down(rt);
	  if(pos <= mid) return Query(ls, l, mid, pos);
	  else return Query(rs, mid + 1, r, pos); 
   }  
}
using namespace Seg;
int main() {
   n = read(), m = read();
   build(1, 1, n);
   for (int i = 1; i <= m; i++) {
   	 int opt = read(), a = read(), b = read();
   	 if(opt == 1) {
   	    Tree now = Query(1, 1, n, a);
	    double l = sqrt(now.Sumx * now.Sumx + now.Sumy * now.Sumy);
	    Modify(1, 1, n, a, now.Sumx * 1.0 * b / l, now.Sumy * 1.0 * b / l);
	 }
	 if(opt == 2) {
	 	update(1, 1, n, a, n, 1.0 * b * pi / 180.0);
	 }
     printf("%.10lf %.10lf\n", T[1].Sumx, T[1].Sumy);
   } 
   return 0;
}

码农公寓

T1 generals

T2 function

T2

T3 （CF618E Robot Arm）

相关文章