immix's blog

A. Order Something Else 题意 ABC 特有的 A 题题意，容易读错。 有一件商品价格为 PPP 元，你可以原价购买，或者多买一件其他商品后以 QQQ 元购买。 其他商品的价格为 D1,D2,…,DnD_1,D_2,\ldots,D_nD1​,D2​,…,Dn​。 请问入手这个商品最少要花多少钱？ 解法 答案为 min⁡{P,Q+min⁡Di}\min\{P,Q+\min D_i\}min{P,Q+minDi​} 12345678910111213141516171819202122232425262728#include<bits/stdc++.h>using namespace std;using ll=long long;using ull=unsigned long long;using pii=pair<int,int>;#define begend(x) x.begin(),x.end()#define mem0(x) memset(x,0,sizeof(x))#define YES puts("Yes")# ...

A. Subtraction Game 题意 有两个正整数 a,b (a<b)a,b\ (a<b)a,b (a<b)。 现在有一个游戏：初始有 nnn 个石子，每个玩家每回合可以拿走 aaa 个或 bbb 个石子。 请求出一个 nnn，使得在这个状况下，后手必胜。 解法 显然 a+ba+ba+b 一定是一个后手必胜的解。 123456789101112131415161718192021222324252627282930#include<bits/stdc++.h>using namespace std;using ll=long long;using ull=unsigned long long;using pii=pair<int,int>;#define begend(x) x.begin(),x.end()#define mem0(x) memset(x,0,sizeof(x))#define YES puts("Yes")#define NO puts("No")int read(){ ...

AK 了！我愿称之为信心场。 A. Rudolph and Cut the Rope 题意 有 nnn 个钉子，每个钉子高度在 aia_iai​，并且有一根长度为 bib_ibi​ 的绳子连接着钉子和糖。 问：想要把糖放到 h=0h=0h=0 的地方，至少要割断几根绳子？ 解法 若 ai>bia_i>b_iai​>bi​，这根绳子就要割掉，否则不用割掉。 1234567891011121314151617181920212223242526272829303132333435#include<bits/stdc++.h>using namespace std;using ll=long long;using ull=unsigned long long;using pii=pair<int,int>;#define begend(x) x.begin(),x.end()#define mem0(x) memset(x,0,sizeof(x))#define YES puts("Yes")#define NO puts(&qu ...

A. The Man who became a God 题意 给定 nnn 个正整数，a1,a2,…,ana_1,a_2,\ldots,a_na1​,a2​,…,an​，把它们分成 kkk 连续的段，每段的值为相邻两数的差绝对值的和。求每段和的最小值。 1≤k≤n≤1001\le k \le n \le 1001≤k≤n≤100。 解法 1 （动态规划） 设 fi,jf_{i,j}fi,j​ 代表前 iii 个数分成 jjj 段的最小值 (i≥j>0)(i\ge j > 0)(i≥j>0)。 fi,j=min⁡j−1≤k<i(fk,j−1+∑p=k+1j−1∣ap−ap+1∣)f_{i,j}=\min_{j-1 \le k < i} \left( f_{k,j-1}+ \sum_{p=k+1}^{j-1} |a_p-a_{p+1}| \right) fi,j​=j−1≤k<imin​​fk,j−1​+p=k+1∑j−1​∣ap​−ap+1​∣​ 边界条件 f1,1=0f_{1,1}=0f1,1​=0。复杂度 O(n2)O(n^2)O(n2)。 123 ...

简单场。 A. New Scheme 题意 给出八个整数，求是否满足如下条件： 都在 [100,675][100,675][100,675] 的范围内； 都是 252525 的倍数； 单调不下降。 代码 12345678910111213141516171819202122232425262728293031323334#include<bits/stdc++.h>using namespace std;using ll=long long;using ull=unsigned long long;using pii=pair<int,int>;#define begend(x) x.begin(),x.end()#define mem0(x) memset(x,0,sizeof(x))#define YES puts("Yes")#define NO puts("No")int read(){ int f=1,x=0;char c=getchar(); while(!isdigit(c))
...

