TIOJ 1213 5樹論 之 最遠距點對

找樹的直徑

#include<cstdio>
#include<cstdlib>
#include<vector>
#include<utility>
#include<cstring>
#include<algorithm>
#define N 100005
using namespace std;
typedef pair<int,int> pii;
vector<pii> link[N];
int H[N];
int n;
int dfs(int fat, int prc){
    vector<int> hv;
    int get_r = 0;
    for(int lx = 0;lx < link[prc].size();lx++){
        int ind = link[prc][lx].first;
        if(fat == ind) continue;
        get_r = max(get_r, dfs(prc, ind));
        hv.push_back(H[ind] + link[prc][lx].second);
    }
    sort(hv.begin(), hv.end());
    int hvc = hv.size();
    if(hvc == 0)
        H[prc] = 0;
    else
        H[prc] = hv[hvc-1];
    if(hvc == 1)
        get_r = max(get_r, hv[hvc-1]);
    else if(hvc >= 2)
        get_r = max(get_r, hv[hvc-1] + hv[hvc-2]);
    return get_r;
}
int main(){
    for(;;){
        scanf("%d", &n);
        if(n == 0)break;
        memset(H, 0, sizeof(H));
        for(int lx=  0;lx < n;lx++)
            link[lx].clear();
        for(int lx = 0;lx < n-1;lx++){
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c); a--, b--;
            link[a].push_back(pii(b, c));
            link[b].push_back(pii(a, c));
        }

        printf("%d\n", dfs(-1, 0));
    }
    return 0;
}

2010-2011 ACM-ICPC Northeastern European Regional Contest Binary Operation

給一個
{0~9}*{0~9} = {0~9} 的表

然後對於兩個正整數，這個二元運算是每位單獨操作
像 ab * cd  =  (a*b)(c*d)

要計算
a*(a+1)*.....(b)

基本上就要算

a*b*b*b.....(n次)

和

(0*0*...(n次)*1*1*....(n次).....)^k

用倍增法蓋表
然後逐位遞推就OK了

測資超兇QQ 總之最後過了.....

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
using namespace std;
typedef unsigned long long int int64;
int64 p10[20];
int mm[10][10];
int dmove[10][10][65];
int mmove[10][20][65];
void TLE(){while(1);}
int get_dmove(int a, int p, int64 n){
    int nn = a;
    for(int s = 0;n;s++, n/=2){
        if(n%2)
            nn = dmove[nn][p][s];
        if(s >= 64) TLE();
    }
    return nn;
}
int get_mmove(int a, int c, int64 n){
    int nn = a;
    for(int s = 0;n;s++, n/=2){
        if(n%2)
            nn = mmove[nn][c][s];
        if(s >= 64) TLE();
    }
    return nn;
}
int gain(int64 src, int p){
    return (src/p10[p])%10;
}
int main()
{
    freopen("binary.in", "r", stdin);
    freopen("binary.out", "w", stdout);
    p10[0] = 1; for(int lx = 1;lx <= 19;lx++) p10[lx] = p10[lx-1]*10LL;
    for(int lx = 0;lx < 10;lx++)
        for(int ly = 0;ly < 10;ly++)
            scanf("%d", &mm[lx][ly]);
    for(int lx = 0;lx < 10;lx++)
        for(int ly=  0;ly < 10;ly++)
            dmove[lx][ly][0] = mm[lx][ly];
    for(int ln = 1;ln <= 64;ln++)
        for(int lx = 0;lx < 10;lx++)
            for(int ly = 0;ly < 10;ly++)
                dmove[lx][ly][ln] = dmove[dmove[lx][ly][ln-1]][ly][ln-1];
    for(int lc = 0;lc <= 18;lc++){
        for(int ln = 0;ln <= 64;ln++){
            for(int la = 0;la<10;la++){
                if(ln == 0){
                    int st = la;
                    for(int lx  = 0;lx < 10;lx++)
                        st = get_dmove(st, lx, p10[lc]);
                    mmove[la][lc][0] = st;
                }else{
                    mmove[la][lc][ln] = mmove[mmove[la][lc][ln-1]][lc][ln-1];
                }
            }
        }
    }
    int64 a, b;
    scanf("%I64u %I64u", &a, &b);
    //if(b < 9*p10[17]+5*p10[16] and b > p10[17]) TLE();
    //if(a > b) TLE();
    int64 mao = 0;
    for(int prb = 0;prb <= 18 and p10[prb] <= b;prb++){
        int64 step = b-a;
        int st = gain(a, prb);
        //if(st >= 10) TLE();
        int64 delta1 = p10[prb]-a%p10[prb]-1LL;
        delta1 = min(step, delta1);
        st = get_dmove(st, st, delta1);
        step -= delta1;
        for(int lx = gain(a, prb)+1;lx <= 9;lx++){
            int64 tostep = min(step, p10[prb]);
            st = get_dmove(st, lx, tostep);
            step -= tostep;
        }
        if(step == 0){ mao += st*p10[prb]; continue;}
        int64 down = a/p10[prb]/10LL + 1LL;
        int64 up = b/p10[prb]/10LL;
        if(up < down ) TLE();
        st = get_mmove(st, prb, up-down);
        step -= p10[prb]*(up-down)*10;
        if(step < 0) TLE();
        for(int lx = 0;lx < gain(b, prb);lx++){
            step -= p10[prb];
            st = get_dmove(st, lx, p10[prb]);
            if(step < 0) TLE();
        }
        step -= b%p10[prb]+1;
        st = get_dmove(st, gain(b, prb), b%p10[prb]+1LL);
        if(step) TLE();
        mao += st*p10[prb];
    }
    printf("%I64u\n", mao);
    return 0;
}

