UVA 12657 Boxes in a Line
模拟
FZU 1876 JinYueTuan 不说话
view code#include <iostream>using namespace std;int main(){ long long n,m,p,ans=1; while(cin>>n>>m>>p){ ans=1; for(int i=n;i<n+m;i++){ ans=ans*i%p; if(ans==0)break; } cout<<ans<<endl; } return 0;}
ZOJ 3684 Destroy
view code#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;const int N = 10010;int _, cas=1, n, m,pre[N], ans=0;int in[N],dp[N<<1];bool vis[N<<1];struct edge{ int u, v, w, p, next; edge() {} edge(int u, int v, int w, int p, int next):u(u),v(v),w(w),p(p),next(next) {}}e[N<<1];int ecnt;int dfs(int u, int h, int p){ int ans = 0; for(int i=pre[u]; ~i; i=e[i].next) { int v = e[i].v; if(v==p) continue; if(!vis[i]) dp[i] = dfs(v, e[i].w, u),vis[i] = 1; ans = max(dp[i], ans); } return h+ans;}void addedge(int u, int v, int w, int p){ e[ecnt] = edge(u, v, w, p, pre[u]); pre[u] = ecnt++; e[ecnt] = edge(v, u, w, p, pre[v]); pre[v] = ecnt++;}//bool dfs2(int u, int lim, int p)//{// if(in[u]==1) return 0;// for(int i=pre[u]; ~i; i=e[i].next)// {// int v = e[i].v;// if(v==p || e[i].p<=lim) continue;// if(!dfs2(v, lim, u)) return 0;// }// return 1;//}void dfs3(int u, int h, int p){ if(in[u]==1) { ans = max(ans, h); return ; } for(int i=pre[u]; ~i; i=e[i].next) { int v = e[i].v; if(v==p) continue; dfs3(v, min(h,e[i].p), u); }}void solve(){ memset(pre, -1, sizeof(pre)); memset(in, 0, sizeof(in)); ecnt = 0; int u, v, w, p, l = 0, r = 0; for(int i=1; i<n; i++) { scanf("%d%d%d%d", &u, &v, &w, &p); addedge(u, v, w, p); in[u]++; in[v]++;// r = max(p, r); } int s=0, Min=INF, tmp; memset(vis, 0, sizeof(vis)); for(int i=1; i<=n; i++) { tmp = dfs(i, 0, 0); if(tmp<Min) s = i, Min=tmp; } ans = 0; dfs3(s, INF, 0);// while(l<=r)// {// int mid = (l+r)>>1;// if(dfs2(s, mid, 0)) ans =mid, r=mid-1;// else l = mid+1;// } printf("%d\n", ans);}int main(){// freopen("in.txt", "r", stdin); while(scanf("%d", &n)>0) solve(); return 0;}
ZOJ 3676 Edward‘s Cola Plan （总是看英文看很久，囧）
view code#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;const int N = 100010;int _, cas=1, n, m;int suma[N], sumb[N], ans[10010];struct edge{ int a, b, c; edge() {} edge(int a, int b, int c):a(a),b(b),c(c) {} bool operator < (const edge &o) const{ return c>o.c; }}e[N];struct node{ int v, id; bool operator < (const node &o) const{ return v>o.v; }}p[10010];void solve(){ int a, b; for(int i=1; i<=n; i++){ scanf("%d%d",&a, &b); e[i] = edge(a,b, b-a); } sort(e+1, e+1+n); for(int i=1; i<=n; i++) { suma[i] = suma[i-1] + e[i].a; sumb[i] = sumb[i-1] + e[i].b; } for(int i=0; i<m; i++) { scanf("%d", &p[i].v); p[i].id = i; } sort(p, p+m); int j = 1, M; for(int i=0; i<m; i++) { M = p[i].v; while(j<=n && e[j].c>M) j++; ans[p[i].id] = sumb[j-1]-M*(j-1)+suma[n]-suma[j-1]; } for(int i=0; i<m; i++) { printf("%d\n", ans[i]); }}int main(){// freopen("in", "r", stdin); while(scanf("%d%d", &n,&m)>0) solve(); return 0;}
ZOJ 2899 Hangzhou Tour
ZOJ 3724 Icecream 线段树，离线，挺经典的
sum[n]表示距离的前缀和
情况1：
如果是询问从u到v的最短距离，(a到b是一条捷径，长度为len)
如果不走捷径dis1 = sumv – sumu;
如果走捷径 dis2 = sumv – sumu +len - (sumb-suma)。
走不走捷径就看len-(sumb-suma)是否小于0,(等于0,走不走无所谓)
对于多个捷径，且走捷径的情况，走len-(sumb-suma)最小的那个捷径
情况2：
如果是询问从u到v的最短距离，(a到b是一条捷径，长度为len)
假设不走捷径为绕一圈, 即dis1 = sumn – sumu+sumv;
走捷径dis2 = suma – sumu + sumv – sumb + len;
要不要走捷径就看 (suma-sumb +len)-sumn是否大于0,
当然这种情况肯定是要走捷径的的，这只是在有多个捷径的时候判断走那个捷径最短的一个方法。
走 (suma-sumb +len)-sumn最小的捷径。
至于那些最小值就是用线段树去维护。
view code#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;typedef long long ll;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1const ll INF = 1LL<<60;const int N = 100010;int n, m, T;ll Min[N<<2], sum[N], ans[N<<1];struct seg{ int l, r; ll w; seg() {} seg(int l, int r, ll w):l(l),r(r),w(w) {} bool operator < (const seg &o) const{ return r<o.r; }}e1[N<<1], e2[N<<2], ask1[N<<2], ask2[N<<2];int ecnt1, ecnt2, acnt1, acnt2;bool cmp(const seg a, const seg b){ return a.l<b.l;}void Up(int rt){ Min[rt] = min(Min[rt<<1], Min[rt<<1|1]);}void build(int l, int r, int rt){ Min[rt] = INF; if(l==r) return ; int m = (l+r)>>1; build(lson); build(rson);}void update(int p, ll c, int l, int r, int rt){ if(l==r) { Min[rt] = min(Min[rt], c); return ; } int m = (l+r)>>1; if(p<=m) update(p, c, lson); else update(p, c, rson); Up(rt);}ll query(int L, int R, int l, int r, int rt){ if(L<=l && R>=r) return Min[rt]; int m = (l+r)>>1; ll ans = INF; if(L<=m) ans = min(ans, query(L, R, lson)); if(R>m) ans = min(ans, query(L, R, rson)); return ans;}void solve(){ int a, b, c; for(int i=2; i<=n; i++) { scanf("%d", &a); sum[i] = sum[i-1] + a; } ecnt1 = ecnt2 = acnt1 = acnt2 = 0; while(m--) { scanf("%d%d%d", &a, &b, &c); if(a<b) { if(sum[a] - sum[b] + c>0) continue; e1[ecnt1++] = seg(a, b, c-(sum[b]-sum[a])); } else e2[ecnt2++] = seg(b, a, (sum[a]-sum[b]+c)-sum[n]); } scanf("%d", &T); for(int i=0; i<T; i++) { scanf("%d%d", &a, &b); if(a<b) ask1[acnt1++] = seg(a, b, i); else if(a>b)ask2[acnt2++] = seg(b, a, i); else ans[i] = 0; } sort(ask1, ask1+acnt1); sort(e1, e1+ecnt1); int i=0, j=0; build(1, n, 1); for(; i<acnt1; i++) { while(j<ecnt1 && e1[j].r<=ask1[i].r) { update(e1[j].l, e1[j].w, 1, n, 1); j++; } ll t = min((ll)0,query(ask1[i].l, ask1[i].r, 1, n, 1)); ans[ask1[i].w] = sum[ask1[i].r] - sum[ask1[i].l] + t; } sort(ask2, ask2+acnt2, cmp); sort(e2, e2+ecnt2, cmp); build(1, n, 1); for(i = 0, j = 0; i<acnt2; i++) { while(j<ecnt2 && e2[j].l<=ask2[i].l) { update(e2[j].r, e2[j].w, 1, n, 1); j++; } ans[ask2[i].w] = sum[n]+sum[ask2[i].l]-sum[ask2[i].r]+query( ask2[i].r, n, 1, n, 1);// printf("(%d, %d)first : %I64d\n",ask2[i].l,ask2[i].r,ans[ask2[i].w]); } for(int i=0; i<T; i++) { printf("%lld\n", ans[i]); }}int main(){// freopen("in.txt", "r", stdin); while(scanf("%d%d", &n, &m)>0) solve(); return 0;}
