这次比赛有显示了自己的不足，之所以是又，是因为基本上每次都暴露了自己很水，囧。
剩下的时间努力刷题，加油
CodeForces 287B Pipeline （二分加贪心）
view code#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;ll n, m;ll solve(){ if(n==1) return 0; ll sum = (1+m)*m/2-(m-2)-1; if(sum<n) return -1; ll l = 2, r = m, ans=0; while(l<=r) { int mid =(l+r)>>1; if((m-mid+1)*(mid+m)/2-(m-mid)>=n) ans = m-mid+1, l = mid+1; else r = mid-1; } return ans;}int main(){ while(cin>>n>>m) cout<<solve()<<endl; return 0;}
HDU 4366 Successor （
单点更新最值，区间查询最值，经典的地方在于将树转化为一个线性序列）
view code#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <queue>#include <map>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1typedef long long ll;const int N = 5e4+10;int _, n, m, pre[N], L[N], R[N], ans[N], Max[N<<2];map<int , int> ma;struct edge{ int v, next; edge() {} edge(int v, int next):v(v),next(next) {}}e[N];int ecnt, tot;struct people{ int id, loy, abi; bool operator < (const people &o) const{ return abi>o.abi; }}man[N];void addedge(int u, int v){ e[ecnt] = edge(v, pre[u]); pre[u] = ecnt++;}void dfs(int u)//将树转化为一个线性序列{ L[u] = tot++; for(int i=pre[u]; ~i; i=e[i].next) dfs(e[i].v); R[u] = tot;}void update(int p, int c, int l, int r, int rt){ if(l==r) {Max[rt] = c; return; } int m = (l+r)>>1; if(p<=m) update(p, c, lson); else update(p, c, rson); Max[rt] = max(Max[rt<<1], Max[rt<<1|1]);}int query(int L, int R, int l, int r, int rt){ if(L<=l && R>=r) return Max[rt]; int ans = -1, m = (l+r)>>1; if(L<=m) ans = max(ans, query(L,R,lson)); if(R>m) ans = max(ans, query(L,R,rson)); return ans;}void init(){ memset(L, 0, sizeof(L)); memset(R, 0, sizeof(R)); memset(pre, -1, sizeof(pre)); memset(Max, -1, sizeof(Max)); memset(ans, -1, sizeof(ans)); tot = ecnt = 0; ma.clear(); ma[-1] = -1;}void solve(){ init(); scanf("%d%d", &n, &m); int fa, loy; for(int i=1; i<n; i++) { scanf("%d%d%d", &fa, &man[i].loy, &man[i].abi); man[i].id = i; addedge(fa, i); ma[man[i].loy] = i; } dfs(0); sort(man+1, man+n); int j, id; for(int i=1; i<n; i = j) { j = i; while(j<n && man[j].abi==man[i].abi) { id = man[j].id; if(L[id]+1<=R[id]-1) loy = query(L[id]+1, R[id]-1, 0, tot-1, 1); else loy = -1; ans[id] = ma[loy]; j++; } j = i; while(j<n && man[j].abi==man[i].abi) { id = man[j].id; update(L[id], man[j].loy, 0, tot-1, 1); j++; } } while(m--) { scanf("%d", &id); printf("%d\n", ans[id]); }}int main(){// freopen("in.txt", "r", stdin); scanf("%d", &_); while(_--) solve(); return 0;}
HDU 3047 Zjnu Stadium（带权值的并查集）**（比赛是这道题竟然做不出，囧，只怪自己太弱）
先来一个类似模拟的做法：比赛的时候没过，汗
view code#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <queue>#include <vector>#include <map>#include <string>#define REP(i,n) for(int i=0; i<(n); i++)#define FOR(i,s,t) for(int i=(s); i<=(t); i++)using namespace std;typedef long long ll;const int INF = 1<<30;const int N = 50010;//const int mod = 300;int id[N], vis[N], n, m;vector<int > vec[N];void add(int cnt, int w, int now, int disu, int disv){ int siz = vec[cnt].size(), v; for(int i=0; i<siz; i++) { v = vec[cnt][i]; id[v] += disu+w-disv; vis[v] = now; vec[now].push_back(v); } vec[cnt].clear();}int main(){// freopen("in.txt", "r", stdin); while(scanf("%d%d", &n, &m)>0) { int ans = 0, u, v, w; memset(vis, 0, sizeof(vis)); for(int i=0; i<=n; i++) vec[i].clear(); int cnt = 0; for(int i=1; i<=m; i++) { scanf("%d%d%d", &u, &v, &w); if(!vis[u] && !vis[v]) { id[u] = 0, id[v] = w; vis[u] = vis[v] = ++cnt; vec[cnt].push_back(u); vec[cnt].push_back(v); } else if(vis[u] == vis[v]) { if(id[v]-id[u]!=w) ans++; } else if(vis[u] && vis[v]) { add(vis[v], w, vis[u], id[u], id[v]); } else if(vis[u]) { id[v] = id[u]+w; vis[v] = vis[u]; vec[vis[u]].push_back(v); } else if(vis[v]) { id[u] = id[v]-w; vis[u] = vis[v]; vec[vis[v]].push_back(u); } } printf("%d\n", ans); }}
并查集
view code#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <algorithm>using namespace std;typedef long long ll;const int N = 5e4+10;int fa[N], dis[N], n, m;int find(int x){ if(x==fa[x]) return fa[x]; int t = fa[x]; fa[x] = find(fa[x]); dis[x] += dis[t]; return fa[x];}int main(){// freopen("in.txt", "r", stdin); while(scanf("%d%d", &n, &m)>0) { for(int i=1; i<=n; i++) fa[i] = i, dis[i] = 0; int u, v, w, fu, fv, ans = 0; for(int i=0; i<m; i++) { scanf("%d%d%d", &u, &v, &w); fu = find(u), fv = find(v); if(fu==fv) { if(dis[u]+w!=dis[v]) ans++; } else { fa[fv] = fu; dis[fv] = w-dis[v]+dis[u]; } } printf("%d\n", ans); } return 0;}
HDU 4886 TIANKENG’s restaurant(Ⅱ)（据说很暴力的做法都能过trie，平时很少接触字符串类的问题）(not yet）
8进制，队友代码
view code#include <iostream>#include <cstdio>#include <cstring>#include <cmath>using namespace std;const int maxn=1000005;int vis[maxn<<2];char str[maxn];int frc[10];int n;bool solve(int k){ memset(vis,0,sizeof vis); int tmp=0; for(int i=0;i<k;i++)tmp=tmp*8+str[i]-‘A‘; vis[tmp]=1; for(int i=k;i<n;i++){ tmp=tmp%frc[k-1]; tmp=tmp*8+str[i]-‘A‘; vis[tmp]=1; } int x=0; while(vis[x])x++; if(x<frc[k]){ for(int i=k;i>=1;i--){ printf("%c",x/frc[i-1]+‘A‘); x%=frc[i-1]; } printf("\n"); return 1; } return 0;}int main(){// freopen("in","r",stdin); frc[0]=1; for(int i=1;i<=8;i++)frc[i]=frc[i-1]*8; int t; scanf("%d",&t); while(t--){ scanf("%s",str); n=strlen(str); for(int i=1;!solve(i);i++); } return 0;}
UVA 12672 Eleven(如果一个数的奇数位之和减去偶数位之和能被11整除，该数就能被11整除)（not yet）
HDU 1853 Cyclic Tour（拆点，最大流）
view code#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;typedef long long ll;const int INF = 1<<30;const int N = 210;int n, m, p[N], d[N], pre[N];int s, t;bool inq[N];struct edge{ int u, v, cap, cost, next; edge() {} edge(int u, int v, int cap, int cost, int next):u(u), v(v),cap(cap),cost(cost),next(next) {}}e[N*N*4];int ecnt;void addedge(int u, int v, int w, int cost){ e[ecnt] = edge(u, v, w, cost, pre[u]); pre[u] = ecnt++; e[ecnt] = edge(v, u, 0, -cost, pre[v]); pre[v] = ecnt++;}bool BellmanFord(int &flow, int &cost){ for(int i=s; i<=t; i++) d[i] = INF; memset(inq, 0, sizeof(inq)); d[s] = 0; p[s] = 0; int minflow = INF; queue<int >q; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); inq[u] = 0; for(int i = pre[u]; ~i; i = e[i].next) { int v = e[i].v; if(e[i].cap>0 && d[v]>d[u]+e[i].cost) { d[v] = d[u]+e[i].cost; p[v] = i; minflow = min(minflow, e[i].cap); if(!inq[v]) q.push(v), inq[v] = 1; } } } if(d[t] == INF) return false; flow += minflow; cost += d[t]*minflow; int u = t; while(u != s) { e[p[u]].cap -= minflow; e[p[u]^1].cap += minflow; u = e[p[u]].u; } return true;}int Mincost(int &flow){ int cost=0; while(BellmanFord(flow, cost)); return cost;}int main(){// freopen("in.txt", "r", stdin); while(scanf("%d%d", &n, &m)>0) { memset(pre, -1, sizeof(pre)); ecnt = 0, s = 0, t = n<<1|1; int u, v, w; for(int i=1; i<=n; i++) addedge(s,i,1,0), addedge(i+n,t,1,0); for(int i=0; i<m; i++) { scanf("%d%d%d", &u, &v, &w); addedge(u, v+n, 1, w); } int flow=0; int cost=Mincost(flow);// printf("mainflow = %d\n", flow); if(flow!=n) puts("-1"); else printf("%d\n", cost); } return 0;}
