ACMak选手的比赛(题解)

回复帖子

@eternal 2016-10-04 21:14 回复

T1 40分的暴力大家应该都会写,那么我就暂时略过了

100分的做法其实也不是太难想,毕竟这是一道送分题,对Ai进行一下Hash pos[ai] = i ,则有bi = pos[bi] , 那么这个问题就被我们转化成了LIS问题,LIS就可以NlogN解决(二分一下就好了)

T2 对高度进行一下Hash,可以有一部分分,如果强悍一点的话,动态开,有可能能够过掉,我在本机上试了下,大概需要5.0s。。。

考虑这样一种情况,记di = c , 表示在满足 c mod x = i 的前提下,仅通过第二和第三个操作能够到达的最小楼层c , 如果我们算出了di , 那么这个问题就解决了, 答案就是 (h - di) / x + 1 ( i : 0 ... x - 1 )

       d(i + y) mod x = di + y

       d(i + z) mod x = di + z

用spfa搞一下就可以了

T3 其实我认为T3比T2简单,因为当时我轻松AT3但是没有想到T2的做法。。。

NO1.首先呢,斐波那契是有一个二次剩余的式子的 Fn = 276601605(691504013^n - 308495997^n ) mod (1e9 + 7)

这个东西相当于是维护一个等比数列,所以只要维护一个首项即可,如果不会求和公式,那就可以翻开高中数学必修书去找一找了。

NO2.这就是很多人在当时写的算法了,对于F1 = 1 , F2 = 1 , F1 + ... Fn = Fn + 2 - 1, 同样的,对于H1 = a , H2 = b , H1 + ... Hn = Hn+2 - b,这样也可以用线段树搞了,不过速度会慢一倍多,T3没有卡常数,不然今天就没有人AK了。。。

PS:感谢那些做过这套题的人帮我捧场,不然分数太难看了,下次的题目会更加的有趣哦!

@eternal 2016-10-04 21:16 回复 举报

T1标程

