首页 > 其他分享 >The 2024 CCPC Online Contest

The 2024 CCPC Online Contest

时间：2024-09-09 19:37:25浏览次数：15  
标签：std Contest int LL kN long CCPC 2024 define

目录

写在前面

补题地址：https://codeforces.com/gym/105336

以下按个人向难度排序。

唉唉唐吧真是

我去居然还能打出名额哈哈真牛逼

L

签到。

K

签到。

dztlb 大神直接秒了。

显然奇数先手取 1 必胜，则偶数时为了让自己不输，先手和后手均会保证在取到 2 之前，取的数和沙堆的大小一直都是偶数，否则会让对方必胜。

于是一个显然的想法是考虑 \(\operatorname{lowbit}(n)\)，发现当 \(\operatorname{lowbit}(n)\le k\) 时，仅需先手取 \(\operatorname{lowbit}(n)\) 然后模仿后手操作即可，否则一次操作后 \(\operatorname{lowbit}(n)\le k\)，则后手必胜。

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

#define ll long long
#define ull unsigned long long

int T,n,k;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin>>T;
	while(T--){
		bool fl=0;
		cin>>n>>k;
		int tt=1;
		while(tt<=k){
			if(n%tt==0){
				if((n/tt)%2==1) fl=1;
			}
			tt*=2;	
		}
		if(fl) puts("Alice");
		else puts("Bob");
	}
	return 0;
}

B

枚举，结论。

一个显然的发现是有序（升序或降序）数列代价最小，可以考虑调整法证明，当某两位置不有序时，一定会对包含这两个位置的一些区间造成更多的代价。于是仅需考虑重复元素之间的顺序的贡献即可。

注意特判全相等时升序降序是等价的。

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

#define LL long long
#define ull unsigned long long

const int kN = 1e6 + 10;
const LL p = 998244353;
int n, a[kN], cnt[kN], num;
LL fac[kN];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	std::cin >> n;
	for (int i = 1; i <= n; ++ i) std::cin >> a[i];
	fac[1] = 1;
	for (int i = 2; i <= n; ++ i) fac[i] = fac[i - 1] * i % p;
	std::sort(a + 1, a + n + 1);
	
	LL ans1 = 0;
	for (int l = 1; l <= n; ++ l) {
		for (int r = l; r <= n; ++ r) {
			ans1 += 1ll * (a[r] - a[l]);
		}
	}
	
	for (int i = 1; i <= n; ++ i) {
		++ cnt[a[i]];
		if (cnt[a[i]] == 1) ++ num;	
	}
	LL ans2 = (num == 1 ? 1 : 2);
	for (int i = 1; i <= n; ++ i) {
		if (cnt[a[i]] == 0) continue;
		ans2 = ans2 * fac[cnt[a[i]]] % p;
		cnt[a[i]] = 0;
	}
	std::cout << ans1 << " " << ans2 % p;
	return 0;
}

D

DP。

显然的 DP，发现构造字符串的方案实际构成一个完全二叉树的结构，于是仅需考虑在构造这棵树的过程中，统计完全位于两棵子树中的字符串数量，以及跨越根节点的字符串数量即可。

于是可以设一个显然的状态 \(f_{i, l, r}\) 表示对于前缀 \(1~i\) 中，子串 \(t[l:r]\) 的出现次数，转移时讨论跨越子树的字符串中，根节点是否有贡献即可。详见代码。

总时间复杂度 \(O(n^4)\) 级别。

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

#define ll long long
#define ull unsigned long long

const int kN = 110;
const ll p = 998244353;

