首页 > 其他分享 >2022NOIPA层联测9

2022NOIPA层联测9

时间：2022-10-15 19:35:21浏览次数：46  
标签：return int ll 联测 2022NOIPA include dir const

A. 泰山压顶

code 
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#include<set>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int read(){
	int x = 0; bool f = 0; char c = getchar();
	while(!isdigit(c))f = c == '-', c = getchar();
	do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
	return f ? -x : x;
}

const int maxn = 305;
const int mod = 1e9 + 7;
const double PI = 3.14159265358979;
const double eps = 1e-10;
int xa, ya, xb, yb, n, p;
struct dir{
	ll a, b;
	friend ll operator * (const dir &x, const dir &y){return x.a * y.a + x.b * y.b; }
	friend dir operator - (const dir &x, const dir &y){return {x.a - y.a, x.b - y.b}; }
}d[maxn], e;
double abs(const dir &x){return sqrt(x.a * x.a + x.b * x.b);}
double eg(const dir &x, const dir &y){
	return acos((x * y) / abs(x) / abs(y));
}

int f[maxn][maxn];
struct zb{
	double the;int id;
	friend bool operator < (const zb &x, const zb &y){return x.the < y.the;}
}z[maxn];
void add(int &x, int y){x += y; x = x >= mod ? x - mod : x;}
double Dis(double x, double y){return (x * x + y * y);}
bool check(int ii, int jj, int kk){
	if(jj == 1)return true;
	int i = z[ii].id, k = z[kk].id, j = z[jj].id;
	dir a = d[i] - d[k], b = d[j] - d[k];
	double cj = a.a * b.b - a.b * b.a;
	return cj >= eps;
}
int main(){
	n = read();
	xa = read(), ya = read(), xb = read(), yb = read();
	d[1] = {xa - xb, ya - yb};
	for(int i = 1; i <= n; ++i){d[i + 1].a = read() - xb; d[i + 1].b = read() - yb;}
	e = {1, 0};
	for(int i = 1; i <= n + 1; ++i){
		z[i].id = i;
		if(d[i].b >= 0) z[i].the = eg(d[i], e);
		else z[i].the = PI * 2 - eg(d[i], e);
	}
	for(int i = 2; i <= n + 1; ++i){
		z[i].the -= z[1].the;
		if(z[i].the <= 0 + eps)z[i].the = PI + PI + z[i].the;
	}
	z[1].the = 0;
	sort(z + 1, z + n + 2);
	f[1][1] = 1;
	int ans =  0;
	for(int i = 2; i <= n + 1; ++i){
		for(int j = i - 1; j >= 1; --j){
			if(z[i].the - z[j].the > PI - eps)break;
			for(int k = j; k >= 1; --k){
				if(z[j].the - z[k].the > PI - eps)break;
				if(check(k, j, i))add(f[i][j], f[j][k]);
			}
			if(z[i].the > PI + eps && check(j, i, 1))add(ans, f[i][j]);
		}
	}
	printf("%d\n",ans);
	return 0;
}

B. 调料瓶

code 
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#include<set>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const double PI = acos(-1);
const double eps = 1e-10;
const int maxn = 100005;
int n;
struct dir{
	double x, y, the, mod;
	dir(){}
	friend bool operator == (const dir x, const dir y){return x.x + eps >= y.x && x.x - eps <= y.x && x.y + eps >= y.y && x.y - eps <= y.y;}
	friend double operator * (const dir &x, const dir &y){return x.x * y.x + x.y * y.y; }
	friend dir operator - (const dir &x, const dir &y){return {x.x - y.x, x.y - y.y}; }
	dir(double _x, double _y){x = _x; y = _y; mod = sqrt(x * x + y * y);}
}d[maxn];
int cnt, equ, a2;
multiset<double>s;
double dx, dy, ds;
char c[2];
void get_the(dir &x){	
	dir e = {1, 0};
	x.the = acos((x * e) / x.mod / e.mod);
	if(x.y < 0)x.the = 2 * PI - x.the;
}
bool check3(){
	if(s.empty())return false;
	double now = *s.begin();
	auto it = --s.upper_bound(now + PI);
	while(1){
		if(now + eps >= (*it) && now - eps <= (*it))break;
		now = (*it);
		it = --s.upper_bound(now + PI);
	}
	now = now - PI + eps;
	if(now >= (*s.begin()))return true;
	return false;
}
bool check2(int x){
	if(s.empty())return false;
	double now = fmod(d[x].the + PI, 2 * PI);
	auto it = s.lower_bound(now);
	if(it != s.end() && (*it) - eps <= now && (*it) + eps >= now)return true;
	return false;
}
int main(){
	scanf("%lf%lf%lf",&dx, &dy, &ds);
	scanf("%d",&n); ds += dx + dy;
	dx = dx / ds; dy = dy / ds;
	d[0] = dir(0, 0);
	for(int i = 1; i <= n; ++i){
		scanf("%s",c);
		if(c[0] == 'A'){
			++cnt;
			double rx, ry, rz;
			scanf("%lf%lf%lf",&rx,&ry,&rz);
			rz += rx + ry; rx /= rz; ry /= rz;
			rx = rx - dx; ry = ry - dy; 
			d[cnt] = dir(rx, ry);
			if(d[cnt] == d[0]){
				++equ; 
			}else{
				get_the(d[cnt]);
				a2 += check2(cnt);
				s.insert(d[cnt].the);
			}
		}else{
			int id; scanf("%d",&id);
			if(d[id] == d[0]){
				--equ;
			}else{
				s.erase(s.lower_bound(d[id].the));
				a2 -= check2(id);
			}
		}
		if(equ)printf("1\n");
		else if(a2)printf("2\n");
		else if(check3())printf("3\n");
		else printf("0\n");
	}
	return 0;
}

