首页 > 其他分享 >HNCPC2024 2024湖南省赛 题解

HNCPC2024 2024湖南省赛 题解

时间：2024-10-16 21:21:58浏览次数：7  
标签：HNCPC2024 int 题解 ll long 2024 while getchar define

目录

写在前面

比赛地址：https://codeforces.com/gym/105423。

以下按个人难度向排序。

利益相关：现场赛 Au。

没有和去年一样整场犯唐，好！感谢队友带飞成功一雪前耻。

题解见官方，这里只放一下代码了。

I 签到

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

#define ll long long
#define ull unsigned long long
const int N=1e5+5;
int read()
{
	int x = 0; bool f = false; char c = getchar();
	while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
	while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	return f ? -x : x;
}
int n,k,m,q;
bool ok[N];
int main() {
	cin>>n>>k>>m>>q;
	for(int i=1,x;i<=m;i++){
		cin>>x;
		int now=x;
		for(int j=1;j<=k;++j){
			now%=n;
			ok[now]=1;	
			now=now*x%n;
		}
	}
	for(int i=1,x;i<=q;i++){
		cin>>x;
		int now=x;
		bool fl=1;
		for(int j=1;j<=k;++j){
			now%=n;
			if(ok[now]==0){
				fl=0;
			}
			now=now*x%n;
		}
		cout<<fl<<' ';
	}
	return 0;
}

C 签到

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

#define ll long long
#define ull unsigned long long

int read()
{
	int x = 0; bool f = false; char c = getchar();
	while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
	while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	return f ? -x : x;
}

int main() {
	int n; cin >> n;
	
	int cnt = 0;
	
	for (int i = 1; i <= n; ++ i) {
		int a; cin >> a;
		cnt += log2(a);
	}
	
	double k = 1.0 * cnt / log2(2024);
	ll ans = ceil(k);
	
	cout << ans << "\n";
	return 0;
}

E 二进制，枚举，子集 DP

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

#define ll long long
#define ull unsigned long long

int read()
{
	int x = 0; bool f = false; char c = getchar();
	while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
	while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	return f ? -x : x;
}

const int N = 1e6 + 5;
int n, a[N], vis[N], num[N];

void solve(int pos)
{
	int S = (1 << (a[pos] - 1));
	vis[S] = 1;
	while(pos < n && !(S & (1 << (a[pos + 1] - 1))))
	{
		++pos;
		S |= (1 << (a[pos] - 1));
		vis[S] = 1;
	}
}

int main() {
	n = read();
	for(int i = 1; i <= n; ++i) a[i] = read();
	for(int i = 1; i <= n; ++i) solve(i);
	int ans = 0, flag = (1 << 18) - 1;
	for(int i = 1; i <= flag; ++i) num[i] = num[i >> 1] + (i & 1);
	vis[0] = 1;
	for(int s = 0; s < (1 << 18); ++s)
		for(int t = flag ^ s; t; t = (flag ^ s) & (t - 1))
			if(vis[s] && vis[t]) ans = max(ans, num[s] + num[t]);
	printf("%d", ans);
	return 0;
}

K 转化，分层图最短路

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

#define ll long long
#define ull unsigned long long

ll read()
{
	ll x = 0; bool f = false; char c = getchar();
	while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
	while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	return f ? -x : x;
}

const int N = 2e5 + 5;
int n, m, S;
vector< pair<int, ll> > V[N];

int vis[N];
ll dis[N];
priority_queue< pair<ll, int> > q;
void dijkstra(int S)
{
	q.push(pair<ll, int>(0, S));
	for(int i = 1; i <= n * 2; ++i) dis[i] = 0x7fffffffffffffff;
	while(!q.empty())
	{
		int now = q.top().second ;
		q.pop();
		if(vis[now]) continue;
		vis[now] = 1;
		for(auto pp : V[now])
		{
			int v = pp.first ;
			ll w = pp.second ;
			if(dis[v] > dis[now] + w)
			{
				dis[v] = dis[now] + w;
				q.push(pair<ll, int>(-dis[v], v));
			}
		}
	}
}

int main() {
	n = read(), m = read();
	S = 2 * n + 1;
	for(int i = 1; i <= m; ++i)
	{
		int u = read(), v = read(), w = read();
		V[u].emplace_back(pair<int, ll>(v, w));
		V[v].emplace_back(pair<int, ll>(u, w));
		V[u].emplace_back(pair<int, ll>(v + n, 0));
		V[v].emplace_back(pair<int, ll>(u + n, 0));
		V[u].emplace_back(pair<int, ll>(u + n, 0));
		V[v].emplace_back(pair<int, ll>(v + n, 0));
		V[u + n].emplace_back(pair<int, ll>(v + n, w));
		V[v + n].emplace_back(pair<int, ll>(u + n, w));
	}
	for(int i = 1; i <= n; ++i)
	{
		ll a = read();
		V[S].emplace_back(pair<int, ll>(i, a));
	}
	dijkstra(S);
	ll ans = 0;
	for(int i = 1; i <= n; ++i) ans = max(ans, dis[i + n]);
	printf("%lld\n", ans);
	return 0;
}

