A.LightOJ 1080 Binary Simulation
操作I i j：翻转i到j之间的01比特（0变成1，1变成0）
操作Q i：询问第i位比特是什么 //线段树#include#include #include #include #define N 100005char s[N];int tr[N << 2], lz[N << 2];void pushDown(int rt){ if(lz[rt]){ lz[rt] = 0; lz[rt << 1] = lz[rt << 1 | 1] =1; tr[rt << 1] ^= tr[rt]; tr[rt << 1 | 1] ^= tr[rt]; tr[rt] = 0; }}void update(int rt, int L, int R, int l, int r){ if(L <= l && r <= R){ tr[rt] ^= 1; lz[rt] = 1; return; } pushDown(rt); int mid = (l+r) >> 1; if(L <= mid) update(rt << 1, L, R, l, mid); if(R > mid) update(rt << 1 | 1, L, R, mid+1, r);}int query(int rt, int x, int l, int r){ if(l == r){ return tr[rt]; } pushDown(rt); int mid = (l+r) >> 1; if(x <= mid) return query(rt << 1, x, l, mid); if(x > mid) return query(rt << 1 | 1, x, mid+1, r);}int main() { int t; scanf("%d", &t); for(int cas = 1, q; cas <= t; ++cas){ memset(tr, 0, sizeof tr); memset(lz, 0, sizeof lz); printf("Case %d:\n", cas); scanf(" %s %d", s, &q); while(q--){ char o; int l,r; scanf(" %c %d ", &o, &l); if(o == 'I'){ scanf("%d", &r); update(1, l, r, 1, N-1); }else{ printf("%d\n", (s[l-1] - '0') ^ query(1, l, 1, N-1)); } } } return 0;}
B. LightOJ 1047 Neighbor House
相邻的两个颜色不能相同，给出每一个屋子涂R、G、B的代价，求全部涂色的最小代价。
//DP，dp[i][0]表示前一个屋子涂i色的最小代价。dp[i][1]表示当前屋子涂i色的最小代价。#includeint dp[4][2];int main(){ int t; scanf("%d",&t); for(int cas = 1; cas <= t; ++cas){ memset(dp, 0, sizeof dp); int n; scanf("%d", &n); printf("Case %d: ", cas); for(int i = 1; i <= n; ++i){ int R, G, B; scanf("%d %d %d", &R, &G, &B); dp[0][1]=std::min(dp[1][0], dp[2][0])+R; dp[1][1]=std::min(dp[0][0], dp[2][0])+G; dp[2][1]=std::min(dp[0][0], dp[1][0])+B; dp[0][0]=dp[0][1]; dp[1][0]=dp[1][1]; dp[2][0]=dp[2][1]; } printf("%d\n", std::min(dp[0][0],std::min(dp[1][0], dp[2][0]))); } return 0;}
C. LightOJ 1072 Calm Down
给半径R的圆，求与它内切且相邻的两两外切的相同大小的圆的半径r。
//简单数学 #include#include int main(){ int t; scanf("%d", &t); for(int cas = 1; cas <= t; ++cas){ double R;int n; scanf("%lf%d", &R, &n); double a = sin(M_PI/n); printf("Case %d: %f\n", cas, R*a/(a+1)); } return 0;}
D. LightOJ 1082 Array Queries
求i到j的最小值
//线段树#include#include const int N = 100005;int n, q;int tr[N<<2];int query(int l, int r, int L, int R, int rt){ if(l <= L && R <= r){ return tr[rt]; } int mid = L+R >> 1; int ans = 0x3f3f3f3f; if(l <= mid)ans = std::min(ans, query(l, r, L, mid, rt << 1)); if(r > mid)ans = std::min(ans, query(l, r, mid+1, R, rt << 1 | 1)); return ans;}void build(int l, int r, int rt){ if(l==r){ scanf("%d", &tr[rt]); return; } int mid = l+r >> 1; build(l, mid, rt << 1); build(mid+1, r, rt << 1 | 1); tr[rt]=std::min(tr[rt << 1], tr[rt << 1 | 1]);}int main(){ int t; scanf("%d", &t); for(int cas = 1; cas <= t; ++cas){ printf("Case %d:\n", cas); scanf("%d %d", &n, &q); build(1, n, 1); for(int i = 1; i <= q; ++i){ int l, r; scanf("%d %d", &l, &r); printf("%d\n", query(l, r, 1, n, 1)); } } return 0;}
E. LightOJ 1088 Points in Segments
给出一些x轴上的点，再询问m条线段，求每个线段上包含多少个点。
//二分#include#include const int N = 100005;int a[N];int main(){ int t; scanf("%d", &t); for(int cas = 1; cas <= t; ++cas){ printf("Case %d:\n", cas); int n, q; scanf("%d %d", &n, &q); for(int i = 0; i < n; ++i){ scanf("%d", &a[i]); } for(int i = 1; i <= q; ++i){ int st, ed; scanf("%d %d", &st, &ed); printf("%d\n", std::lower_bound(a, a+n, ed+1) - std::upper_bound(a, a+n, st-1)); } } return 0;}
F. LightOJ 1094 Farthest Nodes in a Tree
求树上的最远距离。
//两次DFS，任一点DFS到最远点，然后该点到从它开始DFS的最远点的距离就是最远距离。#include#include #include #include #define N 30005int t,n;struct edge{ int next,v,w;}e[N<<1];int head[N],cnt;int dis[N],maxd,s;void add(int u,int v,int w){ e[++cnt]=(edge){head[u],v,w}; head[u]=cnt;}void dfs(int x,int fa){ if(dis[x]>maxd){ maxd=dis[x]; s=x; } for(int i=head[x];i;i=e[i].next){ if(e[i].v==fa)continue; dis[e[i].v]=dis[x]+e[i].w; dfs(e[i].v, x); }}int main() { scanf("%d",&t); for(int cas = 1;cas <= t; ++cas){ memset(head,0,sizeof head); cnt=0; printf("Case %d: ",cas); scanf("%d",&n); for(int i=1;i