ll f[kN][kN][kN], pw2[kN];
int n, m;
string s, t;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	std::cin >> s >> t;
	n = s.length(), m = t.length();
	s = "$" + s, t = "$" + t;
	
	
	pw2[0] = 1; 
	for (int i = 1; i <= 10; ++ i) pw2[i] = pw2[i - 1] * 2;
	
	for (int i = 1; i <= n; ++ i) {
		for (int l = 1; l <= m + 1; ++ l) {
			for (int r = 0; r < l; ++ r) {
				f[i - 1][l][r] = 1;
			}
		}
		
		for (int l = 1; l <= m; ++ l) {
			for (int r = l; r <= m; ++ r) {
				int len = r - l + 1;
				if (i <= 8 && pw2[i] < len) break;
				
				f[i][l][r] = 2ll * f[i - 1][l][r] % p;
				for (int j = l; j < r; ++ j) {
					f[i][l][r] += 1ll * f[i - 1][l][j] * f[i - 1][j + 1][r] % p;
					f[i][l][r] %= p;
				}
				for (int j = l; j <= r; ++ j) {
					if (s[i] != t[j]) continue;
					f[i][l][r] += 1ll * f[i - 1][l][j - 1] * f[i - 1][j + 1][r] % p;
					f[i][l][r] %= p;
				}
			}
		}
	}
	cout << f[n][1][m];
	return 0;
}
/*
aaaaaa a

abc abca
*/

E

期望。

呃呃这题场上三个人看了 4h 中间过了三道题没做出来真唐吧

最大数量即尽量使所有字符串没有公共前缀，即尽可能使每一层的节点均填满。则答案即为：

\[\sum_{i=0}^{m} \min(n, 26^i) \]

考虑期望。插入的每个字符串长度均为 \(m\)，则每个字符串都会占据 \(1\sim m\) 层的一个节点。即对于建出来的字典树，第 \(i\) 层上的所有节点，一定是对应了这 \(n\) 个字符串的长度为 \(i\) 的前缀。又字符串随机构造，则相当于在第 \(i\) 层上随机选择了 \(n\) 个节点，并求随机选择节点的数量。

考虑每一个节点对这一层的贡献再乘上本层总数即为本层贡献。考虑反面，求该节点没有被选择的概率（相当于限制仅能从 \(26^i - 1\) 个节点中独立地随便选 \(n\) 个），则可知期望的总数为：

\[\sum_{i=0}^{m} \left[ 1 - \left(\frac{26^i - 1}{26^i}\right)^n \right] 26^i \]

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

#define LL long long
#define ull unsigned long long

const int kN = 1e6 + 10;
const LL p = 998244353;

LL n, m;

