SCAU 2015 GDCPC team

A。题目：http://acm.timus.ru/problem.aspx?space=1&num=2024

题意：求一个包含K个不同字符的集合的最大长度，还有组成这个长度的集合的个数

做法：因为求的集合，不需连续，直接统计各个字符的出现次数。

那么答案一就是按出现次数排序再加前K个。

答案二只与K个中集合大小最小的分配相关。

/* hl */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
char s[100010];
ll c[30][30];

ll calc(int n, int m) {
    ll res = 1;
    for(int i=1; i<=m; i++) {
        res *= n-i+1;
        res /= i;
    }
    return res;
}

void c_init() {
    for(int i=1; i<=26; i++)
        for(int j=0; j<=26; j++)
            c[i][j] = calc(i, j);
}

struct node {
    ll cnt ; int vis ;
    bool operator <( const node &a ) const{
        if( vis!=a.vis ) return vis >a.vis ;
        else return cnt > a.cnt ;
    }
}e[30];

void init() {
    for( int i = 0 ; i < 26 ; ++i ) e[i].cnt = e[i].vis = 0 ;
}

int main()
{
    #ifdef LOCAL
        freopen("in","r",stdin);
    #endif
    c_init();
    int k ;
    while( ~scanf("%s%d",s,&k) ) {
        int len = strlen(s);
        init();
        for( int i = 0 ; i < len ; ++i ) {
            e[ s[i] - 'a' ].cnt ++ ;
            e[ s[i] - 'a' ].vis = 1 ;
        }
        sort( e , e + 26 ) ;
        ll ans1 = 0 , ans2 = 1 , last = -1  ;
        int tmp = 0 ;
        for( int i = 0 ; i < k && e[i].vis ; ++i ) {
            ans1 += e[i].cnt;
            if( e[i].cnt == last ) tmp++ ;
            else {
                last = e[i].cnt ; tmp = 1 ;
            }
        }
        int all = 0 ;
        for( int i = 0 ; i < 26 && e[i].vis ; ++i ) {
            if( e[i].cnt == last ) all++ ;
        }
        ans2 = c[all][tmp];
        printf("%I64d %I64d\n",ans1,ans2);
    }
    return 0;
}

View Code

B. 题目： http://acm.timus.ru/problem.aspx?space=1&num=2025

题意： n 个人分到 k 个组，不同组的人可以打架，求打架次数最多是多少

平均分配后，处理一个前缀/后缀和，然后一个个组统计

/*  hl  */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 10010;
int x[N] , sum[N] ;
int main()
{
    #ifdef LOCAL
    freopen("in","r",stdin);
    #endif
    int _ , n , m ;
    scanf("%d", &_);
    while(_--) {
        scanf("%d%d",&n,&m);
        for( int i = 1 ; i <= m ; ++i ) {
            x[i] = n / m ;
        }
        int c = n % m ;
        for( int i = 1 ; i <= m && i <= c ; ++i ) {
            x[i]++ ;
        }
        sum[m] = x[m] ;
        for( int i = m - 1 ; i >= 1 ; --i ) sum[i] = sum[i+1] + x[i] ;
        int ans = 0 ;
        for( int i = 1 ; i < m ; ++i ) {
            ans += x[i] * sum[i+1] ;
        }
        printf("%d\n",ans);
    }
    return 0;
}

View Code

C. 题目： http://acm.timus.ru/problem.aspx?space=1&num=2026

题意： n 节课 .. 不同字母不同课， ‘？’代表未确定，

奇位置加字符权，偶位置减字符权，问至少安排k节不同的课能够得到的最大权

若然,已经够k个不同字符就直接贪心放

　　　不然,先统计奇偶位置的问号 , 再看看应该在奇问号，还是在偶问号处放新字符。

这就要选跟最优字符的距离较小的那个新字符了

放够了剩下的就贪心

/* hl */
#include <bits/stdc++.h>
using namespace std ;
string s ;
int k ;
bool vis[30] ;
queue<int> o , e ;

