T1 移动距离
答案是sqrt(233×233+666×666)+构成的一个圆弧对应的弧长。
至于这个弧长对应的圆心角，方法很多，但是赛时系统计算机比较抽象就没整出来，误差挺大的当时，得出来一个1620。
正解：1576
T2 客流量上限
首先可以根据 i=j 时的限制计算出一个上界 ai≤√i2+2025，但是这个条件并不是充分的。不过它引出了一个重要观察：当 i≥1013 时一定有 ai≤i。
注意到 1 位置只可以填 1,2，考虑每个位置和 2025 的限制，有 2025ai≤2025i+2025，即 ai≤i+1。
接下来我们证明 ai≤min 就是充要条件，必要性已经在前面完成证明。此时会有
a_i \leq \begin{cases} i + 1 & i < 1013 \\ i & i \geq 1013 \end{cases}
将 i,j(i \leq j) 分为三类：
-
i,j \geq 1013，此时 a_i a_j \leq ij \leq ij + 2025。
-
i < 1013 \leq j，此时 a_i a_j \leq (i+1)j = ij + j \leq ij + 2025。
-
i,j < 1013，此时 a_i a_j \leq (i+1)(j+1) = ij + i + j + 1 \leq ij + 2025。
因此上述条件是充要的。
计数部分考虑从 1 → 2025 一个一个填，1 ~ 1012 每个位置都只有两个选法，1013 ~ 2025 每个位置只有唯一填法。因此答案是 2^{1012} \equiv 781448427 \pmod{10^9 + 7}。
T3 可分解的正整数
找规律
对于任意一个除了1的值，都可以构成（）x的一个序列，（-(x-1)，…0,…x-1）中的数求和为0 。
赛时代码
#include<bits/stdc++.h>
using namespace std;
const int N = 123456;
#define ll long long
const int mod = 1e9+7;
int main ()
{
int n;
cin>>n;
int res=0;
while(n--)
{
int x;
cin>>x;
if(x!=1)
res++;
}
cout<<res;
return 0;
}
T4 产值调整
模拟+剪枝
当模拟到的三个值都一样的时候就没必要继续枚举下去了
赛时代码
#include<bits/stdc++.h>
using namespace std;
const int N = 123456;
void solve()
{
// cout<<"\n";
int a,b,c,k;
cin>>a>>b>>c>>k;
int A,B,C;
while(k--)
{
A=(b+c)/2;
B=(a+c)/2;
C=(a+b)/2;
if(A==B&&A==C)
{
cout<<A<<" "<<B<<" "<<C<<"\n";
return ;
}
//cout<<A<<" "<<B<<" "<<C<<"\n";
a=A;
b=B;
c=C;
}
cout<<A<<" "<<B<<" "<<C<<"\n";
return ;
}
int main ()
{
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}
T5 画展布置
题意简述
画展策展人准备展出 N 幅画作，每幅画有一个对应的艺术价值 A1,A2,…,ANA_1, A_2, \ldots, A_N。他们希望从中挑选出 M 幅画作，并将其按某种顺序排列用于展出。
为了提升展览整体的观赏体验，需要使得所选画作在序列中艺术价值变化尽可能平缓。用一个值 L 来衡量整体画作排列的“协调性”，定义如下：
L=\sum_{i=1}^{M-1} |B_{i+1}^2-B_i^2|
其中 B_i 表示展览中第 i 幅画作的艺术价值。
你的任务是：从 N 幅画中选择 M 幅并排序，使得 L 最小，输出这个最小值是多少。
题目分析
考虑到选择是价值最小，那必然选择的是紧挨着的一些数。
排序后，选择任意区间长度为m的区间，利用前缀和优化得到一个价值。
取价值最小的 。
双指针也可以。
时间复杂度 O(n)。
赛时代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 123456;
int n,m;
int a[N];
int s[N];
signed main ()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1);
for(int i=2;i<=n;i++)
{
s[i]=s[i-1]+abs(a[i]*a[i]-a[i-1]*a[i-1]);
}
int ans=LONG_LONG_MAX-2;
for(int i=1;i<=n-m+1;i++)
{
ans=min(ans,s[i+m-1]-s[i]);
}
cout<<ans;
return 0;
}
T6 水质检测
总结：初始状态定义一定要好好看啊啊啊
题意简述
给定一个大小为 2 \times n 的网格，网格中的部分位置已经安装了水质检测器（用 # 表示），其余位置为空（用 . 表示）。若两个相邻格子（上下或左右）都有检测器，则它们之间是“连通”的。两个检测器若可以通过一系列连通的检测器相互到达，则认为它们属于同一个连通块。
现在的目标是，在原有基础上最少新增检测器，使得所有检测器最终构成一个连通块（即所有检测器连成一片）。输出所需新增的检测器数量。
题目分析
这个题的方法有很多，模拟，贪心，bfs，动态规划都可以，题目不难。
这里给出赛时 dp 的做法。
由于可以从把一个大问题分解成每一个小位置合法情况的方案，所以必然可以考虑 dp。
dp 做法可以将该题的两个字符串扩展到 n 个也可以做出
- 状态定义
dp_{i,u} 表示在第 i 个位置第 u 行要跟前面联通需要产生的贡献。 - 状态转移
当前位置如果为 #，则不需要新产生贡献，由 i-1,u或者 i,!u得到，取最小值
当前位置如果为 .，则需要新产生贡献，由（i-1,u 或者 i,!u）+1得到，取最小值
即：
\begin{array}{c} dp_{i,u} = \min(dp_{i-1,u}, dp_{i,\lnot u}) \quad \text{if } s[i][u] == ‘#‘ \[2em] dp_{i,u} = \min(dp_{i-1,u}, dp_{i,\lnot u}) + 1 \quad \text{if } s[i][u] == ‘.’ \end{array}
- 初始状态定义
只需要将初始没有#的位置定义为 0，其余位置均定义为最大即可。 - 状态遍历
只需要遍历从第一个#到最后一个#的位置即可。
时间复杂度 O(n)
赛时代码(把1改成0之后)
/*
动态规划
定义状态dp[i][u]表示在第i个位置第u行要跟前面联通需要产生的贡献
状态转移：
当前位置如果为#，则不需要新产生贡献，由i-1,u或者i,!u得到，取最小值
当前位置如果为.，则需要新产生贡献，由（i-1,u或者i,!u）+1得到，取最小值
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1234567;
int dp[N][4];
int n;
int main()
{
string s1 = " ", s2 = " ";
string s;
cin >> s;
n = s.size();
for (int i = 1; i <= n; i++)
{
dp[i][1] = n;
dp[i][2] = n;
}
s1 += s;
cin >> s;
s2 += s;
int be;
int en;
// cout<<s1<<"\n";
// cout<<s2<<"\n";
for (int i = 1; i <= n; i++)
{
// cout<<s1[i]<<" "<<s2[i]<<"\n";
if (s1[i] != '.' || s2[i] != '.')
{
be = i;
break;
}
dp[i][1] = 0;
dp[i][2] = 0;
}
for (int i = n; i >= 1; i--)
{
if (s1[i] != '.' || s2[i] != '.')
{
en = i;
break;
}
}
for (int i = be; i <= en; i++)
{
// cout<<i<<" ";
// cout<<s1[i]<<" "<<s2[i]<<"\n";
if (s1[i] == '#')
dp[i][1] = dp[i - 1][1];
if (s2[i] == '#')
dp[i][2] = dp[i - 1][2];
if (s1[i] == '#' && s2[i] == '#')
{
int k = min(dp[i][1], dp[i][2]);
dp[i][1] = k;
dp[i][2] = k;
}
if (s1[i] == '.')
dp[i][1] = min(dp[i - 1][1], dp[i][2]) + 1;
if (s2[i] == '.')
dp[i][2] = min(dp[i - 1][2], dp[i][1]) + 1;
// cout<<dp[i][1]<<" "<<dp[i][2]<<"\n";
}
if (s1[en] == '#')
cout << dp[en][1];
else
cout << dp[en][2];
return 0;
}
T7 生成车间
总结：建树（图）一定要建立双向边啊（如果没有明确有向图时）
题意简述
给定一棵有 n 个节点的树，第 i 个节点有一个容量上限 a_i。要求选择若干节点使得这些节点构成一棵以 1 为根的子树，且所有子树节点的容量和不超过根节点 a_1。目标是求这棵树所能“容纳”的最大容量和。
题目分析
那在建立好一颗树以后，问题就缩小成了，给定一个节点，该节点有几个不同的数，求这些数能凑出来的 1000 以内的数都有什么。
显然，这是一个集合的问题。举个例子来说，对于一个子节点有 2 2 7 三个数，那么就可以可以凑出来的数有 2 4 7 9 11。这个只需要一个 2 重循环的遍历即可，然后我们把，凑出来的数和原来的数一块儿塞到一个新的集合中，那么该新的集合就是该节点的能向父节点传递的数的方案。同样的，父节点选取的时候，也是按照如下方案进行选取。
限制条件：每个节点选取的时候，集合中最大数不超过 a_i ， 父节点选取子节点的集合时就是一个 0/1 背包（赛时利用了集合的去重特性，就用集合写了），每个节点只可以使用 1 个数。
时间复杂度（O(n^3logn)），但是最坏复杂度绝对不会到到达，洛谷上通过了 95pts 。
赛时代码（加了双向边后）
#include <bits/stdc++.h>
using namespace std;
const int N = 1234;
struct nihao
{
int to, next;
};
nihao e[N * 2]; // 双向边要开2倍空间
int h[N], cnt;
int a[N];
int n;
vector<int> q[N];
set<int> Q[N];
void add(int u, int v)
{
e[cnt].to = v;
e[cnt].next = h[u];
h[u] = cnt++;
}
void dfs(int u, int fa)
{
bool isLeaf = true;
for (int i = h[u]; i != -1; i = e[i].next)
{
int v = e[i].to;
if (v == fa)
continue; // 跳过父节点
isLeaf = false;
dfs(v, u);
}
if (isLeaf)
{
Q[u].insert(a[u]);
return;
}
set<int> p;
for (int i = h[u]; i != -1; i = e[i].next)
{
int v = e[i].to;
if (v == fa)
continue;
for (auto x : Q[v])
{
for (auto y : Q[u])
{
if (y + x <= a[u])
p.insert(y + x);
}
}
for (auto x : p)
Q[u].insert(x);
for (auto x : Q[v])
{
if (x <= a[u])
Q[u].insert(x);
}
}
}
int main()
{
memset(h, -1, sizeof(h));
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n - 1; i++)
{
int u, v;
cin >> u >> v;
add(u, v); // 无向边
add(v, u);
}
dfs(1, 0); // 从根节点1出发，父亲设为0
int ans = 0;
for (auto x : Q[1])
{
ans = max(ans, x);
}
cout << ans << endl;
return 0;
}
为了优化一下，我们就需要写一个数组的 0/1 背包问题了，这里用了一个vector 代替 set 并 vis 来去重。时间复杂度就变成了 O(n^3) ，虽然复杂度依然不是很优，但已经可以过全部测试点了。
代码（vector 优化后）
#include <bits/stdc++.h>
using namespace std;
const int N = 1234;
const int MAX_A = 1005; // 单个 a[i] 最大值
struct Edge {
int to, next;
};
Edge e[N * 2];
int h[N], cnt;
int a[N], n;
vector<int> Q[N];
bool vis[N][MAX_A]; // vis[u][x] 表示 x 是否已在 Q[u] 中出现
void add(int u, int v) {
e[cnt].to = v;
e[cnt].next = h[u];
h[u] = cnt++;
}
void dfs(int u, int fa) {
bool isLeaf = true;
for (int i = h[u]; i != -1; i = e[i].next) {
int v = e[i].to;
if (v == fa) continue;
isLeaf = false;
dfs(v, u);
}
if (isLeaf) {
Q[u].push_back(a[u]);
vis[u][a[u]] = true;
return;
}
for (int i = h[u]; i != -1; i = e[i].next) {
int v = e[i].to;
if (v == fa) continue;
vector<int> temp;
for (int x : Q[v]) {
for (int y : Q[u]) {
if (x + y <= a[u] && !vis[u][x + y]) {
vis[u][x + y] = true;
temp.push_back(x + y);
}
}
}
for (int x : Q[v]) {
if (x <= a[u] && !vis[u][x]) {
vis[u][x] = true;
Q[u].push_back(x);
}
}
for (int x : temp) {
Q[u].push_back(x);
}
}
}
int main() {
memset(h, -1, sizeof(h));
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
add(u, v);
add(v, u); // 无向边
}
dfs(1, 0);
int ans = 0;
for (int x : Q[1]) {
ans = max(ans, x);
}
cout << ans << endl;
return 0;
}
T8 装修报价
总结：题目并不难，主要是放最后一题了，可能会导致误判
题意简述
题目本质上是让我们枚举出所有合法的括号表达式结构，在每一对相邻数字之间放置「+」「-」「⊕」三种操作符，并求出这些所有表达式的最终计算结果的和。最后对 10^9+7 取模。
题目分析
观察到，对于每一个位置均可以填 「+」「-」「⊕」三种操作符，那方案数就是 3^{n-1}，时间复杂度必然是过不去的。可以观察到，对于一个位置如果填「+」，那么就必然存在 「-」会使得该位置后添加的数产生一个无贡献的情况，这种情况对于答案的贡献就是前面一些数的异或和。只需要维护一个异或前缀和，枚举第 i 位置填非 「⊕」位置的所有方案数产生的贡献，即
res_i = sum⊕_{i} \times 2 \times 3^{i-1}
预处理出来 3 的指数幂，时间复杂度 O(n)。
赛时代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 123456;
const int mod=1e9+7;
int n;
int a[N];
int _3[N];
int ans=0;
void init()
{
int res=1;
for(int i=1;i<=n;i++)
{
res=(res*3)%mod;
_3[i]=res;
}
_3[0]=1;
}
signed main ()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
init();
int ans=0;
int k=0;
for(int i=1;i<=n-1;i++)
{
k^=a[i];
ans=(ans+k*2*_3[n-i-1])%mod;
//cout<<ans<<"\n";
}
k^=a[n];
// cout<<k<<"\n";
ans=(ans+k)%mod;
cout<<ans;
return 0;
}
