首页 > 编程语言 >2023“钉耙编程”中国大学生算法设计超级联赛(5)

2023“钉耙编程”中国大学生算法设计超级联赛(5)

时间:2023-09-10 15:25:11浏览次数:46  
标签:钉耙 const point int 编程 st ++ 2023 return

1001 Typhoon

题意:

给你台风的轨迹坐标以及避难所的坐标,台风的半径不可预测,求让每个避难所不安全的最小台风半径是多少。

分析:

枚举每个点到所有“线段”的距离取个min。

代码:

附上队友的代码(懒):

#include <bits/stdc++.h>
#include <math.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
const double eps=1e-8;
int precision_cmp(double x){
	if(x<eps&&x>-eps) return 0;
	if(x>0) return 1;
	return -1;
}
#ifndef POINT_H
#define POINT_H

struct point { 	/*以向量的形式表示*/
	double x,y;
	point() {}
	point(double a,double b): x(a),y(b) {}
	void input() {
		scanf("%lf %lf",&x,&y);
	}
	friend point operator + (const point &a,const point &b) {
		return point(a.x+b.x,a.y+b.y);
	}
	friend bool operator == (const point &a,const point &b) {
		return precision_cmp(a.x-b.x)==0&&precision_cmp(a.y-b.y)==0;
	}
	friend point operator -(const point &a,const point &b) {
		return point(a.x-b.x,a.y-b.y);
	}
	friend point operator *(const point &a,const double b) {
		return point(a.x*b,a.y*b);
	}
	friend point operator *(const double a,const point b) {
		return point(a*b.x,a*b.y);
	}
	friend point operator /(const point &a,const double b) {
		return point(a.x/b,a.y/b);
	}
	
	double norm(){//这里为欧氏范数 
		return sqrt(x*x+y*y);
	}
	
	double modulus(){//模长 据知乎上的一篇文章说,modulus一词源于拉丁语"unit of measure",指测量的单位. 
		return sqrt(x*x+y*y);
	}
};

double det(const point &a,const point &b){//叉积  A到B逆时针为正,顺时针为负 
	return a.x*b.y-b.x*a.y;
}

double dot(const point &a,const point &b){//点积 
	return a.x*b.x+a.y*b.y;
}

double dist(const point &a,const point &b){
	return (a-b).norm();
}

