随笔档案

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int main() {
    int a , b;
    int aa , aaa , bb , bbb;
    while(~scanf("%d%d",&a,&b)) {
        if(a == b) {
            puts("0");
            continue;   
        }
        if(a > b) swap(a , b);
        aa = (int)sqrt(1.0*a);
        if(aa * aa == a) aa --;
        aaa = a - aa * aa;
        bb = (int)sqrt(1.0*b);
        if(bb * bb == b) bb --;
        bbb = b - bb * bb;
        //printf("aa : %d , aaa : %d\n",aa,aaa);
        //printf("aaa : %d , bbb : %d\n",bb,bbb);
        int left1 , right1 , left2 , right2;
        int delta = 0;
        if(aa == bb) {
            printf("%d\n",bbb - aaa);
            continue;   
        }
        if(aaa % 2 == 0) {
            delta ++;
            left1 = aaa / 2;
            right1 = left1 + 1;
        }
        else left1 = right1 = (aaa + 1) / 2;
        if(bbb % 2 == 1) {
            delta ++;
            left2 = bbb / 2;
            right2 = left2 + 1;   
        }
        else left2 = right2 = bbb / 2;
        //printf("left1 is %d , right1 is %d\n",left1 , right1);
        //printf("left2 is %d , right2 is %d\n",left2 , right2);
        delta += (bb - aa - 1) * 2;
        right1 += bb - aa - 1;
        if(bbb >= left1 && bbb <= right1) ;
        else if(left2 >= left1 && left2 <= right1) ;
        else if(right2 >= left1 && right2 <= right1) ;
        else {
            delta += 2 * min(abs(left1 - right2) , abs(left2 - right1));   
        }
        delta += 1;
        printf("%d\n",delta);
    }
    return 0;   
}
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 50005;
int dp[maxn] , a[maxn];
int Lis(int n) {
    int len = 1 , left , right , mid;
    dp[1] = a[1];
    for(int i=2;i<=n;i++) {
        left = 1;
        right = len;
        while(left <= right) {
            mid = (left + right) / 2;
            if(a[i] > dp[mid])
                left = mid + 1;
            else right = mid - 1;
        }
        dp[left] = a[i];
        if(left > len) len = left;
    }
    return len;
}
int main() {
    int n , cas = 1;
    while(~scanf("%d",&n)) {
        int x , y;
        for(int i=0;i<n;i++) {
            scanf("%d%d",&x,&y);
            a[x] = y;
        }
        int ans = Lis(n);
        printf("Case %d:\n",cas++);
        if(ans == 1) printf("My king, at most 1 road can be built.\n\n");
        else printf("My king, at most %d roads can be built.\n\n",ans);
    }
    return 0;
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define inf (1<<29)
const int maxn = 222 , maxm = 1111;
int dp[maxn][maxm] , n , m;
int w[maxn];
bool vis[maxn];
int dist[maxn], sta[maxn];
struct Edge {
    int v,w,next;   
}edge[maxm];
int E,head[maxn];
void init() {
    E =  0;
    for(int i=1;i<=n;i++) head[i] = -1;   
}
void addedge(int u,int v,int w) {
    edge[E].v=v;edge[E].w=w;edge[E].next=head[u];head[u]=E++;
    edge[E].v=u;edge[E].w=w;edge[E].next=head[v];head[v]=E++;   
}
int p[maxn],pre[maxn];
void spfa() {
    for(int i=1;i<=n;i++) dist[i]=inf,vis[i]=0;
    int top = 0;
    dist[1] = 0;
    sta[++top] = 1;
    while(top) {
        int u = sta[top --];
        vis[u] = 0;
        for(int i=head[u];i!=-1;i=edge[i].next) {
            int v = edge[i].v;
            if(dist[v] > dist[u] + edge[i].w) {
                dist[v] = dist[u] + edge[i].w;
                p[v] = u; pre[v] = i;   
                if(!vis[v]) {
                    vis[v] = 1;
                    sta[++top] = v;   
                }
            }   
        }   
    }   
    for(int i=n;i!=1;i=p[i])
        edge[pre[i]].w = 0;
    return;
}
void dfs(int u) {
    vis[u] = 1;
    for(int k=head[u];k!=-1;k=edge[k].next) {
        int v = edge[k].v;
        if(vis[v]) continue;
        dfs(v);
        int tmp = edge[k].w * 2;
        for(int i=m;i>=tmp;i--)
            for(int j=i-tmp;j>=0;j--)  
                dp[u][i]=max(dp[u][i],dp[u][j]+dp[v][i-tmp-j]);
    }   
    for(int i=0;i<=m;i++) dp[u][i] += w[u];
}
int main() {
    while(~scanf("%d%d",&n,&m)) {
        init();
        memset(dp,0,sizeof(dp));
        int u,v,ww;
        for(int i=1;i<n;i++) {
            scanf("%d%d%d",&u,&v,&ww);
            addedge(u,v,ww);   
        }   
        for(int i=1;i<=n;i++)
            scanf("%d",&w[i]);
        spfa();
        if(dist[n] > m)
        puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!");
        else {
            for(int i=1;i<=n;i++) vis[i] = 0;
            m -= dist[n];
            dfs(1);
            printf("%d\n",dp[1][m]);
        }
    }
    return 0;   
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define inf 1000000100
const int maxn = 10100 , maxm = 300300;
int n , m;
struct Edge {
    int v,next;   
}edge[maxm];
int  E,head[maxn];
int least[maxn] , most[maxn];
void init() {
    for(int i=1;i<=n;i++) {
        head[i] = -1;
        least[i] = 1;
        most[i] = inf;   
    }   
}
void addedge(int u,int v) {
    edge[E].v=v;edge[E].next=head[u];head[u]=E++;   
}
void dfs(int u) {
    int leastt = 1;
    for(int i=head[u];i!=-1;i=edge[i].next) {
        int v = edge[i].v;
        dfs(v);
        leastt += least[v];
    }    
    if(least[u] < leastt) least[u] = leastt;
}
int main() {
    while(~scanf("%d",&n)) {
        init();
        for(int i=2;i<=n;i++) {
            int u;
            scanf("%d",&u);
            addedge(u,i);   
        }   
        scanf("%d",&m);
        int u , val;
        char ch[5];
        for(int i=0;i<m;i++) {
            scanf("%d%s%d",&u,ch,&val);
            if(ch[0] == '=') {
                if(least[u] <= val) least[u] = val;
                if(most[u] >= val) most[u] = val;   
            }
            if(ch[0] == '<') {
                if(most[u] >= val - 1) most[u] = val - 1;   
            }
            if(ch[0] == '>') {
                if(least[u] <= val + 1) least[u] = val + 1;   
            }
        }
        dfs(1);
        int ok = 1;
        for(int i=1;i<=n;i++) {
            if(least[i] > most[i]) {
                ok =  0;
                break;   
            }   
        }
        if(ok) puts("True");
        else puts("Lie");
    }
    return 0;   
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define inf (1<<29)
const int maxn = 150050;
int opt[505],n,K,root,w[maxn];
vector<int> g[maxn];
void dfs(int u,int *best) {
    int sz = g[u].size();
    int cur[505];
    for(int i=0;i<=K;i++) cur[i]=best[i];
    for(int i=0;i<sz;i++) {
        int v =  g[u][i];
        dfs(v,cur);   
    }   
    best[0] = 0;
    for(int i=K;i>0;i--) {
        best[i] = cur[i];
        if(best[i-1] >= 0)
            best[i] = max(best[i],best[i-1]+w[u]);   
    }
}
int main() {
    while(~scanf("%d%d",&n,&K)) {
        int p;
        for(int i=1;i<=n;i++) g[i].clear();
        for(int i=0;i<=K;i++) opt[i] = -inf;
        opt[0] = 0;
        for(int i=1;i<=n;i++) {
            scanf("%d%d",&p,&w[i]);
            if(p == 0) root = i;
            else g[p].push_back(i);   
        }   
        dfs(root,opt);
        if(opt[K] == -inf) puts("impossible");
        else printf("%d\n",opt[K]);
    }
    return 0;   
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define inf (1<<29)
const int maxn = 10010 , maxm = 30030;
int n , s , K;
int dp[maxn][15];
struct Edge {
    int v,w,next;   
}edge[maxm];
int E,head[maxn];
void init() {
    E=0;
    for(int i=1;i<=n;i++) head[i] = -1;   
    memset(dp,0,sizeof(dp));
}
void addedge(int u,int v,int w) {
    edge[E].v=v;edge[E].w=w;edge[E].next=head[u];head[u]=E++;
    edge[E].v=u;edge[E].w=w;edge[E].next=head[v];head[v]=E++;  
}
void dfs(int u,int pre) {
    for(int i=head[u];i!=-1;i=edge[i].next) {
        int v = edge[i].v , w = edge[i].w;
        if(v == pre) continue;
        dfs(v,u);
        for(int j=K;j>=0;j--) {
            dp[u][j] += dp[v][0] + 2 * edge[i].w;
            for(int k=1;k<=j;k++) {
                int tmp = dp[u][j-k] + dp[v][k] + k * edge[i].w;
                if(tmp < dp[u][j]) dp[u][j] = tmp;   
            }  
        }   
    }   
}
int main() {
    while(~scanf("%d%d%d",&n,&s,&K)) {
        init();
        int u,v,w;
        for(int i=1;i<n;i++) {
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);   
        }
        dfs(s,-1);   
        printf("%d\n",dp[s][K]);
    }
    return 0;   
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define inf (1<<29)
const int maxn = 10010 , maxm = 30030;
int n;
int dist1[maxn],dist2[maxn],dist3[maxn],p[maxn],node1[maxn],node2[maxn],d[maxn],pre[maxn];
struct Edge {
    int v,w,next;   
}edge[maxm];
int E,head[maxn];
void init() {
    E=0;
    p[1] = -1;
    for(int i=1;i<=n;i++) {
        dist1[i]=dist2[i]=dist3[i]=inf;
        d[i]=0;
        head[i]=-1;
        node1[i]=node2[i]=-1;
    }   
}
void addedge(int u,int v,int w) {
    edge[E].v=v;edge[E].w=w;edge[E].next=head[u];head[u]=E++;
    edge[E].v=u;edge[E].w=w;edge[E].next=head[v];head[v]=E++;   
}
int dfs1(int u) {
    if(d[u]==1 && u != 1) {
        node1[u] = u;
        dist1[u] = 0;
        return dist1[u];   
    }   
    for(int i=head[u];i!=-1;i=edge[i].next) {
        int v = edge[i].v , w = edge[i].w;
        if(v == p[u]) continue;
        p[v] = u;
        pre[v] = i;
        if(dfs1(v) + w < dist1[u]) {
            node1[u] = v;
            dist1[u] = dist1[v] + w;   
        }    
    }
    for(int i=head[u];i!=-1;i=edge[i].next) {
        int v = edge[i].v , w = edge[i].w;
        if(v == p[u] || v == node1[u]) continue;
        if(dist1[v] + w < dist2[u]) dist2[u] = dist1[v] + w;    
    }
    return dist1[u];
}
void dfs2(int u) {
    if(u == 1) {
        if(d[u] == 1) dist3[u] = 0;
        else dist3[u] = inf;
    }  
    else {
        if(u == node1[ p[u] ]) {
            dist3[u] = min(dist3[ p[u] ] , dist2[ p[u] ]) + edge[ pre[u] ].w;   
        }   
        else {
            dist3[u] = min(dist3[ p[u] ] , dist1[ p[u] ]) + edge[ pre[u] ].w;   
        }
    }
    for(int i=head[u];i!=-1;i=edge[i].next) {
        int v = edge[i].v;
        if(v == p[u]) continue;
        dfs2(v);   
    }
}
int main() {
    while(~scanf("%d",&n) && n) {
        init();
        for(int i=1;i<n;i++) {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);   
            d[u] ++; d[v] ++;
        }
        dfs1(1);
        dfs2(1);
        int ans = inf;
        for(int i=1;i<=n;i++) {
            if(dist1[i] + dist2[i] < ans) ans = dist1[i] + dist2[i];
            if(dist1[i] + dist3[i] < ans) ans = dist1[i] + dist3[i];   
        }   
        printf("%d\n",ans);
    }
    return 0;   
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define inf 1000100
const int maxn = 1010 , maxm = 3030;
struct Edge {
    int v,w,next;   
}edge[maxm];
int E,head[maxn];
int n , m;
int dp[maxn] , d[maxn] , p[maxn];
void init() {
    E = 0;
    for(int i=1;i<=n;i++)
        head[i] = p[i] = -1, d[i] = dp[i] = 0;
}
void addedge(int u,int v,int w) {
    edge[E].v=v;edge[E].w=w;edge[E].next=head[u];head[u]=E++;
    edge[E].v=u;edge[E].w=w;edge[E].next=head[v];head[v]=E++;
}
void dfs(int u,int mid) {
    for(int i=head[u];i!=-1;i=edge[i].next) {
        int v = edge[i].v;
        if(v == p[u]) continue;
        p[v] = u;
        dfs(v,mid);
        if(edge[i].w <= mid) dp[u] += min(dp[v] , edge[i].w);
        else dp[u] += dp[v];   
    }   
}
int main() {
    while(~scanf("%d%d",&n,&m) && n+m) {
        init();
        int u,v,w;
        for(int i=1;i<n;i++) {
           scanf("%d%d%d",&u,&v,&w);
           addedge(u,v,w);
           d[u]++; d[v]++;   
        }   
        int ans = -1;
        int left = 1 , right = m;
        while(left <= right) {
            dp[1] = 0;
            for(int i=2;i<=n;i++)
                if(d[i]==1) dp[i] = inf;
                else dp[i] = 0;
            int mid = (left + right) >> 1;
            dfs(1,mid);
            if(dp[1] <= m) {
                ans = mid;
                right = mid - 1;   
            }   
            else left = mid + 1;
        }
        printf("%d\n",ans);
    }   
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100000;
int p[maxn];
int b[505][505];
int n;
void init() {
    for(int i=0;i<(2*n+1)*32+100;i++) p[i] = i;   
}
int find(int x) {
    return x==p[x] ? x : p[x] = find(p[x]);   
}
void Union(int x,int y) {
    int a = find(x) , b = find(y);
    p[a] = p[b] = p[x] = p[y] = min(a , b);   
}
bool check() {
    for(int i=1;i<=n;i++) {
        for(int j=i+1;j<=n;j++)
            if(b[i][j] != b[j][i]) return 0;
        if(b[i][i] != 0) return 0;   
    }
    init();
    int m = 32 * n;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++) {
            if(i % 2 == 0 && j % 2 == 0) {
                for(int k=0;k<32;k++) {
                    if(b[i][j] & (1<<k) == 0) {
                        int u = i*32+k , v = j*32+k;
                        if(find(u) == find(1) || find(v) == find(1) || find(u) == find(v+m)) return 0;
                        Union(u,0);
                        Union(v,0);
                        Union(u+m,1);
                        Union(v+m,1);
                    }   
                }   
            }   
            else if(i % 2 == 1 && j % 2 == 1) {
                for(int k=0;k<32;k++) {
                    if(b[i][j] & (1<<k)) {
                        int u = i* 32 + k , v = j*32+k;
                        if(find(u) == find(0) || find(v)==find(0) || find(u) == find(v+m)) return 0;
                        Union(u,1);
                        Union(v,1);
                        Union(u+m,0);
                        Union(v+m,0);   
                    }   
                }   
            }
            else {
                for(int k=0;k<32;k++) {
                    int u = i * 32 + k , v = j * 32 + k;
                    if(b[i][j] & (1<<k)) {
                        if(find(u) == find(v)) return 0;
                        Union(u,v+m);
                        Union(u+m,v);   
                    }
                    else {
                        if(find(u) == find(v+m)) return 0;
                        Union(u,v);
                        Union(u+m,v+m);   
                    }
                }   
            }
        }
    return 1;
}
int main() {
    while(~scanf("%d",&n)) {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",&b[i][j]);
        if(check()) puts("YES");
        else puts("NO");   
    }
    return 0;   
}