UVA 10779 Collectors Problem

題目簡述：
你和一群人都有一些貼紙，然後你想要越多不同種貼紙，所以你設法和這些人做交易
每次交易都是一張貼紙換一張貼紙，交易是成立的若且唯若且(1)你給他的貼紙是他沒有的(2)他給你的貼紙是多出來的

給定初始狀態，問最後最多可以有多少種貼紙？

總之就是設好幾個限制

(1) 固定人，對於每種貼紙都有上限為1的進入限制。
設好一些邊：
(2) 代表貼紙交換的邊
(3) 每種貼紙最多只會流出1張
(4) 每個人願意交出的貼紙是原本的少一個

若這樣設定，每一條流就會是一次貼紙的交換

testdata:

100
2 2
3 1 1 1
2 2 2

2 2
3 1 1 1
2 2 1

3 3
3 1 1 1
2 2 2
2 2 3

2 3
3 1 2 2
2 3 3




#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#define INF 100000
using namespace std;
typedef long long int int64;
int indc; int getind(){return indc++;} int getcnt(){return indc;}
struct edge{int a, b, c;}es[500000]; int ecnt;
vector<int> to[100000]; int nn;
void init(int n){
nn = n;
for(int lx = 0;lx < n;lx++)
to[lx].clear();
ecnt = 0;
return;
}
void addedge(int a, int b, int ab, int ba=0){
if((ab == 0) and (ba == 0)) return;
es[ecnt].a = a, es[ecnt].b = b, es[ecnt].c = ab; to[a].push_back(ecnt++);
es[ecnt].a = b, es[ecnt].b = a, es[ecnt].c = ba; to[b].push_back(ecnt++);
return;
}
int dis[100000];
int path[100000];
int post[100000];
int que[100000];
int bfs(int s, int t){
for(int lx = 0;lx < nn;lx++)
dis[lx] = -1, post[lx] = -1;
int qs = 0, qe = 1; que[0] = s, dis[s] = 0;
while(qs < qe){
int gg = que[qs++];
for(int lx = 0;lx < to[gg].size();lx++){
int lind = to[gg][lx];
if(es[lind].c <= 0) continue;
int pind = es[lind].b;
if(dis[pind] != -1) continue;
dis[pind] = dis[gg] + 1;
post[pind] = lind;
que[qe++] = pind;
}
}
if(dis[t] == -1) return 0;
int pgg = t;
int mm = 10000;
int pathcnt = 0;
while(pgg != s){
int lid = post[pgg];
mm = min(mm, es[lid].c);
path[pathcnt++] = lid;
pgg = es[lid].a;
}
for(int lx = 0;lx < pathcnt;lx++){
es[path[lx]].c -= mm;
es[path[lx]^1].c += mm;
}
return mm;
}
int EKarp(int s, int t){
int cc = 0;
for(;;){
int dc = bfs(s, t);
if(dc == 0) break;
cc += dc;
}
return cc;
}
void pes(){
for(int lx = 0;lx < ecnt;lx++)
if(es[lx].c)
printf("%d -> %d w = %d\n", es[lx].a, es[lx].b, es[lx].c);
return;
}
int main()
{
int T;scanf("%d", &T);
for(int lt = 0;lt < T;lt++){
int n, m;scanf("%d %d", &n, &m);
int own[40][100];

memset(own, 0, sizeof(own));
for(int lx = 0;lx < n;lx++){
int acnt = 0;scanf("%d", &acnt);
for(int la = 0;la < acnt;la++){
int inp;scanf("%d", &inp);
own[lx][inp-1]++;
}
}
int pstin[20][30], pstout[20][30], pvin[20][30], pvout[20][30];
int lim[100];
indc = 0;int st = getind(), ed = getind();
for(int lx = 0;lx < m;lx++){
lim[lx] = getind();
//printf("lim%d = %d\n", lx, lim[lx]);
}
for(int lx = 0;lx < n;lx++){
for(int lm = 0;lm < m;lm++){
pstin[lx][lm] = getind();
pstout[lx][lm] = getind();
pvin[lx][lm] = getind();
pvout[lx][lm] = getind();
// printf("%d->%d X %d->%d\n", pvin[lx][lm], pvout[lx][lm], pstin[lx][lm], pstout[lx][lm]);
}
//printf("--\n");
}
init(getcnt());
//printf("pcnt = %d\n", getcnt());
for(int lx = 0;lx < m;lx++){
addedge(st, pstout[0][lx], own[0][lx]);
addedge(lim[lx], ed, 1);
}
for(int lx = 1;lx < n;lx++){
for(int lm = 0;lm < m;lm++){
addedge(pvin[lx][lm], pvout[lx][lm], 1-(own[lx][lm]>0));
if(own[lx][lm] > 1)
addedge(pstin[lx][lm], pstout[lx][lm], own[lx][lm]-1);
}
for(int lm1 = 0;lm1 < m;lm1++)
for(int lm2 = 0;lm2 < m;lm2++)
if(lm1 != lm2)
addedge(pvout[lx][lm1], pstin[lx][lm2], 1);
for(int ly = 1;ly < n;ly++){
if(lx == ly) continue;
for(int lm = 0;lm < m;lm++){
addedge(pstout[lx][lm], pvin[ly][lm], 1);
addedge(pstout[lx][lm], lim[lm], 1);
}
}
}
for(int lx = 1;lx < n;lx++)
for(int lm = 0;lm < m;lm++)
addedge(pstout[0][lm], pvin[lx][lm], 1);
for(int lx = 0;lx < n;lx++)
for(int lm = 0;lm < m;lm++)
addedge(pstout[lx][lm], lim[lm], 1);
//pes();
int ans = EKarp(st, ed);
if(ans > m) printf("%d\n", 1/0);
printf("Case #%d: %d\n", lt+1, ans);
}
return 0;
}