A 枚举，DP，简单计算几何

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

#define LL long long
#define ull unsigned long long
#define int long long
const int kN = 1e3 + 10;
const double eps=1e-9;
int n,x[kN],y[kN], into[kN];
int ans=0;
struct node{
	int x,y;
};
node get_node(int a,int b){
	return (node){x[b]-x[a],y[b]-y[a]};
}
int f[55];
double len(node a){
	return sqrt(a.x*a.x+a.y*a.y);
}
bool check(node a,node b,bool fl){
	if(fl){
		if(a.x*b.y-a.y*b.x<0) return 0;
	}else{
		if(a.x*b.y-a.y*b.x>0) return 0;
	}
	double oo=(1.0*a.x*b.x+1.0*a.y*b.y)/(1.00*len(a)*len(b));
	if(oo<0-eps) return 0;
	if(oo-eps>1) return 0;
	return 1;
}
void get(node now,bool fl){
	for(int i=1;i<=n;++i) f[i]=-9999999;
	vector<int> edge[kN];
	for (int i = 0; i <= n; ++ i) into[i] = 0;
	
	for(int i=0;i<=n;++i){
		if (!check(get_node(0, i), now, fl)) continue;
		for(int j=1;j<=n;++j){
			if(i==j) continue;
			if (!check(get_node(0, j), now, fl)) continue;
			if(check(get_node(i,j),now,fl)){
				edge[i].push_back(j);
				++ into[j];
			}
		}
	}
	
	queue<int> q;
	q.push(0);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (auto v: edge[u]) {
			f[v] = max(f[v], f[u] + 1);
			if (!(--into[v])) q.push(v);
		}
	}
	
	for(int i=0;i<=n;++i) ans=max(ans,f[i]);
}
signed main(){
	cin>>n;
	f[0]=0;
	x[0]=0,y[0]=0;
	for(int i=1;i<=n;++i){
		cin>>x[i]>>y[i];
		if(x[i]==0&&y[i]==0){
			f[0]++;
			--i;
			--n;
		}
		
	}
	ans=f[0];
	for(int i=0;i<=n;++i){
		for(int j=0;j<=n;++j){
			if(i==j) continue;
			get(get_node(i,j),0);
			get(get_node(i,j),1);
		}
	}
	cout<<ans<<endl;
	return 0;
}

J 单调性，枚举，数据结构

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ull unsigned long long

const int N = 1e6 + 10;

int read()
{
	int x = 0; bool f = false; char c = getchar();
	while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
	while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	return f ? -x : x;
}
int n;
int a[N],b[N],ans=0;
int ida[N],idb[N];
set<int> s;

struct BIT {
	#define low(x) ((x)&(-x))
	int sum[N];
	int lim;
	void init(int lim_) {
		lim = lim_;
		for (int i = 1; i <= lim; ++ i) sum[i] = 0;
	}
	void insert(int p_, int val_) {
		for (int i = p_; i <= lim; i += low(i)) {
			sum[i] += val_;
		}
	}
	int Sum(int p_) {
		int ret = 0;
		for (int i = p_; i; i -= low(i)) ret += sum[i];
		return ret;
	}
} bit[2];

bool check(int x){
	int rka = bit[0].Sum(ida[x]);
	int rkb = bit[1].Sum(idb[x]);
	return rka == rkb;
}
void push(int x){
	bit[0].insert(ida[x], 1);
	bit[1].insert(idb[x], 1);
}
void del(int x){
	bit[0].insert(ida[x], -1);
	bit[1].insert(idb[x], -1);
}
signed main() {
	cin>>n;
	bit[0].init(n);
	bit[1].init(n);
	for(int i=1;i<=n;++i){
		cin>>a[i];
		ida[a[i]]=i;
	}
	for(int i=1;i<=n;++i){
		cin>>b[i];
		idb[b[i]]=i;
	}
	int r=1;
	push(r);
	for(int l=1;l<=n;++l){
		while(r+1<=n&&check(r+1)){
			push(r+1);
			++r;
		}
		ans+=(r-l+1);
		del(l);
	}
	cout<<ans;
	return 0;
}

H DP，字符串，KMP

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

#define LL long long
#define ull unsigned long long