LL qpow(LL x_, LL y_) {
	LL ret = 1;
	while (y_) {
		if (y_ & 1ll) ret = ret * x_ % p;
		x_ = x_ * x_ % p, y_ >>= 1ll;
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	std::cin >> n >> m;
	
	LL ans = 0;
	for (int i = 0; i <= m; ++ i) {
		if (i <= 3 && qpow(26, i) <= n) ans += qpow(26, i);
		else ans += n;
	}
	cout << ans % p << " ";
	
	LL sum = 0, inv = qpow(26, p - 2), invpw = 1, pw = 1;
	for (int i = 0; i <= m; ++ i) {
		LL s = (1 - qpow(1 - invpw + p, n) + p) % p * pw % p;
		invpw = invpw * inv % p, pw = pw * 26 % p;
		sum += s, sum %= p;
	}
	cout << sum;
	return 0;
}

J

异或，线性基

感觉线性基裸题啊呃呃

考虑令 \(c_i = a_i\oplus b_i\)，并预处理 \(s_a = \oplus_{1\le i\le n} a_i, s_b = \oplus_{1\le i\le n} b_i\)。由异或的性质，则交换 \(a_i, b_i\) 对 \(s_a, s_b\) 的影响等价于令两者均异或上 \(c_i\)。问题变为可以任意异或 \(c_i\)，求 \(\min \max(s_a, s_b)\)。

考虑从高位到低按位贪心，设当前枚举到第 \(i\) 位，且有 \(\max(s_a, s_b) = s_{1}\)，另一方为 \(s_{2}\)：

  • 若 \(s_1, s_2\) 该位均为 0，或仅有 \(s_2\) 该位为 0，则异或后不会使答案更优，跳过；
  • 若 \(s_1\) 该位为 1，则考虑尽量将这一位消除，且不影响已确定的更高的位的答案。

由上述不影响更高位的要求，想到考虑对 \(c_i\) 维护线性基，然后直接在上述贪心过程中使用对应的向量消去答案中某位的 1 即可。

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

#define int long long
#define ull unsigned long long

const int kN = 1e6 + 10;

int n, a[kN], b[kN], suma, sumb, c[kN];
int ans, p[70];

void insert(int c_) {
	for (int i = 60; ~i; -- i) {
		if (!(c_ >> i)) continue;
		if (!p[i]) {
			p[i] = c_;
			break;
		}
		c_ ^= p[i];
	}
}
void solve(int sa_, int sb_) {
	int x = sa_, y = sb_;
	for (int i = 60; ~i; -- i) {
		if (x < y) std::swap(x, y);
		if (!(x >> i & 1) && !(y >> i & 1)) continue;
		if ((x >> i & 1) && (y >> i & 1)) {
			x ^= p[i], y ^= p[i];
		} else if ((x >> i & 1) && x >= y) {
			x ^= p[i], y ^= p[i];
		} else {
			continue;
		}
	}
	ans = min(ans, max(x, y));
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int T; std::cin >> T;
	while (T --) {
		std::cin >> n;
		suma = sumb = 0;
		for (int i = 1; i <= n; ++ i) std::cin >> a[i], suma ^= a[i];
		for (int i = 1; i <= n; ++ i) std::cin >> b[i], sumb ^= b[i];
		
		for (int i = 0; i <= 60; ++ i) p[i] = 0;
		for (int i = 1; i <= n; ++ i) c[i] = a[i] ^ b[i], insert(c[i]);
		
		ans = max(suma, sumb);
		solve(suma, sumb);
		cout << ans << "\n";
	}
	return 0;
}
/*
1
2
2147483646 2147483647
1 2147483647
*/

I

DP。

dztlb 大神写的，看起来是简单题，就不补了。

code by dztlb：

#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 int N=505;
const int mod=998244353;
int n,m;
int a[N],b[N];
int sum[N];
int f[N][N];
int dp[N];
void solve(int k){
	memset(f,0,sizeof(f));
	sum[0]=0;
	for(int i=0;i<=m;++i) f[i][0]=1;
	for(int i=1;i<=m;++i){
		for(int j=1;j<=min(i, n);++j){
			if(j>sum[max(b[i]-k,0ll)]) break;
			f[i][j]=f[i-1][j]+f[i-1][j-1]*max(sum[max(b[i]-k,0ll)]-j+1,0ll)%mod;
			f[i][j]%=mod;
		}
	}
	for(int i=1;i<=min(n, m);++i){
		dp[k]+=f[m][i];
		dp[k]%=mod;
	}
}
signed main() {
//	ios::sync_with_stdio(false);
//	cin.tie(0), cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i) {
		cin>>a[i];
		sum[a[i]]++;
	}
	
	for(int i=1;i<=m;++i) cin>>b[i];
	sort(b+1,b+1+m);
	sort(a+1,a+1+n);
	int maxx=0;
	int minn=1000;
	for(int i=1;i<=m;++i){
		for(int j=b[i]-1;j>=1;--j){
			if(sum[j]) minn=min(minn,b[i]-j),maxx=max(maxx,b[i]-j);
		}
	}
	if(minn==1000||maxx==0){
		puts("0");
		return 0;
	}
	for(int i=1;i<=500;++i) sum[i]+=sum[i-1];
//	minn=1;
//	cout<<minn<<' '<<maxx<<endl;
	for(int k=minn;k<=maxx;++k){
		solve(k);
	}
	int ans=dp[maxx]*maxx%mod;
	for(int i=minn;i<maxx;i++){
		ans+=(dp[i]-dp[i+1]+mod)%mod*(i)%mod;
		ans%=mod;
	}
	cout<<ans<<endl;
	return 0;
}
/*
5 5
1 2 3 4 5
2 3 4 5 6
*/

G

网络流

显然应当让第一个人尽量在他要吃的所有菜都买单，于是可以直接计算出第一个人花的钱的上界，其他人花的钱的上界一定是第一个人的上界减 1，问能否在所有上界满足情况下能买所有菜。

仅有上界则是显然的最大流问题，建图求最大流检查是否等于所有菜的总价即可。

注意建边时的实际意义一定要符合真实情况！

