A.Extremely Round
算法本质
模拟
题目大意
给定一个n，求1~n中美丽的数字个数。
- 美丽：
数字十进制中，有且仅有1个位数字不为0：如1、7、100、4000。
思路推演
以十进制的位为单位，第一位、第二位……
实际做的时候，为了抢时间，考虑可以打表，写了一个暴力打表预处理。
B.Notepad#
算法本质
模拟
题目大意
给出一个长度为n的字符串s，现在需要判断能否用至多n-1次操作制造出字符串t，其等于s。
每次操作可以：
- 向
t末尾加入任意一个字符 - 复制
t的某个子字符，在末尾粘贴
思路推演
至多n-1次，考虑能不能有一次复制粘贴相当于多次加字符。
将t中所有长度为2的子字符串放入set，添加新字符的时候检测。
C.Hamiltonian Wall
算法本质
模拟
题目大意
给出一个2*m的格子，格子只有黑白两种颜色。
可否找到一个路径走遍所有的黑色格子（不准重复走）。
思路推演
因为只有2行，从左向右推进即可。
对于每一列，只有数种情况：
- 上下都黑
可以通过，方位改变。 - 某一格黑
方位是否一致，一致可以通过 - 无黑
不可通过
D.Lucky Chains
算法本质
思维
题目大意
给定一对x y（x<y），对于答案k来说，任意的0 <= val < k，都满足gcd(x+val, y+val)==1的情况。
输出最大化k。（无限大请输出-1）
思路推演
可以发现，x y的差是不变的，而根据基本的数学定理可知，当gcd(x+v, y-x)==1时，x+v y+v也互质。
所以说本质上，就是y-x分解的各种素数，会像拦路虎一样拦截逐渐增大的x+val。
这个计算是相当简单的，但是可能会T，请用注意下面的优化：
- 先用埃式处理素数，用已经获得的素数集分解质因数
- 用
int别用long long（可能是为了卡掉普通的质因数分解方法，时间卡的比较紧）
E.Decomposition
算法本质
思维、状压dp
题目大意
给出长度为n的数组a[]，所有元素范围在0~3。
对于某个a[]的连续子数组依，其中元素次放入分组器使得其分为若干组：（设放入a[i]时已经存在k组）
- 依次讲元素尝试放入前
k组，若a[i]与当前组的末尾元素值按位和大于0，则将a[i]放入当前组的末尾 - 若当前
k组能无法接受a[i]，则新开编号为++k组，放入a[i]
每个a[]的连续子数组对ans的贡献是其最后的组数（k值）。
计算所有的a[]连续子数组的k值和——ans。
n <= 3e5思路推演
按位和、0~3的小大……毫无疑问，需要先找到规则的特征。
- 0值在任意时候都会单独成立一组
- 除去0值，其他元素最多成立3组
这是一个想到有效的结论，如果抛去0值，我们的状态数最多存在3*4*4=48种，如果满足前后缀的转移，则毫无疑问，使用状压dp的复杂度是ok的。
事实如此。
代码思路
dp(状态, pos)表示：目前状态经历了a[pos]的值 + 经历了a[pos~pos+1]的值 + 经历了a[pos~n]的值。
状态用vector<int>来表示。
我们固定左边界l，对于每个左边界，都ans += dp(全0状态, l)。dp(当前状态, i) = dp(经历i后的状态, i+1) + 贡献值(经历i后的状态的元素个数)
这里有一些问题的是，对于0，理论上我们也需要开一个新组，但是这样会导致内存爆掉。
所以我们可以统一记录当前0值的贡献，假设我们固定的左值下标为l，当前0值下标为i，在r取i~n时都会具有1的贡献，所以直接加上n-i+1的值即可。
其实其他值也可以，我们可以针对每一个导致开新组的元素，如果其下标为
i，则直接加上n-i+1的值。不过为了便于理解，还是挨个加。
思路推演-2（未ac）
同时因为状态足够少，我们可以推出新组数变化的特征：（暂时自动忽略0）
- 1组-->2组
出现1 2或者2 1 - 2组-->3组
若前面有1 2，则是3 2 2 ... 2 2 1
若前面有2 1，则是3 1 1 ... 1 1 2
所以搜索所有特征区间，这4种特征分别放入4个队列，可以叫做q12 q21 q321 q312。
保证左边界较小的在前。（顺序历便的话自动就是左边界小的在前）
随后枚举l = 1~n。
详细看代码，但是WA16，不知道哪错了。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int a[maxn];
map<vector<int>, int> dp[maxn];
vector<int> go(vector<int> tai, int pos)
{
int val=a[pos];
if (val==0)
return tai; // 默认状态不添加0
else
{
bool f=0;
for (int i=0; i<tai.size() && f==0; i++)
if ((tai[i]&val) > 0)
{
f=1; // f==1表示不需要新加组，更新状态，但是此点贡献为0
tai[i] = val; // 更新状态
}
if (f==0) // 说明需要加组
tai.push_back(val);
return tai;
}
}
int f(vector<int> tai, int pos) //记录状态、当前pos
{
if (pos == n+1) return 0;
if (dp[pos].count(tai)) return dp[pos][tai]; //记忆化
auto nxt=go(tai, pos); //tai经历a[pos]后的状态
int res = nxt.size() + f(nxt, pos+1); //当前贡献值 + 之后的贡献值
if (a[pos]==0) res+=n-pos+1; //0值的贡献值单独计算
return dp[pos][tai]=res;
}
inline void solve()
{
//init
cin>>n;
rep(i,1,n) cin>>a[i];
//cal
int ans=0;
for (int l=1; l<=n; l++) //枚举固定左边界
ans += f(vector<int>(0), l);
//out
cout<<ans<<endl;
return;
}
评论 (0)