随笔档案

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 300300;
int c[maxn];
int lowbit(int x) {
 return x&(-x);
}
int sum(int x) {
 int s = 0;
 for(int i=x;i>0;i-=lowbit(i))
  s += c[i];
 return s;
}
int main() {
 int m;
 while(~scanf("%d",&m)) {
  memset(c,0,sizeof(c));
  while(m--) {
   int op;
   scanf("%d",&op);
   if(op == 0) {
    int x;
    scanf("%d",&x);
    for(int i=x;i<maxn;i+=lowbit(i)) c[i] ++;
   }
   else if(op==1) {
    int x;
    scanf("%d",&x);
    int s = sum(x) - sum(x-1);
    if(s) for(int i=x;i<maxn;i+=lowbit(i)) c[i] --;
    else printf("No Elment!\n");
   }
   else {
    int x , k;
    scanf("%d%d",&x,&k);
    k += sum(x);
    int l = 1 , r = maxn - 1;
    while(l < r) {
     int mid = (l + r) >> 1;
     if(sum(mid) < k) l = mid + 1;
     else r = mid;
    }
    if(sum(l) < k) printf("Not Find!\n");
    else printf("%d\n",l);
   }
  }
 }
 return 0;
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,x,y;
int a[55] , b[55] , dp[55][222];
bool check(int mid) {
 memset(dp,-1,sizeof(dp));
 dp[0][0] = 0;
 for(int i=1;i<=n;i++) {
  if(dp[i][x]>=y) return true;
  for(int j=0;j<=x;j++) {
   if(dp[i-1][j] != -1) {
    int tmp = min(mid/a[i] , x - j);
    for(int k=0;k<=tmp;k++) {
     int t = (mid-a[i]*k) / b[i];
     if(dp[i][j+k] < dp[i-1][j] + t)
      dp[i][j+k] = dp[i-1][j] + t;
    }
   }
  }
 }
 if(dp[n][x] >= y) return true;
 return false;
}
int main() {
 int T,cas = 1;
 scanf("%d",&T);
 while(T--) {
  scanf("%d%d%d",&n,&x,&y);
  for(int i=1;i<=n;i++) {
   scanf("%d%d",&a[i],&b[i]);
  }
  int left = 0 ,right = a[1] *x + b[1] * y;
  int ans = -1;
  while(left <= right) {
   int mid = (left + right) >> 1;
   if(check(mid)) {
    ans = mid;
    right = mid - 1;
   }
   else left = mid + 1;
  }
  printf("Case %d: %d\n",cas++,ans);
 }
 return 0;
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define inf (1<<29)
const int maxn = 10010;
vector <pair<int,int> > G[maxn];
int node1[maxn],node2[maxn];
int dis1[maxn],dis2[maxn],dis3[maxn];
int p[maxn];
int n;
void init() {
    for(int i=1;i<=n;i++) {
        G[i].clear();
        node1[i] = node2[i] = -1;
        dis1[i] = dis2[i] = dis3[i] = 0; 
        p[i] = -1;
    }   
}
int dfs1(int u) {
    if(dis1[u]) return dis1[u];
    int sz = G[u].size();
    for(int i=0;i<sz;i++) {
        int v = G[u][i].first , w = G[u][i].second;
        if(v == p[u]) continue;
        p[v] = u;
        if(dfs1(v) + w > dis1[u]) dis1[u] = dis1[node1[u] = v] + w;
    }
    for(int i=0;i<sz;i++) {
        int v = G[u][i].first , w = G[u][i].second;
        if(v == p[u] || v == node1[u]) continue;
        if(dis1[v] + w > dis2[u]) dis2[u] = dis1[v] + w;
    }
    return dis1[u];
}
void dfs2(int u) {
    int sz = G[u].size();
    for(int i=0;i<sz;i++) {
        int v = G[u][i].first , w = G[u][i].second; 
        if(v == p[u]) continue;    
        dis3[v] = dis3[u] + w;
        if(v == node1[u])
            dis3[v] = max(dis3[v],dis2[u]+w);
        else
            dis3[v] = max(dis3[v],dis1[u]+w);
        dfs2(v);
    }
}
int main() {
    while(~scanf("%d",&n)) {
        init();
        int a , b;
        for(int i=2;i<=n;i++) {
            scanf("%d%d",&a,&b);
            G[i].push_back(make_pair(a,b));
            G[a].push_back(make_pair(i,b));
        }   
        dfs1(1);
        dfs2(1);
        for(int i=1;i<=n;i++) {
            printf("%d\n",max(dis1[i],dis3[i]));   
        }
    }
    return 0;   
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 202;
int n,m;
int val[maxn];
vector<int> G[maxn];
int dp[maxn][maxn];
bool vis[maxn];
void dfs(int u) {
    vis[u] = 1;
    int sz = G[u].size();
    for(int i=0;i<sz;i++) {
        int v = G[u][i];
        if(vis[v]) continue;
        dfs(v);
        for(int j=m;j>=0;j--)
            for(int k=1;k<=j;k++) {
                dp[u][j] = max(dp[u][j],dp[u][j-k]+dp[v][k]);   
            }   
    }   
    for(int i=m+1;i>=1;i--)
        dp[u][i] = dp[u][i-1] + val[u];
    dp[u][0] = 0;
}
int main() {
    while(~scanf("%d%d",&n,&m) && n + m) {
        for(int i=0;i<=n;i++) {
            G[i].clear();
            vis[i]=0;
            for(int j=0;j<=m+1;j++)
                dp[i][j] = 0;   
        }   
        val[0] = 0;
        int a,b;
        for(int i=1;i<=n;i++) {
            scanf("%d%d",&a,&b);
            G[a].push_back(i);
            val[i] = b;
        }
        dfs(0);
        int ans = dp[0][m+1];
        printf("%d\n",ans);
    }  
    return 0;
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 6060;
vector<int> G[maxn];
//int val[maxn];
int n;
int dp[maxn][2];
bool vis[maxn];
void dfs(int u) {
    vis[u] = 1;
    int sz = G[u].size();
    for(int i=0;i<sz;i++) {
        int v=G[u][i];
        if(vis[v]) continue;
        dfs(v);
        dp[u][1] += dp[v][0];
        dp[u][0] += max(dp[v][1],dp[v][0]);   
    }   
}
int d[maxn];
int main() {
    while(~scanf("%d",&n)) {
        if(n == 0) break;
        for(int i=1;i<=n;i++) {
            scanf("%d",&dp[i][1]);
            dp[i][0] = 0;   
            G[i].clear();
            vis[i] = d[i] = 0;
        }  
        int u,v;
        for(;scanf("%d%d",&u,&v);) {
            if(u + v == 0) break;
            G[v].push_back(u); 
            d[u] = 1; 
        }
        int ans = 0;
        for(int i=1;i<=n;i++) {
            if(!d[i]) {
                dfs(i);
                ans += max(dp[i][0],dp[i][1]);
            }   
        }
        printf("%d\n",ans);
    }
    return 0;   
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 1555;
vector<int> G[maxn];
int n;
int dp[maxn][2];
bool vis[maxn];
void dfs(int u) {
    vis[u] = 1;
    int sz = G[u].size();
    for(int i=0;i<sz;i++) {
        int v = G[u][i];
        if(vis[v]) continue;
        dfs(v);
        dp[u][0] += dp[v][1];
        dp[u][1] += min(dp[v][1],dp[v][0]);   
    }   
}
int main() {
    while(~scanf("%d",&n)) {
        for(int i=0;i<n;i++) G[i].clear();
        int u,num,v;
        for(int i=0;i<n;i++) dp[i][0]=0,dp[i][1]=1,vis[i]=0;
        for(int i=0;i<n;i++) {
            scanf("%d:(%d)",&u,&num);
            while(num--) {
                scanf("%d",&v);
                G[u].push_back(v);
                G[v].push_back(u);   
            }   
        }   
        dfs(0);
        int ans = min(dp[0][0],dp[0][1]);
        printf("%d\n",ans);
    }
    return 0;   
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 1555 , maxm = 3333;
int linky[maxn],visy[maxn];
vector<int> G[maxn];
int n;
bool find(int u) {
    int sz = G[u].size();
    for(int i=0;i<sz;i++) {
        int v = G[u][i];
        if(visy[v]) continue;
        visy[v] = 1;
        if(linky[v] == -1 || find( linky[v] )) {
            linky[v] = u;
            return 1;   
        }   
    }
    return 0;   
}
int ans;
void solve() {
    ans = 0;
    memset(linky,-1,sizeof(int)*n);
    for(int i=0;i<n;i++) {
        memset(visy,0,sizeof(visy));
        if(find(i)) ans ++;
    }   
}
int main() {
    while(~scanf("%d",&n)) {
        for(int i=0;i<n;i++) G[i].clear();
        int u,num,v;
        for(int i=0;i<n;i++) {
            scanf("%d:(%d)",&u,&num);
            while(num--) {
                scanf("%d",&v);
                G[u].push_back(v);
                G[v].push_back(u);   
            }   
        }   
        solve();
        printf("%d\n",ans/2);
    }
    return 0;   
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 111;
int n,m;
vector<int> G[maxn];
int dp[maxn][maxn];
bool vis[maxn];
int c[maxn],w[maxn];//c means the number of bugs,w beans brains
void dfs(int u) {
    vis[u] = 1;
    int t=(c[u]+19) / 20;
    int sz = G[u].size();
    for(int i=0;i<sz;i++) {
        int v=G[u][i];
        if(vis[v]) continue;
        dfs(v);
        for(int j=m-t;j>=1;j--)
            for(int k=1;k<=j;k++)
                dp[u][j] = max(dp[u][j],dp[u][j-k]+dp[v][k]);   
    }
    for(int i=m;i>=t;i--)
        dp[u][i] = dp[u][i-t] + w[u];
    for(int i=t-1;i>=0;i--)
        dp[u][i] = 0;
}
int main() {
    while(~scanf("%d%d",&n,&m)) {
        if(n < 0) break;
        for(int i=1;i<=n;i++) G[i].clear(),vis[i]=0;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++) scanf("%d%d",&c[i],&w[i]);
        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);   
        }   
        if(m == 0) {
            puts("0");
            continue;   
        }
        dfs(1);
        printf("%d\n",dp[1][m]);
    }
    return 0;   
}
     摘要: 因为本人不会在codeforces上面把代码换行神马的，所以在这里加个链接，一般是错误的代码，目前还没有发表什么文章，所以大家请跳过这篇文章。【ｐｕｚｚｌｅｓ】题型：网络流错误类型：Runtime Error(ACCESS_VIOLATION) Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.C...  阅读全文