C. 一虎杀二羊

code 
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<map>
#include<set>
#include<cmath>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int read(){
	int x = 0; bool f = 0; char c = getchar();
	while(!isdigit(c))f = c == '-', c = getchar();
	do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
	return f ? -x : x;
}

const int maxn = 100005;
ll a[maxn], b[maxn];
int n, m;
ll prime[500005], cnt, d;
bool flag[2000005];
ll qpow(ll x, ll y, ll mod){
	ll ans = 1;
	for(; y; y >>= 1, x = x * x % mod)if(y & 1)ans = ans * x % mod;
	return ans;
}
bool check(ll x, ll p){
	ll now = 0;
	for(int i = d - 1; i >= 0; --i){
		now = (now * x % p + b[i]) % p;
	}
	return now == 0;
}
int main(){
	n = read(), m = read();
	for(int i = 0; i < n; ++i)a[i] = read(), b[i] = read();
	for(int i = 0; i < n; ++i)	a[i] -= b[i];
	for(int i = 2; i <= 2000000; ++i){
		if(!flag[i])prime[++cnt] = i;
		for(int j = 1; j <= cnt && i * prime[j] <= 2000000; ++j){
			flag[i * prime[j]] = 1;
			if(i % prime[j] == 0)break;
		}
	}
	for(d = 2; d <= 1000000; ++d){
		for(int i = 0; i < d; ++i){
			b[i] = 0;
			for(int j = i; j <= n; j += d)b[i] += a[j];
		}
		for(ll k = ((m - 1) / d + 1); k * d <= 2000000; ++k){
			ll now = d * k + 1;
			if(flag[now])continue;
			int up = rand() % 5 + 1;
			for(int t = 1; t <= up; ++t){
				ll x = qpow(prime[rand() % cnt + 1], k, now);
				if(x > now - 2 || x < 2)continue;
				if(check(x, now)){
					printf("%lld %lld\n",now, x);
					return 0;
				}
			}
		}
	}
	return 0;
}

D. 逆序对

code 
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<bitset>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int read(){
	int x = 0; bool f = 0; char c = getchar();
	while(!isdigit(c))f = c == '-', c = getchar();
	do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
	return f ? -x : x;
}
int n, m;
bitset<100000001>f;

int main(){
	n = read(), m = read();
	f[0] = 1;
	for(int j = 1; j <= n; ++j){
		ll p1 = 1ll * j * (3 * j + 1) / 2;
		ll p2 = 1ll * j * (3 * j - 1) / 2;
		if(p2 > n)break;
		f[p1] = f[p1] ^ 1, f[p2] = f[p2] ^ 1;
	}
	for(int i = 0; (1ll << i) <= n; ++i)if(((1ll << i) & (n - 1)) == 0){
		f ^= (f << (1ll << i));
	}
	for(int i = 1; i <= m; ++i){
		int x = read();
		printf("%d",(int)f[x]);
	}
	return 0;
}

标签：return,int,ll,联测,2022NOIPA,include,dir,const
From： https://www.cnblogs.com/Chencgy/p/16794854.html

相关文章

  • 2022NOIPA层联测7
    \(accoder\)用数据告诉我们，找女朋友是个假命题找（a）简单推一下柿子，维护总和和平方和code#include<cstdio>#include<cstring>#include<algorithm>#include<set>#inc......
  • A层联测7
    A.推个柿子直接高就行#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constllMOD=998244353;constintN=2E5+10;structp_s{ llx,y;......
  • 2022NOIPA层联测7之only部分分
    问题A:【2022NOIP联测710月11日】找（a）一看到是个数学题还感觉挺恐怖，把式子写出来才发现它很水。没开longlong大样例跑不出来还以为T1又没了……然而幸好及时发现问题。......
  • 2022NOIPA层联测6
    设密码比较失败，所以，A.构造字符串（str）并查集维护一下相同的位置，注意到$LCP+1$位置不同，于是每个集合取出来最靠前的为代表，两个集合不同，大集合向小集合连边，每次集合复......
  • 2022NOIP联测5
    T1挑战题意：有两行字符串，有\(*\)和\(.\)两种字符，你可以进行一种操作，将一个格子的\(*\)推到相邻的格子，如果推到一个有\(*\)的格子，那么将\(*\)合并，求最后把所有......
  • 2022NOIPA层联测4
    正手一个[南猪入侵]，反手一个[万箭齐发]，我的[桃]真的快用完了……OI啊(MP)，我(ZP)劝你出手前考虑一下，如果我DEAD了，你可就没牌了……话说难道我没有跳过忠吗？？ 问题A:【202......
  • 多校联测4
    三个字符串可还行T1.字符串还原我一开始读错题了，以为是要不断拆分，回头一看发现只用拆依次，这不就枚举断点，然后用\(hash\)判断不就行了吗。不过这样你会得到80分，原因是不同......
  • 长城汽车选择北汇信息作为C-V2X智能网联测试系统及服务供应商
    随着C-V2X关键技术及其标准演进，C-V2X在全球竞争中已形成超越态势。长城汽车作为一家全球化智能科技公司，不断加大对C-V2X等前沿技术的投入和研究。长城汽车选择北汇信息作为......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99