本场链接：Codeforces Round #722 (Div. 2)
闲话
因为误读了D卡了一个半小时，遗憾，E会了之后再补。
A. Eshag Loves Big Arrays
任何一个数和一个比它小的数组合在一起一定可以把较大的数删去，数量变多之后也是一样，所以所有非最小值的数都可以删掉。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
const int N = 105;
int a[N];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
forn(i,1,n) scanf("%d",&a[i]);
int minv = a[1];
forn(i,1,n) minv = min(minv,a[i]);
int res = 0;
forn(i,1,n) if(a[i] != minv) ++res;
printf("%d\n",res);
}
return 0;
}
B. Sifid and Strange Subsequences
由于元素可以任取，所以不妨先排序。注意到最小值肯定是相邻的两个数做差取到的，如果排序后两个数违反了规则说明肯定不能放在一起，并且删掉其中一个与其他的元素组合在一起只会让情况变得更差：从左到右看能不能构成连续的段，如果可以就向右边推，否则说明一定要在这里断开重新做一段。维护最大值即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
const int N = 1e5+7;
int a[N];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
forn(i,1,n) scanf("%d",&a[i]);
sort(a + 1,a + n + 1);
int res = 1;
forn(i,1,n)
{
int j = i,minv = 1e9;
while(j + 1 <= n && min(minv,abs(a[j + 1] - a[j])) >= a[j + 1])
{
minv = min(minv,abs(a[j + 1] - a[j]));
++j;
}
res = max(res,j - i + 1);
i = j;
}
printf("%d\n",res);
}
return 0;
}
C. Parsa's Humongous Tree
猜想：每个权值虽然给了一个范围，但是取边界值肯定不会让情况变得更差。
考虑dp，每个元素只有选最小值和最大值区别。
-
状态：\(f[u][j = 0/1]\)表示对于以\(u\)为根的子树，\(j=0\)时\(u\)取最小值，反之\(u\)取最大值的最大和。
-
入口：叶子节点为\(0\)。
-
转移：\(f[u][0] += max(f[v][0] + abs(l[v] - l[u]),f[v][1] + abs(r[v] - l[u]))\).
\(f[u][1] += max(f[v][0] + abs(l[v] - r[u]),f[v][1] + abs(r[v] - r[u]))\).
-
出口：\(res = max(f[u][0],f[u][1])\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
const int N = 1e5+7;
vector<int> E[N];
int l[N],r[N];
ll f[N][2];
void dfs(int u,int fa = -1)
{
for(auto& v : E[u])
{
if(v == fa) continue;
dfs(v,u);
f[u][0] += max(f[v][0] + abs(l[v] - l[u]),f[v][1] + abs(r[v] - l[u]));
f[u][1] += max(f[v][0] + abs(l[v] - r[u]),f[v][1] + abs(r[v] - r[u]));
}
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
forn(i,1,n) E[i].clear(),f[i][0] = f[i][1] = 0;
forn(i,1,n) scanf("%d%d",&l[i],&r[i]);
forn(i,2,n)
{
int u,v;scanf("%d%d",&u,&v);
E[u].push_back(v);E[v].push_back(u);
}
dfs(1);
printf("%lld\n",max(f[1][0],f[1][1]));
}
return 0;
}
D. Kavi on Pairing Duty
由于题目的数据范围是\(10^6\)，不考虑公式解，考虑递推：
- 方程：\(f[i]\)表示\(2* i\)个点划分成好方案的方案数。
- 入口：\(f[0] = f[1] = 1\)。
- 转移：按第一组的位置划分方案，设与\(1\)配对的点为\(x\)，那么任何一个点\(p \in [x + 1,n]\)一定属于一段与\([1,x]\)段相同长度的段中。因为他不能在一个大的内部，所以只能是长度相同的。讨论\(x \geq n\)的情形：手推可以发现会剩下一部分完全连续的，这样方案数就对应\(f[x - n - 1]\)。\(x < n\)的由于长度必须是\(n\)的因数，所以方案数就是\(D(n)\)，其中\(D(n)\)是\(n\)的约数个数（但不含有这个数本身)。递推方程：\(f[i] = D(i) + \sum\limits_{j = 0}^{i - 1}f[j]\)。
- 出口：\(f[n]\)。
实现时维护前缀和\(S\)并递推即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
const int MOD = 998244353,N = 1e6+7;
ll f[N];
int main()
{
forn(i,1,N - 1) for(int j = 2 * i;j <= N - 1;j += i) ++f[j];
ll S = 1;f[0] = 1;
int n;scanf("%d",&n);
forn(i,1,n)
{
f[i] = (f[i] + S) % MOD;
S = (S + f[i]) % MOD;
}
printf("%lld\n",f[n]);
return 0;
}