danihao123's Blog

aji波兰题！（直球）

这个题显然就是对那个排列乘上一个置换，然后置换的每一个循环事独立的，于是分别考虑每一个循环。

然后每一个循环有一种显然的构造方法就是从一个点开始，逆着边不停的交换两个点。这样的话有一个点会对答案做\(s - 1\)次贡献（\(s\)为循环大小），其他点都会只做一次循环。显然那个点选权值最小的点事坠吼的。

还有一种构造就是把全局最小值和循环最小值换一下，然后用上面的手段构造，最后再把全局最小值和循环最小值换回来。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
const int maxn = 1000005;
int next[maxn];

using ll = long long;
ll m[maxn];
int A[maxn], B[maxn], ma[maxn];
bool vis[maxn];

int main() {
  int n; scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &m[i]);
  }
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &A[i]); ma[A[i]] = i;
  }
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &B[i]);
    next[ma[B[i]]] = i;
  }
  ll ans = 0LL; ll tv = *std::min_element(m + 1, m + 1 + n);
  for(int i = 1; i <= n; i ++) {
    if(next[i] != i && !vis[i]) {
      int p = i; ll sumv = 0LL, minv = 0x7fffffffLL;
      ll cnt = 0;
      do {
        vis[p] = true; cnt ++;
        sumv += m[A[p]]; minv = std::min(minv, m[A[p]]);
        p = next[p];
      } while(p != i);
      ll delta = sumv + std::min(minv * (cnt - 2LL), minv + tv * (cnt + 1LL));
      ans += delta;
    }
  }
  printf("%lld\n", ans);
  return 0;
}

我从未见过有像SZKOpuł这样迷的OJ……

很好玩的一道题qwq

首先多源最短路太不好处理，我们搞一个超级源一个超级汇，分别和所有点连边。然后转成求超级源和超级汇的最长路。

我们不妨将这张图拓扑排序。然后我们思考对于拓扑排序得到的序列\(A\)，如果我们删除\(A_i\)的话，哪些路径不会收到影响？如果说有一个路径有一条边\((u, v)\)，满足\(u\)和\(v\)在拓扑排序中分别位于\(A_i\)的两侧，那么这条路径不会受到影响。

反过来考虑每条边\((u, v)\)，过这条边最优的路径一定是从源到\(u\)的最长路加上1再加上从\(v\)到汇的最长路（用两遍DP就能搞出来），他能影响的点在拓扑排序中显然事一段区间。

然后问题变成区间取max了，然后不需要在线，所以随便做了。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <queue>
#include <vector>
const int maxn = 500005;
const int maxm = 750005;
std::vector<int> G[maxn], RG[maxn];
int inv[maxn], outv[maxn];
void add_edge(int u, int v) {
  inv[v] ++; outv[u] ++;
  G[u].push_back(v);
  RG[v].push_back(u);
}

int T[maxn], ma[maxn];
void toposort() {
  std::queue<int> Q; Q.push(0);
  int num = 0;
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
    T[++ num] = u; ma[u] = num;
    for(auto v : G[u]) {
      inv[v] --;
      if(inv[v] == 0) Q.push(v);
    }
  }
}

int n, m;
int f[maxn], g[maxn];
int dp1(int x) {
  if(x == n + 1) return 0;
  if(f[x] != -1) return f[x];
  f[x] = 0;
  for(auto v : G[x]) {
    f[x] = std::max(f[x], dp1(v) + 1);
  }
  return f[x];
}
int dp2(int x) {
  if(x == 0) return 0;
  if(g[x] != -1) return g[x];
  g[x] = 0;
  for(auto v : RG[x]) {
    g[x] = std::max(g[x], dp2(v) + 1);
  }
  return g[x];
}

struct Interval {
  int l, r, v;
  bool operator <(const Interval &res) const {
    return v < res.v;
  }
};
int E[maxm][2]; std::vector<Interval> I;
void pro_I() {
  memset(f, -1, sizeof(f));
  memset(g, -1, sizeof(g));
  for(int u = 0; u <= n + 1; u ++) {
    for(auto v : G[u]) {
      int l = ma[u], r = ma[v];
      l ++; r --;
      if(l <= r) {
        Interval seg;
        seg.l = l; seg.r = r;
        seg.v = dp2(u) + dp1(v) + 1;
        I.push_back(seg);
      }
    }
  }
  std::sort(I.begin(), I.end());
}

