统计 & 难度情况
- AK 人数：1 人，低于预期。
- ADE 相对之前的小白月赛可能偏易，BC 适中，我们注意到了 F 略高的难度。
A
显然每次操作都要让得分为正，且正数用的越多越好。
从大到小排序，扫前缀和并累加，直到前缀和为负为止。
时间复杂度 。
#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l;i<=r;i++)
#define dn(l,r,i) for(int i=l;i>=r;i--)
using namespace std;
typedef long long LL;
const int INF =2147483647;
const int MAXN =2e5+3,MOD=1e7+7;
LL qread(){
LL w=1,c,ret;
while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0';
while((c=getchar())>='0'&&c<='9') ret=ret*10ll+c-'0';
return ret*w;
}
void write(LL t){
if(t>9ll) write(t/10ll); putchar('0'+t%10ll);
}
LL n,ans,sum,A[MAXN];
void Solve(){
sum = 0, ans = 0;
n=qread(); up(1,n,i) A[i]=qread();
sort(A+1,A+1+n); sum+=A[n]; dn(n-1,1,i){
sum+=A[i]; if(sum>=0ll) ans=(ans+sum)%MOD; else break;
}
write(ans%MOD); puts("");
return;
}
int main(){
int T = qread();
while(T--) Solve();
return 0;
} B
题目要求身上不带有一种 debuff 即可。我们可以考虑枚举这个不带有的 debuff，强制不取到它，每次贪心进入尽量多的房间。
则我们考虑，若不取到编号为 的 debuff，可以进到哪些房间。显然，对于
和
的房间我们均可以进入，其余的我们均不可以进入。则我们有了
的做法。
由于 ，上述做法是不会进入重复的房间的。则我们考虑进行前缀和优化，
表示
的房间积分的和，
表示
的房间积分的和。则答案为
。时间复杂度
。
#include <bits/stdc++.h>
#define rep(i, b, s) for(int i = (b); i <= (s); ++i)
#define per(i, b, s) for(int i = (b); i >= (s); --i)
#define ll long long
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define fi first
#define se second
#define mp make_pair
#define Ld long double
#define pii pair<int, int>
#define mid (l + r >> 1)
using namespace std;
const int N = 1e6 + 5;
int n, m;
int l[N], r[N], s[N];
ll pre[N], suf[N];
int main() {
ios;
cin >> n >> m;
assert(n >= 1 && n <= (int)(1e6));
assert(m >= 1 && m <= (int)(1e6));
rep(i, 1, n) cin >> l[i] >> r[i] >> s[i];
rep(i, 1, n) {
assert(l[i] >= 1 && l[i] <= m);
assert(r[i] >= l[i] && r[i] <= m);
assert(s[i] >= 1 && s[i] <= (int)(1e9));
pre[r[i]] += s[i];
suf[l[i]] += s[i];
}
rep(i, 1, m) pre[i] += pre[i - 1];
per(i, m, 1) suf[i] += suf[i + 1];
ll ans = 0;
rep(i, 1, m) ans = max(ans, pre[i - 1] + suf[i + 1]);
cout << ans << endl;
return 0;
} C
算法 1
我会开数组！
直接开一个二维数组 ，
。
对于每一个区间，暴力枚举这个区间内的所有时刻，存储在 数组中。
无法通过此题。
算法 2
我会暴力！
对于每一个询问的 ，枚举
个区间，暴力判断
是否在区间中。
时间复杂度 ，无法通过此题。
算法 3
我会找规律！
开两个数组 和
，
表示第
个小时能否通话，
表示
能否通话。
对于 的区间，做如下操作：
- 将
标记为不可通话。
- 将
标记为不可通话。
- 将
标记为不可通话。
伪代码如下（对于单个区间）：
时间复杂度 ，以及空间复杂度
，无法通过此题。
算法 4
我会分块！
考虑仍然将 拆分为
三部分，但对于
两段，我们仅维护对应小时内左右最大拓展的端点。
同时注意到 时，需要在该小时内另外维护一个中间段的左右端点
。
这样一来消去了算法 3 中 数组的一维，同时复杂度为
，可以通过此题。
#include <cstdio>
#define N 10010
#define min(a, b) ((a) < (b)) ? (a) : (b)
#define max(a, b) ((a) > (b)) ? (a) : (b)
using namespace std;
inline int rd();
int a, b, c, d, x, y, n, q, h, m;
bool H[N];
int l[N], r[N], p[N], s[N];
int main(){
n = rd(), h = rd(), m = rd(), q = rd();
for(int i = 0 ; i < h ; i++) l[i] = s[i] = m, r[i] = p[i] = -1;
for(int i = 1 ; i <= n ; i++){
a = rd(), b = rd(), c = rd(), d = rd();
if(a < c){
s[a] = min(s[a], b), p[c] = max(p[c], d);
for(int i = a + 1 ; i < c ; i++)
H[i] = 1;
}
else
l[a] = min(l[a], b), r[a] = max(r[a], d);
}
while(q--){
x = rd(), y = rd();
puts((y >= l[x] && y <= r[x])
|| (y <= p[x] || y >= s[x]) || H[x] ? "No" : "Yes");
}
return 0;
}
inline int rd(){
char c;
bool flag = 0;
while((c = getchar()) < '0' || c > '9')
if(c == '-') flag = 1;
int res = c - '0';
while((c = getchar()) >= '0' && c <= '9')
res = (res << 3) + (res << 1) + c - '0';
return flag ? -res : res;
} D
发现对于每一个单词表里的单词，我们只需要知道其最少多少步可以由 变化而来，以及上一步由谁变化而来。而每次仅能改变一个位置的字母。
考虑进行 bfs，每步枚举改变的位置和变成什么字母。对于每一个单词表里的单词以及 ，我们只会让其入队一次，而每次会枚举如何改变。我们用 map 记录每个单词在单词表中的位置，从而时间复杂度是
。
#include <bits/stdc++.h>
#define rep(i, b, s) for(int i = (b); i <= (s); ++i)
#define per(i, b, s) for(int i = (b); i >= (s); --i)
#define ll long long
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define fi first
#define se second
#define mp make_pair
#define Ld long double
#define pii pair<int, int>
#define mid (l + r >> 1)
using namespace std;
const int N = 5005;
int n, m;
string s[N];
int frm[N];
bool vis[N];
int st[N];
map<string, int> id;
void print(int x) {
if(x == -1) return ;
print(frm[x]);
cout << s[x] << '\n';
}
void bfs() {
memset(frm, -1, sizeof frm);
queue<int> q; q.push(0);
vis[0] = 1;
while(!q.empty()) {
int u = q.front();
q.pop();
string nw = s[u];
rep(i, 0, m - 1) {
char lst = nw[i];
rep(j, 0, 25) {
nw[i] = (char)('a' + j);
int idd = id[nw];
if(id.find(nw) != id.end() && !vis[idd]) {
vis[idd] = 1;
frm[idd] = u;
st[idd] = st[u] + 1;
q.push(idd);
}
}
nw[i] = lst;
}
}
cout << st[n] - 1 << endl;
if(!st[n]) return ;
print(n);
}
int main() {
ios;
cin >> n >> m;
rep(i, 1, n) cin >> s[i];
cin >> s[0] >> s[n + 1]; ++n;
rep(i, 0, n) id[s[i]] = i;
bfs();
return 0;
} E
考虑 dp，设 表示走到
时已经匹配到
的第
个字符时能获得的最大答案。
然后可以扫一遍转移，最终答案是 。
时间复杂度 。
注意 的情况，特意卡了。
#include <bits/stdc++.h>
#define rep(i, b, s) for(int i = (b); i <= (s); ++i)
#define per(i, b, s) for(int i = (b); i >= (s); --i)
#define ll long long
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define fi first
#define se second
#define mp make_pair
#define Ld long double
#define pii pair<int, int>
#define mid (l + r >> 1)
using namespace std;
const int N = 105;
int n, m, sz;
string s;
char mz[N][N];
int dp[N][N][N];
int main() {
cin >> n >> m;
cin >> s;
sz = s.size();
s = ' ' + s;
rep(i, 1, n) scanf("%s", mz[i] + 1);
memset(dp, -0x3f, sizeof dp);
dp[0][1][0] = dp[1][0][0] = 0;
if(sz == 1 && mz[1][1] == s[1]) dp[1][1][0] = 1;
rep(i, 1, n) rep(j, 1, m) {
rep(k, 1, sz) {
if(s[k] != mz[i][j]) continue;
if(k == 1 && sz != 1) dp[i][j][1] = max(dp[i][j][1], max(dp[i - 1][j][0], dp[i][j - 1][0]));
else dp[i][j][k] = max(dp[i][j][k], max(dp[i - 1][j][k - 1], dp[i][j - 1][k - 1]) + (k == sz));
}
rep(k, 0, sz) dp[i][j][0] = max(dp[i][j][0], max(dp[i][j][k], max(dp[i][j - 1][k], dp[i - 1][j][k])));
}
int ans = 0;
rep(i, 0, sz) ans = max(ans, dp[n][m][i]);
cout << ans << '\n';
return 0;
} F
考虑先判断无解的情况。
，
容易发现，前者则无法联通，后者则必有重边。
，
由于限制形如“必须经过点
”，则必有
。
其余的无解会在下面进行说明。在上面的限制下，观察到我们可以构造形如 的无用边来达到总边数
的目标，则我们只需要最小化满足要求的图
的总边数。
接下来我们考虑直接对这张图进行构造。首先我们提出所有 的点
，并将其连成链。我们将其中一条边的边权设为
，其余的设为
。
对于剩下的 的所有
，我们考虑其奇偶性。
若
，我们只对其连一条边
。此时由于只有这一条边可以到达
经过
的最短路方案一定是
。
若
，我们对于所有这样的
组成的集合
，找到一个位置
使
，连边
，
。对于其余的
，连边
。然而对于
的特例是无解的。容易看出，这种情况下
和
这两条路径中必有一条长度为
。
容易证明，如上的构造一定是最优的。则我们只需要判断上面提到的无解，以及在最优构造方案下边数不够用的情况。
对于无用边的构造，注意满足 和无重边即可。
时间复杂度 。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<map>
#include<vector>
using namespace std;
int n,m;
int d[300005];
struct note{
struct G{
struct note{
int x,y,w;
};
map<pair<int,int>,bool> vis;
vector<note> anslist;
bool insert(int x,int y,int w) {
if (x>y) swap(x,y);
if (vis.count({x,y})) return false;
vis[{x,y}]=true;
anslist.push_back({x,y,w});
return true;
}
void print() {
for (auto e : anslist) {
printf("%d %d %d\n",e.x,e.y,e.w);
}
}
}g;
vector<int> ext;
void insert_ext(int id) {
ext.push_back(id);
}
vector<int> spec;
void insert_spec(int id) {
spec.push_back(id);
}
void work() {
g.insert(1,n,d[1]);
for (auto id : ext) {
g.insert(1,id,(d[id]-d[1])/2);
}
int Min = 2e9, Minid = -1;
for (auto id : spec) {
if (Min>d[id]) {
Min = d[id];
Minid = id;
}
}
if (Minid != -1) {
g.insert(1,Minid,d[1]);
g.insert(Minid,n,d[Minid]-d[1]);
if (d[1]==0 || d[Minid]==0) throw -5;
}
for (auto id : spec) {
if (id!=Minid) {
g.insert(id,Minid,(d[id]-d[Minid])/2);
}
}
int res = m - g.anslist.size();
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++) if (i!=j) {
if (res==0) return;
if (g.insert(i,j,1e9)==true) res--;
}
if (res) throw -6;
}
}ans;
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&d[i]);
try {
if (m<n-1) throw -1;
if (d[1]!=d[n]) throw -2;
for (int i=2;i<n;i++)
if (d[i]<d[1]) throw -3;
for (int i=2;i<n;i++) {
if ((d[i]-d[1])%2==0) {
ans.insert_ext(i);
}else{
if (m<n) throw -4;
ans.insert_spec(i);
}
}
ans.work();
}catch(int error) {
puts("No");
return 0;
}
puts("Yes");
ans.g.print();
}
全部评论
(2) 回帖