建站
咨詢
售后
建站咨詢
新聞中心
最近小藝醬漸漸變成了一個(gè)圓滑的形狀 - 球??！ 小藝醬開始變得喜歡上球！小藝醬得到 n n n 個(gè)同心圓。
小藝醬對(duì)著
n
n
n 個(gè)同心圓進(jìn)行染色。 相鄰的圓范圍內(nèi)不能有相同的顏色。相隔一層的圓顏色相同。 小藝醬想知道圓最外層的那種顏色全部染了多
少？
發(fā)現(xiàn)只有兩種顏色，設(shè)最外層的那種顏色為 a a a ，另一種為 b b b 。
整個(gè)過程相當(dāng)于先把大的圓染成 a a a 顏色，再把次大的染成 b b b 顏色（會(huì)覆蓋原來的顏色），再把第三大的染成 a a a 顏色……
由于是同心圓，可以直接算，圓的面積是
S
=
π
r
2
S=\pi r^2
S=πr2 ，從大往小染色更新答案，同色加上，異色減去即可（x&1相當(dāng)于
x
x
x 除以
2
2
2 的余數(shù)）。
另，C++ 中的
π
\pi
π 可以使用acos(-1)。
#includeusing namespace std;
#define f(i,j,k) for(register int i=j;i<=k;++i)
#define g(i,j,k) for(register int i=j;i>=k;--i)
int n,m,s,l;
int a[10101010];
double ans;
signed main(){cin>>n;
f(i,1,n)cin>>a[i];
sort(a+1,a+n+1);
g(i,n,1){if((n-i)&1)ans-=a[i]*a[i];
else ans+=a[i]*a[i];
}
printf("%.3lf",ans*acos(-1));
return 0;
} 存在 n n n 個(gè)節(jié)點(diǎn)，目標(biāo)節(jié)點(diǎn)在 m m m。 每個(gè)節(jié)點(diǎn)有自己的權(quán)值 a a a。 在權(quán)值 k k k 內(nèi)（含 k k k 值）選擇一個(gè)權(quán)值非 0 0 0 節(jié)點(diǎn)且與目標(biāo)節(jié)點(diǎn)距離最近。
節(jié)點(diǎn) i i i 與節(jié)點(diǎn) j j j 的距離為 a b s ( i ? j ) abs(i-j) abs(i?j)。
思路枚舉選擇的節(jié)點(diǎn)，先判斷是否符合要求，再更新答案，C++ 有自帶的絕對(duì)值函數(shù)即題面中的abs()。
注意要輸出的是最近的距離。
代碼#includeusing namespace std;
#define f(i,j,k) for(register int i=j;i<=k;++i)
#define g(i,j,k) for(register int i=j;i>=k;--i)
int n,m,s,l;
int a[20202020];
signed main(){cin>>n>>m>>s;l=-1e9;
f(i,1,n)scanf("%lld",&a[i]);
f(i,1,n)if(a[i]&&a[i]<=s){if(abs(l-m)>abs(i-m))l=i;
}
cout< 已知存在
n
n
n 個(gè)寶物，每個(gè)寶物都有自己的質(zhì)量
m
m
m 和價(jià)值
v
v
v，在考慮選擇寶物時(shí)只能選擇總質(zhì)量小于等于
M
M
M 的方案，請(qǐng)問在最
優(yōu)方案下選擇寶物，能獲取到大價(jià)值
V
V
V 是多少？
經(jīng)典 DP 題，設(shè) d p i , j dp_{i,j} dpi,j? 為選擇前 i i i 個(gè)寶物，總質(zhì)量恰好為 j j j ，能得到的大價(jià)值。
由定義得到轉(zhuǎn)移式 d p i , j = max ? { d p i ? 1 , j , d p i ? 1 , j ? m i + v i } dp_{i,j}=\max\{dp_{i-1,j},dp_{i-1,j-m_i}+v_i\} dpi,j?=max{dpi?1,j?,dpi?1,j?mi??+vi?} ，注意特判邊界。
另外，只要保證狀態(tài) d p i , a dp_{i,a} dpi,a?不會(huì)向 d p i , b dp_{i,b} dpi,b?轉(zhuǎn)移就可以去掉第一維 i i i，一種方法是反著循環(huán)，詳情見代碼。
代碼#includeusing namespace std;
#define f(i,j,k) for(register int i=j;i<=k;++i)
#define g(i,j,k) for(register int i=j;i>=k;--i)
int n,m,s,l;
int dp[2020202];
signed main(){cin>>n>>m;
f(i,1,n){cin>>s>>l;
g(i,m,s)dp[i]=max(dp[i],dp[i-s]+l);
}
s=0;
f(i,0,m)if(s 有 N N N 個(gè)客人與足夠多張的圓桌。主人安排每位客人坐在（任意）一張圓桌邊，但是每位客人希望自己左右邊上分別有一些空座位，不然會(huì)覺得害羞。
注意，如果一個(gè)客人所在的圓桌只有他一個(gè)人，那么他左邊的空座位數(shù)量就是他右邊的空座位數(shù)量。
試問主人需要準(zhǔn)備多少個(gè)座位，才能讓每個(gè)客人舒適的坐下。
思路若已知第 i i i 個(gè)人左邊坐著第 p i p_i pi? 個(gè)人，那么答案就是 ∑ i = 1 n max ? { l i , r p i } \sum_{i=1}^{n}\max\{l_i,r_{p_i}\} ∑i=1n?max{li?,rpi??} 。
不可能有兩個(gè)人左邊坐著同一個(gè)人，所以 p p p 互不相同。
我們可以考慮一個(gè)貪心：
從 l l l 和 r r r 數(shù)組中找到一個(gè)大的值 x x x，它一定會(huì)出現(xiàn)在求和中某次累加時(shí)（一定有 max ? { l i , r p i } = x \max\{l_i,r_{p_i}\} = x max{li?,rpi??}=x）。
如果 x x x 是從 l l l 中取到的，那么我們還需要從 r r r 中取一個(gè)作為它左邊的人，顯然取的這個(gè)越大越好，我們把這兩個(gè)數(shù)刪掉后繼續(xù) 1. 找數(shù)。
如果 x x x 是從 r r r 中取到的， 那么我們還需要從 l l l 中取一個(gè)作為它右邊的人，顯然取的這個(gè)越大越好，我們把這兩個(gè)數(shù)刪掉后繼續(xù) 1. 找數(shù)。
觀察發(fā)現(xiàn)每次取的兩個(gè)數(shù)就是兩個(gè)數(shù)組排序后的 l i l_i li? 和 r i ri ri。
考場(chǎng)上沒過寫了個(gè)模擬退火，最后發(fā)現(xiàn)答案值域?yàn)?
1
0
13
10^{13}
1013 要開long long。
#includeusing namespace std;
#define int long long
#define f(i,j,k) for(register int i=j;i<=k;++i)
#define g(i,j,k) for(register int i=j;i>=k;--i)
int n,m,s,l;
int a[101010];
int b[101010];
signed main(){cin>>n;
f(i,1,n)cin>>a[i]>>b[i];
sort(a+1,a+n+1);sort(b+1,b+n+1);
f(i,1,n)m+=1+max(a[i],b[i]);
cout< 把 IDE 做好一點(diǎn)，代碼自動(dòng)補(bǔ)全和縮進(jìn)及其反人類。
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
當(dāng)前名稱：CSDN第11次競(jìng)賽題解-創(chuàng)新互聯(lián)
轉(zhuǎn)載源于：http://www.dlmjj.cn/article/ccpdsd.html