const int maxno = maxn << 2;
int setv[maxno];
void pushdown(int o) {
  if(setv[o] != -1) {
    int lc = o << 1, rc = o << 1 | 1;
    setv[lc] = setv[o]; setv[rc] = setv[o];
    setv[o] = -1;
  }
}
int ql, qr, v;
void modify(int o, int L, int R) {
  if(ql <= L && R <= qr) {
    setv[o] = v;
  } else {
    pushdown(o);
    int M = (L + R) / 2;
    if(ql <= M) modify(o << 1, L, M);
    if(qr > M) modify(o << 1 | 1, M + 1, R);
  }
}
int ans[maxn];
void dfs(int o, int L, int R) {
  if(L == R) {
    ans[L] = setv[o];
  } else {
    pushdown(o);
    int M = (L + R) / 2;
    dfs(o << 1, L, M);
    dfs(o << 1 | 1, M + 1, R);
  }
}

int main() {
  memset(setv, -1, sizeof(setv));
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    scanf("%d%d", &E[i][0], &E[i][1]);
    add_edge(E[i][0], E[i][1]);
  }
  for(int i = 1; i <= n; i ++) {
    if(true) {
      add_edge(0, i);
    }
  }
  for(int i = 1; i <= n; i ++) {
    if(true) {
      add_edge(i, n + 1);
    }
  }
  toposort(); pro_I();
  for(auto &seg : I) {
    ql = seg.l, qr = seg.r, v = seg.v;
#ifdef LOCAL
    printf("(%d, %d) -> %d\n", ql, qr, v);
#endif
    modify(1, 1, n + 2);
  }
  dfs(1, 1, n + 2);
  int cho = 1, ret = 0x7fffffff;
  for(int i = 2; i <= n + 1; i ++) {
    if(ans[i] < ret) {
      cho = T[i]; ret = ans[i];
    }
  }
  printf("%d %d\n", cho, ret - 2);
  return 0;
}

很妙的一道题啊。

这个题可以先求一遍KMP的失配函数，然后对于每个失配函数沿着失配边往前一直走（不能走到0）。然后对于每个前缀[tex]i[/tex]，答案就是[tex]i-f[i][/tex]（要求[tex]f[i][/tex]不为0，反之无解）。

为什么这样可以呢？

首先建议大家看一下Matrix67关于KMP的解释。对于一个前缀，如果整个弄上去肯定不行。所以说需要前面和后面重叠一个字串，这个子串是不考虑的。当然，我们希望在这个被删除的子串最短辣。

代码：

/**************************************************************
    Problem: 1511
    User: danihao123
    Language: C++
    Result: Accepted
    Time:148 ms
    Memory:5704 kb
****************************************************************/
 
#include <cstdio>
const int maxn=1000005;
 
char buf[maxn];
int f[maxn];
int main(){
    register int i,j;
    register long long ans=0;
    int n;
    scanf("%d%s",&n,buf);
    f[0]=f[1]=0;
    for(i=1;i<n;i++){
        j=f[i];
        while(j && buf[i]!=buf[j])
            j=f[j];
        f[i+1]=(buf[i]==buf[j]?j+1:0);
    }
    for(i=2;i<=n;i++){
        if(f[i]){
            while(f[f[i]]){
                f[i]=f[f[i]];
            }
        }
    }
    for(i=1;i<=n;i++){
        if(f[i]){
            ans+=i-f[i];
        }
    }
    printf("%lld\n",ans);
    return 0;
}

Hash第一题……

这个题直接枚举串长Hash判断即可。不过，注意读题。

感觉Hash挺简单的。还有就是我用了wyy的生日做Hash种子辣！

代码：

/**************************************************************
    Problem: 2081
    User: danihao123
    Language: C++
    Result: Accepted
    Time:5636 ms
    Memory:10904 kb
****************************************************************/
 
