0821上午有感而發(fā)
T1 Circle
給出N個(gè)圓，保證任意兩個(gè)圓都是相離的，然后給出兩個(gè)點(diǎn)(x1,y1)(x2,y2)保證均不在某個(gè)圓上，要從點(diǎn)(x1,y1)到(x2,y2)畫條曲線，問這條曲線最少要跨越多少次圓的邊界？對(duì)于100%的數(shù)據(jù)：1<=N<=50,坐標(biāo)范圍[-1000,1000],每個(gè)圓的半徑1<=R<=1000。
保證沒有兩個(gè)圓有公共點(diǎn)，起點(diǎn)和終點(diǎn)不會(huì)落到某個(gè)圓的邊界上。
考場(chǎng)上想到了直接數(shù)兩個(gè)點(diǎn)一共被幾個(gè)圓包起來就是答案了。
判斷一個(gè)點(diǎn)在不在圓內(nèi)，只用看這個(gè)點(diǎn)到圓心的距離是否小于R就可以了，判斷的時(shí)候得開double，不然見祖宗。。。
直接枚舉圓+判斷=\(AC\)
還要考慮到重復(fù)的情況，但是我沒有想到。。。題目太美麗了，喜提\(90pts\)
復(fù)雜度\(O(n)\)
$90pts$ $code$
#define rgi register int
#define ll long long
#define ull unsigned long long
#define N 55
using namespace std;
struct cir{
int x,y,r;
}e[N];
inline int contains(int x,int y,cir z){
long double del=sqrt((x-z.x)*(x-z.x)+(y-z.y)*(y-z.y));
return del<z.r;
}
int n,x,y,x2,y2,ans=0;
int main(){
freopen("circle.in","r",stdin);
freopen("circle.out","w",stdout);
cin.tie(0)->ios::sync_with_stdio(false);
cin>>n;
for(rgi i=1;i<=n;i++) cin>>e[i].x;
for(rgi i=1;i<=n;i++) cin>>e[i].y;
for(rgi i=1;i<=n;i++) cin>>e[i].r;
cin>>x>>y>>x2>>y2;
for(rgi i=1;i<=n;i++){
ans+=contains(x,y,e[i])+contains(x2,y2,e[i]);
}
printf("%d",ans);
return 0;
}
T2 Ski
【題目描述】
建造滑雪場(chǎng)的升降軌道。起點(diǎn)和終點(diǎn)的高度已知，x坐標(biāo)分割成若干份，間隔為1，每一點(diǎn)都給出支架的高度。要選擇盡可能少的支架頂端建立固定點(diǎn)，兩個(gè)固定點(diǎn)之間用一條直鋼軌連接，要求中間支架的高度都不能超過鋼軌在那里的高度。而且兩個(gè)相鄰固定點(diǎn)之間的距離（x坐標(biāo)的差值）不能超過給定的K。
【輸入格式】
第一行是N和K，2≤N≤5000；1≤K≤N-1；
接下來N行，按順序給定支架的高度h，0≤h≤1000000000；
【輸出格式】
一個(gè)整數(shù)，表示最少要選擇幾個(gè)固定點(diǎn)。第一個(gè)（起點(diǎn)）和最后一個(gè)（終點(diǎn)）一定是固定點(diǎn)。
簡(jiǎn)單來說就是在點(diǎn)上架橋，橋的數(shù)量要最少。
考慮鋼軌的斜率，如果兩根柱子之間的柱子都小于鋼軌的當(dāng)點(diǎn)高度就進(jìn)行轉(zhuǎn)移。設(shè)計(jì)狀態(tài)就也很簡(jiǎn)單。。
\(dp[i]\)表示到第i個(gè)點(diǎn)的最小固定點(diǎn)數(shù)，枚舉區(qū)間\([j,i]\)，如果滿足條件，轉(zhuǎn)移\(dp[i]=min(dp[j]+1)\)
我也是比較無奈，考場(chǎng)上算的復(fù)雜度感覺起來過不了這題，想了一下優(yōu)化大概30min，之后就放棄了，這種解法都沒打。。悲提\(0pts\)
復(fù)雜度不會(huì)算（真的太蒻了。。。
T3 Patric
有N個(gè)人，每個(gè)人有一個(gè)身高，他們排成一條直線，求有多少對(duì)人能夠互相看到對(duì)方。看到對(duì)方的條件為：兩個(gè)人相鄰或兩個(gè)人之間不存在任何人比他們高。
大水，單調(diào)棧板子題。
看完發(fā)現(xiàn)就是單調(diào)棧，因?yàn)楫?dāng)前比當(dāng)前點(diǎn)高度小的都沒用，維護(hù)單調(diào)遞減的序列就可以了。
ans加的時(shí)候教練用了二分優(yōu)化。。，感覺作用不大。
當(dāng)其他人在美美地寫暴力時(shí)，我不知為何和高度相同的杠上了，。，。白費(fèi)（蒻爆了。。
T4 Cdrom
題面太長(zhǎng)，簡(jiǎn)單來說就是一群\(OIer\)拷文件，u可以拷給v，求\(CCF\)最少要發(fā)幾個(gè)u盤
寫的時(shí)候想到了是有向邊，但是腦筋急轉(zhuǎn)彎覺得沒大影響，數(shù)連通塊去了。。。用的并查集。其實(shí)思路一樣，就是數(shù)有幾塊。
班里一位神犇用了Tarjan？？感覺不是很必要。
教練還說考慮環(huán)，有Floyd又刪邊的。。
直接BFS不就好了嗎，加一個(gè)vis就可以處理環(huán)了。
神犇code
using namespace std;
const int maxn = 205;
const int maxm = 40005;
inline int read(){
int ret=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f*=-1;ch=getchar();}
while(isdigit(ch)) ret=(ret<<3)+(ret<<1)+(ch&15),ch=getchar();
return ret*f;
}
int a[maxn][maxn];
int r[maxn][maxn];
bool visited[maxn];
stack<int> st;
bool has_edge[maxn][maxn];
int n,cnt,in_degree[maxn],comp[maxn];
void dfs1(int u) {
visited[u] = true;
for (int i=1;i<=a[u][0];i++) {
int v=a[u][i];
if (!visited[v]) {
dfs1(v);
}
}
st.push(u);
}
void dfs2(int u) {
visited[u] = true;
comp[u] = cnt;
for (int i=1;i<=r[u][0];++i) {
int v=r[u][i];
if (!visited[v]) {
dfs2(v);
}
}
}
int main() {
freopen("cdrom.in","r",stdin);
freopen("cdrom.out","w",stdout);
n=read();
memset(a,0,sizeof(a));
memset(r,0,sizeof(r));
for (int i=1;i<=n;++i) {
int j;
while(cin>>j&&j!=0) {
a[i][++a[i][0]] = j;
r[j][++r[j][0]] = i;
}
}
memset(visited, 0, sizeof(visited));
for (int i=1;i<=n;++i) {
if (!visited[i]) {
dfs1(i);
}
}
memset(visited, 0, sizeof(visited));
cnt = 0;
while (!st.empty()) {
int u=st.top();
st.pop();
if (!visited[u]) {
cnt++;
dfs2(u);
}
}
memset(in_degree,0,sizeof(in_degree));
memset(has_edge,0,sizeof(has_edge));
for (int u =1;u<=n;++u) {
for (int i=1;i<=a[u][0];++i) {
int v=a[u][i];
int q=comp[u];
int b=comp[v];
if (q!=b&&!has_edge[q][b]) {
has_edge[q][b] = true;
in_degree[b]++;
}
}
}
int ans=0;
for (int i=1;i<=cnt;++i) {
if (in_degree[i] == 0) {
ans++;
}
}
cout << ans << endl;
return 0;
}
浙公網(wǎng)安備 33010602011771號(hào)