这次比赛有显示了自己的不足,之所以是又,是因为基本上每次都暴露了自己很水,囧。
剩下的时间努力刷题,加油
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|1 typedef 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 ", 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 ", 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 ", 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(" "); 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 ", flow); if(flow!=n) puts("-1"); else printf("%d ", cost); } return 0; }