前言
方队让我们来打
于是来打。
赛时2h过了AFGIJL,感谢qsq贡献的G。
评价:A:唐,F:唐,G:没看,I:小清新构造,J:国王游戏,L:不做评价。
补题补了C,E
E Escape
题意
给你 \(n\) 个波特和一个人与一张无向联通图,波特有一个共同的活动距离 \(d\)。不能在原地不动。问人在保证不遇到波特的情况下能否走到终点,并输出路径。
起点为 \(1\),终点为 \(n\)。
sol
对于能走到的点考虑奇偶分类(由于不能停留)。
所以只需要对波特跑一遍多源bfs,并且对人在波特的基础上跑,如果当前点当前奇偶性上的波特来的比人早,那么人就不能进入这个点,否则能。
最后判一下无解,通过pre输出就行了
#include<bits/stdc++.h>
#define int long long
#define pb push_back
namespace IO {
#define gh getchar
inline int read(){char ch=gh();int x=0;bool t=0;while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();return t?-x:x;}
inline char getc(){char ch=gh();while(ch<'a'||ch>'z') ch=gh();return ch;}
inline void write(int x){if(x < 0){putchar('-');x = -x;}if(x > 9){write(x / 10);}putchar((x % 10 + '0'));}
}
using namespace IO;
using namespace std;
const int Maxn = 500010, mod = 1e8;
int pre[Maxn][2]; int pos[Maxn]; int vis[Maxn][2]; int vp[Maxn][2]; int w[Maxn][2];
vector<int> G[Maxn]; struct Node{int o, u;}; //is:0:bot else not
int ds[Maxn][2];
void work(){
int n, m, d; n = read(), m = read(), d = read(); int u, v; int s = 1, t = n;
for(int i = 1; i <= n; i++) G[i].clear();
for(int i = 1; i <= n; i++) pre[i][0] = pre[i][1] = pos[i] = 0, w[i][1] = w[i][0] = ds[i][0] = ds[i][1] = 1e18;
for(int i = 1; i <= m; i++) u = read(), v = read(), G[u].pb(v), G[v].pb(u); int c = read();
for(int i = 1; i <= c; i++) pos[i] = read();
queue<Node> q;
for(int i = 1; i <= c; i++) q.push({0,pos[i]}), ds[pos[i]][0] = 0;
while(!q.empty()){
auto [o,u] = q.front(); q.pop();
for(int i : G[u])if(ds[i][o^1] > ds[u][o] + 1){
ds[i][o^1] = ds[u][o] + 1; q.push({o^1,i});
}
}
for(int i = 1; i <= n; i++) for(int o : {0,1}) if(ds[i][o] > d) ds[i][o] = 1e18;
w[1][0] = 0; q.push({0,1});
while(!q.empty()){
auto [o,u] = q.front(); q.pop(); if(w[u][o] >= ds[u][o]) continue;
for(int i : G[u])if(w[i][o ^ 1] > w[u][o] + 1){
w[i][o ^ 1] = w[u][o] + 1; pre[i][o^1] = u; q.push({o^1,i});
}
}
for(int i = 1; i <= n; i++) for(int o : {0,1}) if(w[i][o] >= ds[i][o]) w[i][o] = 1e18;
int o=(w[n][0]<w[n][1]?0:1);
if(w[t][o] >= 1e18) puts("-1");
else {
int x = t; vector<int> ans;
while(x ^ 1 || o){
ans.pb(x); x = pre[x][o]; o ^= 1;
}
ans.pb(s); reverse(ans.begin(),ans.end());
cout << ans.size() - 1 << endl;
for(int i : ans){
printf("%lld ",i);
}puts("");
}
}
signed main(){
int t = read(), p = 0;
while(t--){
work(); p++;
}
}
C Prefix of Suffixes
宇宙超级无敌原神启动字符串题。
不会字符串不会字符串
不会字符串不会字符串
不会字符串不会字符串
不会字符串不会字符串
不会字符串不会字符串
不会字符串不会字符串
不会字符串不会字符串
不会字符串不会字符串
不会字符串不会字符串
不会字符串不会字符串
转换一下式子整个增量 \(\Delta = A_i\sum\limits_{j=1}^{i}B_j[z_j = i - j + 1]\)。\
然后就是动态维护 \(z\) 数组。然后发现 exkmp
做不了动态。
然而有个题解里说
然后不是很懂为什么这题要强制在线,可能是存在某些神奇做法可以离线秒了吧?
emm。离线跑一下 exkmp
就做完了好吧。
然后发现 \([z_j = i - j + 1]\) 表明这个 \(j\) 其实是 \(1\) ~ \(i\) border
的一部分。
然而这道题就是用 kmp
可以动态来维护 border
的功能来解决的。
然后处理一下,理解一下,做完了。 (等会写。
复杂度 \(\operatorname{O}(n)\)。
#include<bits/stdc++.h>
#define int long long
#define pb push_back
namespace IO {
#define int long long
#define gh getchar
inline int read(){char ch=gh();int x=0;bool t=0;while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();return t?-x:x;}
inline char getc(){char ch=gh();while(ch<'a'||ch>'z') ch=gh();return ch;}
inline void write(int x){if(x < 0){putchar('-');x = -x;}if(x > 9){write(x / 10);}putchar((x % 10 + '0'));}
}
using namespace IO;
using namespace std;
const int Maxn = 300010, mod = 1e8;
int s[Maxn], a[Maxn], b[Maxn], z[Maxn];
vector<int> f[Maxn];
void solve() {
int n = read();
int ans = 0, res = 0;
for(int i = 1; i <= n; i++){
s[i] = (read() + ans) % n; a[i] = read(), b[i] = read();
res += b[i];
if(i != 1){
int j = z[i - 1];
while(j > 0 and s[j + 1] != s[i]) f[i].pb(j), j = z[j];
if(s[j + 1] == s[i]){
for(int k : f[j + 1]) f[i].pb(k);
j++;
}else f[i].pb(j);
z[i] = j;
for(int k : f[i]) res -= b[i - k];
} ans += res * a[i];
cout << ans << endl;
}
}
signed main(){
solve();
}
其他题太抽象了,不补了。
标签:ch,Contest,int,II,打题,Maxn,字符串,不会,gh From: https://www.cnblogs.com/theshumo/p/18474987