int Run() {

    while( cin >> s >> k ) {
        memset( vis , false , sizeof vis ) ;
        int c = 0 , cnt1 = 0 , cnt2 = 0 ;
        for( int i = 0 ; i < s.length() ; ++i ) {
            if( s[i] == '?') {
                if( i&1 ) cnt2++ ;
                else cnt1++ ;
            }
            else if( !vis [ s[i] - 'a' ] ) {
                vis[ s[i] - 'a' ] = true , c++ ;
            }
        }
        //cout << cnt1 << ' ' << cnt2<< ' ' << c << endl ;
        if( cnt1 + cnt2 + c < k ) {
            cout << "-1" << endl ; continue ;
        }
        for( int i = c ; i < k ; ++i ) {
            int c1 = -1 , c2 = 26 ;
            for( int j = 25 ; j >= 0 ; --j ) if( !vis[j] ) { c1 = j ; break ; }
            for( int j = 0 ; j < 26 ; ++j ) if( !vis[j] ) { c2 = j ; break ; }
            if( 25 - c1 <= c2 && cnt1 ) {
                cnt1-- ;
                vis[c1] = true ;
                o.push(c1);
            } else {
                vis[c2] = true ;
                e.push(c2);
            }
        }
        for( int i = 0 ; i < s.length() ; ++i ) {
            if( s[i] == '?' ) {
                if( i&1 ) {   // even position
                    if( !e.empty() ) { s[i] = e.front() + 'a' ; e.pop() ; }
                    else s[i] = 'a' ;
                } else {
                    if( !o.empty() ) { s[i] = o.front() + 'a' ; o.pop() ; }
                    else s[i] = 'z' ;
                }
            }
        }
        cout << s << endl ;
    }
    return 0 ;
}
int main() {
//    freopen("in.txt","r",stdin);
    ios::sync_with_stdio(0) ;
    return Run();
}

View Code

D ：http://acm.timus.ru/problem.aspx?space=1&num=2027

模拟题

blue :
用一个数组保存整个程序
用一个pii的指针保存指针的位置
用一个27位的数组保存寄存器
剩下就是模拟了，注意异常的处理
其实我写的复杂，写烂了。。后来想想应该是十几分钟写完的代码

/* blue */
#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(i=(l); i<(r); i++)
#define drep(i, l, r) for(int i=(l); i<(r); i++)
typedef long long ll;
typedef pair<int,int> pii;
const int N = 105;

// Exception define
#define OE 0
#define RE 1
#define TLE 2
#define OK 3
char EXCEPTION[][30] = {"OVERFLOW ERROR","RUNTIME ERROR","TIME LIMIT EXCEEDED"};

// global
int n,m;
char program[N][N];

// input stream system
int read_pos, read_cnt, read_num[100010];
void read_init() {
    read_pos = 0;
    scanf("%d", &read_cnt);
    for(int i=0; i<read_cnt; i++) scanf("%d", read_num+i);
}
int read_next() {
    if(read_pos >= read_cnt) return read_num[read_cnt-1];
    return read_num[read_pos++];
}

// pointer system
pii pointer;
#define xx first
#define yy second
int dir;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};
inline bool inside(const int &x, const int &y) {return x>=0&&x<n && y>=0&&y<m;}
int move() {
    pointer.xx += dx[dir];
    pointer.yy += dy[dir];
    if(!inside(pointer.xx, pointer.yy)) return RE;
    return OK;
}
void changedir(char c) {
    if(c=='>') dir = 0;
    else if(c=='v') dir = 1;
    else if(c=='<') dir = 2;
    else dir = 3;
}

// REG system
int reg[30];
#define CURREG reg[26]
void swap_reg(char c) {
    int t = reg[c-'A'];
    reg[c-'A'] = CURREG;
    CURREG = t;
}

