A.LightOJ 1080 Binary Simulation
操作I i j：翻转i到j之间的01比特（0变成1，1变成0）
操作Q i：询问第i位比特是什么
//线段树
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define N 100005
char 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:
", 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
", (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色的最小代价。
#include<bits/stdc++.h>
int 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
", std::min(dp[0][0],std::min(dp[1][0], dp[2][0])));
}
return 0;
}
C. LightOJ 1072 Calm Down
给半径R的圆，求与它内切且相邻的两两外切的相同大小的圆的半径r。
//简单数学
#include<cmath>
#include<cstdio>
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
", cas, R*a/(a+1));
}
return 0;
}
D. LightOJ 1082 Array Queries
求i到j的最小值
//线段树
#include<algorithm>
#include<cstdio>
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:
", 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
", query(l, r, 1, n, 1));
}
}
return 0;
}
E. LightOJ 1088 Points in Segments
给出一些x轴上的点，再询问m条线段，求每个线段上包含多少个点。
//二分
#include<algorithm>
#include<cstdio>
const int N = 100005;
int a[N];
int main(){
int t;
scanf("%d", &t);
for(int cas = 1; cas <= t; ++cas){
printf("Case %d:
", 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
", 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 <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define N 30005
int 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<n;++i){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
maxd=-1;
dis[0]=0;
dfs(0,-1);
int ans=maxd;
memset(dis,0,sizeof dis);
maxd=-1;
dfs(s,-1);
printf("%d
", maxd);
}
return 0;
}