TIOJ 1017 . C.Node of Sequence

O(N)

#include<cstdio>
#include<cstdlib>
int arr[1000005];
bool ch1[1000005];
bool ch2[1000005];
int main(){
    int T;scanf("%d", &T);while(T--){
        int a;scanf("%d", &a);
        for(int lx = 0;lx < a;lx++) scanf("%d", arr+lx);
        int mm1 = arr[0], mm2 = arr[a-1];
        for(int lx = 1;lx < a;lx++){
            ch1[lx] = arr[lx] > mm1;
            if(arr[lx] > mm1) mm1 = arr[lx];
        }
        for(int lx = a-2;lx >= 0;lx--){
            ch2[lx] = arr[lx] < mm2;
            if(arr[lx] < mm2) mm2 = arr[lx];
        }
        int mao = 0;
        for(int lx = 1; lx < a-1;lx++)
            mao += ch1[lx] and ch2[lx];
        printf("%d\n", mao);
    }
    return 0;
}

UVA 563 Crimewave

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=504

題目大概這樣:
給一個n*m的盤面，和一些格子點
要判斷是否存在一個規劃方法，使得每個點都能走出盤面而不在corner碰撞，
path限定要沿著盤面格子邊邊走。


方法大概這樣: 把每個點當作S，把邊點當作E，每個點限定流量1，每條邊限定流量INF