// INC and DEC
int INC() {
    CURREG++;
    if(CURREG > 100000 || CURREG < -100000) return OE;
    return OK;
}
int DEC() {
    CURREG--;
    if(CURREG > 100000 || CURREG < -100000) return OE;
    return OK;
}

// At @
void At() {
    if(CURREG==0) dir--;
    else dir++;
    if(dir<0) dir=3;
    if(dir>3) dir=0;
}

// choose command system
#define CMD program[pointer.xx][pointer.yy]
inline bool isDir() {return CMD=='v' || CMD=='^' || CMD=='<' || CMD=='>';}
inline bool isREG() {return CMD>='A' && CMD<='Z';}
inline bool isRead() {return CMD=='?';}
inline bool isWrite() {return CMD=='!';}
inline bool isINC() {return CMD=='+';}
inline bool isDEC() {return CMD=='-';}
inline bool isAt() {return CMD=='@';}
inline bool isTerminal() {return CMD=='#';}

int main()
{
    #ifdef LOCAL
    freopen("in","r",stdin);
    #endif
    while(scanf("%d%d", &n, &m)!=EOF) {
        memset(reg, 0, sizeof(reg));
        // read program
        for(int i=0; i<n; i++) scanf("%s", program[i]);
        // input stream
        read_init();
        // pointer
        pointer = pii(0, 0); dir = 0;
        int cnt = 0;
        while(true) {

            cnt++;
            if(cnt>1000000) {
                puts(EXCEPTION[TLE]);
                break;
            }

            int status = OK;

            if(isDir()) changedir(CMD);
            else if(isREG()) swap_reg(CMD);
            else if(isRead()) CURREG = read_next();
            else if(isWrite()) {printf("%d\n", CURREG);CURREG=0;}
            else if(isINC()) status = INC();
            else if(isDEC()) status = DEC();
            else if(isAt()) At();
            else if(isTerminal()) break;
            if(status != OK) {
                puts(EXCEPTION[status]);
                break;
            }

            if(status != OK) {
                puts(EXCEPTION[status]);
                break;
            }

            status = move();
            if(status != OK) {
                puts(EXCEPTION[status]);
                break;
            }
        }
    }
    return 0;
}

View Code

赛后我自己也写了一次。

注意下 TLE 的判断要符合这句话：

If the termination operator is not executed during 10⁶ steps and none of the above two errors occurs, then the program terminates with TIME LIMIT EXCEEDED.

然后还要注意得先判 OVE 再判 RE. ,这里我wa了好几发才发现

/* hl */
#include <bits/stdc++.h>
using namespace std ;
const int N = 101 ;
const int TLE = 1000000;
#define OVE  100000
int h , w ;
string mp[N] ;
int dx[] = { 0 , 1 , 0 , -1 } ;
int dy[] = { 1 , 0 , -1 , 0 } ;
int x , y , dir , tim ;
int scan[100010] , reg[30] ;

int Run() {
    while( cin >> h >> w ) {
        for( int i = 0 ; i < h ; ++i ) cin >> mp[i] ;
        int n ; cin >> n ;
        for( int i = 0 ; i < n ; ++i ) cin >> scan[i] ;
        dir = x = y = tim = 0 ;
        int c = 0 , cur = 0 ;
        bool finish = false ;
        memset( reg , 0 , sizeof reg ) ;
        while( true ) {
            tim++ ;
            switch( mp[x][y] ) {
                case '>' : dir = 0 ; break ;
                case 'v' : dir = 1 ; break ;
                case '<' : dir = 2 ; break ;
                case '^' : dir = 3 ; break ;
                case '.' : break; 
                case '?' : cur = scan[c>=n?n-1:c] ; c++;  break ;
                case '!' : cout<<cur<<endl ; cur = 0 ; break ;
                case '+' : cur++ ; break ;
                case '-' : cur-- ; break ;
                case '@' : dir = ( cur ? ( dir + 1 ) % 4 : ( dir + 3 ) % 4 ) ; break ;
                case '#' : finish = true ; break ;
                default  : swap( cur , reg[  mp[x][y] - 'A' ] ) ; break; 
            }
            if( finish ) break ;
            x += dx[dir] ; y += dy[dir] ;
                        if( cur > OVE || cur < -OVE ) {
                cout << "OVERFLOW ERROR" << endl;
                break ;
            } else if( x < 0 || x >= h || y < 0 || y >= w ) {
                cout << "RUNTIME ERROR" << endl;
                break ;
            } else if( tim == TLE ) {
                cout << "TIME LIMIT EXCEEDED" << endl;
                break ;
            }
        }
    }
    return 0 ;
}
int main() {
//    freopen("in.txt","r",stdin);
    ios::sync_with_stdio(0) ;
    return Run();
}

