Preface
最唐氏的一集，有人写 03 一直过不去红温了然后白兰了一整场，怎么回事呢
最后很可惜 06 因为多维数组调用时顺序出了点问题，导致 cache 爆了然后常数太大 TLE 了，但凡时间延长 1min 都改完过了
由于今天过的题少就只写过了的六个题，剩下时间还要写昨晚 CF 的博客
最优 K 子段
致敬传奇红温闪总赛时挂了 17 发还没过，最后扔给徐神看一眼就秒了
首先一眼二分答案 \(lim\)，然后考虑贪心地找满足要求的子段
枚举当前的右端点 \(r\)，则满足要求的左端点 \(l\) 需要满足 \(pfx_r-pfx_{l-1}\ge lim\)，同时要满足 \(r-l+1\) 为质数
考虑按照 \(pfx_{l-1}\) 的大小从小到大枚举所有左端点并依次检验，由于数据随机且质数的分布大致均匀，可以发现如果合法的左端点则不会找太多次就能找到
复杂度约为 \(O(n\log^2 n)\)
#include <bits/stdc++.h>
bool is_prime[1000001];
int n, k;
int a[1000001];
int check(int limit) {
std::set<std::pair<int, int>> s{ {0, 0} };
int res = 0;
for(int i = 1; i <= n; ++i) {
auto it = s.begin();
while(it != s.end()) {
if(a[i] - it->first < limit) it = s.end();
else if(is_prime[i - it->second]) break;
else it++;
}
if(it != s.end()) res += 1, s.clear();
s.insert({a[i], i});
}
return res;
}
void work() {
std::cin >> n >> k;
for(int i = 1; i <= n; ++i) std::cin >> a[i], a[i] += a[i - 1];
if(k + k > n) {
std::cout << "impossible\n";
return ;
}
int L = -2000, R = 10000000, M;
while(L < R) {
M = (L + R + 1) / 2;
if(check(M) >= k) L = M;
else R = M - 1;
}
std::cout << L << char(10);
}
int main() {
std::ios::sync_with_stdio(false);
memset(is_prime, 1, sizeof(is_prime));
is_prime[0] = is_prime[1] = 0;
for(int64_t i = 2; i <= 1000000; ++i) if(is_prime[i])
for(int64_t j = i * i; j <= 1000000; j += i) is_prime[j] = false;
int T; std::cin >> T; while(T--) work();
return 0;
}
多层血条
签到，只需特别处理要替换为 . 的位置即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,n,m,hp,dmg; char s[805];
int main()
{
for (scanf("%d",&t);t;--t)
{
RI i,j; scanf("%d%d%d%d",&n,&m,&hp,&dmg);
int k=hp/m; for (i=1;i<=m;++i) s[i]=' ';
if (k>0)
{
for (i=1;i<=m;++i) s[i]=(k-1)%5+'A';
}
int rem=hp-m*k;
for (i=1;i<=rem;++i) s[i]=(k+1-1)%5+'A';
if (dmg>=m)
{
for (i=1;i<=m;++i) s[i]='.';
} else
{
for (i=rem;i>=1&&dmg>0;--i) s[i]='.',--dmg;
for (i=m;i>rem&&dmg>0;--i) s[i]='.',--dmg;
}
putchar('+'); for (i=1;i<=m;++i) putchar('-'); puts("+");
for (i=1;i<=n;++i)
{
putchar('|'); for (j=1;j<=m;++j) putchar(s[j]); puts("|");
}
putchar('+'); for (i=1;i<=m;++i) putchar('-'); puts("+");
}
return 0;
}
延时操控
赛时基本已经过了这题，但被卡 cache 了，最后改了数组顺序然后没交上去
首先有一个很关键的转化，可以看作两个人先一起走若干步，然后再让己方角色多走 \(k\) 步
因此可以考虑一个暴力 DP，需要记录的是当前的轮次、己方角色的坐标、对方角色的坐标，以及对方的血量
但直接这样搞复杂度是 \(O(n^4m\times hp)\) 的，还有个每次转移选一个方向的常数，铁定是过不去的
考虑优化，注意到如果第二个人不撞墙，则两人位置之差将保持不变；而一次撞墙会导致某一维的差值产生 \(\pm 1\) 的变化
因此实质上对方角色的坐标只要存因为撞墙导致的差值即可，复杂度变为 \(O(n^2m\times hp^3)\)，可以通过
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
void add(int &x, int a){if ((x+=a)>=MOD) x-=MOD;}
using pii = pair<int, int>;
int n, m, k, hp;
string tbl[52];
int f[51][52][52][11][11][6];
int g[51][52][52];
const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
void solve(){
cin >> n >> m >> k >> hp;
tbl[0] = tbl[n+1] = string(n+2, '#');
for (int i=1; i<=n; ++i){
cin >> tbl[i];
tbl[i] = "#" + tbl[i] + "#";
}
int px, py, ex, ey;
for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j){
if (tbl[i][j]=='P') px=i, py=j;
if (tbl[i][j]=='E') ex=i, ey=j;
}
int difx = ex-px, dify = ey-py;
for (int w=0; w<=m; ++w) for (int x=1; x<=n; ++x) for (int y=1; y<=n; ++y){
if (tbl[x][y]=='#') g[w][x][y] = 0;
else g[w][x][y] = (0==w ? 1 : 0);
for (int ddx=0; ddx<=10; ++ddx) for (int ddy=0; ddy<=10; ++ddy){
for (int h=0; h<=hp; ++h) f[w][x][y][ddx][ddy][h]=0;
}
}
f[0][px][py][5][5][hp]=1;
for (int w=0; w<m-k; ++w) for (int d=0; d<4; ++d){
int dx=dir[d][0], dy=dir[d][1];
for (int x=1; x<=n; ++x) for (int y=1; y<=n; ++y){
if (tbl[x+dx][y+dy]=='#') continue;
for (int ddx=0; ddx<=10; ++ddx) for (int ddy=0; ddy<=10; ++ddy){
int eex=x+difx+ddx-5, eey=y+dify+ddy-5;
if (eex<=0 || eex>n || eey<=0 || eey>n) continue;
int nx=eex+dx, ny=eey+dy;
for (int h=hp; h>0; --h){
if (0==f[w][x][y][ddx][ddy][h]) continue;
if (tbl[nx][ny]=='#') add(f[w+1][x+dx][y+dy][ddx-dx][ddy-dy][h-1], f[w][x][y][ddx][ddy][h]);
else add(f[w+1][x+dx][y+dy][ddx][ddy][h], f[w][x][y][ddx][ddy][h]);
}
}
}
}
for (int w=0; w<k; ++w){
for (int x=1; x<=n; ++x) for (int y=1; y<=n; ++y){
if (!g[w][x][y]) continue;
if (tbl[x][y]=='#') continue;
for (int d=0; d<4; ++d){
int nx=x+dir[d][0], ny=y+dir[d][1];
if ('#'!=tbl[nx][ny]) add(g[w+1][nx][ny], g[w][x][y]);
}
}
}
int ans=0;
for (int w=0; w<=m-k; ++w) for (int x=1; x<=n; ++x) for (int y=1; y<=n; ++y){
for (int ddx=0; ddx<=10; ++ddx) for (int ddy=0; ddy<=10; ++ddy){
add(ans, 1LL*f[w][x][y][ddx][ddy][0]*g[k][x][y]%MOD);
}
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t; while (t--) solve();
return 0;
}
序列更新
这场好多随机数据题，不过这题还是比较显然的
考虑设一个阈值 \(S\)，对于某个 \(a_i\)，若 \(\{b_i\}\) 中大于 \(a_i\) 的数的个数 \(\le S\)，则可以将这个 \(a_i\) 放入将会改变当前这个数的 vector 中，这部分的复杂度就是 \(O(n\times S)\)
对于剩下的数我们可以每次暴力更新，直到它们符合上面讲的限制
由于数据随机，某个数经历一次暴力更新操作仍然不符合限制的概率为 \(1-\frac{S}{n}\)，因此做一个等比数列求和得到这部分复杂度为 \(O(\frac{n^2}{S})\)
因此取 \(S=\sqrt n\) 即可得到 \(O(n\sqrt n)\) 的算法
#include<cstdio>
#include<iostream>
#include<utility>
#include<algorithm>
#include<vector>
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=250005,LIM=500;
int t,n,q,a[N],b[N],rk[N]; pi p[N]; vector <int> pos[N];
int main()
{
for (scanf("%d",&t);t;--t)
{
RI i,j; long long sum=0; scanf("%d%d",&n,&q);
for (i=0;i<n;++i) scanf("%d",&a[i]),sum+=a[i];
for (i=0;i<n;++i) scanf("%d",&b[i]),p[i]=pi(b[i],i);
for (sort(p,p+n),i=0;i<n;++i) rk[p[i].se]=i;
for (i=0;i<n;++i) pos[i].clear(); vector <int> vec;
for (i=0;i<n;++i)
{
int mp=upper_bound(p,p+n,pi(a[i],n))-p;
if (n-mp<=LIM)
{
for (j=mp;j<n;++j) pos[(p[j].se-i+n)%n].push_back(i);
} else vec.push_back(i);
}
/*for (i=0;i<n;++i)
{
printf("pos = %d : ",i);
for (auto x:pos[i]) printf("%d ",x);
putchar('\n');
}*/
while (q--)
{
int k; scanf("%d",&k);
for (auto x:pos[k]) sum-=a[x],a[x]=max(a[x],b[(x+k)%n]),sum+=a[x];
pos[k].clear(); vector <int> tmp;
for (auto x:vec)
{
if (b[(x+k)%n]>a[x])
{
sum-=a[x]; a[x]=b[(x+k)%n]; sum+=a[x];
int mp=rk[(x+k)%n]+1;
if (n-mp<=LIM)
{
for (i=mp;i<n;++i) pos[(p[i].se-x+n)%n].push_back(x);
} else tmp.push_back(x);
} else tmp.push_back(x);
}
vec=tmp; printf("%lld\n",sum);
//for (i=0;i<n;++i) printf("%d%c",a[i]," \n"[i==n-1]);
}
}
return 0;
}
昵称检索
众所周知字符串一般我题都不看就扔给徐神
#include <bits/stdc++.h>
constexpr int $n = 1000006;
std::vector<std::string> date;
int go[$n][26], dp1[$n], dp2[$n];
void work() {
int n, m; std::cin >> n >> m;
std::string s; std::cin >> s;
s = "a" + s + "0";
static int g[26];
memset(g, -1, sizeof(int) * 10);
for(int i = 1; i <= m + 1; ++i) if(std::isdigit(s[i])) {
memcpy(go[i], g, sizeof(int) * 10);
g[s[i] - '0'] = i;
}
memset(g, -1, sizeof(g));
for(int i = m; i >= 0; --i) if(std::isalpha(s[i])) {
memcpy(go[i], g, sizeof(g));
g[s[i] - 'a'] = i;
}
memset(dp1, 0, sizeof(int) * (m + 2));
memset(dp2, 0, sizeof(int) * (m + 2));
while(n--) {
static char name[25]; std::cin >> name;
int cur = 0;
for(int i = 0; cur >= 0 && name[i]; ++i) cur = go[cur][name[i] - 'a'];
if(cur >= 0) dp1[cur] += 1;
}
for(auto date: date) {
int cur = m + 1;
for(int i = 0; cur >= 0 && i < date.size(); ++i) cur = go[cur][date[i] - '0'];
if(cur >= 0) dp2[cur] += 1;
}
// for(int i = 1; i <= m; ++i) std::cout << dp1[i] << ' ' << dp2[i] << char(10);
// for(int i = 2; i <= m; ++i) dp1[i] += dp1[i - 1];
for(int i = m - 1; i; --i) dp2[i] += dp2[i + 1];
int64_t ans = 0;
for(int i = 1; i < m; ++i) ans += int64_t(dp1[i]) * int64_t(dp2[i + 1]);
std::cout << ans << char(10);
return;
}
int main() {
std::ios::sync_with_stdio(false);
{
constexpr int day[12] = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
for(int i = 0; i < 12; ++i) for(int j = 0; j < day[i]; ++j) {
static char s[10];
sprintf(s, "%02d%02d", i + 1, j + 1);
std::reverse(s, s + 4);
date.push_back(std::string(s));
}
}
int T; std::cin >> T; while(T--) work();
return 0;
}
寻找宝藏
首先考虑没有限制时，通过 DP 预处理一些东西
令 \(f_i\) 表示从 \((0,0)\) 到 \((i,p_i)\) 的最大收益，\(g_i\) 表示从 \((i,p_i)\) 到 \((n+1,n+1)\) 的最大收益，这个很容易用扫描线预先求出
对于询问可以分类讨论合并两边的贡献，可以离线后用四个树状数组维护，总复杂度 \(O(n\log n)\)
#include <bits/stdc++.h>
struct Rect {
int x1, y1, x2, y2;
int64_t val[2], ans;
};
struct Event {
int type, x, y, id;
int64_t val;
};
struct FWT {
std::vector<int64_t> c;
FWT(size_t n): c(n + 1, 0) {}
void reset() {
c.assign(c.size(), 0);
}
void update(size_t i, int64_t val) {
i += 1;
assert(i < c.size());
while(i < c.size()) {
if(val > c[i]) c[i] = val;
i += i&-i;
}
}
int64_t get(size_t i) const {
i += 1;
assert(i < c.size());
int64_t res = 0;
while(i > 0) {
res = std::max(res, c[i]);
i ^= i&-i;
}
return res;
}
};
void work() {
int n, m; std::cin >> n >> m;
std::vector<int> p(n + 2);
std::vector<int64_t> v(n + 2), ans(n + 2, 0);
p[0] = v[0] = 0; for(int i = 1; i <= n; ++i) std::cin >> p[i] >> v[i]; p[n + 1] = n + 1, v[n + 1] = 0;
std::vector<Rect> rect(m);
for(auto &[x1, y1, x2, y2, val, ans]: rect) {
std::cin >> x1 >> y1 >> x2 >> y2;
val[0] = val[1] = ans = 0;
}
std::vector<Event> event;
for(int i = 0; i <= n + 1; ++i) event.emplace_back(Event {
.type = 0,
.x = i,
.y = p[i],
.id = i,
.val = v[i],
});
for(int i = 0; i < m; ++i) {
auto [x1, y1, x2, y2, val, ans] = rect[i];
event.emplace_back(Event {
.type = 1,
.x = x1 - 1,
.y = y2 + 1,
.id = i,
.val = 0,
});
event.emplace_back(Event {
.type = 2,
.x = x2 + 1,
.y = y1 - 1,
.id = i,
.val = 0,
});
}
auto get_infer = [&](int type, int id) -> int64_t& {
if(type) return rect[id].val[type - 1];
else return ans[id];
};
std::sort(event.begin(), event.end(), [&](const Event &a, const Event &b) {
return a.x != b.x ? a.x < b.x
: a.y != b.y ? a.y < b.y
: a.type < b.type;
});
FWT c(n + 2);
for(auto [type, x, y, id, val]: event) {
const int64_t hkr = c.get(y) + val;
get_infer(type, id) += hkr;
c.update(y, hkr);
}
std::sort(event.begin(), event.end(), [&](const Event &a, const Event &b) {
return a.x != b.x ? a.x > b.x
: a.y != b.y ? a.y > b.y
: a.type > b.type;
});
c.reset();
for(auto [type, x, y, id, val]: event) {
const int64_t hkr = c.get(n + 1 - y) + val;
get_infer(type, id) += hkr;
c.update(n + 1 - y, hkr);
}
for(int i = 1; i <= n; ++i) ans[i] -= v[i];
std::sort(event.begin(), event.end(), [&](const Event &a, const Event &b) {
return a.x != b.x ? a.x < b.x
: a.y != b.y ? a.y > b.y
: a.type < b.type;
});
c.reset();
for(auto [type, x, y, id, val]: event) {
c.update(n + 1 - y, get_infer(type, id));
if(type == 1) rect[id].ans = std::max(rect[id].ans, c.get(n + 1 - y));
}
std::sort(event.begin(), event.end(), [&](const Event &a, const Event &b) {
return a.x != b.x ? a.x > b.x
: a.y != b.y ? a.y < b.y
: a.type < b.type;
});
c.reset();
for(auto [type, x, y, id, val]: event) {
c.update(y, get_infer(type, id));
if(type == 2) rect[id].ans = std::max(rect[id].ans, c.get(y));
}
for(int i = 0; i < m; ++i) std::cout << rect[i].ans << char(10);
}
int main() {
std::ios::sync_with_stdio(false);
int T; std::cin >> T; while(T--) work();
return 0;
}
Postscript
感觉这场策略有大问题，被 03 搞红温了就几乎全程零作用了，本来换一下我去接手队友的题可能会更好
标签：钉耙,std,const,val,int,编程,2024,type,id From： https://www.cnblogs.com/cjjsb/p/18330851