double cross(point a,point b,point c){//ab与ac的叉积 
	return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

point rotate_point(const point &a,const double A){//向量旋转 
	double tx=a.x,ty=a.y;
	return point(tx*cos(A)-ty*sin(A),tx*sin(A)+ty*cos(A));
}
#endif

using namespace std;
double dis(point a,point b,point c){
	point r=point(b.x-a.x,b.y-a.y);
	point q=point(c.x-a.x,c.y-a.y);
	point p=point(c.x-b.x,c.y-b.y);
	if(dot(p,r)*dot(p,q)<0){
		return abs(det(p,q)/p.modulus());
	}
	else return min(r.modulus(),q.modulus());
	
}
int main(){
	int m,n;
	scanf("%d %d",&m,&n);
	double x,y;
	point p[m+1],s[n+1];
	rep(i,1,m){
		scanf("%lf %lf",&x,&y);
		p[i]=point(x,y);
	}
	rep(i,1,n){
		cin>>x>>y;
		s[i]=point(x,y);
	}
	double ans[n+1];
	for(int i=n;i>=1;i--){
		ans[i]=999999999;
		rep(j,1,m-1){
			ans[i]=min(dis(s[i],p[j],p[j+1]),ans[i]);
		}
	}
	rep(i,1,n){
		printf("%.4lf\n",ans[i]);
	}
}

1003 String Magic (Easy Version)

题意:

给定一个长度为n的字符串,编号1-n,求满足条件的区间(i, j)的数量:
①1 ≤ i < j ≤ n
②j − i + 1 = 2k, k > 0(即区间长度为大于0的偶数)
③S[i, i + k − 1] = S[i + k, j] (左半段字符串和右半段相同)
④S[i, i + k − 1]是回文串

分析:

根据题目要求,我们实际要求的是满足如下条件的子串s数量:
①s是长度为偶数的回文串
②s的左半段也是回文串
根据manacher算法可知中心点为"#"的回文串满足条件1。
现在考虑条件2:
设s的对称中心为i,最长回文半径为r。对称中心j分布在[(i + (i - r + 1)) / 2, i - 1]内(设他的最长回文半径r2),且j + r2 - 1 ≥ i的子串满足条件2。
综上,我们可以枚举回文中心点"#"的位置i,通过计算区间[(i + (i - r + 1)) / 2, i - 1]内满足j + r2 - 1 ≥ i的对称中心点的数量即可求出以i为对称中心的对称回文子串s的数量。
现在问题在于如何求出区间[(i + (i - r + 1)) / 2, i - 1]内满足j + r2 - 1 ≥ i的对称中心点的数量。很容易想到前缀和,用[1, i - 1]内满足条件的数量减去[1, (i + (i - r + 1)) / 2]满足条件的数量,因此我们要保存[1, (i + (i - r + 1)) / 2]的记录,因此有了主席树,可以用主席树来维护值i + r - 1出现的次数。

代码:

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

const int N = 2e5 + 5;
typedef long long LL;
 
struct Tr {
	int l, r; // l,r 存的是指针
	LL cnt; // 区间内值出现的次数
}tr[4 * N + N * 18]; // 一次insert产生一个新版本,对应增加logN个节点
int root[N],idx; // root存历史版本根节点 

char s[N], s2[N];
int r[N], n, m;

void manacher() {
	n = strlen(s);
    s2[m ++] = '$', s2[m ++] = '#';
    for (int i = 0; i < n; i ++)
        s2[m ++] = s[i], s2[m ++] = '#';
    s2[m ++] = '^';
    
    int mr = 0, mid = 0;
    for (int i = 1; i <= m - 2; i ++) {
        r[i] = i < mr ? min(r[2 * mid - i], mr - i) : 1;
        while (s2[i + r[i]] == s2[i - r[i]])
            r[i] ++;
        if (i + r[i] > mr) {
            mr = i + r[i];
            mid = i;
        }
    }
}

void init() {
	idx = m = 0;
	for (int i = 0; i <= 4 * N + N * 18; i ++)
		tr[i] = {0, 0, 0};
}

int build(int l, int r) {
	int p = idx ++;
	if (l == r)
		return p;
	int mid = l + r >> 1;
	tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
	return p;
}

int insert(int p, int l, int r, int x) {
	int q = ++ idx;
    tr[q] = tr[p];
    
    if(l == r) {
        tr[q].cnt ++;
        return q;
    }
    
    int mid = l + r >> 1;
    if(x <= mid)
        tr[q].l = insert(tr[p].l, l, mid, x);
    else
        tr[q].r = insert(tr[p].r, mid + 1, r, x);
        
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
    
    return q;
}

LL query(int p, int q, int l, int r, int l2, int r2) {
	if (l2 <= l && r <= r2)
		return tr[q].cnt - tr[p].cnt;
	
	int mid = (l + r) >> 1;
	LL ans = 0;
	
    if(l2 <= mid)
		ans = query(tr[p].l, tr[q].l, l, mid, l2, r2);
    if(r2 > mid)
		ans += query(tr[p].r, tr[q].r, mid + 1, r, l2, r2);
    
    return ans;
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --) {
		cin >> s;
		
		init();
		
		manacher();
		
		root[0] = build(1, m - 2);
		
		LL ans = 0;
		
		for (int i = 1; i <= m - 2; i ++) {
			root[i] = insert(root[i - 1], 1, m - 2, i + r[i] - 1);
		}
		
		for (int i = 1; i <= m - 2; i ++) {
			if (s2[i] == '#') {
				int j = (2 * i - r[i] + 1) / 2;
				ans += query(root[j - 1], root[i - 1], 1, m - 2, i, m - 2);
			}	
		}
		
		cout << ans << "\n";
	} 
	
	return 0;
}

1006 Touhou Red Red Blue

题意:

现在有三种颜色的球:R、G、B,两个袋子,依次给你n个球,对于某个球,你可以选择选或不选,若选择,你要按照下面规则将其放入袋子中:
1.每个袋子只允许放一个球。优先放袋子1,若袋子1满放袋子2
2.若两个袋子都满:
①若袋中球和你手中的球颜色两两相同,获得一点分数,然后扔掉三个球,生成一个新球放入袋子1,新球颜色自定。
②若袋中球和你手中的球颜色两两不同,则扔掉三球,生成两个球分别放入袋1袋2,新球颜色自定。
③若不是上述两种情况,则扔掉袋1的球,将袋2的球放入袋1,并将手中的球放入袋2。
问,最后获得的最大分数是多少。