View Code

E：http://acm.timus.ru/problem.aspx?space=1&num=2028

题目要求.. 弄一个输入，然后再输入 1 n ，放到D题能够跑出前 n 项和。

做法：根据D题，数字每次操作只能够+1 ，还有交换操作当前寄存器和内存寄存器的值，一个判断操作@ ，能够判当前寄存器是否为 0 。

当前寄存器用reg表示，其余寄存器 A~Z吧

如何把一个数n弄成两个呢？直接把这个数放到reg上，每次-1，就换出A来+1 ，换出B+1 。

用@判出reg值为0 的时候， A ， B 就有n了

然后再用一个C来保存结果。 A 复制成两个后，把B也像上述操作一样加到C上，直到B为0 。

A不等于0 ？ A的值 -1 ，复制到B上，进行操作1 。

A 等于0 ？输出C 。

然后画一下图，按照D题题意换成字符就OK了。

/* hl */
#include <bits/stdc++.h>
using namespace std ;
int h , w ;
string s[] = {
    "?......A.>..v..........<",
    "...............>C.!#....",
    ".v..........@>A@........",
    "...............>.>....v.",
    "..............>..^......",
    "..............@-B+BA+A<.",
    "..............>..A-AB..^",
    ".>C+C-...^.............."
};

int Run() {
    cout << 8 << ' ' << 24 << endl ;
    for( int i = 0 ; i < 8 ; ++i ) cout << s[i] << endl ;
    return 0 ;
}
int main() {
//    freopen("in.txt","r",stdin);
    ios::sync_with_stdio(0) ;
    return Run();
}

View Code

F： http://acm.timus.ru/problem.aspx?space=1&num=2029

汉诺塔变形吧。题意就是把一个全部放在A汉诺塔移成给出的状态

可以发现所有状态都是可以得到的，只要你合法地移动

要明白，移动第i个到目标位置。

如果第i个已经在目标位置的话，可以直接忽略它了。然后去处理第 i - 1 个。

　　　　　　如果不在目标位置，要把第 i 个移动到目标位置，必须把上面的 i -1 个移动到除原位置和目标位置的那个位置上，需要 2^( i-1)-1 步。

加上自己移动的那一步就是 2^( i-1) 因为移动的位置唯一，这里是无可避免的，必须加到答案上。

/* hl */
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL;
int n ;
string s ;
LL ans ;
void dfs( int dep , int pos ) {
    if( dep < 0 ) return ;
    int goal = s[dep] - 'A' ;
//    cout << dep << ' ' << pos << ' ' << ans << endl ;
    if( goal == pos ) dfs( dep - 1 , pos ) ;
    else {
        ans += (1LL<<dep) ;
        if( pos == 0 ) {
            if( goal == 2 ) dfs( dep - 1 , 1 ) ;
            else dfs( dep - 1 , 2 ) ;
        } else if( pos == 1 ) {
            if( goal == 0 ) dfs( dep - 1 , 2 ) ;
            else dfs( dep - 1 , 0 ) ;
        } else {
            if( goal == 1 ) dfs( dep - 1 , 0 ) ;
            else dfs( dep - 1 , 1 ) ;
        }
    }
}
int Run() {
    while( cin >> n >> s ) {
        ans = 0 ;
        dfs( s.length() - 1 , 0 ) ;
        cout << ans << endl ;
    }
    return 0 ;
}
int main() {
//    freopen("in.txt","r",stdin);
    ios::sync_with_stdio(0) ;
    return Run();
}

