目錄
- A-眼花繚亂黑白配（CF 40A）
- B-尋找n邊形（CF 45I）
- C-小孩子才做選擇題（CF 1096C）
- D-其實并不難的博弈（CF 197A）
- E-簡單的周長計算（CF 224A）
- F-有些巧妙的DP（CF 1452D）
- G-動物（CF 35D）
- H-序列排隊（CF 1241D）
- I-立方體（CF 166E）
- J-~~下班快樂~~ 回家快樂 （CF 550C）
A-眼花繚亂黑白配（CF 40A）
鏈接： CF40A Find Color
題意： 判斷落點的顏色，
題解： 簽到題，咕，
代碼：
#include<bits/stdc++.h>
using namespace std;
int x,y,l,r;
int main()
{
cin>>x>>y;
l=x*x+y*y;
r=sqrt(l);
if(r*r==l)cout<<"black"<<endl;
else cout<<((r%2==0)^(x*y<0)?"black":"white")<<endl;
return 0;
}
B-尋找n邊形（CF 45I）
鏈接：45I TCMCF++
題意： 給出n個問題，總積分為解決問題積分的乘積，可自由選擇解決多少問題，最大化總積分，
題解： 對于問題的積分，正數全都取，0不取，負數取最多的偶數個，排序遍歷即可，
代碼： 簽到題，咕，
C-小孩子才做選擇題（CF 1096C）
鏈接：1096C Polygon for the Angle
題意： 給出一個整數的角度，要求找出一個正n邊形，使得其中三個頂點可以得去該角度，
題解： 對于一個正n邊形，其中所有可能的角度
a
n
g
=
180
°
?
k
n
（
1
≤
k
≤
n
?
2
）
ang=\frac{180°·k}{n}（1 \le k \le n-2）
ang=n180°?k?（1≤k≤n?2）,資料范圍較小，直接暴力列舉n即可，
證明： 將正多邊形放入外接圓，由等邊對等角可得證一點到其他點連線后所得角是相等的，即
n
?
2
n-2
n?2個三角形，
代碼： 解法較多，可以多觀摩借鑒不同方法，
D-其實并不難的博弈（CF 197A）
鏈接：CF 197A Plate Game
題意： 你有一張長a寬b的長方形桌子，桌子上有半徑為r的無限多的盤子，兩個玩家玩下面的游戲：他們輪流把盤子放在桌子上，使盤子之間不躺在一起（但可以互相接觸），并使任何盤子上的任何一點都位于桌子的邊界內，在游戲程序中，不能移動已經躺在桌子上的盤子，不能再移動的棋手即為輸家，決定哪位棋手獲勝，是先移動的棋手還是后移動的棋手，前提是兩位棋手都能發揮出最佳水平，
題解： 只要第一個人可以放下盤子則必勝，第一個人將盤子放在桌子中心，如果第二個人可以采取行動，第一個人采取對稱的行動即可，
代碼：
#include<bits/stdc++.h>
using namespace std;
int a,b,r;
int main()
{
cin>>a>>b>>r;
if(r*2>min(a,b))cout<<"Second"<<endl;
else cout<<"First"<<endl;
return 0;
}
E-簡單的周長計算（CF 224A）
鏈接：224A Parallelepiped
題意： 你有一個邊長為整數的矩形平行六面體，你知道它有一個公共頂點的三個面面積，你的任務是找出這個平行六面體所有12條邊的長度之和，
題解： 設六面體的共點三邊為 a , b , c , a,b,c, a,b,c,則六面體的三個面積為 s 1 = a ? b , s 2 = a ? c , s 3 = b ? c s_1=a*b,s_2=a*c,s_3=b*c s1?=a?b,s2?=a?c,s3?=b?c，即 a = s 1 ? s 2 s 3 , b = s 1 ? s 3 s 2 , c = s 2 ? s 3 s 1 a=\sqrt \frac{s_1·s_2}{s_3},b=\sqrt \frac{s_1·s_3}{s_2},c=\sqrt \frac{s_2·s_3}{s_1} a=s3?s1??s2?? ?,b=s2?s1??s3?? ?,c=s1?s2??s3?? ?
代碼：
#include<bits/stdc++.h>
using namespace std;
int a,b,c,ans;
int main()
{
cin>>a>>b>>c;
ans=4*(sqrt(a*b/c)+sqrt(a*c/b)+sqrt(b*c/a));
cout<<ans;
return 0;
}
F-有些巧妙的DP（CF 1452D）
鏈接：1452D Radio Towers
題意： 在一條坐標線上有n+2個城鎮，編號從0到n+1，第i個城鎮位于i點，
你在每一個城鎮1,2,…,n建立一個無線電塔，概率為 1 2 \frac{1}{2} 21?（這些事件是獨立的），之后，你要將每個塔上的信號功率設定為1到n的某個整數（信號功率不一定相同，但也不一定不同），位于城市i的信號塔的信號功率為p，到達每個城市c，這樣 ∣ c ? i ∣ < p |c-i|<p ∣c?i∣<p，
建好塔后，你要選擇信號功率的方式，使，
城鎮0和n+1不會從無線電塔上得到任何信號，
城鎮1,2,…,n各從一個無線電塔獲得信號，
例如，如果n=5，你在2、4、5三個鎮建了鐵塔，可以將2鎮的鐵塔信號功率設為2，4、5鎮的鐵塔信號功率設為1，這樣，0和n+1鎮得不到任何鐵塔的信號，1、2、3鎮得到2鎮鐵塔的信號，4鎮得到4鎮鐵塔的信號，5鎮得到5鎮鐵塔的信號，
計算建好鐵塔后，信號功率滿足所有約束條件的概率，
題解： 規律類似于斐波那契數列，
d
p
[
1
]
=
d
p
[
2
]
=
1
,
d
p
[
n
]
=
d
p
[
n
?
1
]
+
d
p
[
n
?
2
]
(
n
>
2
)
dp[1]=dp[2]=1,dp[n]=dp[n-1]+dp[n-2](n>2)
dp[1]=dp[2]=1,dp[n]=dp[n?1]+dp[n?2](n>2)
思路1：
可以想到，不管信號強度為多少，該信號塔能覆寫到的數量一定是奇數，
題目就轉變為
d
p
(
i
)
2
n
\frac{dp(i)}{2^n}
2ndp(i)? ，其中
d
p
(
i
)
dp(i)
dp(i) 表示
i
i
i能被拆成奇數的方案個數，（注意這里是順序可換的方案）
比如
d
p
(
3
)
=
2
dp(3)=2
dp(3)=2，因為
3
=
1
+
1
+
1
=
3
3 = 1 + 1 + 1 = 3
3=1+1+1=3
考慮狀態轉移方程就可以了：
d
p
(
i
)
=
d
p
(
i
?
1
)
+
d
p
(
i
?
3
)
+
?
+
d
p
(
(
x
?
(
2
k
+
1
)
)
>
0
)
dp(i)=dp(i-1)+dp(i-3)+\cdots+dp((x-(2k+1))>0)
dp(i)=dp(i?1)+dp(i?3)+?+dp((x?(2k+1))>0)
就用一個前綴和
p
r
e
[
x
]
=
d
p
(
x
)
+
d
p
(
x
?
2
)
+
?
pre[x]=dp(x)+dp(x-2)+\cdots
pre[x]=dp(x)+dp(x?2)+? 就可以了，【鳴謝@溢流眼淚】
代碼：
#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
#define ll long long
ll quickpow(ll a,ll b)//快速冪板子
{
if(b<0)return 0;
ll ret=1;
a%=mod;
while(b)
{
if(b & 1 ) ret = ( ret *a ) % mod;
b>>=1;
a = (a * a)% mod;
}
return ret;
}
ll inv(ll a)//逆元板子
{
return quickpow(a,mod-2);
}
ll n,p,ans;
ll dp[200500];
int main()
{
cin>>n;
dp[1]=dp[2]=1;
for(int i=3;i<=n;i++)dp[i]=(dp[i-1]+dp[i-2])%mod;
p=quickpow(2,n);
ans=dp[n]*inv(p)%mod;
cout<<ans<<endl;
return 0;
}
G-動物（CF 35D）
鏈接：35D Animals
題意： 有某種動物，可以在農場中待n天，如果它是第i天來的話，從第i天到第n天每天要吃的食物為a[i]，這些動物可以中途來，不可以中途走，問最多能容納多少只動物
題解： 貪心，預處理動物第i天來時總共需要消耗的食物，sort排序后從小的開始選，
代碼：
#include<bits/stdc++.h>
using namespace std;
int n;
int k;
int a[1000000];
int cnt=1;
int ans;
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i]=a[i]*(n-i+1);//n-i+1是剩余天數，處理后的a[i]
}//即為第i天來的動物所需要的糧食
sort(a+1,a+n+1);
while(k-a[cnt]>=0&&cnt<=n)//從小的開始選
{
ans++;
k-=a[cnt++];
}
cout<<ans<<endl;
return 0;
}
H-序列排隊（CF 1241D）
鏈接：1241D Sequence Sorting
題意： 對于一個序列，每次操作可以把所以相同的數字挪到隊首或者隊尾，問最少操作幾次可以保證這個序列是一個非降序列，
題解：
網路題解：我們只需要記錄一個元素的第一次出現的位置和最后一次出現的位置然后記錄有多少不同的元素，我們不找需要操作的元素，找不用操作的元素，用總的元素減去不用操作的就是答案，
個人題解：對于相同的數字，我們可以當成一個整體，將序列排序，記錄每個數字的左右出現的位置（當成線段），如果
A
<
B
,
A
r
>
B
l
,
A<B,A_r>B_l,
A<B,Ar?>Bl?,即線段相交，說明
A
、
B
A、B
A、B位置有逆序的部分，需要重排1次A或B，當時如果
A
<
B
,
A
r
<
B
l
,
A<B,A_r<B_l,
A<B,Ar?<Bl?,且
A
、
B
A、B
A、B相鄰，可以說明
A
、
B
A、B
A、B是有序的，即
A
、
B
A、B
A、B可視為一個整體，我們用總共的數字（不重復）數減去最大的一段有序部分數字數，即為答案（剩余的無序數字），
代碼：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct node
{
int v,id;
}a[300500];
bool cmp(node a,node b)
{
if(a.v==b.v)return a.id<b.id;
return a.v<b.v;
}
int l[300500],r[300500];
int T,n,cnt,key,t;
int main(){
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].v;
a[i].id=i;
}
sort(a+1,a+1+n,cmp);//將原陣列按值、位置排序
cnt=1;
for(int i=1;i<n;i++)
{
if(a[i].v!=a[i+1].v)r[cnt]=a[i].id,l[++cnt]=a[i+1].id;
}//記錄每個數最左、最右的位置；
key=1;t=1;
for(int i=1;i<cnt;i++)
{
if(r[i]>l[i+1])key=1;
else key++;
t=max(t,key);
}
cout<<cnt-t<<endl;
}
return 0;
}
I-立方體（CF 166E）
鏈接：166E Tetrahedron
題意： 一只螞蟻站在一個正四面體的頂點D上，求走過n（1≤n≤1e7）條棱后回到原頂點的方案總數對1e9+7取模，
思路： dp，可打表找規律，
f[i]表示走i步回到原點的方案數，g[i]表示走i步回到不原點的方案數，
f[i]=g[i?1]×3，g[i]=f[i?1]+g[i?1]×2
代碼：
#include<bits/stdc++.h>
using namespace std;
long long n;
long long f1={1};
long long f2;
int main(){
long long i,j,n;
cin>>n;
for(i=1;i<=n;i++){
long long x,y;
x=f1;y=f2;
f1=y*3%1000000007;
f2=(x+y*2)%1000000007;
}
cout<<f1<<endl;
return 0;
}
J-下班快樂 回家快樂 （CF 550C）
鏈接：550C Divisibility by Eight
題意： 給你一個長度最大為100的整數，問你能不能去掉這個整數里面的數字，使去掉后的整數能被8整除，
思路： 一個數要是能被8整除，只需滿足后三位能被8整除，暴力尋找長度和 k = 1 , 2 , 3 k=1,2,3 k=1,2,3位數字，k位數字和為8即滿足要求，
祝大家回家快樂，聽說明天難度又要開始回歸了~~~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/253558.html
標籤：其他