总表 刘汝佳，陈锋《算法竞赛入门经典训练指南》第 1 章——算法设计基础 更新中…… 题号 题目名称（点击跳转题解） 备注 UVA 11636 Hello World! 递推 UVA 11039 Building Designing 贪心 UVA 1368 DNA Consensus String 贪心 UVA 10970 Big Chocolate 模拟，公式 UVA 10382 Watering Grass 贪心，区间覆盖 UVA 10905 Children’s Game 贪心 UVA 1422 Processor 二分答案，贪心 UVA 11627 *Slalom 暂缺 UVA 11100 The Trip, 2007 贪心 UVA 1450 Airport 二分答案 UVA 1467 *Installation 暂缺 UVA 1344 Tian Ji – The Horse Racing 贪心 UVA 11389 The Bus Driver Problem 贪心 UVA 1418 *WonderTeam 暂缺 ...

例题来自《信息学奥赛一本通·提高篇》。 哈希函数 设字符串为 s=c1c2…cms=c_1c_2\ldots c_ms=c1​c2​…cm​，定义哈希函数 f(s)=(c1bm−1+c2bm−2+⋯+cmb0) mod Mf(s)=(c_1b^{m-1}+c_2b^{m-2}+\dots+c_mb^0)\bmod Mf(s)=(c1​bm−1+c2​bm−2+⋯+cm​b0)modM。其中 MMM 为一大质数，bbb 为小于 MMM 的任意整数。 比如说这样： 123456789const int b=114,M=1e9+9;int h(char* str){ int l = strlen(str); int res=0; for(int i=0;i<l;i++){ res=((ll)res*b+str[i])%M; } return res;} O(1) 求子串哈希 先预处理数组 HiH_iHi​ 代表字符串 sss 前 iii 位的哈希值。则字串 [l,r][l,r][l,r] 的哈希值可以表 ...

约定下标从 1 开始。 字符串匹配问题 给定字符串 s1s_1s1​，以及模式串 s2s_2s2​，求 s2s_2s2​ 在 s1s_1s1​ 内的所有出现位置。 一个很朴素的想法就是一位一位进行比较，复杂度 O(MN)O(MN)O(MN)，M,NM,NM,N 为两字符串长度。 123456789101112131415const int N = 1e6+5;char s1[N],s2[N];void brute_force(){ int l1 = strlen(s1); int l2 = strlen(s2); for(int i=0;i+l2<=l1;i++){ bool flag=1; for(int j=0;j<l2;j++){ if(s1[i+j]!=s2[j]){ flag=0;break; } } if(flag)printf("match at ...

众所周知，平衡树是提高数据结构。 平衡树 平衡树首先是一颗二叉搜索树 (BST)。二叉搜索树的定义如下： 空树是二叉搜索树。 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。 二叉搜索树的左右子树均为二叉搜索树。 我们不难发现，在二叉搜索树上可以很方便的进行如下操作： 从大到小遍历 查询最值 插入元素 删除元素 求元素排名 求排名为 k 的元素 除了第一个操作复杂度为 O(n)O(n)O(n)，其他这些操作的复杂度都是 O(h)O(h)O(h) 的，其中 hhh 为树的高度。最坏情况下，二叉搜索树会退化成一条链，于是复杂度都退化为 O(n)O(n)O(n)，这是我们不希望看到的。因此，出现了平衡树的概念。平衡指：每一个结点的左子树和右子树高度差最多为 111，这样就可以保证所有复杂度都是在 O(log⁡n)O(\log n)O(logn) 级别完成的。 set 首先，在你写平衡树之前，先想想 STL 的 set （或者 multiset） 够不够你用。 从大到小遍历：可以 ...

U N R A T E D 今回のコンテストは、採点の遅れの影響で、Unratedとさせていただきます。申し訳ありません。 /　Due to the delay in scoring, this contest will be Unrated. We are sorry for the inconvenience. A. Echo 题意 给定一个字符串。每个字符输出两遍。 代码 1234567891011#include<bits/stdc++.h>using namespace std;int main(){ int x;cin>>x; string s;cin>>s; for(auto x:s){ cout<<x<<x; } return 0;} B. Base 2 题意 给定 A0,A1,…,A63A_0,A_1,\ldots,A_{63}A0​,A1​,…,A63​ 求 A020,A121,…,A63263A_02^0,A_12^1 ...