//知识点：
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
const int kM = 2e6 + 10;
const LL kInf = 1e18 + 2077;
//=============================================================
int n, m, S, T, a[kN], car[kN];
int x[kN], y[kN], dish[kN];
int nodenum, maxnodenum, edgenum = 1, v[kM], ne[kM], head[kN];
int cur[kN], dep[kN];
LL w[kM];
LL flag, maxa, maxflow;
//=============================================================
void addedge(int u_, int v_, LL w_) {
  v[++ edgenum] = v_;
  w[edgenum] = w_;
  ne[edgenum] = head[u_];
  head[u_] = edgenum;

  v[++ edgenum] = u_;
  w[edgenum] = 0;
  ne[edgenum] = head[v_];
  head[v_] = edgenum;
}
void init() {
  std::cin >> n >> m;
  
  edgenum = 1;
  nodenum = n + m;
  maxnodenum = n + m + 2;
  S = ++ nodenum, T = ++ nodenum;
  for (int i = 1; i <= maxnodenum; ++ i) head[i] = 0;

  for (int i = 1; i <= n; ++ i) {
    std::cin >> a[i] >> car[i]; 
  }
  maxa += car[1];
  for (int i = 1; i <= m; ++ i) {
    std::cin >> x[i] >> y[i] >> dish[i];
    if (x[i] == 1 || y[i] == 1) maxa = std::min(1ll * a[1], maxa + dish[i]);
  }

  addedge(S, 1, maxa - car[1]);
  for (int i = 2; i <= n; ++ i) {
    if (car[i] >= maxa) flag = 1;

    LL w_ = std::max(0ll, maxa - car[i] - 1);
    w_ = std::min(std::max(0ll, 1ll * a[i] - car[i]), w_);
    addedge(S, i, w_);
  }
  for (int i = 1; i <= m; ++ i) {
    addedge(x[i], i + n, kInf);
    addedge(y[i], i + n, kInf);
    addedge(i + n, T, dish[i]);
    maxflow += dish[i];
  }
}
bool bfs() {
  std::queue <int> q;
  memset(dep, 0, (nodenum + 1) * sizeof (int));
  dep[S] = 1; //注意初始化 
  q.push(S); 
  while (!q.empty()) {
    int u_ = q.front(); q.pop();
    for (int i = head[u_]; i > 1; i = ne[i]) {
      int v_ = v[i], w_ = w[i];
      if (w_ > 0 && !dep[v_]) {
        dep[v_] = dep[u_] + 1;
        q.push(v_);
      }
    }
  }
  return dep[T];
}
LL dfs1(int u_, LL into_) {
  if (u_ == T) return into_; 
  int ret = 0;
	for (int i = cur[u_]; i > 1 && into_; i = ne[i]) {
    int v_ = v[i];
    LL w_ = w[i];
    if (w_ && dep[v_] == dep[u_] + 1) {
			LL dist = dfs1(v_, std::min(into_, w_));
			if (!dist) dep[v_] = kN;
			into_ -= dist; 
      ret += dist;
      w[i] -= dist, w[i ^ 1] += dist;
			if (!into_) return ret;
		}
  }
	if (!ret) dep[u_] = 0; 
  return ret;
}
LL dinic() {
  LL ret = 0;
  while (bfs()) {
    memcpy(cur, head, (nodenum + 1) * sizeof (int));
    ret += dfs1(S, kInf);
  }
  return ret;
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  init();
  if (flag) {
    std::cout << "NO\n";
    return 0;
  }
  std::cout << ((dinic() == maxflow) ? "YES" : "NO") << "\n";
  return 0;
}
/*
4 3
1000 900
1000 900
1000 900
1000 900
1 2 100
1 3 100
1 4 100

3 1
100 50
70 50
100 48
3 3 1
*/

C

贪心，DP。

场上想出来那个树形 DP 但是觉得讨论起来会很麻烦就没写。

写在最后

学到了什么：

  • E：每个元素均等概率情况，考虑单个元素出现在答案中的期望概率，然后乘上元素数量即为总贡献。
  • G：注意实际意义！

标签：std,Contest,int,LL,kN,long,CCPC,2024,define
From： https://www.cnblogs.com/luckyblock/p/18405153

