A.Trust Nobody
算法本质
思维
题目大意
给定长n的数组a[]，其a[x]表示第x个人说：这里有至少a[x]个说谎者。
一共n个人，每个人只有说谎者和非说谎者身份。
若存在满足条件的情况，输出说谎者数目
反之输出-1
思路推演
很显然，我们只需要暴力假设说谎者数目，然后检查当前假设的数目是否符合条件（通过前缀和、桶排序、sort处理等等其中一种方法，可以使得单次查询复杂度O(1)），所以整体是O(n)的复杂度。
B.Lunatic Never Content
算法本质
思维
题目大意
给定长度n的数组a[]，对齐进行一次以下操作：
- 选择整数
x，使得a[]中所有元素都对x取余
保证最后a[]成为一个回文数组，输出最大化x。（若x无限大输出0）
思路推演
最后的目的是让a[]形成回文，则将a[]的元素一对一对拿出来，有n/2对：
现在目的是找到一个x，使得这些对元素对x同余。
这一步，更换题意，进一步抽象题目的意思，找到算法本质
两数对x同余，很快可以写成两数之差对x取余为0。
显然，这里有n/2个条件，要使得x尽可能大，我们取差的最大公因数即可。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int a[maxn];
inline void solve()
{
cin>>n;
rep(i,1,n) cin>>a[i];
int ans=0;
for (int l=1, r=n; l<=r; l++, r--)
ans = gcd(ans, abs(a[l]-a[r])); // gcd对于0的一些特性
cout<<ans<<endl;
return;
}C.Dreaming of Freedom
算法本质
思维
题目大意
给定n m，现在有n个人，m个选项。
会经历若干次投票，直到选项个数为1，规则如下：
- 每个投票某个选项
- 票数最多的选项保留，其余丢弃
询问，是否存在一直投票的可能。
思路推演
”可能“一词，表示我们的思考方向应该是尽可能让人们平票，贴近无限投票情况。
显然当选项>=人数时，肯定是存在无限情况——因为每个人可以分别投票给某个选项。
既然如此，进一步思考：两人投一个选项、三人投一个选项……
然后会发现，这于因子有关。
当选项数>=人数的某个非1因数时，就可以一直保留某几个选项。
D.Running Miles
算法本质
思维
题目大意
给定长度n的数组b[]。
有n种草药，每种草药的价值为b[]，现在小明可以选择一对l r，带走下标属于[l, r]的三种草药，同时消耗r-l的价值。
输出最大化带走草药的价值。
n <= 1e5思路推演
观察题目：
n为1e5范围，显然此题需要信息复用——贪心、dp、二分等等- 同时这个“三种”也让人心生疑惑：为什么刚好是三种，不是两种，不是四种
- 价值的消耗，与范围线性相关（可以联想类似的题目解法）
这些都是题目的疑点，在不能看题就想到思路的时候，从疑点入手。
为了快速解题，先尝试了从n范围入手：但是思路寥寥，暂无解法。
随后选择从“三种”疑点切入：
“一种”，显然可解。
“两种”，我们可以在确定某个值后，贪心计算出另外一个值的信息。
显然，想到了“两种”的解法，就知道了“三种”的解法：
我们假设第二个元素下标为x，贪心计算出左右边元素价值，加上即可。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int a[maxn], pre[maxn], suf[maxn];
inline void solve()
{
//init
cin>>n;
rep(i,1,n) cin>>a[i];
for (int i=1; i<=n; i++)
{
pre[i] = a[i]+i; // 这个值设计的很巧，十分方便后面的r-l代价计算
suf[i] = a[i]-i;
}
//cal
pre[0] = pre[n+1] = suf[0] = suf[n+1] = -1e18; // 注意这里是负数，因为pre和suf可能是负数，最大-n左右
for (int i=1; i<=n; i++)
pre[i] = max(pre[i], pre[i-1]);
for (int i=n; i>=1; i--)
suf[i] = max(suf[i], suf[i+1]);
int ans = 0;
for (int i=2; i<=n-1; i++)
ans = max(ans, pre[i-1]+suf[i+1]+a[i]);
cout<<ans<<endl;
return;
}E.Walk the Runway
算法本质
思维、bitset
题目大意
有n个模特，每个模特有自己的出场费a[]。（走m场秀的出场费）
有m场秀，每场秀的每个模特的评分为b[][]。
对于每场秀，有以下规定：
- 所有秀出现的模特集合相等
- 所有秀模特的出场顺序相同
- 所有秀出场的模特所得评分必须严格单增
输出最大化的模特出场费之和。
思路推演
所有秀中，模特出场集合、顺序都是一致的，所以我们可以把每个模特看成一个node，第i场秀的评分为这个node的第i个属性。（抽象题意）
在编排模特出场顺序时，发现模特之间有大小关系（大于、小于、不相等三种关系），且这种关系具备一定传递性。
这导致其n个node会组合成一个DAG（无环有向图）
最后要最大化的出场费，实际是找一条路径的最大和，显然可以在建图后使用dp搞定。
目前的核心问题在于建图（二维直达图）的朴素做法是n^2^m——每2个node之间的关系需要通过m个属性来判断，即使其有传递性，但是传递性并无法降低如此大的复杂度。
当时的希望是从评分<=n这点入手的，但是思路寥寥。
思路推演 - 正解
正解做法是：利用bitset加速处理。
因为最终要建的图，可以用临边矩阵表示，用1表示可达，用0表示不可达。
通过调整代码，使代码符合bitset的处理方式，从而使得复杂度降低为n^2^m/w（这里w通常为32或64）。
ac核心代码
因为后面缺乏思维性理解，所以使用别人代码，添加自己注释作为代码。
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
//init
cin>>m>>n;
vector<vector<int>> a(n, vector<int>(m+1));
rep(i,0,n-1) cin >> a[i][m]; // 价格放入a中，方便一会排序带着走
for (int i=0; i<m; i++)
for (int j=0; j<n; j++)
cin>>a[j][i]; // 评分表：[模特][走秀]
sort(a.begin(), a.end()); // 评分表根据模特的第一场秀评分重新排序（偏序），方便后面计算
//cal
vector<bitset<maxn>> lower(n);
for (int i=0; i<n; i++)
lower[i].set(); // 全部设置为1
vector<int> inds(n);
iota(inds.begin(), inds.end(), 0); // inds[i]=i
for (int i=0; i<m; i++)
{
sort(inds.begin(), inds.end(), [&] (int x, int y){
return a[x][i] < a[y][i];
}); // inds表示第i场秀评分从小到大的模特编号
bitset<maxn> cur=0; // cur[i]=1表示模特i在第i场秀的评分比当前模特小
int p=0;
for (int j=0; j<n; j++)
{
while (a[inds[p]][i] < a[inds[j]][i]) // 避免相等但是仍然不可达的情况
cur.set(inds[p++], 1);
lower[inds[j]] &= cur; // 利用bitset加速
}
}
vector<long long> dp(n); // dp[i]表示走到i点所获得的最大值
for (int i = 0; i < n; i++)
{
dp[i] = a[i][m]; // 初始赋值
for (int j = 0; j < i; j++)
{
if (lower[i][j]) // 可达
dp[i] = max(dp[i], dp[j]+a[i][m]); // 更新
}
}
cout << *max_element(dp.begin(), dp.end()) << '\n'; // 输出最大值
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)