分析:

贪心。只有颜色相同的时候才能获得分数,球的数量有限,因此最优解要尽可能的往这一状态靠。设st = 0,1,2 表示从上轮的结果转移过来,这轮要先生成st个球。
1.st = 0:
累计三种颜色的球的数量,考虑转移到st = 1和 st = 2的条件。
2.st = 1:
判断当前手中的球和下一个球颜色是否相同,如果相同则让其满足两两相同的局面,获得分数,转移到st = 1;否则优先让其满足两两不同的局面, 转移到st = 2。倘若不转移到st = 2则只能转移到st = 0。由于st = 2必得分显然比先到st=0再到st = 1或2得分消耗的球更少更有利于得更多分,所以转移至st = 2更优。
3.st = 2:
优先令两个球的颜色与手中球颜色相同,获得分数,转移到st = 1。

代码:

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

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --) {
		string s;
		cin >> s;
		
		int n = s.size(), r = 0, g = 0, b = 0, res = 0, st = 0;
	    for (int i = 0; i < n; ) {
	        if (st == 1) {
	            if (i == n - 1)
					break; // 只剩两个球,不能得分了
	            if (s[i] == s[i + 1])
					st = 1, res ++;
	            else
					st = 2;
	            i += 2; // 跳过本次和下一次
	        } else if (st == 2) {
	            st = 1, res ++, i ++; // 跳过本次
	        } else {
	            if (s[i] == 'R')
					r ++;
	            else if (s[i] == 'G')
					g ++;
	            else
					b ++;
	            if (r && g && b)
					st = 2;
	            else if (r == 3 || g == 3 || b == 3) 
					st = 1, res ++;
	            i ++; // 继续
	        }
	    }
				
		cout << res << "\n";
	}
	
	return 0;
}

1007 Expectation (Easy Version)

题意:

玩一个游戏n次,每次有\(\frac{a}{b}\)的概率赢,如果某次赢了,将获得\(k^m\)的分数,k是到目前为止赢得总次数。问最终得分的期望。

分析:

推公式,期望为:\(\sum_{k = 1}^n(1^m+2^m+...+k^m)C_n^k(\frac{a}{b})^k(1 - \frac{a}{b})^{n - k}\) = \(\sum_{k = 1}^n(1^m+2^m+...+k^m)C_n^k\frac{a^k(b - a)^{n - k}}{b^n}\)
通过预处理逆元的方式求组合数,其他部分也可以通过预处理求出来。

代码:

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

const int N = 2e6 + 5, mod = 998244353;
typedef long long LL;
LL f[N], f2[N], p[N], s[N], B[N];

LL qmi(LL m, LL k) {
    LL res = 1, t = m;
    while (k) {
        if (k & 1)
            res = res * t % mod;
        t = t * t % mod;
        k >>= 1;
    }
    return res;
}

void init() {
    f[0] = f2[0] = 1;
    for (int i = 1; i < N; i ++) {
        f[i] = f[i - 1] * i % mod;
        f2[i] = f2[i - 1] * qmi(i, mod - 2) % mod;
    }
    
}

int main() {
	std::ios::sync_with_stdio(false); 
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	init();
	
	while (t --) {
		LL n, m, a, b;
		cin >> n >> m >> a >> b;
		
		LL A = 1, tmp = 1;
		
		for (int i = n; i >= 1; i --) {
			B[i] = tmp;
			tmp = tmp * (b - a) % mod;
		}
		
		for (int i = 1; i <= n; i ++) {
			A = A * a % mod;
			
			s[i] = qmi(i, m);
			s[i] = (s[i] + s[i - 1]) % mod;
			p[i] = A * B[i] % mod;
		}
		
		LL p2 = qmi(qmi(b, n), mod - 2);
		
		LL res = 0;
		for (int i = 1; i <= n; i ++) {
			res = (res + ((f[n] * f2[i]) % mod * f2[n - i]) % mod * p[i] % mod * p2 % mod * s[i] % mod) % mod;
		}
		
		cout << res << "\n";
	}
	
	return 0;
}

1009 Tree

题意:

给你有一个有根树,在这棵树的每条重链上构造一个二叉树,重链上的每个点都是该链构造的二叉树的叶子节点且他们的深度都相同,重链上的点依旧连接着他们的轻儿子。问构造出的二叉树的深度是多少。
二叉树(双杠表示重边):

重链有:

构造出的二叉树:

分析:

设重链长度为len,根据题意,该链所能构成的二叉树的深度为\(\lceil log_22len \rceil\)。我们可以dfs遍历每条重链,在重链末尾更新该链能构成的二叉树的深度并下传至与其相连的轻儿子,回溯的过程中给该链上的重儿子赋相同的值,最后对每个点记录的depth取个max即可。

代码:

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

const int N = 1e6 + 5;
int h[N], e[N], ne[N], idx;
int depth[N], weight[N], len[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u, int d) {
    if (weight[u]) { // 优先遍历重链 
        int j = weight[u];
        len[j] = len[u] + 1;
        dfs(j, d);
        len[u] = len[j];
        depth[u] = depth[j]; // 回溯赋值 
    } else {
        depth[u] += (int)ceil(log(2 * len[u]) / log(2)); // 当前重链所能构造的搜索树深度 
        depth[u] += d; // 深度下传 
    }
    
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        
        if (weight[u] == j)
            continue;
        
        dfs(j, depth[u]); // 遍历轻儿子 
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    // 按题目提示扩大栈空间 
    int size(512<<20); // 512M
    __asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size)); 
    
    int t;
    cin >> t;
    
    while (t --) {
        int n;
        cin >> n;
        
        idx = 0;
        for (int i = 1; i <= n; i ++) {
            depth[i] = 0;
            len[i] = 1; // 单个点也是一条重链 
            h[i] = -1;
        }
        
        for (int i = 1; i <= n; i ++) {
            int fa;
            cin >> fa;
            
            if (fa) {
                add(fa, i);
            }
        }
        
        for (int i = 1; i <= n; i ++) {
            int a;
            cin >> a;
            
            weight[i] = a;
        }
        
        dfs(1, 0);
        
        int res = -0x3f3f3f3f;
        for (int i = 1; i <= n; i ++) {
            res = max(res, depth[i]);
        }
        cout << res << "\n";
    }
    
    exit(0);
    
    return 0;
}

1012 Counting Stars

题意:

我们定义k-星图:一个有k+1个点和k个边的图称为k-星图。给定一个无向图,设k-星图的数量为\(cnt_k\),求\(cnt_k\)(2 ≤ k ≤ n - 1)的异或和。

分析:

设点u的度为d,则u对k-星图数量的贡献为:\(C_d^k\),因此统计每个点对不同k-星图的贡献即可

代码:

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

const int N = 1e6 + 5, mod = 1e9 + 7;
typedef long long LL;
LL cnt[N], f[N], f2[N], d[N];

LL qmi(LL m, LL k) {
	LL res = 1, t = m;
	
	while (k) {
		if (k & 1) 
			res = res * t % mod;
		t = t * t % mod;
		k >>= 1;
	}
	
	return res;
}