#include <bits/stdc++.h>
#include <tr1/unordered_map>
#define REP( i , l , r ) for( int i = (l) ;  i <= (r) ; i++ ) 
using namespace std;
inline int _read(){
    register int x = 0 , f = 1;
    register char ch = getchar();
    while( ch > '9' || ch < '0' ) { if( ch == '-' ) f = -1; ch = getchar(); }
    while( ch >= '0' && ch <= '9' ){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
int N , M;
const int maxn = 300000 + 5;
const int INF = 0x7f7f7f7f;
int a[maxn] , b[maxn];
int c[maxn] , pos = 0;
int g[maxn] ;
tr1::unordered_map<int , int> _hash;
int main(){
    N = _read() , M = _read();
    REP( i , 0 , N - 1 ) a[i] = _read();
    REP( j , 0 , M - 1 ) b[j] = _read();
    REP( i , 0 , N - 1 )  _hash.insert( make_pair(a[i] , i) );
    REP( i , 0 , M - 1 )
        if( _hash.count(b[i]) ) { c[pos++] = _hash[b[i]]; }
    int ans = 1;
    REP( i , 0 , N ) g[i] = INF;
    REP( i , 0 , pos - 1 ){
        int k = lower_bound( g + 1 , g + N + 1 , c[i] ) - g;
        g[k] = c[i]; ans = max( ans , k );
    }
    cout << ans << endl;
    return 0;
}
@eternal 2016-10-04 21:17 回复 举报

T2

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define red(i, a, b) for(int i = (a); i >= (b); i--)
#define LD long double
#define ll long long
#define abs ABS
#define sqr SQR
#define PII pair<int, int>
#define MP make_pair
#define PB push_back
#define FI first
#define SE second
template<typename tn> void read(tn& a) {
    tn x = 0, f = 1; char c = getchar();
    while(!isdigit(c)) {
        if (c == '-') f = -1;
        c = getchar();
    }
    while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
    a = x * f;
}
template<typename tn> void cmax(tn& a, tn b) { if (b > a) a = b; }
template<typename tn> void cmin(tn& a, tn b) { if (b < a) a = b; }
template<typename tn> tn abs(tn a) { return a < 0 ? -a : a; }
template<typename tn> tn sqr(tn a) { return a * a; }
const int N = 110000;
const ll inf = 1000000000ll * 1000000000ll + 10ll;
struct Edge {
    int from, to, len, nxt;
}E[N << 1];
int head[N], vis[N];
ll d[N];
struct Node {
    int x;
    ll dis;
};
bool operator < (Node a, Node b) { return a.dis < b.dis; }
bool operator > (Node a, Node b) { return a.dis > b.dis; }
priority_queue< Node, vector<Node>, greater<Node> > q;
ll h;
int x, y, z, tail = 0;
inline void addEdge(int from, int to, int len) {
    E[++tail] = (Edge){from, to, len, head[from]};
    head[from] = tail;
}
inline void Dijkstra() {
    rep(i, 0, x) d[i] = inf;
    d[1 % x] = 1;
    q.push((Node){1 % x, d[1 % x]});
    while(!q.empty()) {
        Node now = q.top();
        while(vis[now.x]) {
            q.pop();
            if (q.empty()) return;
            now = q.top();
        }
        q.pop();
        int x = now.x; vis[x] = 1;
        for(int i = head[x]; i != -1; i = E[i].nxt) {
            int v = E[i].to;
            if (vis[v] || d[x] + E[i].len > h) continue;
            if (d[x] + E[i].len < d[v]) {
                d[v] = d[x] + E[i].len;
                q.push((Node){v, d[v]});
            }
        }
    }
}
int main() {
    read(h);
    read(x); read(y); read(z);
    rep(i, 0, x) head[i] = -1;
    rep(i, 0, x - 1) {
        addEdge(i, (i + y) % x, y);
        addEdge(i, (i + z) % x, z);
    }
    Dijkstra();
    ll ans = 0;
    rep(i, 0, x - 1) {
        if (d[i] > h) continue;
        ans += (h - d[i]) / x + 1;
    }
    cout << ans << endl;
    return 0;
}
@eternal 2016-10-04 21:17 回复 举报

T3

#include <bits/stdc++.h>
#define REP( i , l , r ) for( int i = (l) ; i <= (r) ; i++ )
using namespace std;
typedef long long ll;
inline int _read(){
    int x = 0;
    char ch = getchar();
    while( ch < '0' || ch > '9' ) ch = getchar();
    while( ch >='0' && ch <='9' ){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
const int MOD = 1e9 + 9;
const int maxn = 300000;
ll bas = 276601605 , q1 = 691504013 , q2 = 308495997;
ll mul1[maxn] , mul2[maxn] , s[maxn];
int c[maxn] , N , K ;
struct node{
    ll a , b ;
    ll sum;
} t[maxn * 4];
void prework( int M ){
    mul1[0] = mul2[0] = 1;
    REP( i , 1 , M ){
        mul1[i] = mul1[i - 1] * q1 % MOD;
        mul2[i] = mul2[i - 1] * q2 % MOD;
    }
}
void build( int x , int l , int r ){
    t[x].a = t[x].b = t[x].sum = 0;
    if( l == r ) return;
    int mid = ( l + r ) >> 1;
    build( x << 1 , l , mid );
    build( (x << 1) + 1 , mid + 1 , r );
}
void push_down( int x , int l , int r ){
    ll aa = t[x].a , bb = t[x].b;
    if( 0 == aa && 0 == bb ) return;
    int lc = x << 1 , rc = (x << 1) | 1 , mid = (l + r) >> 1;
    int l1 = mid - l + 1 , l2 = r - mid;
    t[lc].a = (t[lc].a + aa) % MOD;
    t[lc].b = (t[lc].b + bb) % MOD;
    t[lc].sum = ( t[lc].sum + aa * (mul1[l1 + 2] - mul1[2]) ) % MOD;
    t[lc].sum = ( t[lc].sum - bb * (mul2[l1 + 2] - mul2[2]) ) % MOD;
    t[rc].a = ( t[rc].a + aa * mul1[l1] ) % MOD;
    t[rc].b = ( t[rc].b + bb * mul2[l1] ) % MOD;
    t[rc].sum = ( t[rc].sum + aa * mul1[l1] % MOD * (mul1[l2 + 2] - mul1[2] ) % MOD ) % MOD;
    t[rc].sum = ( t[rc].sum - bb * mul2[l1] % MOD * (mul2[l2 + 2] - mul2[2] ) % MOD ) % MOD;
    t[x].a = t[x].b = 0;
}
void push_up( int x ){
    t[x].sum = ( t[x << 1].sum + t[(x << 1) + 1].sum ) % MOD;
}
ll query( int x , int l , int r , int ql , int qr ){
    if( l == ql && r == qr ) return t[x].sum;
    push_down( x , l , r );
    int mid = (l + r) >> 1;
    if( qr <= mid ) return query( x << 1 , l , mid , ql , qr );
    else if( ql > mid ) return query( (x << 1) | 1 , mid + 1 , r , ql , qr );
    else return (query( x << 1 , l , mid , ql , mid ) + query( (x << 1) | 1 , mid + 1 , r , mid + 1 , qr )) % MOD;
}
void update( int rt , int l , int r , int ql , int qr , ll x , ll y ){
    if( l == ql && r == qr ){
        int len = r - l + 1;
        t[rt].a = (t[rt].a + x) % MOD;
        t[rt].b = (t[rt].b + y) % MOD;
        t[rt].sum = ( t[rt].sum + x * (mul1[len + 2] - mul1[2]) ) % MOD;
        t[rt].sum = ( t[rt].sum - y * (mul2[len + 2] - mul2[2]) ) % MOD;
        return;
    }
    push_down( rt , l , r );
    int mid = (l + r) >> 1;
    if( qr <= mid ) update( (rt << 1) , l , mid , ql , qr ,  x , y );
    else if( ql > mid ) update( (rt << 1) | 1 , mid + 1 , r , ql , qr , x , y );
    else{
        int len = mid - ql + 1;
        update( rt << 1 , l , mid , ql , mid , x , y );
        update( (rt << 1) | 1 , mid + 1 , r , mid + 1 , qr , x * mul1[len] % MOD , y * mul2[len] % MOD );
    }
    push_up( rt );
}
int main(){
    N = _read() , K = _read();
    REP( i , 1 , N ){
        c[i] = _read();
        s[i] = s[i - 1] + c[i];
    }
    prework( 60200 );
    build( 1 , 1 , N );
    REP( i , 1 , K ){
        int opt , l , r;
        opt = _read() , l = _read() , r = _read();
        if( opt == 1 ) update( 1 , 1 , N , l , r , 1 , 1 );
        else{
            ll ret = ( bas * query( 1 , 1 , N , l , r ) % MOD + s[r] - s[l - 1] ) % MOD;
            if( ret < 0 ) ret += MOD;
            printf( "%lld\n" , ret );
        }
    }
    return 0;
}
@eternal 2016-10-04 21:26 回复 举报

T3NO2

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define red(i, a, b) for(int i = (a); i >= (b); i--)
#define LD long double
#define ll long long
#define abs ABS
#define sqr SQR
#define PII pair<int, int>
#define MP make_pair
#define PB push_back
#define FI first
#define SE second
template<typename tn> void read(tn& a) {
    tn x = 0, f = 1; char c = getchar();
    while(!isdigit(c)) {
        if (c == '-') f = -1;
        c = getchar();
    }
    while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
    a = x * f;
}
template<typename tn> void cmax(tn& a, tn b) { if (b > a) a = b; }
template<typename tn> void cmin(tn& a, tn b) { if (b < a) a = b; }
template<typename tn> tn abs(tn a) { return a < 0 ? -a : a; }
template<typename tn> tn sqr(tn a) { return a * a; }
const int N = 110000;
const ll mod = 1000000009;
struct Node {
    int l, r;
    ll sum, f1, f2;
}t[N * 4];
int n, m;
ll a[N], F[N];
void Build(int x, int l, int r) {
    int mid = (l + r) >> 1, lc = x << 1, rc = lc + 1;
    t[x].l = l; t[x].r = r;
    t[x].f1 = t[x].f2 = 0;
    if (l == r) {
        t[x].sum = a[l];
        return;
    }
    Build(lc, l, mid); Build(rc, mid + 1, r);
    t[x].sum = (t[lc].sum + t[rc].sum) % mod;
}
inline ll getH(ll a, ll b, ll n) {
    if (n == 1) return a;
    if (n == 2) return b;
    return (a * F[n - 2] % mod + b * F[n - 1] % mod) % mod;
}
inline ll SUM(ll a, ll b, ll n) {
    if (n == 1) return a;
    if (n == 2) return (a + b) % mod;
    return (getH(a, b, n + 2) - b + mod) % mod;
}
void pushdown(int x) {
    int l = t[x].l, r = t[x].r;
    int mid = (l + r) >> 1, lc = x << 1, rc = lc + 1;
    (t[lc].f1 += t[x].f1) %= mod;
    (t[lc].f2 += t[x].f2) %= mod;
    (t[lc].sum += SUM(t[x].f1, t[x].f2, mid - l + 1)) %= mod;
    (t[rc].f1 += getH(t[x].f1, t[x].f2, mid - l + 2)) %= mod;
    (t[rc].f2 += getH(t[x].f1, t[x].f2, mid - l + 3)) %= mod;
    t[rc].sum += SUM(t[x].f1, t[x].f2, r - l + 1) - SUM(t[x].f1, t[x].f2, mid - l + 1);
    (t[rc].sum += mod) %= mod;    
    t[x].f1 = t[x].f2 = 0;
}
void update(int x, int l, int r, int ql, int qr) {
    int mid = (l + r) >> 1, lc = x << 1, rc = lc + 1;
    if (ql <= l && r <= qr) {
        (t[x].f1 += F[l - ql + 1]) %= mod;
        (t[x].f2 += F[l - ql + 2]) %= mod;
        (t[x].sum += SUM(F[l - ql + 1], F[l - ql + 2], r - l + 1)) %= mod;
        return;
    }
    pushdown(x);
    if (ql <= mid) update(lc, l, mid, ql, qr);
    if (qr > mid) update(rc, mid + 1, r, ql, qr);
    t[x].sum = (t[lc].sum + t[rc].sum) % mod;
    return;
}
ll query(int x, int l, int r, int ql, int qr) {
    int mid = (l + r) >> 1, lc = x << 1, rc = lc + 1;
    if (ql <= l && r <= qr) return t[x].sum;
    pushdown(x);
    if (qr <= mid) return query(lc, l, mid, ql, qr);
    else if (ql > mid) return query(rc, mid + 1, r, ql, qr);
    else return (query(lc, l, mid, ql, qr) + query(rc, mid + 1, r, ql, qr)) % mod;
}
int main() {
    read(n); read(m);
    rep(i, 1, n) read(a[i]);
    F[1] = F[2] = 1; 
    rep(i, 3, n + 10) F[i] = (F[i - 1] + F[i - 2]) % mod;
    Build(1, 1, n);
    rep(i, 1, m) {
        int tp, l, r;
        read(tp); read(l); read(r);
        if (tp == 1) update(1, 1, n, l, r);
        else printf("%lld\n", query(1, 1, n, l, r));
    }
    return 0;
}
@eternal 2016-10-04 22:25 回复 举报
pas No1const
  maxn=300000;
var
  n,m,i,j,all,t,ans:longint;
  a,b,e,f,g:array[1..maxn] of longint;
  hash:array[1..maxn*2] of longint;
  c,d:array[1..maxn*2] of longint;
  function func(x:longint):longint;
  var
    l,r,mid:longint;
  begin
    if ans=0
    then exit(0);
    l:=0;r:=ans;
    while l<r do
      begin
        mid:=(l+r+1) div 2;
        if x>=g[mid]
        then l:=mid
        else r:=mid-1;
      end;
    exit(l);
  end;
  function max(x,y:longint):longint;
  begin

if x>y

    then exit(x)
    else exit(y);
  end;
  procedure sort(l,r:longint);
  var
    i,j,x,y:longint;
  begin
    i:=l;
    j:=r;
    x:=c[(l+r) div 2];
    repeat
      while c[i]<x do
        inc(i);
      while x<c[j] do
        dec(j);
        if not(i>j)
        then begin
               y:=c[i];
               c[i]:=c[j];
               c[j]:=y;
               y:=d[i];
               d[i]:=d[j];
               d[j]:=y;
               inc(i);
               j:=j-1;
             end;
    until i>j;
    if l<j
    then sort(l,j);
    if i<r
    then sort(i,r);
  end;
begin
  read(n,m);
  for i:=1 to n do
    begin
      read(a[i]);
      c[i]:=a[i];
      d[i]:=i;
    end;
  for i:=1 to m do
    begin
      read(b[i]);
      c[i+n]:=b[i];
      d[i+n]:=i+n;
    end;
  sort(1,n+m);
  all:=0;
  for i:=1 to n+m do
    begin
      if (i=1)or(c[i]<>c[i-1])
      then inc(all);
      if d[i]<=n
      then a[d[i]]:=all
      else b[d[i]-n]:=all;
    end;
  for i:=1 to n do
    hash[a[i]]:=i;
  for i:=1 to m do
    if hash[b[i]]<>0
    then e[hash[b[i]]]:=i;
  ans:=0;
  for i:=1 to n do
    begin
      if e[i]=0
      then continue;
      t:=func(e[i])+1;
      f[i]:=t;

if t>ans

      then ans:=t;
      if (g[t]=0)or(e[i]<g[t])
      then g[t]:=e[i];
    end;
  writeln(ans);
end.
@eternal 2016-10-04 22:26 回复 举报

pas T2

const
  maxv=100000;
  maxq=10000000;
var
  n,ans,x,y,z,t,m,l,r:int64;
  i:longint;
  a,b:array[0..maxv] of int64;
  q:array[1..maxq] of int64;
  procedure func(var x,y,z:int64);
  var
    t:int64;
  begin
    if x>y then begin t:=x;x:=y;y:=t;end;
    if y>z then begin t:=y;y:=z;z:=t;end;
    if x>y then begin t:=x;x:=y;y:=t;end;
  end;
begin
  read(n,x,y,z);
  func(x,y,z);
  if x=1
  then begin writeln(n);exit;end;
  l:=1;r:=1;
  a[1]:=1;
  b[1]:=1;
  q[1]:=1;
  while not((l=r+1)or(r=maxq)and(l=1)) do
  begin
    if b[q[l]]=1
    then begin
           t:=a[q[l]]+y;
           m:=t mod x;
           if (t<=n)and((a[m]=0)or(a[m]>t))
           then begin
                  a[m]:=t;
                  inc(b[m]);
                  inc(r);

if r>maxq

                  then r:=1;
                  q[r]:=m;
                end;
           t:=a[q[l]]+z;
           m:=t mod x;
           if (t<=n)and((a[m]=0)or(a[m]>t))
           then begin
                  a[m]:=t;
                  inc(b[m]);
                  inc(r);

if r>maxq

                  then r:=1;
                  q[r]:=m;
                end;
         end;
    dec(b[q[l]]);
    inc(l);

if l>maxq

    then l:=1;
  end;
  for i:=0 to x-1 do
    if a[i]<>0
    then inc(ans,(n-a[i]) div x+1);
  writeln(ans);
end.
@eternal 2016-10-04 22:27 回复 举报

pas T3

const
  v=1000000009;
  maxn=100000;
type
  node=record
         lc:longint;
         rc:longint;
         t1:int64;
         t2:int64;
         sum:int64;
       end;
var
  n,m,i,c,l,r,all:longint;
  x,f,s:array[0..maxn] of int64;
  a:array[1..maxn*2] of node;
  function cal(x,y,z:int64):int64;
  var
    sa,sb:int64;
  begin
    if z=2
    then exit(x+y);
    sa:=f[z];
    sb:=s[z-1];
    exit((sa*x+sb*y) mod v);
  end;
  function get(x,y,z:int64):int64;
  begin
    exit((x*f[z-2]+y*f[z-1]) mod v);
  end;
  procedure pushdown(i,l,r:longint);
  var
    mid,x,y:longint;
    t1,t2:int64;
  begin
    mid:=(l+r) div 2;
    x:=a[i].lc;y:=a[i].rc;
    a[x].t1:=(a[x].t1+a[i].t1) mod v;
    a[x].t2:=(a[x].t2+a[i].t2) mod v;
    a[x].sum:=(a[x].sum+cal(a[i].t1,a[i].t2,mid-l+1)) mod v;
    t1:=get(a[i].t1,a[i].t2,mid-l+2);
    t2:=get(a[i].t1,a[i].t2,mid-l+3);
    a[y].t1:=(a[y].t1+t1) mod v;
    a[y].t2:=(a[y].t2+t2) mod v;
    a[y].sum:=(a[y].sum+cal(t1,t2,r-mid)) mod v;
    a[i].t1:=0;
    a[i].t2:=0;
  end;
  procedure maintain(i,l,r,ql,qr:longint;t1,t2:int64);
  var
    mid:longint;
  begin
    if l=r
    then begin
           a[i].sum:=(a[i].sum+t1) mod v;
           exit;
         end;
    if (l=ql)and(r=qr)
    then begin
           a[i].t1:=(a[i].t1+t1) mod v;
           a[i].t2:=(a[i].t2+t2) mod v;
           a[i].sum:=(a[i].sum+cal(t1,t2,r-l+1)) mod v;
           exit;
         end;
    mid:=(l+r) div 2;
    a[i].sum:=(a[i].sum+cal(t1,t2,qr-ql+1)) mod v;
    pushdown(i,l,r);
    if qr<=mid
    then maintain(a[i].lc,l,mid,ql,qr,t1,t2)
    else if ql>mid
         then maintain(a[i].rc,mid+1,r,ql,qr,t1,t2)
         else begin
                maintain(a[i].lc,l,mid,ql,mid,t1,t2);
                maintain(a[i].rc,mid+1,r,mid+1,qr,get(t1,t2,mid-ql+2),get(t1,t2,mid-ql+3));
              end;
  end;
  procedure build(i,l,r:longint);
  var
    mid:longint;
  begin
    if l=r
    then begin
           a[i].sum:=x[l];
           exit;
         end;
    mid:=(l+r) div 2;
    inc(all);
    a[i].lc:=all;
    build(all,l,mid);
    inc(all);
    a[i].rc:=all;
    build(all,mid+1,r);
    a[i].sum:=(a[a[i].lc].sum+a[a[i].rc].sum) mod v;
  end;
  function query(i,l,r,ql,qr:longint):longint;
  var
    mid:longint;
  begin
    if (l=ql)and(r=qr)
    then exit(a[i].sum);
    mid:=(l+r) div 2;
    pushdown(i,l,r);
    if qr<=mid
    then exit(query(a[i].lc,l,mid,ql,qr))
    else if ql>mid
         then exit(query(a[i].rc,mid+1,r,ql,qr))
         else exit((query(a[i].lc,l,mid,ql,mid)+query(a[i].rc,mid+1,r,mid+1,qr)) mod v);
  end;
begin
  read(n,m);
  for i:=1 to n do
    read(x[i]);
  f[1]:=1;
  f[2]:=1;
  for i:=3 to n do
    f[i]:=(f[i-1]+f[i-2]) mod v;
  s[1]:=f[1];
  for i:=2 to n do
    s[i]:=(s[i-1]+f[i]) mod v;
  all:=1;
  build(1,1,n);
  for i:=1 to m do
    begin
      read(c,l,r);
      case c of
        1:maintain(1,1,n,l,r,1,1);
        2:writeln(query(1,1,n,l,r));
      end;
    end;
end.
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。