然後看最大流是否是點的數量

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#define INF 100000
using namespace std;
typedef long long int int64;
typedef struct _edge{ int a, b, w;}edge;
edge es[100000]; int ecnt = 0; int s = 0, t = 0;
vector<int> link[100000];
int nn = 0;
void init(int n){
ecnt = 0;
for(int lx =0;lx < n;lx++)
link[lx].clear();
nn = n;
return;
}
void addedge(int a, int b, int ab, int ba = 0){
es[ecnt].a = a, es[ecnt].b = b, es[ecnt].w = ab; ecnt++; link[a].push_back(ecnt-1);
es[ecnt].a = b, es[ecnt].b = a, es[ecnt].w = ba; ecnt++; link[b].push_back(ecnt-1);
return;
}
void printes(){
for(int lx = 0;lx < ecnt;lx++){
printf("%d: %d -> %d w = %d\n", lx, es[lx].a, es[lx].b, es[lx].w);
}
printf("--\n");
}
int dis[10000];
int q[10000];
int path[10000];
int post[10000];
int bfs(int s, int t){
//printf("bfs %d->%d\n", s, t);
for(int lx = 0;lx < nn;lx++)
dis[lx] = -1, post[lx] = -1;
int qs = 0, qe = 1;
q[0] = s;
while(qs < qe){
int gg =  q[qs]; qs++;
//printf("bfs at %d\n", gg);
int get_dis = dis[gg];
for(int lx = 0;lx < link[gg].size();lx++){
int ind = es[link[gg][lx]].b;
//printf("ind = %d\n", ind);
if(dis[ind] == -1 and es[link[gg][lx]].w)
q[qe++] = ind, dis[ind] = get_dis + 1, post[ind] = link[gg][lx];
}
//printf("--\n");
}
if(dis[t] == -1)
return 0;
int pathcnt = 0;
int nowg = t;
int min_f = INF;
//printf("A\n");
while(nowg != s){
int rvlinkind = post[nowg];
//printf("%d\n", rvlinkind);
if(rvlinkind == -1) break;
path[pathcnt++] = rvlinkind;
nowg = es[rvlinkind].a;
//printf("nowg = %d\n", nowg);
//for(int ppp = 0;ppp/10000 < 10000;ppp++);
min_f = min(min_f, es[rvlinkind].w);
}
for(int lx = 0;lx < pathcnt;lx++){
int linkind = path[lx];
//printf("link%d\n", linkind);
es[linkind].w -= min_f;
es[linkind^1].w += min_f;
}
return min_f;
}
int Ekarp(int s, int t){
int v = 0;
int mao = 0;
while(1){
v = bfs(s, t);
//printf("%d\n", v);
if(v == 0) break;
mao += v;
}
return mao;
}
int chmap[55][55];
int ss, aa;
int get_index(int x, int y){return y*ss + x;}
int main()
{
int T;scanf("%d", &T);
while(T-->0){
int n;scanf("%d %d %d", &ss, &aa, &n);
init(2*ss*aa + 2);
memset(chmap, 0, sizeof(chmap));
for(int lx = 0;lx < n;lx++){
int p, q;scanf("%d %d", &p, &q);
p--, q--; chmap[p][q] = 1;
}
int sss = 2*ss*aa, eee = 2*ss*aa+1;
for(int lx = 0;lx < ss;lx++)
for(int ly = 0;ly < aa;ly++)
if(chmap[lx][ly] == 0)
addedge(2*get_index(lx, ly), 2*get_index(lx, ly)+1, 1-chmap[lx][ly]);

for(int lx = 0;lx+1 < ss;lx++){
for(int ly = 0;ly < aa;ly++){
addedge(2*get_index(lx, ly)+1, 2*get_index(lx+1, ly), INF);
addedge(2*get_index(lx+1, ly)+1, 2*get_index(lx, ly), INF);
}
}
for(int lx = 0;lx < ss;lx++){
for(int ly = 0;ly+1 < aa;ly++){
addedge(2*get_index(lx, ly+1)+1, 2*get_index(lx, ly), INF);
addedge(2*get_index(lx, ly)+1, 2*get_index(lx, ly+1), INF);
}
}
for(int lx = 0;lx < ss;lx++){
for(int ly = 0;ly < aa;ly++){
if((lx == 0) or (ly == 0) or (lx == ss-1) or (ly == aa-1))
addedge(2*get_index(lx, ly)+1, eee, INF);
if(chmap[lx][ly])
addedge(sss, 2*get_index(lx, ly)+1, 1);
}
}
//printes();
puts(Ekarp(sss, eee) == n ? "possible" : "not possible");
}
return 0;
}