void init() {
	f[0] = f2[0] = 1;
	for (int i = 1; i < N; i ++ ) {
	    f[i] = f[i - 1] * i % mod;
	    f2[i] = f2[i - 1] * qmi(i, mod - 2) % mod;
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	init();
	
	while (t --) {
		int n, m;
		cin >> n >> m;
		
		for (int i = 1; i <= n; i ++) {
			d[i] = cnt[i] = 0;
		}
		
		while (m --) {
			int a, b;
			cin >> a >> b;
			
			d[a] ++, d[b] ++;
		}
		
		for (int i = 1; i <= n; i ++) {
			for (int j = 2; j <= d[i]; j ++) { // 所有度累加起来不超过2m, 所以两层循环整体是O(n + m)的时间复杂度。 
				cnt[j] = (cnt[j] + ((f[d[i]] * f2[j]) % mod * f2[d[i] - j]) % mod) % mod;
			}
		}
		
		LL res = 0;
		for (int i = 2; i <= n - 1; i ++) {
			res = res ^ cnt[i] % mod;
		}
		
		cout << res << "\n";
	}
	
	return 0;
}

标签:钉耙,const,point,int,编程,st,++,2023,return
From: https://www.cnblogs.com/scoxty/p/17688215.html

相关文章

  • 深入理解Java if判断:提升编程效率的关键步骤
    Java中的if判断语句是一种条件语句,用于根据指定条件执行不同的代码块。if语句通常由一个布尔表达式和一个或多个语句组成。如果布尔表达式的结果为true,则执行if语句后面的语句;否则,跳过if语句后面的语句。下面是一个if语句的示例:intx=10;if(x>5){System.out.println("x......
  • 2023.36 腾讯混元大模型
    9月7日,在2023腾讯全球数字生态大会上,腾讯混元大模型正式亮相。腾讯集团副总裁蒋杰介绍,混元大模型参数量超千亿,具备多轮对话能力,内容创作能力,逻辑推理能力,搜索增强和知识图谱。训练数据更新至今年7月份,未来会不断更新迭代。目前,腾讯已有超过50个自有产品和业务接入混元大模型测试。......
  • C++编程语言在线学习系统-计算机毕业设计源码+LW文档
    摘要随着互联网技术的推进,我国高等教育逐渐实现信息化。许多精品C++编程语言在线学习系统的开发建设大大提高了教职工的教学效率,也为培养更多的高素质人才提供了途径。但是C++编程语言在线学习系统的发展也存在交互性不强、资源更新缓慢、教学形式单一等问题。因此,笔者设想开发一......
  • 2023年全国大学生数学建模竞赛赛题思路分析
    今年的数模难度和去年差不多,只是赛题的类型有所调整,粗略扫了一眼每个赛题,简单讲一下C题的思路吧。C题问题1:这道题其实考察的是最基础的数学知识,这道题可以拆解成两个小问。1.1求解蔬菜各品类及单品销售量的分布规律1)采用Excel等绘制品类销售量的直方图,利用Minitab等分析分布规律。......
  • Keil C51下载_Keil C51最新版下载「编程软件」新功能介绍
    KeilC51是美国KeilSoftware公司出品的51系列兼容单片机C语言软件开发系统,使用KeilC51编写生成的代码效率非常高,相比其它语言更容易理解些。本站免费提供KeilC51官方版软件,有需要的前来下载试试看吧。软件地址:看置顶贴软件特色-mdkcore–mdk核心mdkcore包含微控制器开发......
  • 2023最新总结,Mac下使用Homebrew完全指南!
    2023最新总结,Mac下使用Homebrew完全指南!滚石前端成长之路  45人赞同了该文章1.介绍Homebrew是一款包管理工具,目前支持macOS和Linux系统。主要有四个部分组成:brew、homebrew-core、homebrew-cask、homebrew-bottles。 2.安装2.1执行安装脚本执行......
  • Matlab 2023a图文安装教程及下载
    MATLAB是由美国MathWorks公司出品的专业数学软件,用于算法开发,数据可视化,数据分析以及数值计算的高级技术计算语言和交互式环境,MATLAB是矩阵和实验室两个词的组合,意为矩阵工厂(矩阵实验室),主要包括MATLAB和Simulink两大部分。它将数值分析,矩阵计算,科学数据可视化以及非线性动态系统的......
  • Linux环境编程-进程管理
    一、进程的基本概念1、进程与程序程序是存储在磁盘上的可执行文件,程序被加载到内存中开始运行称为进程,一个程序可以同时加载成多个进程,进程就是处于活动状态下的程序2、进程的分类进程根据功能不同一般分为三种类型:交互进程、批处理进程、守护进程交互进程:由一个shell终端......
  • nodejs采集淘宝、天猫网商品详情数据以及解决_m_h5_tk令牌及sign签名验证(2023-09-09)
    一、淘宝、天猫sign加密算法淘宝、天猫对于h5的访问采用了和APP客户端不同的方式,由于在h5的js代码中保存appsercret具有较高的风险,mtop采用了随机分配令牌的方式,为每个访问端分配一个token,保存在用户的cookie中,通过cookie带回服务端分配的token,客户端利用分配的token对请求的URL......
  • JOISC 2023 纪录
    记录一下JOISC2023的做题记录Day1T1TwoCurrencies给定一棵树,在边上有总计\(m\)个检查站,经过一个检查站需要叫\(1\)枚金币或者若干枚银币。\(Q\)次询问,问一个人有\(X\)枚金币和\(Y\)枚银币,能否从\(u\)走到\(v\),同时回答最多可以留下多少枚金币。发现一定是......