#include <cstdio>
#include <set>
#include <vector>
using namespace std;
typedef unsigned long long ull;
const int maxn=200005;
const ull x=200261;
ull s[maxn];
ull sufHash[maxn],preHash[maxn],x_pow[maxn];
int n;
inline void InitHash(){
    register int i;
    for(i=n;i>=1;i--){
        sufHash[i]=s[i]+sufHash[i+1]*x;
    }
    for(i=1;i<=n;i++){
        preHash[i]=s[i]+preHash[i-1]*x;
    }
    x_pow[0]=1;
    for(i=1;i<=n;i++){
        x_pow[i]=x*x_pow[i-1];
    }
}
inline ull Hash(int i,int L){
    return sufHash[i]-x_pow[L]*sufHash[i+L];
}
inline ull FilpHash(int i,int L){
    return preHash[i+L-1]-x_pow[L]*preHash[i-1];
}
 
set<ull> S;
vector<int> AnsList;
int tot=0;
inline void Check(int k){
    register int i,ans=0;
    register ull h;
    S.clear();
    for(i=1;(i+k-1)<=n;i+=k){
        h=Hash(i,k)*FilpHash(i,k);
        if(!S.count(h)){
            S.insert(h);
            ans++;
        }
    }
    if(ans>tot){
        tot=ans;
        AnsList.clear();
        AnsList.push_back(k);
    }else{
        if(ans==tot)
            AnsList.push_back(k);
    }
}
 
int main(){
    register int i,ans=0,maxv=0,cnt,temp;
    bool flag;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%llu",&s[i]);
    InitHash();
    for(i=1;i<=n;i++){
        Check(i);
    }
    printf("%d %d\n",tot,AnsList.size());
    flag=false;
    for(i=0;i<AnsList.size();i++){
        if(flag)
            putchar(' ');
        flag=true;
        printf("%d",AnsList[i]);
    }
    putchar('\n');
    return 0;
}

单调队列水体……然而我这蒟蒻仍然WA一墙

这个题本质是一个动态规划，然后我们发现取区间递推最小值这个任务可以交给单调队列君来做~不过优先级似乎是一个问题……

优先级直接按照递推值来搞即可，递推值一样的话才按照高度比。因为就算递推值比较小但高度会带来额外影响，也不过是1，这样撑死也不会使答案更差

但凡是单调队列的题，都会有神秘细节，这题也不例外……顺便说一下这题不要傻乎乎的用pair

代码：

/**************************************************************
    Problem: 3831
    User: danihao123
    Language: C++
    Result: Accepted
    Time:11596 ms
    Memory:16228 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <queue>
#include <deque>
using namespace std;
const int maxn=1e6+1;
int D[maxn],f[maxn];
bool d_cmp(int x,int y){
    if(f[x]==f[y])
        return D[x]<D[y];
    else
        return f[x]>f[y];
}
struct DQueue{
    deque<int> D;
    queue<int> Q;
    void push(int x){
        Q.push(x);
        while(!D.empty() && d_cmp(D.back(),x))
            D.pop_back();
        D.push_back(x);
    }
    int top(){
        return D.front();
    }
    void pop(){
        if(D.front()==Q.front())
            D.pop_front();
        Q.pop();
    }
    int size(){
        return Q.size();
    }
    void clear(){
        while(!Q.empty())
            Q.pop();
        D.clear();
    }
};
DQueue hhh;
int main(){
    register int i,temp,ans;
    int n,Q,k;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&D[i]);
    scanf("%d",&Q);
    while(Q--){
        scanf("%d",&k);
        hhh.push(1);
        f[1]=0;
        for(i=2;i<=n;i++){
            while(hhh.size()>k)
                hhh.pop();
            temp=hhh.top();
            f[i]=f[temp]+(D[temp]<=D[i]);
            hhh.push(i);
        }
        printf("%d\n",f[n]);
        hhh.clear();
    }
    return 0;
}

这道题有了主席树，就是裸题了……

只要用主席树维护出现次数，然后二分求解即可

但是！数组一定要开大，开大，再开大，重要的事情说三遍！

代码：