TIOJ 1794 Count On a Tribe

給一個陣列，問最大同色面積

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
using namespace std;
typedef long long int int64;
typedef pair<int, int> pii;
int arr[3010][3010];
bool vis[3010][3010];
pii q[9000010];
int main()
{
 int n, m;scanf("%d %d", &n, &m);
 for(int lx = 0;lx < n;lx++)
  for(int ly = 0;ly < m;ly++)
   scanf("%d", &arr[lx+1][ly+1]);
 memset(vis, false, sizeof(vis));
 for(int lx = 0;lx <= n+1;lx++)
  arr[lx][0] = -1, arr[lx][m+1] = -1;
 for(int ly = 0;ly <= m+1;ly++)
  arr[0][ly] = -1, arr[n+1][ly] = -1;
 int mao = 0;
 for(int lx = 1;lx <= n;lx++){
  for(int ly = 1;ly <= m;ly++){
   if(vis[lx][ly]) continue;
   int st = 0, ed = 1;
   int typ = arr[lx][ly];
   q[0] = pii(lx, ly);
   vis[lx][ly] = true;
   int cnt = 0;
   while(st < ed){
    int px = q[st].first, py = q[st].second; st++;
    cnt++;
    if(vis[px+1][py] == false and typ == arr[px+1][py])
     vis[px+1][py] = true, q[ed++] = pii(px+1, py);
    if(vis[px-1][py] == false and typ == arr[px-1][py])
     vis[px-1][py] = true, q[ed++] = pii(px-1, py);
    if(vis[px][py-1] == false and typ == arr[px][py-1])
     vis[px][py-1] = true, q[ed++] = pii(px, py-1);
    if(vis[px][py+1] == false and typ == arr[px][py+1])
     vis[px][py+1] = true, q[ed++] = pii(px, py+1);
   }
   mao = max(mao, cnt);
  }
 }
 printf("%d\n", mao);
 return 0;
}