const int kN = 10010;
const LL p = 998244353;

int n, k;

LL f[kN][13][110];
int fail[110];
int len;

char s[110]; 

int read()
{
	int x = 0; bool f = false; char c = getchar();
	while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
	while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	return f ? -x : x;
}

int main() {
	n = read(), k = read();
	scanf("%s", s + 1);
	len = strlen(s + 1);
	
	fail[1] = 0;
	for (int i = 2, j = 0; i <= len; ++ i) {
		while (j && s[i] != s[j + 1]) j = fail[j];
		if (s[i] == s[j + 1]) ++ j;
		fail[i] = j;
	}
	
	f[0][0][0] = 1;
	for (int i = 0; i < n; ++ i) {
		for (int j = 0; j <= k; ++ j) {
			for (int l = 0; l < len; ++ l) {
				for (int c = 0; c < 26; ++ c) {
					bool flag = 0;
					for (int pre = l; 1; pre = fail[pre]) {
						if (s[pre + 1] == (char)(c + 'a')) {
							if (pre == len - 1) {
								f[i + 1][j + 1][0] += f[i][j][l];
								f[i + 1][j + 1][0] %= p;
							} else {
								f[i + 1][j][pre + 1] += f[i][j][l];
								f[i + 1][j][pre + 1] %= p;
							}
							flag = 1;
							break;
						}
						if (pre == 0) break;
					}
					if (flag) continue;
					f[i + 1][j][0] += f[i][j][l];
					f[i + 1][j][0] %= p;
				}
			}
		}
	}
	
//	for (int i = 1; i <= n; ++ i) {
//		for (int j = 0; j <= k; ++ j) {
//			for (int l = 0; l <= len; ++ l) {
////				printf("%d %d %d %lld\n", i, j, l, f[i][j][l]);
//			}
//		}
//	}
	
	LL ans = 0;
	for (int i = 0; i < len; ++ i) {
		ans += f[n][k][i];
		ans %= p;
	}
	printf("%lld\n", ans);
	return 0;
}
/*
4 1
aa
*/

D 莫比乌斯反演，枚举

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

#define int long long
#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

const ll mod = 998244353;
const int N = 2e5;

int n;
struct node{ ll a, b; } A[N + 5];

bool cmp(const node &a, const node &b)
{ return (a.a == b.a ) ? (a.b < b.b ) : (a.a < b.a ); }

int vis[N + 5], prime[N + 5], cnt;
ll jc[N + 5], inv[N + 5], u[N + 5], f[N + 5];
vector<int> yve[N + 5];