View Code

G: http://acm.timus.ru/problem.aspx?space=1&num=2030

有3种做法：

O（ n + m ） : 转成有根树，在线更新父亲，离线更新儿子。

更新的时候就是父亲的离线值 + 自身的在线值。

然后按照上面讲的来更新

/*  VM  */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for(int i = 1; i <= (n); ++i)
#define For(i, b, e, s) for(int i = (b); i != (e); i += (s))
const int N = 100005;
const int mod = 1000000007;
vector<int> G[N];
int par[N], val[N], add[N], n;

void dfs(int u, int p){
    par[u] = p;
    for(unsigned int i = 0; i < G[u].size(); ++i) if(G[u][i] != p) dfs(G[u][i], u);
}

int main(){
    int u, v, m;
    while(scanf("%d", &n) == 1){
        rep(i, n + 1) G[i].clear();
        memset(add, 0, sizeof(add[0]) * (n + 1));
        rep1(i, n) scanf("%d", &val[i]);
        rep(i, n - 1){
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs(1, 0);   
        scanf("%d", &m);
        while(m--){
            scanf("%d%d", &u, &v);
            if(u == 1){
                int t = val[v] + add[par[v]];
                if(t >= mod) t-= mod;
                if((val[par[v]] += t) >= mod) val[par[v]] -= mod;
                if((add[v] += t) >= mod) add[v] -= mod;
            }
            else{
                int t = val[v] + add[par[v]];
                if(t >= mod) t-= mod;
                printf("%d\n", t);
            }
        }
    }
    return 0;
}

View Code

O( n logn )

转成有根树，再bfs一次把树给分成一层层，同一个父亲的结点编号要连续。

然后就是用一个能够区间 logn 操作的数据结构进行单点查询，对父亲单点更新，对孩子成段更新。

/* hl */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define X first
#define Y second
const int N = 100100;
const int mod = 1e9+7;

int n , fa[N] , cnt , idx[N] , l_s[N] , r_s[N] , x[N] ;
vector<int>g[N];

void bfs() {
    int cnt = 1 ;
    memset( l_s , 0x3f , sizeof l_s );
    memset( r_s , -1 , sizeof r_s );
    queue<pii>que;
    que.push( pii(1,0) ) ;
    while( !que.empty() ) {
        int u = que.front().X , pre = que.front().Y ;
        que.pop();
        fa[u] = pre ;
        idx[u] = cnt++ ;
        l_s[pre] = min( l_s[pre] , idx[u] );
        r_s[pre] = max( r_s[pre] , idx[u] );
        for( int i = 0 ; i < g[u].size() ; ++i ) {
            int v = g[u][i] ;
            if( pre == v ) continue ;
            que.push( pii( v,u ) ) ;
        }
    }
}

ll c[N];
void init() {
    memset( c , 0 , sizeof c );
}
int lowbit( int x ) {
    return x&-x;
}

void update( int pos , ll key ) {
    while( pos < n + 10 ) {
        c[pos] = ( c[pos] + key + mod ) % mod ;
        pos += lowbit(pos);
    }
}

ll query( int pos ) {
    ll res = 0 ;
    if( !pos ) return 0 ;
    while( pos > 0 ) {
        res = ( res + c[pos] ) % mod ;
        pos -= lowbit(pos);
    }
    return res ;
}

int main()
{
    #ifdef LOCAL
        freopen("in.txt","r",stdin);
    #endif
    while( ~scanf("%d",&n) ) {

        for( int i = 1 ; i <= n ; ++i ) scanf("%d",&x[i]);
        for( int i = 1 ; i <= n ; ++i ) g[i].clear();

        for( int i = 1 ; i < n ; ++i ) {
            int u , v ; scanf("%d%d",&u,&v);
            g[u].push_back(v); g[v].push_back(u);
        }

        bfs(); init();
        for( int i = 1 ; i <= n ; ++i ) {
            update( idx[i] , x[i] );
            update( idx[i] + 1 , -x[i] );
        }

        int m ;
        scanf("%d",&m);
        while( m -- ) {
            int op , c ;
            scanf("%d%d",&op,&c);
            if( op == 1 ) {
                ll v = query( idx[c] ) ;
                if( c != 1 ) {
                    update( idx[ fa[c] ] , v ) ;
                    update( idx[ fa[c] ] + 1 , -v ) ;
                }
                if( r_s[c] != -1 ) {
                    update( l_s[c] , v ) ;
                    update( r_s[c] + 1 , -v ) ;
                }
            } else {
                printf("%I64d\n",query( idx[c] ));
            }
        }
    }
    return 0;
}

树分层+树状数组

用树状数组要注意一点就是差分的时候有减操作，取模后有负数出现，（x % mod + mod ） % mod 就可以解决了。

线段树的话可以避免上面的差错，不过不知道训练中何解WA ，重新写过一次然后就过了

/* hl */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define X first
#define Y second
const int N = 100100;
const int mod = 1e9+7;
#define root 1,n+20,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define lr rt<<1
#define rr rt<<1|1

int n , fa[N] , cnt , idx[N] , l_s[N] , r_s[N] ;
ll x[N] ;
vector<int>g[N];

ll date[N<<2] , lazy[N<<2] ;

void build( int l , int r , int rt ){
    date[rt] = lazy[rt] = 0 ;
    if( l == r ) return ;
    int mid = (l+r)>>1;
    build(lson) , build(rson) ;
}

void Down( int rt ) {
    if( lazy[rt] ) {
        date[lr] = ( date[lr] + lazy[rt]  ) % mod ;
        date[rr] = ( date[rr] + lazy[rt]  ) % mod ;
        lazy[lr] = ( lazy[lr] + lazy[rt]  ) % mod ;
        lazy[rr] = ( lazy[rr] + lazy[rt]  ) % mod ;
        lazy[rt] = 0 ;
    }
}

void update( int l , int r , int rt , int L , int R , ll v ) {
    if( l == L && r == R ) {
        date[rt] = ( date[rt] + v  ) % mod ;
        lazy[rt] = ( lazy[rt] + v  ) % mod ;
        return ;
    }
    Down( rt ) ;
    int mid = (l+r)>>1;
    if( R <= mid ) update( lson , L , R , v ) ;
    else if( L > mid ) update( rson , L , R , v ) ;
    else update( lson , L , mid , v ) , update( rson , mid + 1 , R , v ) ;

}

ll query( int l , int r , int rt , int x ) {
    if( l == r ) {
        return date[rt] ;
    }
    Down( rt ) ;
    int mid = (l+r)>>1;
    if( x <= mid ) return query( lson , x ) ;
    else return query( rson , x );
}

void bfs() {
    int cnt = 1 ;
    memset( l_s , 0x3f , sizeof l_s );
    memset( r_s , -1 , sizeof r_s );
    queue<pii>que;
    que.push( pii(1,0) ) ;
    while( !que.empty() ) {
        int u = que.front().X , pre = que.front().Y ;
        que.pop();
        fa[u] = pre ;
        idx[u] = cnt++ ;
        l_s[pre] = min( l_s[pre] , idx[u] );
        r_s[pre] = max( r_s[pre] , idx[u] );
        for( int i = 0 ; i < g[u].size() ; ++i ) {
            int v = g[u][i] ;
            if( pre == v ) continue ;
            que.push( pii( v,u ) ) ;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0) ;
    while( cin >> n ) {

        for( int i = 1 ; i <= n ; ++i ) cin >> x[i] ;
        for( int i = 1 ; i <= n ; ++i ) g[i].clear();

        for( int i = 1 ; i < n ; ++i ) {
            int u , v ; cin >> u >> v ;
            g[u].push_back(v); g[v].push_back(u);
        }

        bfs();
        build(root);
        for( int i = 1 ; i <= n ; ++i )
            update( root , idx[i] , idx[i] , x[i] );
        int m ; cin >> m ;
        while( m -- ) {
            int op , c ; cin >> op >> c ;
            if( op == 1 ) {
                ll v = query( root , idx[c] ) ;
                if( c != 1 ) {
                    update( root , idx[ fa[c] ] , idx[ fa[c] ] , v ) ;
                }
                if( r_s[c] != -1 ) {
                    update( root , l_s[c] , r_s[c] , v ) ;
                }
            } else {
                cout << query( root , idx[c] ) << endl ;;
            }
        }
    }
    return 0;
}

线段树

O( n sqrt(n) )

把结点分层两类，孩子结点大于 sqrt(n) 个的，孩子结点小于 sqrt(n) 。

对前面的离线更新，后面的在线更新。

/* lys */
#include <bits/stdc++.h>
using namespace std;

const int UB = 111;
const int N = 111111;
const int MOD = 1e9 + 7;

vector<int> nx[N], bnx[N];
int sum[N], out[N];

void Add(int &a, const int b) {
    a += b;
    if (a >= MOD) {
        a -= MOD;
    }
}

int Run() {
    int n;

    while (cin >> n) {
        int x, y;

        for (int i = 1; i <= n; ++i) {
            nx[i].clear();
            cin >> sum[i];
            out[i] = 0;
        }
        for (int i = 1; i < n; ++i) {
            cin >> x >> y;
            nx[x].push_back(y);
            nx[y].push_back(x);
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < nx[i].size(); ++j) {
                if (nx[nx[i][j]].size() > UB) {
                    bnx[i].push_back(nx[i][j]);
                }
            }
        }
        int m;

        cin >> m;
        for (int i = 0; i < m; ++i) {
            cin >> x >> y;
            if (x == 1) {
                if (nx[y].size() > UB) {
                    for (int i = 0; i < bnx[y].size(); ++i) {
                        Add(sum[bnx[y][i]], sum[y]);
                    }
                    Add(out[y], sum[y]);
                } else {
                    int s = sum[y];

                    for (int i = 0; i < nx[y].size(); ++i) {
                        Add(s, out[nx[y][i]]);
                    }
                    for (int i = 0; i < bnx[y].size(); ++i) {
                        Add(sum[bnx[y][i]], s);
                    }
                    Add(out[y], s);
                }
            } else {
                if (nx[y].size() > UB) {
                    cout << sum[y] << endl;
                } else {
                    int s = sum[y];

                    for (int i = 0; i < nx[y].size(); ++i) {
                        Add(s, out[nx[y][i]]);
                    }
                    cout << s << endl;
                }
            }
        }
    }

    return 0;
}

int main() {
    ios::sync_with_stdio(0);
    return Run();
}

View Code

H: http://acm.timus.ru/problem.aspx?space=1&num=2031

全过了，忽略

I ：http://acm.timus.ru/problem.aspx?space=1&num=2032

blue :
原理就是固定三角形一个点在原点上，那剩下就是找两个点，然后判断一下长度是否符合题目给出的三条边长
根据题目给出的边长A，可以在o（len）找出这些符合条件的点。

就是枚举x坐标，然后看y坐标是否符合，不符合就y--，x越大的话y肯定要越小。同理用同样的方法找出边长B对应的整点。这样找出来满足条件的整点其实数量是很少的。
然后就是枚举这两组顶点的组合，看看这两个点连起来的长度是否为C

/* blue */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
vector<pll> va, vb;
const int dx[] = {1,1,-1,-1};
const int dy[] = {1,-1,1,-1};
#define x first
#define y second
inline ll sqr(ll x) {return x*x;}

int main()
{
    ll a,b,c;
    while(cin>>a>>b>>c) {
        va.clear();
        vb.clear();
        for(ll i=0, j=a; i<=a; i++) {
            while(i*i+j*j>a*a) j--;
            if(i*i+j*j==a*a) va.push_back(pll(i,j));
        }
        for(ll i=0, j=b; i<=b; i++) {
            while(i*i+j*j>b*b) j--;
            if(i*i+j*j==b*b) vb.push_back(pll(i,j));
        }
        for(unsigned i=0; i<va.size(); i++) {
            for(unsigned j=0; j<vb.size(); j++) {
                for(int d=0; d<4; d++) {
                    if(sqr(va[i].x-vb[j].x*dx[d]) + sqr(va[i].y-vb[j].y*dy[d]) == c*c) {
                        cout << "0 0" << endl;
                        cout << va[i].x << ' ' << va[i].y << endl;
                        cout << vb[j].x*dx[d] << ' ' << vb[j].y*dy[d] << endl;
                        goto bk;
                    }
                }
            }
        }
        cout << "-1" << endl;
        bk: continue;
    }
    return 0;
}

View Code

J: http://acm.timus.ru/problem.aspx?space=1&num=2033 水，忽略

K: http://acm.timus.ru/problem.aspx?space=1&num=2034

blue :
首先用BFS求出每个结点离r点的距离，用dis[u]来表示u到r的距离
然后用一次dij来求，额外用一个数组mx[u]表示从s点到u点上，距离最短的是多少。
那从点u到点v的递推关系就是： mx[v] = min(max(mx[v],mx[u]), dis[v])
求完dij以后，答案就是mx[t]了

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const int INF = 1e9;
#define drep(i, l, r) for(int i=l; i<(r); i++)
#define MAX(x, y) (x>y?x:y)
#define MIN(x, y) (x<y?x:y)
#define fi first
#define se second
typedef pair<int,int> pii;

int n, m, s, f, r, mx[N], dis[N], d[N];
bool vis[N];
vector<int> g[N];

void bfs(int s) {
    memset(vis, 0, sizeof(vis));
    queue<pii> que;
    que.push(pii(s, 0));
    while(!que.empty()) {
        int u = que.front().fi;
        int l = que.front().se;
        que.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        dis[u] = l;
        for(unsigned i=0; i<g[u].size(); i++) {
            int &v = g[u][i];
            que.push(pii(v, l+1));
        }
    }
}

int dij(int s, int t) {
    memset(vis, 0, sizeof(vis));
    priority_queue<pii, vector<pii>, greater<pii> > que;
    drep(i, 1, n+1) d[i] = INF, mx[i] = -1;
    d[s] = 0;
    que.push(pii(0, s));
    while(!que.empty()) {
        int u = que.top().se;
        que.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        if(mx[u] == -1) mx[u] = dis[u];
        else mx[u] = MIN(mx[u], dis[u]);
        if(u == t) return mx[t];
        for(unsigned i=0; i<g[u].size(); i++) {
            int &v = g[u][i];
            if(d[u]+1 <= d[v]) {
                d[v] = d[u]+1;
                if(mx[v] == -1) mx[v] = mx[u];
                else mx[v] = MAX(mx[v], mx[u]);
                que.push(pii(d[v], v));
            }
        }
    }
    return d[t];
}

int main() {
    #ifdef LOCAL
    freopen("case.txt","r",stdin);
    #endif
    while(scanf("%d%d", &n, &m)!=EOF) {
        drep(i,1,n+1) g[i].clear();
        int u, v;
        drep(i, 0, m) {
            scanf("%d%d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        scanf("%d%d%d", &s, &f, &r);
        bfs(r);
//        drep(i, 1, n+1) cout << dis[i] << ' '; cout << endl;
        cout << dij(s, f) << endl;
    }
}

View Code

L: http://acm.timus.ru/problem.aspx?space=1&num=2035 水，忽略

SCAU 2015 GDCPC team_training0

推荐阅读