2018CCPC吉林总结

文章目录

2018 CCPC 吉林
- A
  - 题意
  - 分析
- B
  - 分析
- C
  - 题意
  - 分析
- D
  - 题意
  - 分析
- E
  - 题意
  - 分析
- F
- H Lovers

2018 CCPC 吉林

A

题意

求 $\sum_{i}^{n} ⌊ \frac{n}{i} ⌋$ 的奇偶性

分析

分块求和的经典题目，kuangbin数论专题十四G - Harmonic Number (II)

B

题意略，

分析

模拟题，转换成分钟，各种处理时间的技巧

C

题意

给定一个序列 $k_{1}, k_{2}, k_{3} . . . k_{n}$ 其中 $k_{i}$ 代表的值是 $2^{k_{i}}$ ，要求把这k个数分成两堆，使得每一堆的值都大于1/2

分析

利用二进制的原理，优先队列+并查集，先取出权值最小的，进行合并，如果两个值相同，则可以合并成一个k-1,最后判断是否有两个或两个以上的1出现即可


#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define FI first
#define SE second
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define IOS ios::sync_with_stdio(false)
#define DEBUG cout<<endl<<"DEBUG"<<endl; 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<int,int> P;
const int maxn = 1e5+10;
int a[maxn];
int F[maxn];
int Find(int x){
   return x == F[x]?x:F[x] = Find(F[x]);
}
int main(void)
{
  int T;cin>>T;
  int kase =0;
  while(T--){
  	
  	int n;cin>>n;

  	for(int i = 1;i <= n; ++i)
  		F[i] = i;
  	for(int i = 1;i <= n; ++i)
  		scanf("%d",&a[i]);
  	priority_queue<P>Q;
  	for(int i = 1;i <= n; ++i)
  		Q.push(P(a[i],i));

  	while(!Q.empty()&&Q.top().first > 1){
  		P p = Q.top(); Q.pop();
  		if(p.first != Q.top().first){
  			continue;
  		}
  		if(Q.empty()) break;
  		P p2 = Q.top();Q.pop();
  		int x = Find(p.second);
  		int y = Find(p2.second);
  		if(x < y)
  			swap(x,y);
  		F[x] = y;
  		Q.push(P(p.first-1,y));
  	}
  	printf("Case %d: ",++kase);
  	if(Q.size() < 2)
  		puts("NO");
  	else{
  		puts("YES");
  		for(int i = 1;i <= n; ++i){
  			int x = Find(i);
  			printf("%c",x == Q.top().second?'1':'0');
  		}
  		puts("");
  	}
  }    

  return 0;
}

/* 3 6 2 100 2 2 100 2 */

D

D和F的顺序记不清了，记错改一下

题意

先说游戏：

$q = 2 %$
玩一局游戏获胜概率是 $p %$ ，如果没获胜， $q = q + 1.5 %$ ，继续游戏。
如果获胜，进行抽奖，抽中的概率是 $q %$
如果抽中游戏停止
如果没抽中， $q = q + 2 %$ ，继续游戏
给定p，求玩游戏轮数的期望

分析

先求Q=100%的期望是1/p,错位相减自己推导，dp[100] = 1/p;
初始化 $d p [i] = 0$
状态转移方程，如果游戏没赢 $d p [i] = p * (i / 100 + (1 - i / 100) * (1 + d p [m i n (i + 2, 100)]))$
如果游戏赢了 $d p [i] = d p [i] + (1 - p) * (1 + d p [m i n (i + 1.5, 100)])$
其中i代表p*100，表示当前抽中的概率，dp[i] 代表如果起始抽中概率是i/100,轮数的期望是多少，dp[2] 就是所求答案

E

题意

给出三维空间起始点 $x_{0}, y_{0}, z_{0} <mtext> </mtext> (z_{0} > 0)$ ，给出方向矢量 $v_{x}, v_{y}, v_{z}$ ，求与圆锥相交的时间，圆锥底面圆的圆心在x,y平面的坐标原点，半径r，高 h，

分析

射线方程
$x = x_{0} + v_{x}$
$y = y_{0} + v_{y}$
$z = z_{0} + v_{z}$
圆锥侧面方程

$\frac{\sqrt{x^{2} + y^{2}}}{r} = \frac{h - z}{h}$
计算几何，联立求解圆锥方程和直线方程，求出t，注意特殊情况就ok了
注意判断增根， $0 < = z < = h, x^{2} + y^{2} < = r^{2}$

F

***题 $a n s = \sum_{i = 1}^{n} (r_{i} - 2)$

H Lovers

题意：
修改：将l,r 的所有字符串执行修改，在前后都加一个字符
查询：查询l,r 的和
分析：
我们发现这个修改操作满足可加行，两次修改可以合并成一个，类似区间加，用线段树维护以下value：
$s u m [o]$ 代表区间 $[l, r]$ 的和
$k 10$ 代表 $k 10 = \sum_{i \in [l, r]} 2^{l e n_{i}}$
修改可以看做分解
$a d d l e f t = 左边加的部分$
$a d d r i g h t = 右边加的部分$
$a d d l e n = 加入字符串的个数$
然后按照相应规则进行更新
例如：只加入一个字符

		tree[o].addleft 	= (v * pow10[tree[o].addlen] + tree[o].addleft) % mod;
		tree[o].addright  	= (tree[o].addright * 10 + v) % mod;
		tree[o].addlen 		+= 1;

		tree[o].sum = ( tree[o].sum * 10 + tree[o].k10 * v%mod * 10 + v * (r - l + 1)) % mod;
		// cout << tree[o].sum << endl;
		tree[o].k10 = (tree[o].k10 * 100) % mod;