ll qpow(ll a, ll b, ll mod)
{
	ll ans = 1;
	while(b)
	{
		if(b & 1) ans = ans * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return ans;
}

void init()
{
	u[1] = 1;
	for(int i = 2; i <= N; ++i)
	{
		if(!vis[i]) prime[++cnt] = i, u[i] = -1;
		for(int j = 1; j <= cnt && prime[j] * i <= N; ++j)
		{
			vis[prime[j] * i] = 1;
			if(i % prime[j] == 0) break;
			u[i * prime[j]] = -u[i];
		}
	}

	for(int i = 1; i <= N; ++i)
		for(int j = 1; j * i <= N; ++j)
		{
			f[i * j] = (f[i * j] + u[i] * i * i % mod + mod) % mod;
			yve[i * j].emplace_back(i);
		}
	
	// 求单个数的逆元
	jc[0] = jc[1] = inv[0] = inv[1] = 1;
	for(int i = 2; i <= N; ++i) jc[i] = jc[i - 1] * i % mod;
	inv[N] = qpow(jc[N], mod - 2, mod);
	for(int i = N - 1; i >= 2; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
	for(int i = 2; i <= N; ++i) inv[i] = inv[i] * jc[i - 1] % mod;

	for(int i = 2; i <= N; ++i) f[i] = f[i] * inv[i] % mod * inv[i] % mod;
}

ll Sum1[N + 5], Sum2[N + 5], ans;

signed main()
{
	init();
	n = read();
	for(int i = 1; i <= n; ++i) A[i].a = read();
	for(int i = 1; i <= n; ++i) A[i].b = read();
	sort(A + 1, A + n + 1, cmp);
	for(int i = 1; i <= n; ++i)
		for(auto T : yve[A[i].b ])
		{
			ans = (ans + f[T] * ((A[i].a * A[i].b % mod * Sum2[T] % mod - A[i].b * Sum1[T] % mod + mod) % mod) % mod) % mod;
			Sum1[T] = (Sum1[T] + A[i].a * A[i].b ) % mod;
			Sum2[T] = (Sum2[T] + A[i].b ) % mod;
		}
	ans = (ans % mod + mod) % mod;
	printf("%lld\n", ans * 2 % mod);
    return 0;
}

写在最后

回来之后厌学了。

标签：HNCPC2024,int,题解,ll,long,2024,while,getchar,define
From： https://www.cnblogs.com/luckyblock/p/18470949

相关文章

  • 创建第一个Servlet（IDEA2024版）
    1.创建新项目2.添加web架构3.在web/WEB-INF下创建classes和lib两个文件夹4.配置项目的编译输出路径配置完如图5.添加servlet包找到安装的Tomcat的路径6.配置Tomcat修改此处地址这里也会随之改变7.添加servlet模型右键src后，发现New里面没有Servl......
  • 2024.10.16 模拟赛
    2024.10.16模拟赛T1divide简要题意给定一棵树的\(n\)个结点以及每个结点的\(fa_i\)，每个点的点权\(v_i\)，删除树中的两条边，将树拆分为三个非空部分。每个部分的权值等于该部分包含的所有节点的权值之和。出一种合理的拆分方案。根节点的\(fa_i=0\)\(n≤10^6\)solution......
  • [题解]NOIP2018模拟赛 plutotree
    题目描述给定一棵有\(n\)个节点的树，根节点为\(1\)，节点\(i\)有权值\(w[i]\)。这棵树非常奇怪，它的每个叶子结点都有一条连向根节点的权值为\(0\)的边。给定\(q\)次询问，每次给定\(u,v\)，请计算出一条\(u\)到\(v\)的路径（每条边最多经过\(1\)次），最小化该路径上的点权之和，并在其基础上最......
  • 2024CSP-J模拟赛9————S12678
    一，赛中得分T1100T2100T350T440总分290二，赛中概括  T1T2较快过，T3T4骗了90分（意料之中，这么好骗分！！！）。三，题目解析涂格子(paint)问题描述现在有一个 n 行 m 列的网格纸，一开始每个格子都是白色的。现在你可以任意挑选恰好 x 行和 y 列，将挑......
  • .NET周刊【10月第2期 2024-10-13】
    国内文章C#/.NET/.NETCore优秀项目和框架2024年9月简报https://www.cnblogs.com/Can-daydayup/p/18457705文章介绍了多个与C#.NET和ASP.NET相关的优秀开源项目和框架，包括AvaloniaUI、WaterCloud、CodeMaid、NetCoreServer等。这些项目各具特色，涵盖UI设计、快速开发、代码简化......
  • [20241016]Oracle C functions annotations补充.txt
    [20241016]OracleCfunctionsannotations补充.txt--//网站orafun.info可以查询oraclecfunctions.CreatedbyFritsHooglandwithalittlehelpfromKamilStawiarski.--//可以通过它了解oracle内部C函数.实际上可以直接下载相关文件,在本地使用.https://gitlab.com/Frits......
  • P10353 [PA2024] Grupa permutacji 题解
    神秘！在这些排列生成的置换群\(G\)里，若\(\exists\pi\inG\)使得\(\pi_i=k,\pi_j=l\)，则所有这些\((k,l)\)被同样数量的\(\pi\inG\)通过前述方法得出。证明：设\(\pi(i,j)=(k,l),\pi'(i,j)=(k',l')\)（意义前述），则\(\pi^{-1}\circ\pi'(k,l)=(k',l')......
  • 2024/10/16 模拟赛总结
    \(30+0+40+40=100\)，T4没看到输入不按顺序痛失\(35\)pts#A.最终测试很少见到不要dp的期望了直接枚举每一个人的四种情况，二分查找有多少种情况有多少人分比他高，最后除以\(16\)即可\(16\)是两个人的所有情况，即\(4\times4\)//BLuemoon_#include<bits/stdc++.h>......
  • 20222315 2024-2025-1 《网络与系统攻防技术》实验二实验报告
    1.实验内容1．使用netcat进行虚拟机和主机的连接，cron启动周期性定时任务。2．使用socat让虚拟机操作主机,并调用提前准备的程序，启动任务计划。3．使用MSFmeterpreter（或其他软件）生成后门程序，利用ncat传送到主机让主机运行后门程序，虚拟机获取主机shell。4．使用MSFmeterpreter（或其他......
  • 2024年 Java 面试八股文（20w字）
    第一章-Java基础篇1、你是怎样理解OOP面向对象   难度系数：⭐面向对象是利于语言对现实事物进行抽象。面向对象具有以下特征：继承：继承是从已有类得到继承信息创建新类的过程封装：封装是把数据和操作数据的方法绑定起来，对数据的访问只能通过已定义的接口多态性：多态性是指允......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99