danihao123's Blog

[SZKOpuł sol][POI2009]Elephants

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ł raj][POI2014]Rally

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

很好玩的一道题qwq

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

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

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

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

代码：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

#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;
}

[BZOJ 1511]Periods of Words

很妙的一道题啊。

这个题可以先求一遍KMP的失配函数，然后对于每个失配函数沿着失配边往前一直走（不能走到0）。然后对于每个前缀 $i$ ，答案就是 $i-f[i]$ （要求 $f[i]$ 不为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;
}

[BZOJ 2081]Beads

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;
}

[BZOJ 3831]Little Bird

单调队列水体……然而我这蒟蒻仍然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;
}

[BZOJ 3524]Couriers

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

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

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

代码：

继续阅读

[SZKOpuł sol][POI2009]Elephants

[SZKOpuł raj][POI2014]Rally

[BZOJ 1511]Periods of Words

[BZOJ 2081]Beads

[BZOJ 3831]Little Bird

[BZOJ 3524]Couriers

danihao123

搜索

分类

标签云

最新评论

最新留言

神犇的Blog

RSS

功能

计数器