526互联

CSP-J 济南刷题训练营

发布时间 2023-07-24 21:12:20作者: CheZiHe929

Day 1：基础算法

枚举

从可能得集合中一一尝试统计贡献。

模拟

模拟题目中要求的操作

NOIP2014 生活大爆炸版石头剪刀布

洛谷链接：P1328 [NOIP2014 提高组] 生活大爆炸版石头剪刀布

注意到赢了是得 \(1\) 分，平局和输都是 \(0\) 分，所以我们直接根据题意打表。

int Vs[5][5]={{0,0,1,1,0},{1,0,0,1,0},{0,1,0,0,1},{0,0,1,0,1},{1,1,0,0,0}};

然后我们又发现是循环出拳，所以我们用取模的方法来实现。

完整代码：

#include <bits/stdc++.h>
using namespace std;
int n,lena,lenb;//题面所示 
int a[205],b[205];//两个人的出拳顺序
int pointa,pointb;//两个人的得分情况 
int Vs[5][5]={{0,0,1,1,0},{1,0,0,1,0},{0,1,0,0,1},{0,0,1,0,1},{1,1,0,0,0}};//打表 
signed main(){
    cin>>n>>lena>>lenb;
    for(int i=0;i<lena;i++)cin>>a[i];
    for(int i=0;i<lenb;i++)cin>>b[i];
    for(int i=0;i<n;i++){
        pointa+=Vs[a[i%lena]][b[i%lenb]];
        pointb+=Vs[b[i%lenb]][a[i%lena]];//取模 
    }
    cout<<pointa<<' '<<pointb<<endl;
    return 0;
}

CODECHEF PAINTING

  • 题面：
    一个无穷大的网格，机器人初始在 \(a_{0,0}\) 上。进行 \(n\) 次操作，每次操作给定一个字符 \(s\) 和一个代表距离的正整数 \(d\)。字符共有四种可能，U 代表向上，D 代表向下，R 表示向左，L 代表向右。机器人会向相应的方向行进 \(d\) 个单位长度，并将其经过的位置染为白色。问每次移动后新增加的白色格子的数量。

  • 注意点：

  1. 一个格子可能被重复染色，但是我们只能计算一次（第一次）。
  2. 但是不能挨个枚举走过的每个格子，会 TLE。
  • 因此得到一个大致的思路：
  1. 依次计算每次路径走过的格子的数量。
  2. 枚举之前的路径计算交集。
  3. 对交集进行处理，求已经被染色的格子的数量。
  4. 用总共经过的格子的数量减去交集的格子的数量就是我们每次要求的答案。
  • 计算交集
  1. 如果是计算横的路径和竖的路径的交集，只可能是有一个格子或者是空集。
  2. 如果同竖或同横的话，两条路径同行（列）交集为空或者是该行（列）的一个区间，不同行（列）交集就为空。
  • 整合
    我们通过上述分讨发现两条路径之间的交集不是为空就是该路径上的一个区间（一个点也算区间），对这些交集求并后可以在排序后将重复的部分合并起来。

小结

  • 用到模拟和枚举的题细节复杂且多，需要注意读题和模拟样例。

  • 先写代码框架后对其拆分成更细的模块，进行补充。

递推

通过若干步可重复的运算来计算复杂问题的方法。

P1192 台阶问题

洛谷链接：P1192 台阶问题

令 \(a_i\) 为到达第 \(i\) 级台阶的方案数，对于每一个 \(a_i\)，我们可以枚举 \(a_{i-1}\) 的方案数。

由此我们可以得到递推式：
\(a_0=1\);
\(a_i=\sum_{j=1}^{min(i,k)} a_{i-j}\)。

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e5+3;
int n,k;
long long a[mod];
signed main(){
	cin>>n>>k;
	a[0]=a[1]=1;
	for(int i=2;i<=n;i++){
		if(i<=k)a[i]=(a[i-1]*2)%mod;
		else a[i]=(a[i-1]*2-a[i-k-1])%mod;
	}
	cout<<(a[n]+mod)%mod<<endl;//别忘了加上再模一次
	return 0;
}

贪心

  • 每次做出一个选择后将原问题转化为相似的、规模更小的子问题求解。

  • 证明时一般先假设所有的最优解都不包括这个局部最优解，然后将其中的一部分替换为该局部选择使得答案不劣。重复上述过程直至找到答案。

例题：分数背包

\(n\) 个物品，第 \(a_i\) 个物品的体积为 \(v_i\) 价值为 \(w_i\)。我们可以对物品进行切割，如果切割出的体积为 \(x\)，则其价值为 \(w_i × （x/v_i）\)，求体积不超过 \(m\) 的物品的最大价值和。

每次取性价比最大的物品，所以按照 \(w_i / v_i\) 排序即可。（具体证明见 PPT）

事实上这道题还可以用类似找中位数的方法直接 O(n) 计算答案

例题：\(k\) 叉哈夫曼树

\(n\) 个权值非负的元素，每次可以合并其中不超过 \(k\) 个元素（和合并果子有点类似，但是只能合并 \(2\) 个数），合并后新产生的元素为这些元素之和，并产生同样数值的代价。求将这些元素合并成一个的代价。

  • 做法
    补 \(0\) 到使 \(n-1\) 是 \(k-1\) 的倍数，然后每次取最小的 \(k\) 个合并（小的数合并多次，大的数少合并几次）。

  • 证明
    假设一定存在最优解不包含该决策，那么假设存在儿子个数不为 \(k\) 的非叶子节点，可以将深度大的叶子补到深度小的空位上；如果没有一个非叶子节点儿子是前 \(k\) 小的，可以将一个前 \(k\) 小的与一个深度最大的节点替换。

CF632C The Smallest String Concatenation

洛谷链接：CF632C The Smallest String Concatenation

用手写 cmp 和 sort 就简单的解决了。

#include <bits/stdc++.h>
using namespace std;
string s[3000000];

bool cmp(string a,string b){//手写 cmp 比较器
	return a+b<b+a;//比较两种拼接方式的大小
}

int n;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>s[i];
	sort(s+1,s+n+1,cmp);
	for(int i=1;i<=n;i++) cout<<s[i];
	return 0;
}

二分