相关文章

  • 【win/mac】Adobe的视频特效编辑软件软件After Effects (AE)2024版本下载与安装
    目录1.1软件概述1.2主要功能1.3版本信息二、安装步骤2.1准备工作下载软件：2.2安装过程三、常用快捷键3.1基础操作快捷键3.2视图与导航快捷键3.3编辑与动画快捷键扩展快捷键1.1软件概述AdobeAfterEffects（简称AE）是Adobe公司推出的一款功能强大的图形视......
  • 【win/mac】Adobe的矢量图形编辑与设计软件Adobe Illustrator (Ai)2024版本下载与安装
    目录一、软件概述1.1定义与用途1.2主要特点1.3用户群体二、安装步骤2.1下载软件2.2安装准备2.3安装过程2.4验证安装三、常用快捷键3.1文件操作3.2编辑与选择3.3视图与导航3.4绘图与变换一、软件概述1.1定义与用途AdobeIllustrator是一款由Ado......
  • 【win/mac】Adobe的专业音频编辑软件Adobe Audition (AU)2024版本下载与安装
    目录一、软件简介二、安装步骤1.下载2.安装软件三、常用快捷键1.文件操作2.播放与录制3.视图与缩放一、软件简介AdobeAudition是一款由Adobe公司开发的专业音频编辑软件，广泛用于音频后期制作，包括混音、剪切、修复、录制和处理等。该软件以其强大的功能和用户......
  • 2024ccpc网络赛补题
    L.网络预选赛题意:查询多少个2*2的子矩阵满足[c,c][p,c]输出个数Code:#include<bits/stdc++.h>usingnamespacestd;strings="ccpc";intdirs[4][2]={{0,0},{0,1},{1,0},{1,1}};chara[505][505];voidsolve(){intn,m;......
  • 安徽大学主办、院士杰青，连续3年EI检索，稳且快易中稿-第四届机械自动化与电子信息工程国
    第四届机械自动化与电子信息工程国际学术会议（MAEIE2024）20244th InternationalConferenceonMechanicalAutomationandElectronicInformationEngineering2024年10月18-20日  中国·安徽·合肥  www.maeie.org※ 收录检索：IEEEXplore、EI(核心)、Scopus​......
  • 2024/8/30总结
    天平题目：物理老师YJ有一个长杆天平，天平的两臂长均为15，将长杆看作x轴，则平衡点在0位置处，负数位置在左臂上，正数位置在右臂上。长杆上有n个位置有挂钩可以挂秤砣。YJ有m个秤砣，质量分别为gi，每个挂钩可以不挂也可以挂任意个秤砣。YJ想要知道，在使用所有秤砣的条件下，......
  • 2024.08.28得物（超简单）
    1.拨动数字已知小红每次可以把一个数字向下拨动，即9变成8，8变成7...1变成0，0变成9。她想知道从第一个状态变成第二个状态需要最少拨动多少次?简单打卡intmain(){stringa,b;cin>>a>>b;intres=0;for(inti=0;i<a.size();i++){intnum1=a[i]-......
  • 华为OD机试真题-字符串化繁为简-2024年OD统一考试（E卷）
    题目描述给定一个输入字符串Q，字符串只可能由英文字母('a'~''、'^'~'')和左右小括号('、”')组成。当字符里存在小括号时，小括号是成对的，可以有一个或多个小括号对，小括号对不会嵌套，小括号对内可以包含1个或多个英文字母9，也可以不包含英文字母。当小括号对内包含多个英文字......
  • 2024.08.17米哈游(有难度)
    1.米小游的原石计划为了抽到心爱的五星角色，米小游需要至少n颗原石。目前米小游手里没有任何的原石，距离卡池结束还有m天。原石有两种获取方式，一种是充小月卡，另一种是直接买。1.充一次月卡需要30块钱，可以增加30天的祝福次数，每天只能领一次祝福（90原石），购买当天可额外领取......
  • 企业文件加密软件怎么选？2024超好用的十款企业文档加密软件推荐！臻品优选！
    "数据如金需锁固，密文守护保安宁。"文件加密软件是守护企业数据安全的重要利器，选择一款适合企业自身需求的加密软件，不仅能够提升数据安全性，还能优化团队协作效率，确保业务连续性。本文特为您臻选2024年超好用的十款企业文档加密软件，助力您的企业数据在数字化浪潮中稳如磐石。......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99