参考代码


#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define FI first
#define SE second
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define IOS ios::sync_with_stdio(false)
#define DEBUG cout<<endl<<"DEBUG"<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
// const int INF = 0x7FFFFFFF;
const LL     INFF = 0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
LL qpow(LL a, LL b) {LL s = 1; while (b > 0) {if (b & 1)s = s * a % mod; a = a * a % mod; b >>= 1;} return s;}
LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
int dr[2][4] = {1, -1, 0, 0, 0, 0, -1, 1};
typedef pair<int, int> P;
#define lson (o << 1)
#define rson (o << 1|1)
const int maxn = 1e5 + 10;
const int INF = 1e9;
typedef long long LL;
LL pow10[maxn * 3];
struct Tree {
	LL sum, k10, addleft, addright, addlen;
	int l, r;
};
Tree tree[maxn << 2];
void pushup(int o, int l, int r) {
	tree[o].sum = (tree[lson].sum + tree[rson].sum) % mod;
	tree[o].k10 =  (tree[lson].k10 + tree[rson].k10) % mod;
}
void Add(Tree &b, Tree &a) {
	b.sum = ( b.sum * pow10[ a.addlen] + a.addleft * b.k10%mod * pow10[a.addlen] + a.addright * (b.r - b.l + 1)) % mod;
	b.k10 = (b.k10 * pow10[2 * a.addlen]) % mod;

	b.addleft = (b.addleft + a.addleft * pow10[b.addlen]) % mod;
	b.addright = (b.addright * pow10[a.addlen] + a.addright) % mod;
	b.addlen = b.addlen + a.addlen;
}

void pushdown(int o, int l, int r) {
	if (tree[o].addlen > 0) {
		Add(tree[lson], tree[o]);
		Add(tree[rson], tree[o]);
		tree[o].addlen = tree[o].addright = tree[o].addleft = 0;
	}
}
void up(Tree & a, Tree b) {
	a.sum = (a.sum + b.sum) % mod;
}
void build(int o, int l, int r) {
	tree[o].l = l;
	tree[o].r = r;
	// cout<<l<<" "<<r<<endl;
	// tree[o].add = 0;
	tree[o].k10 = (r - l + 1);
	if (l == r)
	{
		tree[o].sum = tree[o].addright = tree[o].addleft = tree[o].addlen = 0;
		// cout<<l <<" "<<a[l]<<endl;
	}
	else {
		int m = (l + r) >> 1;
		build(lson, l, m);
		build(rson, m + 1, r);
	}
}
void Update(int o, int l, int r, int L, int R, int v) {
	// cout << tree[o].k10 << endl;
	if (L <= l && R >= r) {
		tree[o].addleft 	= (v * pow10[tree[o].addlen] + tree[o].addleft) % mod;
		tree[o].addright  	= (tree[o].addright * 10 + v) % mod;
		tree[o].addlen 		+= 1;

		tree[o].sum = ( tree[o].sum * 10 + tree[o].k10 * v%mod * 10 + v * (r - l + 1)) % mod;
		// cout << tree[o].sum << endl;
		tree[o].k10 = (tree[o].k10 * 100) % mod;
		return ;
	}
	pushdown(o, l, r);
	int m = (l + r) / 2;
	if (L <= m)
		Update(lson, l, m, L, R, v);
	if (R > m)
		Update(rson, m + 1, r, L, R, v);
	pushup(o, l, r);
}
Tree Query(int o, int l, int r, int L, int R) {

	if (L <= l && R >= r)
	{
		return tree[o];
	}
	Tree tmp;
	tmp.sum = 0;
	pushdown(o, l, r);
	int m = (l + r) >> 1;
	if (L <= m)
		up(tmp, Query(lson, l, m, L, R));
	if (R > m)
		up(tmp, Query(rson, m + 1, r, L, R));
	// cout<<tmp.sum<<endl;
	return tmp;
}
int n, m;
// char
int main(void) {
	pow10[0] = 1;
	for (int i = 1; i < maxn * 3; ++i)
		pow10[i] = pow10[i - 1] * 10 % mod;
	// cout << pow10[2] << endl;
	int T; cin >> T;
	int kase = 0;
	while (T--) {
		printf("Case %d:\n", ++kase);
		cin >> n >> m;
		me(tree);
		build(1, 1, n);
		while (m--) {
			char op[10];
			int l, r, d;
			scanf("%s%d%d", op, &l, &r);
			if (op[0] == 'w') {
				scanf("%d", &d);
				Update(1, 1, n, l, r, d);
			}
			else {
				printf("%lld\n", Query(1, 1, n, l, r).sum);
			}
		}
	}


	return 0;
}

/* 2 3 4 wrap 1 1 1 wrap 1 2 1 wrap 1 3 1 query 1 3 2 4 4 wrap 1 3 0 wrap 2 4 3 query 1 4 query 2 3 */